赋权图匹配问题的一种新的松弛模型

图匹配是一个NP难(NP-hard)问题. 基于置换矩阵是非负正交矩阵这一经典结论, 提出赋权图匹配(Weighted graph matching, WGM)的双向松弛障碍规划, 理论上证明新模型的解与原模型的解是一致的. 该规划是一个二元连续规划, 它是正交矩阵上的线性优化问题, 同时也是非负矩阵上的凸二次优化问题. 故设计求解新模型的交替迭代算法, 并证明算法的局部收敛性. 数值实验表明, 在匹配精度方面, 新方法强于线性规划方法和特征值分解方法.

A New Relaxation Model for Weighted Graph Matching

Graph matching is an NP-hard problem. In this paper, we relax the admissible set of permutation matrices based on a well known result that permutation matrix is a non-negative orthogonal matrix. Meantime, a barrier function is incorporated into the objective function. In theory, the solution of the proposed model is the same as the original model, which distinguishes from the traditional relaxation matching models. The proposed model is a binary optimization problem which is a linear optimization problem on orthogonal variable and a quadratic convex optimization problem on non-negative variable. So, a new matching algorithm, named alternate iteration algorithm, is designed to solve it. It is proved that the proposed algorithm is locally convergent. The numerical experiments show that the proposed algorithm is more accurate than linear programming algorithm and eigen-decomposition algorithm.