Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

A Quadratic Penalty Method for Hypergraph Matching Event

16:00 - 17:00
3 August 2017
Building 2, Room 1027

For more information regarding this event, please email Dr. Konstantinos Katsikopoulos at .

Event details

Hypergraph matching is a fundamental problem in computer vision. Mathematically speaking, it maximizes a polynomial objective function, subject to assignment constraints. In this talk, we reformulate the hypergraph matching problem as a sparse constrained optimization problem. By dropping the sparse 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 algorithm is efficient in terms of both accuracy and speed. This is a joint work with C.F. Cui, L.Q. Qi and H. Yan.

Speaker information

Dr. Quingna Li ,Bejing Institute of Technology ,Qingna Li received her PhD. Degree in Computational Mathematics from Hunan University, China, in 2010, jointly supervised by Prof. Donghui L i(Hunan University) and Prof. Houduo Qi(University of Southampton). She was a visiting student in University of Southampton from 2008-2010. She conducted her Postduc research with Prof. Yaxiang Yuan in Chinese Academy of Sciences from 2010-2012. In June 2012, She joined Beijing Institute of Technology as an assistant professor and has been an associate Professor in School of Mathematics and Statistics, Beijing Institute of Technology, since June 2013. Her research interests include optimization methods and applications in finance, statistics and signal processing. Currently, she chairs one NSF project (11761036, 2017-2020).

Privacy Settings