Abstract

This paper analyses the behavior of the augmented Lagrangian algorithm when it deals with an infeasible convex quadratic optimization problem. It is shown that the algorithm finds a point that, on the one hand, satisfies the constraints shifted by the smallest possible shift that makes them feasible and, on the other hand, minimizes the objective on the corresponding shifted constrained set. The speed of convergence to such a point is globally linear, with a rate that is inversely proportional to the augmentation parameter. This suggests us a rule for determining the augmentation parameter that aims at controlling the speed of convergence of the shifted constraint norm to zero; this rule has the advantage of generating bounded augmentation parameters even when the problem is infeasible.

Author information

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

Alice Chiche

INRIA Paris, 2 rue Simone Iff, CS 42112, 75589 Paris Cedex 12, France
and: EDF R&D, Osiris departement, 1, avenue du Général de Gaulle, 92141 Clamart Cedex, France
and: Artelys France, 12 rue du Quatre Septembre, 75002 Paris, France

Alice.Chiche@artelys.com

Keywords

  • Augmented Lagrangian algorithm
  • augmentation parameter update
  • closest feasible problem
  • convex quadratic optimization
  • feasible shift
  • global linear convergence
  • infeasible problem
  • proximal point algorithm
  • quasi-global error bound
  • shifted constraint

Mathematics Subject Classification

49M27, 49M29, 65K05, 90C05, 90C06, 90C20, 90C25

