Complexity and performance of an Augmented Lagrangian algorithm

References

• 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. doi: 10.1137/060654797
   Web of Science ®Google Scholar
• R. Andreani, E.G. Birgin, J.M. Martínez, and M.L. Schuverdt, Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification, Math. Program. 111 (2008), pp. 5–32. doi: 10.1007/s10107-006-0077-1
   Web of Science ®Google Scholar
• R. Andreani, E.G. Birgin, J.M. Martínez, and M.L. Schuverdt, Second-order negative-curvature methods for box-constrained and general constrained optimization, Comput. Optim. Appl. 45 (2010), pp. 209–236. doi: 10.1007/s10589-009-9240-y
   Web of Science ®Google Scholar
• R. Andreani, N.S. Fazzio, M.L. Schuverdt, and L.D. Secchin, A sequential optimality conditionrelated to the quasi-normality constraint qualification and its algorithmic consequences, SIAM J. Optim. 29 (2019), pp. 743–766. doi: 10.1137/17M1147330
   Web of Science ®Google Scholar
• R. Andreani, G. Haeser, and J.M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization 60 (2011), pp. 627–641. doi: 10.1080/02331930903578700
   Web of Science ®Google Scholar
• R. Andreani, J.M. Martínez, A. Ramos, and P.J.S. Silva, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim. 26 (2016), pp. 96–110. doi: 10.1137/15M1008488
   Web of Science ®Google Scholar
• R. Andreani, J.M. Martínez, A. Ramos, and P.J.S. Silva, Strict constraint qualifications and sequential optimality conditions for constrained optimization, to appear in Math. Oper. Res. doi:10.1287/moor.2017.0879.
   Google Scholar
• R. Andreani, J.M. Martínez, and L.T. Santos, Newton's method may fail to recognize proximity to optimal points in constrained optimization, Math. Program. 160 (2016), pp. 547–555. doi: 10.1007/s10107-016-0994-6
   Web of Science ®Google Scholar
• R. Andreani, J.M. Martínez, L.T. Santos, and B.F. Svaiter, On the behavior of constrained optimization methods when Lagrange multipliers do not exist, Optim. Methods Softw. 29 (2014), pp. 646–657. doi: 10.1080/10556788.2013.841692
   Web of Science ®Google Scholar
• R. Andreani, J.M. Martínez, and B.F. Svaiter, A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim. 20 (2010), pp. 3533–3554. doi: 10.1137/090777189
   Web of Science ®Google Scholar
• M. Andretta, E.G. Birgin, and J.M. Martínez, Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization, Optimization 54 (2005), pp. 305–325. doi: 10.1080/02331930500100270
   Web of Science ®Google Scholar
• P. Armand and R. Omheni, A globally and quadratically convergent primal-dual augmented Lagrangian algorithm for equality constrained optimization, Optim. Methods Softw. 32 (2017), pp. 1–21. doi: 10.1080/10556788.2015.1025401
   Web of Science ®Google Scholar
• P. Armand and R. Omheni, A mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization, J. Optim. Theory Appl. 173 (2017), pp. 523–547. doi: 10.1007/s10957-017-1071-x
   Web of Science ®Google Scholar
• E.G. Birgin, D. Fernández, and J.M. Martínez, On the boundedness of penalty parameters in an Augmented Lagrangian method with lower level constraints, Optim. Methods Softw. 27 (2012), pp. 1001–1024. doi: 10.1080/10556788.2011.556634
   Web of Science ®Google Scholar
• E.G. Birgin, C.A. Floudas, and J.M. Martínez, Global minimization using an Augmented Lagrangian method with variable lower-level constraints, Math. Program. 125 (2010), pp. 139–162. doi: 10.1007/s10107-009-0264-y
   Web of Science ®Google Scholar
• E.G. Birgin and J.M. Martínez, Large-scale active-set box-constrained optimization method with spectral projected gradients, Comput. Optim. Appl. 23 (2002), pp. 101–125. doi: 10.1023/A:1019928808826
   Web of Science ®Google Scholar
