Complexity and performance of an Augmented Lagrangian algorithm

Abstract

Algencan is a well established safeguarded Augmented Lagrangian algorithm introduced in [R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2008), pp. 1286–1309]. Complexity results that report its worst-case behaviour in terms of iterations and evaluations of functions and derivatives that are necessary to obtain suitable stopping criteria are presented in this work. In addition, its computational performance considering all problems from the CUTEst collection is presented, which shows that it is a useful tool for solving large-scale constrained optimization problems.

Keywords:

• Nonlinear programming
• Augmented Lagrangian methods
• complexity
• numerical experiments

2010 Mathematics Subject Classifications:

• 90C30
• 65K05
• 49M37
• 90C60
• 68Q25

Acknowledgments

The authors are indebted to Iain Duff, Nick Gould, Dominique Orban, and Tyrone Rees for their help in issues related to the usage of MA57 from HSL and the CUTEst collection.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

E. G. Birgin http://orcid.org/0000-0002-7466-7663

J. M. Martínez http://orcid.org/0000-0003-3331-368X

Notes

1 Option ‘honor_original_bounds no’, that does not affect Ipopt's optimization process, was used. Ipopt might relax the bounds during the optimization beyond its initial relative relaxation factor whose default value is ${10}^{-8}$. Option ‘honor_original_bounds no’ simply avoids the final iterate to be projected back onto the box defined by the bound constraints. So, the actual absolute violation of the bound constraints at the final iterate can be measured.

Additional information

Funding

This work was supported by Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) (grants 2013/07375-0, 2016/01860-1, and 2018/24293-0) and Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) (grants 302538/2019-4 and 302682/2019-8).

Notes on contributors

E. G. Birgin

E. G. Birgin is a professor in the Department of Computer Science at the Institute of Mathematics and Statistics of the University of São Paulo. He is a member of the editorial boards of Mathematical Programming Computation, Computational Optimization and Applications, Journal of Global Optimization, Springer Nature Operations Research Forum, Computational and Applied Mathematics, International Transactions in Operational Research, Pesquisa Operacional, CLEI Electronic Journal, and Bulletin of Computational Applied Mathematics. He has published over 100 papers on computational optimization and applications.

J. M. Martínez

J. M. Martínez is a professor in the Department of Applied Mathematics at the University of Campinas, Brazil. He is a member of the Brazilian Academy of Sciences, former Editor in Chief of Computational and Applied Mathematics, member of the editorial board of Numerical Algorithms and Optimization Methods and Software, and the author of over 200 papers on numerical mathematics, optimization, and applications.