×

On scaled stopping criteria for a safeguarded augmented Lagrangian method with theoretical guarantees. (English) Zbl 1484.65119

Summary: This paper discusses the use of a stopping criterion based on the scaling of the Karush-Kuhn-Tucker (KKT) conditions by the norm of the approximate Lagrange multiplier in the ALGENCAN implementation of a safeguarded augmented Lagrangian method. Such stopping criterion is already used in several nonlinear programming solvers, but it has not yet been considered in ALGENCAN due to its firm commitment with finding a true KKT point even when the multiplier set is not bounded. In contrast with this view, we present a strong global convergence theory under the quasi-normality constraint qualification, that allows for unbounded multiplier sets, accompanied by an extensive numerical test which shows that the scaled stopping criterion is more efficient in detecting convergence sooner. In particular, by scaling, ALGENCAN is able to recover a solution in some difficult problems where the original implementation fails, while the behavior of the algorithm in the easier instances is maintained. Furthermore, we show that, in some cases, a considerable computational effort is saved, proving the practical usefulness of the proposed strategy.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andreani, R.; Birgin, EG; Martínez, JM; Schuverdt, ML, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 4, 1286-1309 (2007) · Zbl 1151.49027 · doi:10.1137/060654797
[2] Andreani, R.; Fazzio, N.; Schuverdt, M.; Secchin, L., A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences, SIAM J. Optim., 29, 1, 743-766 (2019) · Zbl 1451.90166 · doi:10.1137/17M1147330
[3] Andreani, R.; Haeser, G.; Martínez, JM, On sequential optimality conditions for smooth constrained optimization, Optimization, 60, 5, 627-641 (2011) · Zbl 1225.90123 · doi:10.1080/02331930903578700
[4] Andreani, R., Haeser, G., Mito, L.M., Ramos, A., Secchin, L.D.: On the best achievable quality of limit points of augmented Lagrangian schemes. Tech. rep., Optimization Online (2020). http://www.optimization-online.org/DB_HTML/2020/07/7929.html
[5] Andreani, R.; Haeser, G.; Schuverdt, ML; Silva, PJS, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135, 1, 255-273 (2012) · Zbl 1262.90162 · doi:10.1007/s10107-011-0456-0
[6] Andreani, R., Martínez, J.M., Santos, L.T.: Newton’s method may fail to recognize proximity to optimal points in constrained optimization. Math. Program. 160(1), 547-555 (2016). doi:10.1007/s10107-016-0994-6 · Zbl 1356.90137
[7] Andreani, R.; Martinez, JM; Schuverdt, ML, On the relation between constant positive linear dependence condition and quasinormality constraint qualification, J. Optim. Theory Appl., 125, 2, 473-483 (2005) · Zbl 1125.90058 · doi:10.1007/s10957-004-1861-9
[8] Andreani, R.; Martínez, JM; Ramos, A.; Silva, PJS, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim., 26, 1, 96-110 (2016) · Zbl 1329.90162 · doi:10.1137/15M1008488
[9] Andreani, R.; Martínez, JM; Ramos, A.; Silva, PJS, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res., 43, 3, 693-717 (2018) · Zbl 1516.90091 · doi:10.1287/moor.2017.0879
[10] Andreani, R.; Martínez, JM; Svaiter, BF, A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim., 20, 6, 3533-3554 (2010) · Zbl 1217.90148 · doi:10.1137/090777189
[11] Andreani, R.; Secchin, LD; Silva, PJS, Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints, SIAM J. Optim., 28, 3, 2574-2600 (2018) · Zbl 1406.90114 · doi:10.1137/17M1125698
[12] Bartholomew-Biggs, M.: Nonlinear Optimization with Financial Applications. Springer US (2005). doi:10.1007/b102601 · Zbl 1083.90001
[13] Bartholomew-Biggs, M.: Nonlinear Optimization with Engineering Applications, Springer Optimization and Its Applications, vol. 19. Springer, US (2008). doi:10.1007/978-0-387-78723-7 · Zbl 1167.90001
[14] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific (1999) · Zbl 1015.90077
[15] Bertsekas, D.P.: Convex Analysis and Optimization. Athena Scientific (2003) · Zbl 1140.90001
[16] Bertsekas, DP; Ozdaglar, AE, Pseudonormality and a Lagrange multiplier theory for constrained optimization, J. Optim. Theory Appl., 114, 2, 287-343 (2002) · Zbl 1026.90092 · doi:10.1023/A:1016083601322
[17] Birgin, EG; Martínez, JM, Large-scale active-set box-constrained optimization method with spectral projected gradients, Comput. Optim. Appl., 23, 1, 101-125 (2002) · Zbl 1031.90012 · doi:10.1023/A:1019928808826
[18] Birgin, EG; Martínez, JM, Improving ultimate convergence of an augmented Lagrangian method, Optim. Methods Softw., 23, 2, 177-195 (2008) · Zbl 1211.90222 · doi:10.1080/10556780701577730
[19] Birgin, E.G., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA (2014). doi:10.1137/1.9781611973365 · Zbl 1339.90312
[20] Birgin, E.G., Martínez, J.M.: Complexity and performance of an augmented Lagrangian algorithm. Optimization Methods and Software, pp. 1-36 (2020). doi:10.1080/10556788.2020.1746962
[21] Bueno, L.; Haeser, G.; Rojas, F., Optimality conditions and constraint qualifications for generalized nash equilibrium problems and their practical implications, SIAM J. Optim., 29, 1, 31-54 (2019) · Zbl 1422.91049 · doi:10.1137/17M1162524
[22] Büskens, C., Wassel, D.: The ESA NLP Solver WORHP, pp. 85-110. Springer New York, New York, NY (2013). doi:10.1007/978-1-4614-4469-5_4 · Zbl 1365.90007
[23] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[24] Fletcher, R., Leyffer, S.: User manual for filterSQP. Tech. Rep. NA/181, University of Dundee (1998). https://wiki.mcs.anl.gov/leyffer/images/5/58/SQP_manual.pdf
[25] Gill, PE; Kungurtsev, V.; Robinson, DP, A stabilized SQP method: global convergence, IMA J. Numer. Anal., 37, 1, 407-443 (2016) · Zbl 1433.90162 · doi:10.1093/imanum/drw004
[26] Gondzio, J., Interior point methods 25 years later, Eur. J. Oper. Res., 218, 3, 587-601 (2012) · Zbl 1244.90007 · doi:10.1016/j.ejor.2011.09.017
[27] Guignard, M., Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space, SIAM J. Control, 7, 2, 232-241 (1969) · Zbl 0182.53101 · doi:10.1137/0307016
[28] Janin, R.: Directional derivative of the marginal function in nonlinear programming. In: Fiacco, A. V. (ed.) Sensitivity, Stability and Parametric Analysis, Mathematical Programming Studies, vol. 21, pp. 110-126. Springer Berlin (1984). doi:10.1007/BFb0121214 · Zbl 0549.90082
[29] Mangasarian, O.; Fromovitz, S., The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl., 17, 1, 37-47 (1967) · Zbl 0149.16701 · doi:10.1016/0022-247X(67)90163-1
[30] Murtagh, B.A., Saunders, M.A.: MINOS 5.51 user’s guide. Tech. Rep. SOL 83-20R, Stanford University (2003). https://web.stanford.edu/group/SOL/guides/minos551.pdf
[31] Nocedal, J.; Wright, SJ, Numerical Optimization (2006), Berlin: Springer, Berlin · Zbl 1104.65059
[32] Ozdaglar, AE; Bertsekas, DP, The relation between pseudonormality and quasiregularity in constrained optimization, Optim. Methods Softw., 19, 5, 493-506 (2004) · Zbl 1097.90053 · doi:10.1080/10556780410001709420
[33] Qi, L.; Wei, Z., On the constant positive linear dependence condition and its application to SQP methods, SIAM J. Optim., 10, 4, 963-981 (2000) · Zbl 0999.90037 · doi:10.1137/S1052623497326629
[34] Secchin, L.D.: Scaled-algencan v1.0.0 (2021). doi: doi:10.5281/zenodo.5138345
[35] Sra, S., Nowozin, S., Wright, S.J. (eds.): Optimization for Machine Learning. MIT Press, Neural Information Processing Series (2012)
[36] Terlaky, T., Anjos, M.F., Ahmed, S.: Advances and Trends in Optimization with Engineering Applications. SIAM (2017) · Zbl 1410.90001
[37] Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
[38] Ye, JJ; Zhang, J., Enhanced Karush-Kuhn-Tucker condition and weaker constraint qualifications, Math. Program., 139, 1, 353-381 (2013) · Zbl 1285.90078 · doi:10.1007/s10107-013-0667-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.