CASIA OpenIR  > 毕业生  > 硕士学位论文
Thesis Advisor刘智勇
Degree Grantor中国科学院研究生院
Place of Conferral北京
Keyword渐非凸渐凹化算法 非凸优化 高斯平滑 连续统算法 组合优化 图匹配 二次分配问题 旅行商问题
Other Abstract

      这类问题通常具有非凸的目标函数,考虑到效率因素,寻求其近似解决方案。“自简至难”是学术界和工业届在处理非凸问题时经常采用的一种启发式思想。连续统方法是基于该思想的典型算法,又被称之为渐优化,可以避免陷入较差的局部最优。尽管连续统在实践中得到广泛应用,然而该类算法通常缺乏理论基础。最近有关工作证明,一定条件下,基于高斯平滑的连续统算法,可以实现Vese's PDE的最佳仿射近似,这为连续统算法的设计和使用提供了理论依据。

This work provides a graduated nonconvexity and concavity procedure based on Gaussian smoothing for combinatorial optimization problems defined on partial permutation matrices. 
Combinatorial optimization on partial permutation matrices plays a key role in many areas, such as computer vision, bioinformatics, social network analysis, etc.  It involves many important computer science problems, such as the subgraph matching problem, the quadratic assignment problem, and the traveling salesman problem. These problems are usually nonconvex, and therefore some approximations are necessary for efficiency reasons. 
In practice, when working with such a nonconvex function, a very natural heuristic is to employ a coarse-to-fine search for the global optimum. A popular method that exemplifies this idea is continuation method, which is also called graduated optimization. Empirically, people have observed that the local optimum found by continuation method has high chance to be global minimum. Despite its empirical success, there has been little theoretical understanding about this method. 
In recent years, related work shows that when this process is constructed by Gaussian smoothing, and it is optimal in a specific sense. It is proved that Gaussian smoothing emerges from the best affine approximation to Vese's nonlinear PDE. 

For combinatorial optimization on partial permutation matrices, except the difficulty caused by nonconvexity, the combinatorial constraint makes these problems more difficult. The direct projection from continuous solution to combinaotrial solution will bring significant additional error.The convex-concave relaxation procedure (CCRP) is another continuation method, which can deal with these two difficulties at the same time. The continuous solution can follow a path to finally arrive at a solution on partial permutation matrices.And the graduated nonconvexity concavity procedure (GNCCP) can realize CCRP in a more simple way without the convex and concave relaxation functions of the original function. While in this procedure, the constructed function is not closely to the original function. Our main motivation is that to design a better algorithm if we can combine GNCCP and Gaussian continuation method. Our main work is to improve GNCCP by Gaussian continuation method and design GNCCP based on Gaussian smoothing, specifically, constructing the sequence of subproblems by Gaussian smoothing. 
The proposed algorithm not only can get combinatorial solution in graduated projection but also can have better subproblem sequences, including better initial convex problem and ways to progressively deform it to the original task. Applications of  the improved GNCCP on different combinatorial optimization problems (e.g. subgraph matching) will be provided to testify the efficiency, robustness, and effectiveness of this algorithm compared with the original version. 

Document Type学位论文
Recommended Citation
GB/T 7714
王晶晶. 基于高斯平滑的渐非凸渐凹化算法及应用[D]. 北京. 中国科学院研究生院,2017.
Files in This Item:
File Name/Size DocType Version Access License
thesis.pdf(1823KB)学位论文 暂不开放CC BY-NC-SAApplication Full Text
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[王晶晶]'s Articles
Baidu academic
Similar articles in Baidu academic
[王晶晶]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[王晶晶]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.