Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An Augmented Lagrangian Method for Equality Constrained Optimization with Rapid Infeasibility Detection Capabilities

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We present a primal-dual augmented Lagrangian method for solving an equality constrained minimization problem, which is able to rapidly detect infeasibility. The method is based on a modification of the algorithm proposed in Armand and Omheni (Optim Methods Softw 32(1):1–21, 2017). A new parameter is introduced to scale the objective function and, in case of infeasibility, to force the convergence of the iterates to an infeasible stationary point. It is shown, under mild assumptions, that whenever the algorithm converges to an infeasible stationary point, the rate of convergence is quadratic. This is a new convergence result for the class of augmented Lagrangian methods. The global convergence of the algorithm is also analyzed. It is also proved that, when the algorithm converges to a stationary point, the properties of the original algorithm are preserved. The numerical experiments show that our new approach is as good as the original one when the algorithm converges to a local minimum, but much more efficient in case of infeasibility.

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
$34.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  2. Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Optimization (Symposium of University Keele, Keele, 1968), pp. 283–298. Academic Press, London (1969)

  3. Conn, A.R., Gould, N.I.M., Toint, P.L.: LANCELOT, Springer Series in Computational Mathematics, vol. 17. Springer, Berlin (1992). A Fortran package for large-scale nonlinear optimization (release A)

  4. 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(4), 1286–1309 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  5. Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: Augmented Lagrangian methods under the constant positive linear dependence constraint qualification. Math. Program. 111(1–2), 5–32 (2008)

    MathSciNet  MATH  Google Scholar 

  6. Birgin, E.G., Martínez, J.M.: Practical augmented Lagrangian methods for constrained optimization, Fundamentals of Algorithms, vol. 10. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2014)

  7. Armand, P., Omheni, R.: A globally and quadratically convergent primal-dual augmented Lagrangian algorithm for equality constrained optimization. Optim. Methods Softw. 32(1), 1–21 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  8. Martínez, J.M., Prudente, L.D.F.: Handling infeasibility in a large-scale nonlinear optimization algorithm. Numer. Algorithms 60(2), 263–277 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Birgin, E.G., Martínez, J.M., Prudente, L.F.: Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming. J. Glob. Optim. 58(2), 207–242 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Birgin, E.G., Martínez, J.M., Prudente, L.F.: Optimality properties of an augmented Lagrangian method on infeasible problems. Comput. Optim. Appl. 60(3), 609–631 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Birgin, E.G., Floudas, C.A., Martínez, J.M.: Global minimization using an augmented Lagrangian method with variable lower-level constraints. Math. Program. 125(1), 139–162 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gonçalves, M.L.N., Melo, J.G., Prudente, L.F.: Augmented Lagrangian methods for nonlinear programming with possible infeasibility. J. Glob. Optim. 63(2), 297–318 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Byrd, R.H., Curtis, F.E., Nocedal, J.: Infeasibility detection and SQP methods for nonlinear optimization. SIAM J. Optim. 20(5), 2281–2299 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Burke, J.V., Curtis, F.E., Wang, H.: A sequential quadratic optimization algorithm with rapid infeasibility detection. SIAM J. Optim. 24(2), 839–872 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Bertsekas, D.P.: Constrained optimization and Lagrange multiplier methods. In: Computer Science and Applied Mathematics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York (1982)

  16. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2006)

  17. Forsgren, A., Gill, P.E., Wright, M.H.: Interior methods for nonlinear optimization. SIAM Rev. 44(4), 525–597 (2002). (2003)

    Article  MathSciNet  MATH  Google Scholar 

  18. Armand, P., Benoist, J., Orban, D.: From global to local convergence of interior methods for nonlinear optimization. Optim. Methods Softw. 28(5), 1051–1080 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  19. Forsgren, A., Gill, P.E.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM J. Optim. 8(4), 1132–1152 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  20. Dennis Jr., J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Classics in Applied Mathematics, vol. 16. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1996)

    Book  Google Scholar 

  21. Gould, N.I.M., Orban, D., Toint, P.L.: Cuter and sifdec: a constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003)

    Article  MATH  Google Scholar 

  22. Armand, P., Benoist, J., Omheni, R., Pateloup, V.: Study of a primal-dual algorithm for equality constrained minimization. Comput. Optim. Appl. 59(3), 405–433 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  23. Duff, I.S.: MA57–a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30(2), 118–144 (2004)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  25. Birgin, E.G., Bueno, L.F., Martínez, J.M.: Sequential equality-constrained optimization for nonlinear programming. Comput. Optim. Appl. 65(3), 699–721 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  26. Curtis, F.E.: A penalty-interior-point algorithm for nonlinear constrained optimization. Math. Program. Comput. 4(2), 181–209 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  27. Nocedal, J., Öztoprak, F., Waltz, R.A.: An interior point method for nonlinear programming with infeasibility detection capabilities. Optim. Methods Softw. 29(4), 837–854 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  28. Armand, P., Omheni, R.: A mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization. J. Optim. Theory Appl. 173(2), 523–547 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  29. Armand, P., Tran, N.N.: Rapid infeasibility detection in a mixed logarithmic barrier augmented Lagrangian method for nonlinear optimization. Optim. Methods Softw. (2018). https://doi.org/10.1080/10556788.2018.1528250

Download references

Author information

Authors and Affiliations

  1. Université de Limoges - Laboratoire XLIM, Limoges, France

    Paul Armand & Ngoc Nguyen Tran

Authors
  1. Paul Armand
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ngoc Nguyen Tran
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paul Armand.

Additional information

Communicated by Marco Antonio López-Cerdá.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Armand, P., Tran, N.N. An Augmented Lagrangian Method for Equality Constrained Optimization with Rapid Infeasibility Detection Capabilities. J Optim Theory Appl 181, 197–215 (2019). https://doi.org/10.1007/s10957-018-1401-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-018-1401-7

Keywords

Search

Navigation