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

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

Solving minimum distance problems with convex or concave bodies using combinatorial global optimization algorithms.

Determining the minimum distance between convex objects is a problem that has been solved using many different approaches. On the other hand, computing the minimum distance between combinations of convex and concave objects is known to be a more complicated problem. Most methods propose to partition the concave object into convex subobjects and then solve the convex problem between all possible subobject combinations. This can add a large computational expense to the solution of the minimum distance problem. In this paper, an optimization-based approach is used to solve the concave problem without the need for partitioning concave objects into convex pieces. Since the optimization problem is no longer unimodal (i.e., has more than one local minimum point), global optimization techniques are used. Simulated Annealing (SA) and Genetic Algorithms (GAs) are used to solve the concave minimum distance problem. In order to reduce the computational expense, it is proposed to replace the objects' geometry by a set of points on the surface of each body. This reduces the problem to an unconstrained combinatorial optimization problem, where the combination of points (one on the surface of each body) that minimizes the distance will be the solution. Additionally, if the surface points are set as the nodes of a surface mesh, it is possible to accelerate the convergence of the global optimization algorithm by using a hill-climbing local optimization algorithm. Some examples using these novel approaches are presented.     

A dynamical systems approach to weighted graph matching

Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.     

Maximal matching polytope in trees

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.     

Graph Matching by Simplified Convex-Concave Relaxation Procedure

The convex and concave relaxation procedure (CCRP) was recently proposed and exhibited state-of-the-art performance on the graph matching problem. However, CCRP involves explicitly both convex and concave relaxations which typically are difficult to find, and thus greatly limit its practical applications. In this paper we propose a simplified CCRP scheme, which can be proved to realize exactly CCRP, but with a much simpler formulation without needing the concave relaxation in an explicit way, thus significantly simplifying the process of developing CCRP algorithms. The simplified CCRP can be generally applied to any optimizations over the partial permutation matrix, as long as the convex relaxation can be found. Based on two convex relaxations, we obtain two graph matching algorithms defined on adjacency matrix and affinity matrix, respectively. Extensive experimental results witness the simplicity as well as state-of-the-art performance of the two simplified CCRP graph matching algorithms.     

耳廓点云形状特征匹配的路径跟随算法

路径跟随算法结合凸松弛方法与凹松弛方法,通过跟随凸凹问题的解路径,近似地求解图匹配问题,具有较高的匹配精度.将路径跟随算法用于耳廓特征图的匹配问题:首先,基于PCA方法构造耳廓点云的显著性关键点集合;然后,采用乘积型参数域上的单值二次曲面方法拟合关键点邻域内的点集,并将曲面的局部形状特征定义为耳廓的局部形状相似测度;第三,对关键点集合进行Delaunay三角剖分,得到关键点集合在三维空间内的拓扑结构图,并定义关键点图的整体结构差异测度;最后,记耳廓关键点图的组合差异测度为关键点图的整体结构差异测度与关键点上的局部形状相似测度的线性组合,并基于路径跟随算法快速求解关键点图之间的精确匹配.相关实验结果表明:与其他相关算法相比,该算法具有较高的匹配效率和匹配精度.     

Optimization strategies for discrete multi-material stiffness optimization

Design of composite laminated lay-ups are formulated as discrete multi-material selection problems. The design problem can be modeled as a non-convex mixed-integer optimization problem. Such problems are in general only solvable to global optimality for small to moderate sized problems. To attack larger problem instances we formulate convex and non-convex continuous relaxations which can be solved using gradient based optimization algorithms. The convex relaxation yields a lower bound on the attainable performance. The optimal solution to the convex relaxation is used as a starting guess in a continuation approach where the convex relaxation is changed to a non-convex relaxation by introduction of a quadratic penalty constraint whereby intermediate-valued designs are prevented. The minimum compliance, mass constrained multiple load case problem is formulated and solved for a number of examples which numerically confirm the sought properties of the new scheme in terms of convergence to a discrete solution.     

On Total Unimodularity of Edge–Edge Adjacency Matrices

We consider total unimodularity for edge–edge adjacency matrices that represent adjacency relations between pairs of edges in a graph. These matrices appear in integer programming formulations of the minimum maximal matching problem, the edge dominating set problem, and so on. We investigate the problem of characterizing graphs that have totally unimodular edge–edge adjacency matrices, and give a necessary and sufficient condition for characterization. This condition is the first characterization for total unimodularity of edge–edge adjacency matrices.     

非平衡有向网络下带约束的连续时间分布式优化算法设计EI北大核心CSCD

本文基于权重不平衡有向网络,对一类分布式约束优化问题进行研究,其中全局目标函数等于具有李普希兹梯度的强凸目标函数之和,并且每个智能体的状态都有一个局部约束集.每个智能体仅知道自身的局部目标函数和非空约束集.本文的目标是用分布式方法求解该问题的最优解.针对优化问题,提出了一种新的分布式投影梯度连续时间协调算法,利用拉普拉斯矩阵的零特征值对应的左特征向量消除了图的不平衡性.在某些假设下,结合凸分析理论和李雅普诺夫稳定性理论,证明了算法能够获得问题的最优解.最后,通过仿真验证了算法的有效性.     

用于特征点配准的快速聚类凸集投影算法

提出一种用于特征点配准的快速聚类凸集投影算法. 该算法首先将模板点集和目标点集的配准问题通过聚类转化为相应类集合的配准问题，降低了算法的计算量；进而采用基于二次规划的凸集投影来求解类配准问题，避免了序贯凸集投影算法由于交替行列投影而引起的积累误差. 仿真表明，相对于现有的特征点配准算法，本文算法的配准精度和计算量均有所改善.     

