Worst-case evaluation complexity of a quadratic penalty method for nonconvex optimization

References

• E.G. Birgin, J.L. Gardenghi, J.M. Martínez, S.A. Santos, and Ph.L. Toint, Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models, SIAM. J. Optim. 26(2) (2016), pp. 951–967.
   Web of Science ®Google Scholar
• E.G. Birgin and J.M. Martínez, On the regularization and active-set methods with complexity for constrained optimization, SIAM. J. Optim. 28(2) (2018), pp. 1367–1395.
   Web of Science ®Google Scholar
• L.F. Bueno and J.M. Martínez, On the Complexity of An Inexact Restoration Method for Constrained Optimization, Optimization Online, 2018.
   Google Scholar
• T. Butler and A.V. Martin, On a method of courant for minimizing functionals, J. Math. Phys. 41(1–4) (1962), pp. 291–299.
   Google Scholar
• G.D. Camp, Inequality-constrained stationary value problems, J. Oper. Res. Soc. Am. 3 (1955), pp. 548–550.
   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(4) (2011), pp. 1721–1739.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and Ph.L. Toint, An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity, IMA J. Numer. Anal.32(4) (2012), pp. 1662–1695.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and Ph.L. Toint, On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization, SIAM. J. Optim. 23(3) (2013), pp. 1553–1574.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and Ph.L. Toint, On the complexity of finding first-order critical points in constrained nonlinear optimization, Math. Program. 144(1–2) (2014), pp. 93–106.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and Ph.L. Toint, Corrigendum: on the complexity of finding first-order critical points in constrained nonlinear optimization, Math. Program. 161(1–2) (2017), pp. 611–626.
   Web of Science ®Google Scholar
• C. Cartis, N.I.M. Gould, and Ph.L. Toint, Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order methods, in Approximation and Optimization, C. Demetriou and P.M. Pardalos, eds., 1st ed., Springer Optimization and Its Application, Vol. 145, Springer, 2019, pp. 5–26.
   Google Scholar
• R. Courant, Variational methods for the solution of problems of equilibrium and vibrations, Bulletin Ame. Math. Soc. 49(1) (1943), pp. 1–23.
   Google Scholar
• F.E. Curtis, D.P. Robinson, and M. Samadi, Complexity analysis of a trust funnel algorithm for equality constrained optimization, SIAM. J. Optim. 28(2) (2018), pp. 1533–1563.
   Web of Science ®Google Scholar
• F. Facchinei, V. Kungurtsev, L. Lampariello, and G. Scutari, Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity, Math Oper. Res. 46(2) (2021), pp. 595–627.
   Web of Science ®Google Scholar
• F. Facchinei, V. Kungurtsev, L. Lampariello, and G. Scutari, Iteration complexity of a fixed-stepsize SQP method for nonconvex optimization with convex constraints, in Numerical Analysis and Optimization, M. Al-Baali, A. Purnama, and L. Grandinetti, eds., NAO 2020. Springer Proceedings in Mathematics & Statistics, Vol. 354, Springer, Cham, 2021.
   Google Scholar
• A.V. Fiacco and G.P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968.
   Google Scholar
• G.N. Grapiglia and Yu. Nesterov, Tensor methods for finding approximate stationary points of convex functions, Optimization Methods and Software 37(2) (2020), pp. 605–638.
   Web of Science ®Google Scholar
• G.N. Grapiglia and E.W. Sachs, On the worst-case evaluation complexity of non-monotone line search algorithms, Comput. Optim. Appl. 68(3) (2017), pp. 555–577.
   Web of Science ®Google Scholar
• G.N. Grapiglia and Y. Yuan, On the complexity of an augmented Lagrangian method for nonconvex optimization, IMA J. Numer. Anal. 41(2) (2021), pp. 1546–1568.
   Web of Science ®Google Scholar
• G. Haeser, H. Liu, and Y. Ye, Optimality condition and complexity analysis for linearly constrained optimization without differentiability on the boundary, Math. Program. 178 (2019), pp. 263–299.
   Web of Science ®Google Scholar
• W. Kong, J.G. Melo, and R.D.C. Monteiro, Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs, SIAM. J. Optim. 29(4) (2019), pp. 2566–2593.
   Web of Science ®Google Scholar
• Z. Li, P-Y. Chen, S. Liu, S. Lu, and Y. Xu, Rate-improved inexact augmented Lagrangian method for constrained nonconvex optimization, in Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR; 130, 2021, pp. 2170–2178.
   Google Scholar
• Z. Li and Y. Xu, Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective, (2020). Available at arXiv: 2003.08880 [math.OC].
   Google Scholar
• Q. Lin, R. Ma, and Y. Xu, Inexact proximal-point methods for constrained nonconvex optimization, (2020). Available at arXiv: 1908.11518v4 [math.OC].
   Google Scholar
• J.M. Martínez, On high-order model regularization for constrained optimization, SIAM J. Optim.27(4) (2017), pp. 2447–2458.
   Web of Science ®Google Scholar
• J.G. Melo, R.D.C. Monteiro, and H. Wang, Iteration-complexity of an inexact proximal point accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite problems, (2020). Available at arXiv: 2006.08048 [math.OC].
   Google Scholar
• J. Nocedal and S.J. Wright, Numerical Optimization, Springer, Berlin, 1999.
   Google Scholar
• Y. Xie and S.J. Wright, Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints, J. Sci. Comput. 86(1) (2021), pp. 1–30.
   Google Scholar
• W.I Zangwill, Non-linear programming via penalty functions, Manage. Sci. 13(5) (1967), pp. 344–358.
   Google Scholar