Stability of Lagrangian Duality for Nonconvex Quadratic Programming. Solution Methods and Applications to Computer Vision

Abstract : The problem of minimizing a quadratic form over a ball centered at the origin is considered. The stability of Lagrangian duality is established and complete characterizations of a global optimal solution are given. On the basis of this theoretical study, two principal solution methods are presented. An important application of nonconvex quadratic programming is the computation of the step to a new iterate in the Trust Region (TR) approach methods which are known to be efficient for nonlinear optimization problems. Also, we discuss the mathematical models of some important problems encountered in Computer Vision. Most of them can be formulated as a minimization of a sum of squares of nonlinear functions. A pratical TR-based algorithm is proposed for nonlinear least squares problem which seems to be well suited for our applications.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/inria-00590073
Contributor : Team Perception <>
Submitted on : Thursday, January 16, 2014 - 1:55:52 PM
Last modification on : Thursday, February 7, 2019 - 5:37:29 PM
Long-term archiving on : Thursday, March 30, 2017 - 10:06:56 AM

File

pham_horaud_stability97.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00590073, version 1

Citation

Pham-Dinh Tao, Thai-Quynh Phong, Radu Horaud, Long Quan. Stability of Lagrangian Duality for Nonconvex Quadratic Programming. Solution Methods and Applications to Computer Vision. ESAIM: Mathematical Modelling and Numerical Analysis, EDP Sciences, 1997, 31 (1), pp.57--90. ⟨inria-00590073⟩

Share

Metrics

Record views

260

Files downloads

205