图模型匹配:一种新的凹松弛函数及算法

将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向. 它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲, 相对于离散优化,连续优化问题的近似求解将更为容易. 但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵. 最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵, 并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数. 本文提出一种针对于有向无自环图匹配问题的凹松弛函数, 并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.     

Robust point matching for nonrigid shapes by preserving local neighborhood structures

In previous work on point matching, a set of points is often treated as an instance of a joint distribution to exploit global relationships in the point set. For nonrigid shapes, however, the local relationship among neighboring points is stronger and more stable than the global one. In this paper, we introduce the notion of a neighborhood structure for the general point matching problem. We formulate point matching as an optimization problem to preserve local neighborhood structures during matching. Our approach has a simple graph matching interpretation, where each point is a node in the graph, and two nodes are connected by an edge if they are neighbors. The optimal match between two graphs is the one that maximizes the number of matched edges. Existing techniques are leveraged to search for an optimal solution with the shape context distance used to initialize the graph matching, followed by relaxation labeling updates for refinement. Extensive experiments show the robustness of our approach under deformation, noise in point locations, outliers, occlusion, and rotation. It outperforms the shape context and TPS-RPM algorithms on most scenarios.     

A Parallel Proximal Splitting Method for Disparity Estimation from Multicomponent Images Under Illumination Variation

Proximal splitting algorithms play a central role in finding the numerical solution of convex optimization problems. This paper addresses the problem of stereo matching of multi-component images by jointly estimating the disparity and the illumination variation. The global formulation being non-convex, the problem is addressed by solving a sequence of convex relaxations. Each convex relaxation is non trivial and involves many constraints aiming at imposing some regularity on the solution. Experiments demonstrate that the method is efficient and provides better results compared with other approaches.     

凸松弛全局优化机器人手眼标定

针对机器人运动学正解及相机的外参数标定存在偏差时,基于非线性最优化的手眼标定算法无法确保目标函数收敛到全局极小值的问题,提出基于四元数理论的凸松弛全局最优化手眼标定算法。考虑到机械手末端相对运动旋转轴之间的夹角对标定方程求解精度的影响,首先利用随机抽样一致性（RANSAC）算法对标定数据中旋转轴之间的夹角进行预筛选,再利用四元数参数化旋转矩阵,建立多项式几何误差目标函数和约束,采用基于线性矩阵不等式（LMI）凸松弛全局优化算法求解全局最优手眼变换矩阵。实测结果表明,该算法可以求得全局最优解,手眼变换矩阵几何误差平均值不大于1.4 mm,标准差小于0.16 mm,结果稍优于四元数非线性最优化算法。     

A linear programming approach for the weighted graph matchingproblem

A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L₁ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n ⁶L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods     

时变不确定系统鲁棒控制器设计的新方法

基于包含两个二次项的分段Lyapunov函数,研究了线性时变不确定系统的鲁棒控制器设计问题.所考虑的系统由两个矩阵的凸组合构成,通过引入一个附加矩阵,推导出鲁棒控制器存在的充分条件.该控制器的状态反馈增益的求解问题可以转化为一组带有两个比例参数的线性矩阵不等式的凸优化问题.最后的数值示例说明了该设计方法的可行性.     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

Semidefinite spectral clustering

Multi-way partitioning of an undirected weighted graph where pairwise similarities are assigned as edge weights, provides an important tool for data clustering, but is an NP-hard problem. Spectral relaxation is a popular way of relaxation, leading to spectral clustering where the clustering is performed by the eigen-decomposition of the (normalized) graph Laplacian. On the other hand, semidefinite relaxation, is an alternative way of relaxing a combinatorial optimization, leading to a convex optimization. In this paper we employ a semidefinite programming (SDP) approach to the graph equipartitioning for clustering, where sufficient conditions for strong duality hold. The method is referred to as semidefinite spectral clustering, where the clustering is based on the eigen-decomposition of the optimal feasible matrix computed by SDP. Numerical experiments with several data sets, demonstrate the useful behavior of our semidefinite spectral clustering, compared to existing spectral clustering methods.     

SDU: A Semidefinite Programming-Based Underestimation Method for Stochastic Global Optimization in Protein Docking

This paper introduces a new stochastic global optimization method targeting protein-protein docking problems, an important class of problems in computational structural biology. The method is based on finding general convex quadratic underestimators to the binding energy function that is funnel-like. Finding the optimum underestimator requires solving a semidefinite programming problem, hence the name semidefinite programming-based underestimation (SDU). The underestimator is used to bias sampling in the search region. It is established that under appropriate conditions SDU locates the global energy minimum with probability approaching one as the sample size grows. A detailed comparison of SDU with a related method of convex global underestimator (CGU), and computational results for protein-protein docking problems are provided     

一种考虑区间直觉模糊集的多属性匹配决策方法

针对属性及属性权重均为区间直觉模糊数（IVIFN）的多属性匹配决策问题,提出一种匹配决策方法．首先根据区间直觉模糊数加权绝对值距离的定义,以逼近理想解法的思想,构建一方主体与另一方潜在对象最优匹配度的分式规划模型,并通过Charnes-Cooper变换,将原模型化为线性规划模型并求解模型得到双方的匹配度矩阵;然后,以匹配度最大为目标,建立一种双目标区间优化模型,通过线性加权转为单目标优化模型并求解得到匹配结果．最后,算例说明了所提方法的可行性和有效性．