zbMATH — the first resource for mathematics

A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms. (English) Zbl 1391.90636
Summary: We develop a new notion of second-order complementarity with respect to the tangent subspace related to second-order necessary optimality conditions by the introduction of so-called tangent multipliers. We prove that around a local minimizer, a second-order stationarity residual can be driven to zero while controlling the growth of Lagrange multipliers and tangent multipliers, which gives a new second-order optimality condition without constraint qualifications stronger than previous ones associated with global convergence of algorithms. We prove that second-order variants of augmented Lagrangian (under an additional smoothness assumption based on the Lojasiewicz inequality) and interior point methods generate sequences satisfying our optimality condition. We present also a companion minimal constraint qualification, weaker than the ones known for second-order methods, that ensures usual global convergence results to a classical second-order stationary point. Finally, our optimality condition naturally suggests a definition of second-order stationarity suitable for the computation of iteration complexity bounds and for the definition of stopping criteria.

90C46 Optimality conditions and duality in mathematical programming
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
[1] Anandkumar, A., Ge, R.: Efficient approaches for escaping higher order saddle points in non-convex optimization. arXiv:1602.05908v1 (2016) · Zbl 1433.90162
[2] Andreani, R; Birgin, EG; Martínez, JM; Schuverdt, ML, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 1286-1309, (2008) · Zbl 1151.49027
[3] Andreani, R; Birgin, EG; Martínez, JM; Schuverdt, ML, Second-order negative-curvature methods for box-constrained and general constrained optimization, Comput. Optim. Appl., 45, 209-236, (2010) · Zbl 1187.90265
[4] Andreani, R; Haeser, G; Martínez, JM, On sequencial optimality conditions for smooth constrained optimization, Optimization, 60, 627-641, (2011) · Zbl 1225.90123
[5] Andreani, R; Haeser, G; Ramos, A; Silva, P, A second-order sequential optimality condition associated to the convergence of algorithms, IMA J. Numer. Anal., 37, 1902-1929, (2017) · Zbl 1433.90155
[6] Andreani, R; Haeser, G; Schuverdt, ML; Silva, PJS, Two new weak constraint qualifications and applications, SIAM J. Optim., 22, 1109-1135, (2012) · Zbl 1302.90244
[7] Andreani, R; Martínez, JM; Ramos, A; Silva, PJS, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim., 26, 96-110, (2016) · Zbl 1329.90162
[8] Andreani, R; Martínez, JM; Ramos, A; Silva, PJS, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res., (2018)
[9] Andreani, R; Martínez, JM; Schuverdt, ML, On second-order optimality conditions for nonlinear programming, Optimization, 56, 529-542, (2007) · Zbl 1172.90490
[10] Andreani, R; Martínez, JM; Svaiter, BF, A new sequencial optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim., 20, 3533-3554, (2010) · Zbl 1217.90148
[11] Bertsekas, D.P.: Nonlinear Programming. Athenas Scientific, Belmont (1999) · Zbl 1015.90077
[12] Bian, W; Chen, X; Ye, Y, Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Math. Program., 149, 301-327, (2015) · Zbl 1318.90075
[13] Birgin, E., Martínez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization. SIAM Publications, Philadelphia (2014) · Zbl 1339.90312
[14] Birgin, EG; Gardenghi, JL; Martínez, JM; Santos, SA; Toint, PL, Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models, SIAM J. Optim., 26, 951-967, (2016) · Zbl 1335.90094
[15] Birgin, EG; Haeser, G; Ramos, A, Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points, Comput. Optim. Appl., 69, 51-75, (2018) · Zbl 1411.90316
[16] Bolte, J; Daniilidis, A; Lewis, AS, The lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 1205-1223, (2007) · Zbl 1129.26012
[17] Bonnans, J.F., Shapiro, A.: Pertubation Analysis of Optimization Problems. Springer, Berlin (2000) · Zbl 0966.49001
[18] Cartis, C., Gould, N.I.M., Toint, P.L.: Second-order optimality and beyond: characterization and evaluation complexity in convexly-constrained nonlinear optimization. Found. Comput. Math. (2017). https://doi.org/10.1007/s10208-017-9363-y · Zbl 06680644
[19] Chen, L; Goldfarb, D, Interior-point \(ℓ \)2-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108, 1-36, (2006) · Zbl 1142.90498
[20] Coleman, TF; Liu, J; Yuan, W, A new trust-region algorithm for equality constrained optimization, Comput. Optim. Appl., 21, 177-199, (2002) · Zbl 0988.90034
[21] Conn, A.R., Gould, N.I.M., Toint, P.L.: Lancelot: A Fortran Package for Large-Scale Nonlinear Optimization (Release A). Springer, Berlin (1992) · Zbl 0761.90087
[22] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000) · Zbl 0958.65071
[23] Dennis, JE; Vicente, LN, On the convergence theory of trust-region-based algorithms for equality-constrained optimization, SIAM J. Optim., 7, 927-950, (1997) · Zbl 0891.65073
[24] Facchinei, F; Lucidi, S, Convergence to second order stationary points in inequality constrained optimization, Math. Oper. Res., 23, 746-766, (1998) · Zbl 0977.90049
[25] Fiacco, A.V.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, New York (1968) · Zbl 0193.18805
[26] Gill, PE; Kungurtsev, V; Robinson, DP, A stabilized SQP method: global convergence, IMA J. Numer. Anal., 37, 407-443, (2016) · Zbl 1433.90162
[27] Gould, NIM; Conn, AR; Toint, PL, A note on the convergence of barrier algorithms for second-order necessary points, Math. Program., 85, 433-438, (1998) · Zbl 0643.65031
[28] Haeser, G, On the global convergence of interior-point nonlinear programming algorithms, Comput. Appl. Math., 29, 125-138, (2010) · Zbl 1202.90240
[29] Haeser, G, Some theoretical limitations of second-order algorithms for smooth constrained optimization, Oper. Res. Lett., 46, 295-299, (2018)
[30] Haeser, G., Liu, H., Ye, Y.: Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary. Optimization Online (2017). http://www.optimization-online.org/DB_HTML/2017/02/5861 · Zbl 1172.90490
[31] Haeser, G., Ramos, A.: A survey of constraint qualifications with second-order properties in nonlinear optimization. Optimization Online (2018). http://www.optimizationonline.org/DB_HTML/2018/01/6409.html
[32] Izmailov, AF; Kurennoy, AS; Solodov, MV, A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems, Math. Program., 142, 591-604, (2013) · Zbl 1282.90177
[33] Krantz, S.G., Parks, H.G.: A Primer on Real Analytic Functions. Birkhäuser, Basel (2002) · Zbl 1015.26030
[34] Liu, H; Yao, T; Li, R; Ye, Y, Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions, Math. Program., 166, 207-240, (2017) · Zbl 1386.90116
[35] Moguerza, JM; Prieto, FJ, An augmented Lagrangian interior-point method using directions of negative curvature, Math. Program., 95, 573-616, (2003) · Zbl 1041.90071
[36] Pillo, GD; Liuzzi, G; Lucidi, S, A primal-dual algorithm for nonlinear programming exploiting negative curvature directions, Numer. Algebra Control Optim., 1, 509-528, (2011) · Zbl 1241.90143
[37] Pillo, GD; Lucidi, S; Palagi, L, Convergence to second-order stationary points of a primal-dual algorithm model for nonlinear programming, Math. Oper. Res., 30, 897-915, (2005) · Zbl 1278.90375
[38] Tseng, P, Convergent infeasible interior-point trust-region methods for constrained minimization, SIAM J. Optim., 13, 432-469, (2002) · Zbl 1049.90128
[39] Ye, Y, On affine scaling algorithms for nonconvex quadratic programming, Math. Program., 56, 285-300, (1992) · Zbl 0767.90065
[40] Ye, Y, On the complexity of approximating a KKT point of quadratic programming, Math. Program., 80, 195-211, (1998) · Zbl 0894.90117
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.