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

Mathematical Modelling and Numerical Analysis Journal (vol 31, n°1, 1997, p57-90)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 themathematical models of some important problems encountered in Computer Vision. Most of them can be formulated as a mimmization of a sum of squares of nonlinear functions. A practical TR-based algorithm is proposed for nonlinear least squares problem which seems to be well suited for our applications.L'étude de la stabilité de la dualité Lagrangienne relative au problème de minimisation d'une forme quadratique non convexe sur une boule euclidienne est présentée. Elle permet d'établir les caractérisations complètes des solutions optimales globales du problème. Pour la résolution duquel nous proposons deux algorithmes globaux de type primal-dual basés sur ces résultats théoriques. Une des applications importantes de ces algorithmes concerne le calcul d'un pas de déplacement dans les méthodes de région de confiance qui sont reconnues très robustes et performantes pour les problèmes d'optimisation non linéaire. Nous discutons aussi des modélisations mathématiques des problèmes importants rencontrés en Vision par Ordinateur. La plupart peuvent être formulés comme un problème de moindres carrés non linéaires. Finalement une méthode pratique de région de confiance est proposée pour ces problèmes qui semble très bien adaptée à nos applications