论文部分内容阅读
针对定义在偏置换矩阵上的组合优化问题，本文提出了基于高斯平滑的渐非凸渐凹化算法，并将其应用于图匹配等组合优化问题。定义在偏置换矩阵上的组合优化问题是计算机科学领域的一个基础问题，该类问题在计算机视觉、生物信息学、社交网络分析等领域具有广泛应用，典型问题包括子图匹配、二次分配、旅行商问题等。 这类问题通常具有非凸的目标函数，考虑到效率因素，寻求其近似解决方案。“自简至难”是学术界和工业届在处理非凸问题时经常采用的一种启发式思想。连续统方法是基于该思想的典型算法，又被称之为渐优化，可以避免陷入较差的局部最优。尽管连续统在实践中得到广泛应用，然而该类算法通常缺乏理论基础。最近有关工作证明，一定条件下，基于高斯平滑的连续统算法，可以实现Veses PDE的最佳仿射近似，这为连续统算法的设计和使用提供了理论依据。 然而对于定义在偏置换矩阵上的组合优化问题，除了其目标函数通常非凸，难点还在于问题具有组合约束。得到连续解后直接映射回离散域可能会引入显著的附加误差。凸凹松弛过程是另一种连续统方法，该算法综合考虑了非凸性和组合约束这两个难点。连续解沿着一条路径从连续域逐步而被推至离散域而最终落在偏置换矩阵上。渐非凸渐凹化算法以简单的方式严格实现了凸凹过程，不需要显式地写出原函数的凸凹松弛。但是该过程中新构建的目标函数与原函数联系不够紧密，主要是由于加入的正则项与问题无关。 如果可以将基于高斯平滑的连续统算法与渐非凸渐凹化过程相结合，则可以综合两种方法在处理组合约束以及构造新目标函数上的优势，从而提高渐非凸渐凹化算法的普适性和有效性，这也是本文工作的基本出发点。 本文的主要工作是结合基于高斯平滑的连续统算法，改进已有的渐非凸渐凹化过程，并以此为框架，提出基于高斯平滑的渐非凸渐凹化算法，具体地，利用高斯平滑方式构造新目标函数，并实现新的渐非凸渐凹化过程。该算法既可以通过渐进映射的方式获得满足组合约束的解，又可以通过高斯平滑的方式，使得渐进过程中的每个新目标函数都能更好地描述原问题。本文中，将提出的算法应用于定义在偏置换矩阵上的组合优化问题，在图匹配问题上验证了算法的有效性、鲁棒性和高效性。