毕业生知识库

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.