Combining stabilized SQP with the augmented Lagrangian algorithm | Computational Optimization and Applications Skip to main content

Advertisement

Springer Nature Link
Log in

Combining stabilized SQP with the augmented Lagrangian algorithm

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

For an optimization problem with general equality and inequality constraints, we propose an algorithm which uses subproblems of the stabilized SQP (sSQP) type for approximately solving subproblems of the augmented Lagrangian method. The motivation is to take advantage of the well-known robust behavior of the augmented Lagrangian algorithm, including on problems with degenerate constraints, and at the same time try to reduce the overall algorithm locally to sSQP (which gives fast local convergence rate under weak assumptions). Specifically, the algorithm first verifies whether the primal-dual sSQP step (with unit stepsize) makes good progress towards decreasing the violation of optimality conditions for the original problem, and if so, makes this step. Otherwise, the primal part of the sSQP direction is used for linesearch that decreases the augmented Lagrangian, keeping the multiplier estimate fixed for the time being. The overall algorithm has reasonable global convergence guarantees, and inherits strong local convergence rate properties of sSQP under the same weak assumptions. Numerical results on degenerate problems and comparisons with some alternatives are reported.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. ALGENCAN: http://www.ime.usp.br/~egbirgin/tango/. Accessed Dec 2014

  2. Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: On augmented Lagrangian methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  3. Andreani, R., Haeser, G., Schuverdt, M.L., Silva, P.J.S.: A relaxed constant positive linear dependence constraint qualification and applications. Math. Program 135, 255–273 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)

    MATH  Google Scholar 

  5. Birgin, E.G., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization. SIAM, Philadelphia (2014)

    Book  MATH  Google Scholar 

  6. Boggs, B.T., Tolle, J.W.: Sequential quadratic programming. Acta Numerica 4, 1–51 (1996)

    Article  MathSciNet  Google Scholar 

  7. Conn, A.R., Gould, N., Sartenaer, A., Toint, P.L.: Convergence properties of an augmented Lagrangian algorithm for optimization with a combination of general equality and linear constraints. SIAM J. Optim. 6, 674–703 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  8. DEGEN: http://w3.impa.br/~optim/DEGEN_collection.zip. Accessed Dec 2014

  9. Di Pillo, G., Grippo, L.: A new class of augmented Lagrangians in nonlinear programming. SIAM J. Control Optim. 17, 618–628 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  10. Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program 91, 201–213 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Fernández, D., Pilotta, E.A., Torres, G.A.: An inexact restoration strategy for the globalization of the sSQP method. Comput. Optim. Appl. 54, 595–617 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  12. Fernández, D., Solodov, M.: Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems. Math. Program 125, 47–73 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  13. Fernández, D., Solodov, M.: Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition. SIAM J. Optim. 22, 384–407 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  14. Fischer, A.: Local behavior of an iterative framework for generalized equations with nonisolated solutions. Math. Program 94, 91–124 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  15. Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12, 979–1006 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  16. Gill, P.E., Robinson, D.P.: A primal-dual augmented Lagrangian. Comput. Optim. Appl. 51, 1–25 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  17. Gill, P.E., Robinson, D.P.: A globally convergent stabilized SQP method. SIAM J. Optim. 23, 1983–2010 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  18. Gill, P.E., Kungurtsev, V., Robinson, D.P.: A regularized SQP method with convergence to second-order optimal points. UCSD Center for Computational Mathematics Technical Report CCoM-13-4, Oct 30 (2013)

  19. Gill, P.E., Kungurtsev, V., Robinson, D.P.: A globally convergent stabilized SQP method: superlinear convergence. UCSD Center for Computational Mathematics Technical Report CCoM-13-4, June 30 (2014)

  20. Gill, P.E., Wong, E.: Sequential quadratic programming methods. In: Lee, J., Leyffer, S. (eds.) Mixed Integer Nonlinear Programming, The IMA Volumes in Mathematics and its Applications, vol. 154, pp. 147–224. Springer-Verlag, (2012)

  21. Glad, S.T.: Properties of updating methods for the multipliers in augmented Lagrangian. J. Optim. Theory Appl. 28, 135–156 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  22. Hager, W.W.: Stabilized sequential quadratic programming. Comput. Optim. Appl. 12, 253–273 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  23. Hager, W.W., Gowda, M.S.: Stability in the presence of degeneracy and error estimation. Math. Program 85, 181–192 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  24. Izmailov, A.F.: On the limiting properties of dual trajectories in the Lagrange multipliers method. Comput. Math. Math. Phys. 51, 1–20 (2011)

    Article  MathSciNet  Google Scholar 

  25. Izmailov, A.F., Kurennoy, A.S.: Abstract Newtonian frameworks and their applications. SIAM J. Optim. 23, 2369–2396 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  26. Izmailov, A.F., Kurennoy, A.S., Solodov, M.V.: A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems. Math. Program 142, 591–604 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  27. Izmailov, A.F., Solodov, M.V.: Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints. Comp. Optim. Appl. 42, 231–264 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  28. Izmailov, A.F., Solodov, M.V.: On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions. Math. Program 117, 271–304 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  29. Izmailov, A.F., Solodov, M.V.: On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers. Math. Program 126, 231–257 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  30. Izmailov, A.F., Solodov, M.V.: Stabilized SQP revisited. Math. Program 122, 93–120 (2012)

    Article  MathSciNet  Google Scholar 

  31. Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer Series in Operations Research and Financial Engineering. Springer, Cham (2014)

    Book  MATH  Google Scholar 

  32. Izmailov, A.F., Solodov, M.V.: Newton-type methods: a broader view. J. Optim. Theory Appl. 164, 577–620 (2015)

    Article  MATH  MathSciNet  Google Scholar 

  33. Izmailov, A.F., Solodov, M.V., Uskov, E.I.: Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints. SIAM J. Optim. 22, 1579–1606 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  34. Izmailov, A.F., Solodov, M.V., Uskov, E.I.: Globalizing stabilized SQP by smooth primal-dual exact penalty function. IMPA Preprint A5566 (2014)

  35. Izmailov, A.F., Uskov, E.I.: On the influence of the critical Lagrange multipliers on the convergence rate of the multiplier method. Comput. Math. Math. Phys. 52, 1504–1519 (2012)

    Article  MathSciNet  Google Scholar 

  36. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2006)

    MATH  Google Scholar 

  37. Wright, S.J.: Superlinear convergence of a stabilized SQP method to a degenerate solution. Comput. Optim. Appl. 11, 253–275 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  38. Wright, S.J.: An algorithm for degenerate nonlinear programming with rapid local convergence. SIAM J. Optim. 15, 673–696 (2005)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The authors thank the anonymous referees for many insightful comments, which led to a much improved article. Research of the first author is supported by the Russian Foundation for Basic Research Grant 14-01-00113 and by CNPq Grant PVE 401119/2014-9 (Brazil). The second author is supported in part by CNPq Grant 302637/2011-7, by PRONEX–Optimization, and by FAPERJ. The third author is supported by the Russian Foundation for Basic Research Grant 14-01-00113

Author information

Authors and Affiliations

  1. IO Department, VMK Faculty, Lomonosov Moscow State University (MSU), Uchebniy Korpus 2, Leninskiye Gory, 119991, Moscow, Russia

    A. F. Izmailov & E. I. Uskov

  2. IMPA – Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, 22460-320, Brazil

    M. V. Solodov

Authors
  1. A. F. Izmailov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. V. Solodov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. E. I. Uskov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. V. Solodov.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Izmailov, A.F., Solodov, M.V. & Uskov, E.I. Combining stabilized SQP with the augmented Lagrangian algorithm. Comput Optim Appl 62, 405–429 (2015). https://doi.org/10.1007/s10589-015-9744-6

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-015-9744-6

Keywords

Search

Navigation