CASIA OpenIR  > 毕业生  > 硕士学位论文
基于高斯平滑的渐非凸渐凹化算法及应用
王晶晶
学位类型工学硕士
导师刘智勇
2017-05
学位授予单位中国科学院研究生院
学位授予地点北京
关键词渐非凸渐凹化算法 非凸优化 高斯平滑 连续统算法 组合优化 图匹配 二次分配问题 旅行商问题
其他摘要
       针对定义在偏置换矩阵上的组合优化问题,本文提出了基于高斯平滑的渐非凸渐凹化算法,并将其应用于图匹配等组合优化问题。
 
       定义在偏置换矩阵上的组合优化问题是计算机科学领域的一个基础问题,该类问题在计算机视觉、生物信息学、社交网络分析等领域具有广泛应用,典型问题包括子图匹配、二次分配、旅行商问题等。

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

文献类型学位论文
条目标识符http://ir.ia.ac.cn/handle/173211/14828
专题毕业生_硕士学位论文
作者单位中科院自动化研究所
推荐引用方式
GB/T 7714
王晶晶. 基于高斯平滑的渐非凸渐凹化算法及应用[D]. 北京. 中国科学院研究生院,2017.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
thesis.pdf(1823KB)学位论文 暂不开放CC BY-NC-SA请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[王晶晶]的文章
百度学术
百度学术中相似的文章
[王晶晶]的文章
必应学术
必应学术中相似的文章
[王晶晶]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。