A quadratic penalty method for hypergraph matching

DOI10.1007/S10898-017-0583-0MaRDI QIDQ683734zbMATH OpenOpenAlexFDO

Authors Chunfeng Cui, Liqun Qi, Hong Yan, Qing-Na Li

Publication date 9 February 2018

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.04581

zbMATH Keywords

projected gradient methodhypergraph matchingsparse optimizationquadratic penalty method

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Abstract: Hypergraph matching is a fundamental problem in computer vision. Mathematically speaking, it maximizes a polynomial objective function, subject to assignment constraints. In this paper, we reformulate the hypergraph matching problem as a sparse constrained tensor optimization problem. The optimality conditions are characterized based on the sparse constrained optimization theory. By dropping the sparsity constraint, we show that the resulting relaxation problem can recover the global minimizer of the original problem. The critical step in solving the original problem is to identify the location of nonzero entries (referred as support set) in a global minimizer. Inspired by such observations, we penalize the equality constraints and apply the quadratic penalty method to solve the relaxation problem. Under reasonable assumptions, we show that the support set of the global minimizer in hypergraph matching problem can be correctly identified when the number of iterations is sufficiently large. A projected gradient method is applied as a subsolver to solve the quadratic penalty subproblem. Numerical results demonstrate that the exact recovery of support set indeed happens, and the proposed algorithms are efficient in terms of both accuracy and speed.

Recommendations

• Lagrangian relaxation graph matching
• Graph matching with nonnegative sparse model
• Graph matching by simplified convex-concave relaxation procedure
• scientific article; zbMATH DE number 1844618
• A sparse nonnegative matrix factorization technique for graph matching problems

Cites work

• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A convergent iterative hard thresholding for nonnegative sparsity optimization
• A quadratic penalty method for hypergraph matching
• An augmented Lagrangian method for non-Lipschitz nonconvex programming
• Constraint qualifications and optimality conditions for optimization problems with cardinality constraints
• Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method
• New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds
• On solutions of sparsity constrained optimization
• Optimality conditions for sparse nonlinear programming
• Optimization theory and methods. Nonlinear programming
• Projected Newton Methods for Optimization Problems with Simple Constraints
• Projected gradient methods for linearly constrained problems
• Reducibility among combinatorial problems
• Restricted normal cones and sparsity optimization with affine constraints
• Sparse Approximation via Penalty Decomposition Methods
• Sparsity constrained nonlinear optimization: optimality conditions and algorithms
• The first-order necessary conditions for sparsity constrained optimization
• \(L_p\)-norm regularization algorithms for optimization over permutation matrices

Cited in

(5)

• A quadratic penalty method for hypergraph matching
• Lagrangian relaxation graph matching
• scientific article; zbMATH DE number 6297805 (Why is no real title available?)
• Quasi-best match graphs
• An efficient quadratic programming relaxation based algorithm for large-scale MIMO detection

This page was built for publication: A quadratic penalty method for hypergraph matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q683734)