Optimality conditions and global convergence for nonlinear semidefinite programming. (English) Zbl 1434.90121
Summary: Sequential optimality conditions have played a major role in unifying and extending global convergence results for several classes of algorithms for general nonlinear optimization. In this paper, we extend theses concepts for nonlinear semidefinite programming. We define two sequential optimality conditions for nonlinear semidefinite programming. The first is a natural extension of the so-called Approximate-Karush-Kuhn-Tucker (AKKT), well known in nonlinear optimization. The second one, called Trace-AKKT, is more natural in the context of semidefinite programming as the computation of eigenvalues is avoided. We propose an augmented Lagrangian algorithm that generates these types of sequences and new constraint qualifications are proposed, weaker than previously considered ones, which are sufficient for the global convergence of the algorithm to a stationary point.
MSC:
| 90C22 | Semidefinite programming |
| 90C46 | Optimality conditions and duality in mathematical programming |
| 90C30 | Nonlinear programming |
Keywords:
nonlinear semidefinite programming; optimality conditions; constraint qualifications; practical algorithmsReferences:
| [1] | Andreani, R.; Birgin, Eg; Martínez, Jm; Schuverdt, Ml, On augmented Lagrangian methods with general lower-level constraint, SIAM J. Optim., 18, 4, 1286-1309 (2007) · Zbl 1151.49027 |
| [2] | Andreani, R.; Birgin, Eg; Martínez, Jm; Schuverdt, Ml, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., 111, 5-32 (2008) · Zbl 1163.90041 |
| [3] | Andreani, R., Fazzio, N.S., Schuverdt, M.L., Secchin, L.D.: A sequential optimality condition related to the quasinormality constraint qualification and its algorithmic consequences. Optimization online (2017). http://www.optimization-online.org/DB_HTML/2017/09/6194.html · Zbl 1451.90166 |
| [4] | Andreani, R.; Haeser, G.; Martínez, Jm, On sequential optimality conditions for smooth constrained optimization, Optimization, 60, 5, 627-641 (2011) · Zbl 1225.90123 |
| [5] | Andreani, R.; Haeser, G.; Ramos, A.; Silva, Pjs, A second-order sequential optimality condition associated to the convergence of algorithms, IMA J. Numer. Anal., 37, 4, 1902-1929 (2017) · Zbl 1433.90156 |
| [6] | Andreani, R.; Haeser, G.; Schuverdt, Ml; Silva, Pjs, Two new weak constraint qualifications and applications, SIAM J. Optim., 22, 3, 1109-1135 (2012) · Zbl 1302.90244 |
| [7] | Andreani, R.; Haeser, G.; Schuverdt, Ml; Silva, Pjs, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135, 1-2, 255-273 (2012) · Zbl 1262.90162 |
| [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 |
| [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 |
| [10] | Andreani, R.; Martínez, Jm; Svaiter, Bf, A new sequencial optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim., 20, 6, 3533-3554 (2010) · Zbl 1217.90148 |
| [11] | Andreani, R.; Martínez, Jm; Santos, Lt, Newton’s method may fail to recognize proximity to optimal points in constrained optimization, Math. Program., 160, 547-555 (2016) · Zbl 1356.90137 |
| [12] | 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 |
| [13] | Bazaraa, Ms; Sherali, Hd; Shetty, Cm, Practical Methods of Optimization: Theory and Algorithms (2006), NJ: Wiley, NJ |
| [14] | Birgin, E.; Martínez, Jm, Practical Augmented Lagrangian Methods for Constrained Optimization (2014), Philadelphia: SIAM, Philadelphia · Zbl 1339.90312 |
| [15] | Birgin, Eg; Gardenghi, Jl; Martínez, Jm; Santos, Sa; Toint, Phl, Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models, SIAM J. Optim., 26, 951-967 (2016) · Zbl 1335.90094 |
| [16] | Birgin, Eg; Haeser, G.; Ramos, A., Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points, Comput. Optim. Appl., 69, 1, 51-75 (2018) · Zbl 1411.90316 |
| [17] | Birgin, Eg; Krejic, N.; Martínez, Jm, On the minimization of possibly discontinuous functions by means of pointwise approximations, Optim. Lett., 11, 8, 1623-1637 (2017) · Zbl 1386.90142 |
| [18] | Bolte, J.; Daniilidis, A.; Lewis, As, The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 4, 1205-1223 (2007) · Zbl 1129.26012 |
| [19] | Bonnans, Jf; Shapiro, A., Perturbation Analysis of Optimization Problems (2000), New York: Springer, New York · Zbl 0966.49001 |
| [20] | Correa, R.; Ramírez, H., A global algorithm for nonlinear semidefinite programming, SIAM J. Optim., 15, 1, 303-318 (2004) · Zbl 1106.90057 |
| [21] | Dutta, J.; Deb, K.; Tulshyan, R.; Arora, R., Approximate KKT points and a proximity measure for termination, J. Glob. Optim., 56, 4, 1463-1499 (2013) · Zbl 1297.90150 |
| [22] | Fares, B.; Apkarian, P.; Noll, D., An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory, Int. J. Control, 74, 4, 348-360 (2001) · Zbl 1015.93016 |
| [23] | Fares, B.; Noll, D.; Apkarian, P., Robust control via sequential semidefinite programming, SIAM J. Control Optim., 40, 6, 1791-1820 (2002) · Zbl 1009.93022 |
| [24] | Fiacco, Av; Mccormick, Gp, Nonlinear Programming Sequential Unconstrained Minimization Techniques (1968), New York: Wiley, New York · Zbl 0193.18805 |
| [25] | Forsgren, A., Optimality conditions for nonconvex semidefinite programming, Math. Program., 88, 1, 105-128 (2000) · Zbl 0988.90046 |
| [26] | Freund, Rw; Jarre, F.; Vogelbusch, Ch, Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling, Math. Program., 109, 581-611 (2007) · Zbl 1147.90030 |
| [27] | Giorgi, G.; Jiménez, B.; Novo, V., Approximate Karush-Kuhn-Tucker condition in multiobjective optimization, J. Optim. Theory Appl., 171, 1, 70-89 (2016) · Zbl 1351.90144 |
| [28] | Gómez, W.; Ramírez, H., A filter algorithm for nonlinear semidefinite programming, Comput. Appl. Math., 29, 2, 297-328 (2010) · Zbl 1247.90248 |
| [29] | Haeser, G., A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms, Comput. Optim. Appl., 70, 2, 615-639 (2018) · Zbl 1391.90636 |
| [30] | Haeser, G.; Melo, Vv, Convergence detection for optimization algorithms: approximate-KKT stopping criterion when Lagrange multipliers are not available, Oper. Res. Lett., 43, 5, 484-488 (2015) · Zbl 1408.90281 |
| [31] | Haeser, G.; Schuverdt, Ml, On approximate KKT condition and its extension to continuous variational inequalities, J. Optim. Theory Appl., 149, 3, 528-539 (2011) · Zbl 1220.90130 |
| [32] | Horn, Ra; Johnson, Cr, Topics in Matrix Analysis (1991), Cambridge: Cambridge University Press, Cambridge · Zbl 0729.15001 |
| [33] | Huang, Xx; Teo, Kl; Yang, Xq, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Acta Math. Sin., 22, 5, 1283-1296 (2006) · Zbl 1126.90057 |
| [34] | Janin, R., Directional Derivative of the Marginal Function in Nonlinear Programming, 110-126 (1984), Berlin: Springer, Berlin · Zbl 0549.90082 |
| [35] | Jarre, F.: Elementary optimality conditions for nonlinear SDPs. In: Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science (2012) · Zbl 1334.90106 |
| [36] | Kočvara, M.; Stingl, M.; Di Pillo, G.; Murli, A., PENNON—a generalized augmented Lagrangian method for semidefinite programming, High Performance Algorithms and Software for Nonlinear Optimization, 297-315 (2003), Dordrecht: Kluwer, Dordrecht |
| [37] | Kočvara, M.; Stingl, M., On the solution of large-scale SDP problems by the modified barrier method using iterative solvers, Math. Program., 109, 413-444 (2007) · Zbl 1177.90312 |
| [38] | Kočvara, M.; Stingl, M., PENNON—a code for convex nonlinear and semidefinite programming, Optim. Methods Softw., 18, 3, 317-333 (2010) · Zbl 1037.90003 |
| [39] | Kanno, Y.; Takewaki, I., Sequential semidefinite program for maximum robustness design of structures under load uncertainty, J. Optim. Theory Appl., 130, 265-287 (2006) · Zbl 1278.90300 |
| [40] | Konno, H.; Kawadai, N.; Wu, D., Estimation of failure probability using semi-definite Logit model, Comput. Manag. Sci., 1, 1, 59-73 (2003) · Zbl 1114.62353 |
| [41] | Lewis, As, Convex analysis on the Hermitian matrices, SIAM J. Optim., 6, 1, 164-177 (1993) · Zbl 0849.15013 |
| [42] | Lourenço, Bf; Fukuda, Eh; Fukushima, M., Optimality conditions for nonlinear semidefinite programming via squared slack variables, Math. Program., 166, 1-24 (2016) |
| [43] | Lovász, L., Semidefinite Programs and Combinatorial Optimization, 137-194 (2003), New York: Springer, New York · Zbl 1040.90032 |
| [44] | Luo, Hz; Wu, Hx; Chen, Gt, On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming, J. Glob. Optim., 54, 3, 599-618 (2012) · Zbl 1261.90035 |
| [45] | Martínez, Jm; Pilotta, Ea, Inexact restoration algorithm for constrained optimization, J. Optim. Theory Appl., 104, 1, 135-163 (2000) · Zbl 0969.90094 |
| [46] | Martínez, Jm; Svaiter, Bf, A practical optimality condition without constraint qualifications for nonlinear programming, J. Optim. Theory Appl., 118, 1, 117-133 (2003) · Zbl 1033.90090 |
| [47] | Minchenko, L.; Stakhovski, S., On relaxed constant rank regularity condition in mathematical programming, Optimization, 60, 4, 429-440 (2011) · Zbl 1250.90093 |
| [48] | Qi, H.; Sun, D., A quadratically convergent newton method for computing the nearest correlation matrix, SIAM J. Matrix Anal. Appl., 28, 2, 360-385 (2006) · Zbl 1120.65049 |
| [49] | Qi, L.; Wei, Z., On the constant positive linear dependence conditions and its application to SQP methods, SIAM J. Optim., 10, 4, 963-981 (2000) · Zbl 0999.90037 |
| [50] | Ramos, A.: Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences. Optimization online (2016). http://www.optimization-online.org/DB_HTML/2016/04/5423.html · Zbl 1527.90250 |
| [51] | Shapiro, A., First and second order analysis of nonlinear semidefinite programs, SIAM J. Optim., 77, 1, 301-320 (1997) · Zbl 0888.90127 |
| [52] | Shapiro, A.; Sun, J., Some properties of the augmented Lagrangian in cone constrained optimization, Math. Oper. Res., 29, 479-491 (2004) · Zbl 1082.90109 |
| [53] | Stingl, M.: On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods. PhD thesis, University of Erlangen (2005) |
| [54] | Stingl, M.; Kočvara, M.; Leugering, G., A sequential convex semidefinite programming algorithm with an application to multiple-load free material optimization, SIAM J. Optim., 20, 1, 130-155 (2009) · Zbl 1239.74010 |
| [55] | Sun, D.; Sun, J.; Zhang, L., The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Math. Program., 114, 2, 349-391 (2008) · Zbl 1190.90117 |
| [56] | Sun, J.; Zhang, Lw; Wu, Y., Properties of the augmented Lagrangian in nonlinear semidefinite optimization, J. Optim. Theory Appl., 12, 3, 437-456 (2006) · Zbl 1278.90305 |
| [57] | Theobald, Cm, An inequality for the trace of the product of two symmetric matrices, Math. Proc. Camb. Philos. Soc., 77, 2, 265-267 (1975) · Zbl 0302.15021 |
| [58] | Todd, Mj, Semidefinite optimization, Acta Numer., 10, 515-560 (2003) · Zbl 1105.65334 |
| [59] | Tuyen, N.V., Yao, J., Wen, C.: A Note on Approximate Karush-Kuhn-Tucker Conditions in Locally Lipschitz Multiobjective Optimization. ArXiv:1711.08551 (2017) · Zbl 1434.90186 |
| [60] | Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 1, 549-95 (1996) · Zbl 0845.65023 |
| [61] | Vandenberghe, L.; Boyd, S.; Wu, Sp, Determinant maximization with linear matrix inequality constraints, SIAM J. Matrix Anal. Appl., 19, 2, 499-533 (1998) · Zbl 0959.90039 |
| [62] | Wu, H.; Luo, H.; Ding, X.; Chen, G., Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programmings, Comput. Optim. Appl., 56, 3, 531-558 (2013) · Zbl 1311.90096 |
| [63] | Yamashita, H.; Yabe, H., Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming, Math. Program., 132, 1-2, 1-30 (2012) · Zbl 1262.90126 |
| [64] | Yamashita, H.; Yabe, H., A survey of numerical methods for nonlinear semidefinite programming, J. Oper. Res. Soc. Jpn., 58, 1, 24-60 (2015) · Zbl 1367.65092 |
| [65] | Yamashita, H.; Yabe, H.; Harada, K., A primal-dual interior point method for nonlinear semidefinite programming, Math. Program., 135, 1-2, 89-121 (2012) · Zbl 1273.90150 |
| [66] | Zhu, Zb; Zhu, Hl, A filter method for nonlinear semidefinite programming with global convergence, Acta Math. Sin., 30, 10, 1810-1826 (2014) · Zbl 1327.90187 |
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.