• E.G. Birgin and J.M. Martínez, Structured minimal-memory inexact quasi-Newton method and secant preconditioners for Augmented Lagrangian optimization, Comput. Optim. Appl. 39 (2008), pp. 1–16. doi: 10.1007/s10589-007-9050-z
   Web of Science ®Google Scholar
• E.G. Birgin and J.M. Martínez, Improving ultimate convergence of an Augmented Lagrangian method, Optim. Methods Softw. 23 (2008), pp. 177–195. doi: 10.1080/10556780701577730
   Web of Science ®Google Scholar
• E.G. Birgin and J.M. Martínez, Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization, Comput. Optim. Appl. 51 (2012), pp. 941–965. doi: 10.1007/s10589-011-9396-0
   Web of Science ®Google Scholar
• E.G. Birgin and J.M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, Fundamentals of Algorithms Vol. 10, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014. doi:10.1137/1.9781611973365.
   Google Scholar
• E.G. Birgin and J.M. Martínez, On regularization and active-set methods for constrained optimization, SIAM J. Optim. 28 (2018), pp. 1367–1395. doi: 10.1137/17M1127107
   Web of Science ®Google Scholar
• E.G. Birgin, J.M. Martínez, and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), pp. 1196–1211. doi: 10.1137/S1052623497330963
   Web of Science ®Google Scholar
• E.G. Birgin, J.M. Martínez, and M. Raydan, Algorithm 813: SPG – software for convex-constrained optimization, ACM Trans. Math. Softw. 27 (2001), pp. 340–349. doi: 10.1145/502800.502803
   Web of Science ®Google Scholar
• E.G. Birgin, J.M. Martínez, and M. Raydan, Spectral projected gradient methods: Review and perspectives, J. Stat. Softw. 60(3) (2014), pp. 1–21. doi:10.18637/jss.v060.i03.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and Ph.L. Toint, On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming, SIAM J. Optim. 21 (2011), pp. 1721–1739. doi: 10.1137/11082381X
   Web of Science ®Google Scholar
• N. Chatzipanagiotis and M.M. Zavlanos, On the convergence of a distributed Augmented Lagrangian method for nonconvex optimization, IEEE Trans. Automat. Contr. 62 (2017), pp. 4405–4420. doi: 10.1109/TAC.2017.2658438
   Web of Science ®Google Scholar
• A.R. Conn, N.I.M. Gould, A. Sartenaer, and Ph.L. Toint, Convergence properties of an Augmented Lagrangian algorithm for optimization with a combination of general equality and linear constraints, SIAM J. Optim. 6 (1996), pp. 674–703. doi: 10.1137/S1052623493251463
   Web of Science ®Google Scholar
• A.R. Conn, N.I.M. Gould, and Ph.L. Toint, Lancelot: A Fortran Package for Large ScaleNonlinear Optimization, Springer-Verlag, Berlin, 1992.
   Google Scholar
• A.R. Conn, N.I.M. Gould, and Ph.L. Toint, Trust Region Methods, Society for Industral and Applied Mathematics, Philadelphia, PA, 2000.
   Google Scholar
• F.E. Curtis, N.I.M. Gould, H. Jiang, and D.P. Robinson, Adaptive Augmented Lagrangian methods: Algorithms and practical numerical experience, Optim. Methods Softw. 31 (2016), pp. 157–186. doi: 10.1080/10556788.2015.1071813
   Web of Science ®Google Scholar
• F.E. Curtis, H. Jiang, and D.P. Robinson, An adaptive Augmented Lagrangian method for large-scale constrained optimization, Math. Program. 152 (2015), pp. 201–245. doi: 10.1007/s10107-014-0784-y
   Web of Science ®Google Scholar
• E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), pp. 201–213. doi: 10.1007/s101070100263
   Web of Science ®Google Scholar
• Z. Dostál, Optimal Quadratic Programming Algorithms, Optimizaton and its Applications Vol. 23, Springer, New York, 2009.
   Google Scholar
• Z. Dostál and P. Beremlijski, On convergence of inexact Augmented Lagrangians for separable and equality convex QCQP problems without constraint qualification, Adv. Electr. Electron. Eng. 15 (2017), pp. 215–222.
   Web of Science ®Google Scholar
