Abstract

We consider an augmented Lagrangian algorithm for minimizing a convex quadratic function subject to linear inequality constraints. Linear optimization is an important particular instance of this problem. We show that, provided the augmentation parameter is large enough, the constraint value converges globally linearly to zero. This property is viewed as a consequence of the proximal interpretation of the algorithm and of the global radial Lipschitz continuity of the reciprocal of the dual function subdifferential. This Lipschitz property is itself obtained by means of a lemma of general interest, which compares the distances from a point in the positive orthant to an affine space, on the one hand, and to the polyhedron given by the intersection of this affine space and the positive orthant, on the other hand. No strict complementarity assumption is needed. The result is illustrated by numerical experiments and algorithmic implications, including complexity issues, are discussed.

Author information

Contact details are reproduced from the original publication and may be historical.

Frédéric Delbos

Institut Français du Pétrole, 1&4 ave. de Bois-Préau, 92852 Rueil-Malmaison, France

Keywords

  • Augmented Lagrangian
  • convex quadratic optimization
  • distance to a polyhedron
  • error bound
  • global linear convergence
  • iterative complexity
  • linear constraints
  • proximal algorithm

Mathematics Subject Classification

49M29, 65K05, 90C05; 90C06, 90C20

References

  1. K. J. Arrow, R. M. Solow: Gradient methods for constrained maxima with weakened assumptions, in: Studies in Linear and Nonlinear Programming, K. J. Arrow et al. (eds.), Stanford University Press, Standford (1958) 166–176.Google Scholar
  2. J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: Numerical Optimization – Theoretical and Practical Aspects, Springer, Berlin (2003).https://doi.org/10.1007/978-3-662-05078-1Google Scholar
  3. J. V. Burke, M. C. Ferris: Characterization of solution sets of convex programs, Oper. Res. Lett. 10 (1991) 57–60.https://doi.org/10.1016/0167-6377(91)90087-6Google Scholar
  4. F. Delbos: Problèmes d’Optimisation de Grande Taille avec Contraintes en Tomographie de Réflexion 3D, PhD Thesis, University Pierre et Marie Curie (Paris VI), Paris, 2004.Google Scholar
  5. F. Delbos, J. Ch. Gilbert, R. Glowinski, D. Sinoquet: Constrained optimization in seismic reflection tomography: An SQP augmented Lagrangian approach, Geophys. J. Int. (2005), submitted.https://doi.org/10.1111/j.1365-246X.2005.02729.xGoogle Scholar
  6. F. Delbos, J. Ch. Gilbert, D. Sinoquet: QPAL: A solver of large-scale convex quadratic optimization problems using an augmented Lagrangian approach, Technical report, INRIA, Le Chesnay, 2005, to appear.Google Scholar
  7. D. den Hertog: Interior Point Approach to Linear, Quadratic and Convex Programming, Mathematics and its Applications 277, Kluwer Academic Publishers, Dordrecht (1992).Google Scholar
  8. M. Fortin, R. Glowinski: Méthodes de Lagrangien Augmenté – Applications à la Résolution Numérique de Problèmes aux Limites, Méthodes Mathématiques de l’Informatique 9, Dunod, Paris (1982).Google Scholar
  9. A. Friedlander, J. M. Martínez: On the maximization of a concave quadratic function with box constraints, SIAM J. Optim. 4 (1994) 177–192.https://doi.org/10.1137/0804010Google Scholar
  10. R. Glowinski, Q.-H. Tran: Constrained optimization in reflection tomography: The augmented Lagrangian method, East-West J. Numer. Math. 1(3) (1993) 213–234.Google Scholar
  11. M. R. Hestenes: Multiplier and gradient methods, J. Optimization Theory Appl. 4 (1969) 303–320.https://doi.org/10.1007/BF00927673Google Scholar
  12. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms, Grundlehren der mathematischen Wissenschaften 305-306, Springer (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  13. A. F. Izmailov, M. V. Solodov: Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications, Math. Program. 89 (2001) 413–435.https://doi.org/10.1007/PL00011406Google Scholar
  14. B. Jansen: Interior Point Techniques in Optimization – Complementarity, Sensitivity and Algorithms, Applied Optimization 6, Kluwer Academic Publishers, Dordrecht (1997).https://doi.org/10.1007/978-1-4757-5561-9Google Scholar
  15. M. Kojima, N. Megiddo, T. Noma, A. Yoshise: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538, Springer, Berlin (1991).https://doi.org/10.1007/3-540-54509-3Google Scholar
  16. O. L. Mangasarian: A simple characterization of solution sets of convex programs, Oper. Res. Lett. 7 (1988) 21–26.https://doi.org/10.1016/0167-6377(88)90047-8Google Scholar
  17. J. J. Moré, G. Toraldo: On the solution of large quadratic programming problems with bound constraints, SIAM J. Optim. 1 (1991) 93–113.https://doi.org/10.1137/0801008Google Scholar
  18. Y. E. Nesterov, A. S. Nemirovskii: Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics 13, SIAM, Philadelphia (1994).https://doi.org/10.1137/1.9781611970791Google Scholar
  19. J. Nocedal, S. J. Wright: Numerical Optimization, Springer Series in Operations Research, Springer, New York (1999).https://doi.org/10.1007/b98874Google Scholar
  20. J.-S. Pang: Methods for quadratic programming: A survey, Computers and Chemical Engineering 7 (1983) 583–594.https://doi.org/10.1016/0098-1354(83)80004-0Google Scholar
  21. J.-S. Pang: Error bounds in mathematical programming, Math. Program. 79 (1997) 299–332.https://doi.org/10.1007/BF02614322Google Scholar
  22. M. J. D. Powell: A method for nonlinear constraints in minimization problems, in: Optimization, R. Fletcher (ed.), Academic Press, London (1969) 283–298.Google Scholar
  23. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  24. R. T. Rockafellar: New applications of duality in convex programming, in: Proceedings of the 4th Conference of Probability, Brasov, Romania (1971) 73–81.Google Scholar
  25. R. T. Rockafellar: A dual approach to solving nonlinear programming problems by unconstrained optimization, Math. Program. 5 (1973) 354–373.https://doi.org/10.1007/BF01580138Google Scholar
  26. R. T. Rockafellar: Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control 12 (1974) 268–285.https://doi.org/10.1137/0312021Google Scholar
  27. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  28. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  29. C. Roos, T. Terlaky, J.-Ph. Vial: Theory and Algorithms for Linear Optimization – An Interior Point Approach, John Wiley & Sons, Chichester (1997)Google Scholar
  30. T. Terlaky (ed.): Interior Point Methods of Mathematical Programming, Kluwer Academic Press, Dordrecht (1996).https://doi.org/10.1007/978-1-4613-3449-1Google Scholar
  31. S. J. Wright: Primal-Dual Interior-Point Methods, SIAM, Philadelphia (1997).https://doi.org/10.1137/1.9781611971453Google Scholar

Suggested citation

F. Delbos, J. C. Gilbert. “Global Linear Convergence of an Augmented Lagrangian Algorithm to Solve Convex Quadratic Optimization Problems.” Journal of Convex Analysis 12 (2005), No. 1, 45–69. https://doi.org/10.68381/jca12003

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2005. Rights now held by Banach Press LLC.