A quadratic penalty method for hypergraph matching

DOI10.1007/S10898-017-0583-0zbMATH Open1393.90093arXiv1704.04581OpenAlexW2608707591MaRDI QIDQ683734FDOQ683734

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)

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.

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

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

zbMATH Keywords

projected gradient methodhypergraph matchingsparse optimizationquadratic penalty method

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Cites Work

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

Cited In (5)

• A quadratic penalty method for hypergraph matching
• Lagrangian relaxation graph matching
• Title not available (Why is that?)
• 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)