• J. Eckstein and P.J.S. Silva, A practical relative error criterion for augmented Lagrangians, Math. Program. 141 (2013), pp. 319–348. doi: 10.1007/s10107-012-0528-9
   Web of Science ®Google Scholar
• D. Fernández and M.V. Solodov, Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition, SIAM J. Optim. 22 (2012), pp. 384–407. doi: 10.1137/10081085X
   Web of Science ®Google Scholar
• A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons, New York, 1968.
   Google Scholar
• R. Fletcher, Practical Methods of Optimization, Academic Press, London, 1987.
   Google Scholar
• R. Fletcher, Augmented Lagrangians, box constrained QP and extensions, IMA J. Numer. Anal. 37 (2017), pp. 1635–1656. doi: 10.1093/imanum/drx002
   Web of Science ®Google Scholar
• N.I.M. Gould, D. Orban, and Ph.L. Toint, CUTEst: A constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl. 60 (2014), pp. 545–557. doi: 10.1007/s10589-014-9687-3
   Web of Science ®Google Scholar
• G.N. Grapiglia and Y. Yuan, On the complexity of an Augmented Lagrangian method for nonconvex optimization, Available at arXiv:1906.05622v1.
   Google Scholar
• W.W. Hager and H. Zhang, A new active set algorithm for box constrained optimization, SIAM J. Optim. 17 (2006), pp. 526–557. doi: 10.1137/050635225
   Web of Science ®Google Scholar
• M.R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), pp. 303–320. doi: 10.1007/BF00927673
   Google Scholar
• M. Hong, Z.Q. Luo, and M. Razaviyayn, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim. 26 (2016), pp. 337–364. doi: 10.1137/140990309
   Web of Science ®Google Scholar
• HSL, A collection of fortran codes for large scale scientific computation. Available at http://www.hsl.rl.ac.uk/.
   Google Scholar
• A.F. Izmailov, M.V. Solodov, and E.I. Uskov, Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints, SIAM J. Optim. 22 (2012), pp. 1579–1606. doi: 10.1137/120868359
   Web of Science ®Google Scholar
• C. Kanzow and D. Steck, An example comparing the standard and safeguarded augmented Lagrangian methods, Oper. Res. Lett. 45 (2017), pp. 598–603. doi: 10.1016/j.orl.2017.09.005
   Web of Science ®Google Scholar
• J.M. Martínez and L. Qi, Inexact Newton methods for solving nonsmooth equation, J. Comput. Appl. Math. 60 (1995), pp. 127–145. doi: 10.1016/0377-0427(94)00088-I
   Web of Science ®Google Scholar
• M.J.D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, R. Fletcher, ed., Academic Press, New York, NY, 1969, pp. 283–298.
   Google Scholar
• L. Qi and J. Sun, A nonsmooth version of a Newton's method, Math. Program. 58 (1993), pp. 353–367. doi: 10.1007/BF01581275
   Web of Science ®Google Scholar
• R.T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Contr. Optim. 12 (1974), pp. 268–285. doi: 10.1137/0312021
   Web of Science ®Google Scholar
• R.T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976), pp. 97–116. doi: 10.1287/moor.1.2.97
   Google Scholar
• M.V. Solodov and B.F. Svaiter, A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Anal. 7 (1999), pp. 323–345. doi: 10.1023/A:1008777829180
   Google Scholar
• M.V. Solodov and B.F. Svaiter, A hybrid projection proximal point algorith, J. Convex Anal. 6 (1999), pp. 323–345.
   Web of Science ®Google Scholar
• M.V. Solodov and B.F. Svaiter, An inexact hybrid generalized extragradient-proximal point algorithm and some new results on the theory of Bregman functions, Math. Oper. Res. 25 (2000), pp. 214–230. doi: 10.1287/moor.25.2.214.12222
   Web of Science ®Google Scholar
• W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, Springer, Berlin, 2006.
   Google Scholar
• A. Wächter and L.T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program. 106 (2006), pp. 25–57. doi: 10.1007/s10107-004-0559-y
   Web of Science ®Google Scholar