References

  1. K. J. Arrow, F. J. Gould, S. M. Howe: A general saddle point result for constrained optimization, Math. Program. 5 (1973) 225–234.https://doi.org/10.1007/BF01580123Google Scholar
  2. A. Auslender, M. Teboulle: Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer Monographs in Mathematics, Springer, New York (2003).Google Scholar
  3. E. G. Birgin, J. M. Martínez: Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM, Philadelphia (2014).https://doi.org/10.1137/1.9781611973365Google Scholar
  4. J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: A family of variable metric proximal methods, Math. Program., Ser. A 68 (1995) 15–47.https://doi.org/10.1007/BF01585756Google Scholar
  5. J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: Numerical Optimization. Theoretical and Practical Aspects, 2nd Ed., Universitext, Springer, Berlin (2006).Google Scholar
  6. J. M. Borwein, A. S. Lewis: Convex Analysis and Nonlinear Optimization, Springer, New York (2000).https://doi.org/10.1007/978-1-4757-9859-3Google Scholar
  7. R. E. Bruck, S. Reich: Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston J. Math. 3 (1977) 459–470.Google Scholar
  8. J. V. Burke: A sequential quadratic programming method for potentially infeasible mathematical programs, J. Math. Anal. Appl. 139 (1989) 319–351.https://doi.org/10.1016/0022-247X(89)90111-XGoogle Scholar
  9. J. V. Burke: A robust trust region method for constrained nonlinear programming problems, SIAM J. Optim. 2 (1992) 325–347.https://doi.org/10.1137/0802016Google Scholar
  10. J. V. Burke, S.-P. Han: A robust sequential quadratic programming method, Math. Program., Ser. A 43 (1989) 277–303.https://doi.org/10.1007/BF01582294Google Scholar
  11. J. D. Buys: Dual Algorithms for Constrained Optimization, PhD Thesis, Rijksuniversiteit te Leiden, Leiden (1972).Google Scholar
  12. R. H. Byrd: Robust trust region methods for constrained optimization, at: SIAM Conference on Optimization (Houston, 1987).Google Scholar
  13. R. H. Byrd, R. B. Schnabel, G. A. Shultz: A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numer. Anal. 24 (1987) 1152–1170.https://doi.org/10.1137/0724076Google Scholar
  14. A. R. Conn, N. I. M. Gould, Ph. L. Toint: Trust-Region Methods, MPS-SIAM Series on Optimization 1, SIAM and MPS, Philadelphia (2000).https://doi.org/10.1137/1.9780898719857Google Scholar
  15. R. Correa, C. Lemaréchal: Convergence of some algorithms for convex minimization, Math. Program., Ser. B 62 (1993) 261–275.https://doi.org/10.1007/BF01585170Google Scholar
  16. E. J. Dean, R. Glowinski: An augmented Lagrangian approach to the numerical solution of the Dirichlet problem for the elliptic Monge-Ampère equation in two dimensions, ETNA, Electron. Trans. Numer. Anal. 22 (2006) 71–96.Google Scholar
  17. F. Delbos, J. Ch. Gilbert: Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems, J. Convex Analysis 12 (2005) 45–69.https://doi.org/10.68381/jca12003Google Scholar
  18. Z. Dostál, A. Friedlander, S. A. Santos: Augmented Lagrangians with adaptive precision control for quadratic programming with equality constraints, Comput. Optim. Appl. 14 (1999) 37–53.https://doi.org/10.1023/A:1008700911674Google Scholar
  19. Z. Dostál, A. Friedlander, S. A. Santos: Augmented Lagrangians with adaptive precision control for quadratic programming with simple bounds and equality constraints, SIAM J. Optim. 13 (2003) 1120–1140.https://doi.org/10.1137/S1052623499362573Google Scholar
  20. Z. Dostál, A. Friedlander, S. A. Santos, K. Alesawi: Augmented Lagrangians with adaptive precision control for quadratic programming with equality constraints: corrigendum and addendum, Comput. Optim. Appl. 23 (2000) 127–133.https://doi.org/10.1023/A:1019980809734Google Scholar
  21. J. Eckstein: Augmented Lagrangian and alternating direction methods for convex optimization: a tutorial and some illustrative computational results, RUTCOR Research Report RRR 32-2012, Rutgers University, Piscataway (2012).Google Scholar
  22. J. Eckstein, P. J. S. Silva: Proximal methods for nonlinear programming: double regularization and inexact subproblems, Comput. Optim. Appl. 46 (2010) 279–304.https://doi.org/10.1007/s10589-009-9274-1Google Scholar
  23. J. Eckstein, P. J. S. Silva: A practical relative error criterion for augmented Lagrangians, Math. Program., Ser. A 141 (2013) 319–348.https://doi.org/10.1007/s10107-012-0528-9Google Scholar
  24. 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
  25. M. Frank, P. Wolfe: An algorithm for quadratic programming, Nav. Res. Logist. Q. 3 (1956) 95–110.https://doi.org/10.1002/nav.3800030109Google Scholar
  26. M. Friedlander, S. Leyffer: Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs, SIAM J. Sci. Comput. 30 (2008) 1706–1726.https://doi.org/10.1137/060669930Google Scholar
  27. J. Ch. Gilbert: QPAL – A solver of convex quadratic optimization problems, using an augmented Lagrangian approach, Version 0.6.1, Rapport Technique 0377, INRIA, Le Chesnay (2009).Google Scholar
  28. J. Ch. Gilbert, É. Joannopoulos: OQLA/QPALM - Convex quadratic optimization solvers using the augmented Lagrangian approach, able to deal with infeasibility, Technical report, INRIA, Le Chesnay (2014), to appear.Google Scholar
  29. P. E. Gill, E. Wong: Sequential quadratic programming methods, in: Mixed Integer Nonlinear Programming (Minneapolis, 2008), J. Lee, S. Leyffer (eds.), IMA Volumes in Mathematics and its Applications 154, Springer, New York (2012) 147–224.https://doi.org/10.1007/978-1-4614-1927-3_6Google Scholar
  30. R. Glowinski, P. Le Tallec: Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics 9, SIAM, Philadelphia (1989).https://doi.org/10.1137/1.9781611970838Google Scholar
  31. O. Güler: Augmented Lagrangian algorithms for linear programming, J. Optimization Theory Appl. 75 (1992) 445–470.https://doi.org/10.1007/BF00940486Google Scholar
  32. D. Henrion, J. Malick: Projection methods for conic feasibility problems: applications to polynomial sum-of-squares decompositions, Optim. Methods Softw. 26 (2009) 23–46.https://doi.org/10.1080/10556780903191165Google Scholar
  33. M. R. Hestenes: Multiplier and gradient methods, J. Optimization Theory Appl. 4 (1969) 303–320.https://doi.org/10.1007/BF00927673Google Scholar
  34. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms, Grundlehren der mathematischen Wissenschaften 305–306, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  35. A. F. Izmailov, M. V. Solodov: Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operations Research and Financial Engineering, Springer, Cham (2014).https://doi.org/10.1007/978-3-319-04247-3Google Scholar
  36. K. C. Kiwiel: Proximity control in bundle methods for convex nondifferentiable minimization, Math. Program., Ser. A 46 (1990) 105–122.https://doi.org/10.1007/BF01585731Google Scholar
  37. J. Malick: A dual approach to semidefinite least-squares problems, SIAM J. Matrix Anal. Appl. 26 (2004) 272–284.https://doi.org/10.1137/S0895479802413856Google Scholar
  38. J. Malick, J. Povh, F. Rendl, A. Wiegele: Regularization methods for semidefinite programming, SIAM J. Optim. 20 (2009) 336–356.https://doi.org/10.1137/070704575Google Scholar
  39. J. J. Moreau: Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. Fr. 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  40. E. O. Omojokun: Trust Region Algorithms for Optimization with Nonlinear Equality and Inequality Constraints, PhD Thesis, Department of Computer Science, University of Colorado, Boulder (1991).Google Scholar
  41. B. T. Poljak, N. V. Tret’jakov: A certain iteration method of linear programming and its economic interpretation, Èkon. Mat. Metody 8 (1972) 740–751 (in Russian).Google Scholar
  42. M. J. D. Powell: A method for nonlinear constraints in minimization problems, in: Optimization (Keele, 1968), R. Fletcher (ed.), Academic Press, London (1969) 283–298.Google Scholar
  43. M. J. D. Powell: A fast algorithm for nonlinearly constrained optimization calculations, in: Numerical Analysis (Dundee, 1977), G. A. Watson (ed.), Lecture Notes in Mathematics 630, Springer, Berlin (1978) 144–157.https://doi.org/10.1007/BFb0067703Google Scholar
  44. M. J. D. Powell, Y. Yuan: A trust region algorithm for equality constrained optimization, Math. Program., Ser. A 49 (1991) 189–211.https://doi.org/10.1007/BF01588787Google Scholar
  45. S. Reich: On infinite products of resolvents, Atti Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat. (1977) 338–340.Google Scholar
  46. R. T. Rockafellar: Convex Analysis, Princeton Mathematics Ser. 28, Princeton University Press, Princeton (1970).Google Scholar
  47. R. T. Rockafellar: New applications of duality in convex programming, in: Proc. 4th Conf. of Probability, Brasov, Romania (1971) 73–81.Google Scholar
  48. 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
  49. R. T. Rockafellar: The multiplier method of Hestenes and Powell applied to convex programming, J. Optimization Theory Appl. 12 (1973) 555–562.https://doi.org/10.1007/BF00934777Google Scholar
  50. 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
  51. R. T. Rockafellar: Conjugate Duality and Optimization, Regional Conference Series in Applied Mathematics 16, SIAM, Philadelphia (1974).https://doi.org/10.1137/1.9781611970524Google Scholar
  52. 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
  53. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Grundlehren der mathematischen Wissenschaften 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  54. A. Shapiro, J. Sun: Some properties of the augmented Lagrangian in cone constrained optimization, Math. Oper. Res. 29 (2004) 479–491.https://doi.org/10.1287/moor.1040.0103Google Scholar
  55. M. V. Solodov, B. F. Svaiter: A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Anal. 7 (1999) 323–345.https://doi.org/10.1023/A:1008777829180Google Scholar
  56. M. V. Solodov, B. F. Svaiter: A hybrid projection-proximal point algorithm, J. Convex Analysis 6 (1999) 59–70.https://doi.org/10.68381/jca06005Google Scholar
  57. M. V. Solodov, B. F. Svaiter: An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions, Math. Oper. Res. 25 (2000) 214–230.https://doi.org/10.1287/moor.25.2.214.12222Google Scholar
  58. J. E. Spingarn: Partial inverse of a monotone operator, Appl. Math. Optimization 10 (1983) 247–265.https://doi.org/10.1007/BF01448388Google Scholar
  59. J. E. Spingarn: A projection method for least-squares solutions to overdetermined systems of linear inequalities, Linear Algebra Appl. 86 (1987) 211–236.https://doi.org/10.1016/0024-3795(87)90296-5Google Scholar
  60. A. Vardi: A trust region algorithm for equality constrained minimization: convergence properties and implementation, SIAM J. Numer. Anal. (1985) 575–591.https://doi.org/10.1137/0722035Google Scholar
  61. Z. Wen, D. Goldfarb, W. Yin: Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput. 2 (2010) 203–230.https://doi.org/10.1007/s12532-010-0017-1Google Scholar

Suggested citation

A. Chiche, J. C. Gilbert. “How the Augmented Lagrangian Algorithm Can Deal with an Infeasible Convex Quadratic Optimization Problem.” Journal of Convex Analysis 23 (2016), No. 2, 425–459. https://doi.org/10.68381/jca23016

Download BibTeXPublished by Heldermann Verlag.

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