Sufficient optimality conditions hold for almost all nonlinear semidefinite programs. (English) Zbl 1358.90090
The authors obtain a new genericity result for nonlinear semidefinite programming (NLSDP). Namely, almost all linear perturbations of a given NLSDP are shown to be nondegenerate. The nondegeneracy for NLSDP refers to the transversality constraint qualification, strict complementarity and second-order sufficient condition. The derived result is a nontrivial extension of the corresponding results for linear semidefinite programs (SDP) from F. Alizadeh et al. [ibid. 77, No. 2 (B), 111–128 (1997; Zbl 0890.90141)] due to the presence of the second-order sufficient condition. The proof of the new result makes use of Forsgren’s derivation of optimality conditions for NLSDP in [A. Forsgren, ibid. 88, No. 1 (A), 105–128 (2000; Zbl 0988.90046)]. Due to the latter approach, the positive semidefiniteness of a symmetric matrix \(G(x)\), depending continuously on \(x\), is locally equivalent to the fact that a certain Schur complement \(S(x)\) of \(G(x)\) is positive semidefinite. This yields a reduced NLSDP by considering the new semidefinite constraint \(S(x)\geq 0\), instead of \(G(x)\geq 0\). While deriving optimality conditions for the reduced NLSDP, the well-known and often mentioned “H-term” in the second-order sufficient condition vanishes. This leads to the proof of the genericity result for NLSDP.
Reviewer: Paulo Mbunga (Kiel)
MSC:
| 90C22 | Semidefinite programming |
| 90C30 | Nonlinear programming |
| 57N75 | General position and transversality |
Keywords:
nonlinear semidefinite programming; transversality constraint qualification; strict complementarity; second-order sufficient condition; Schur complement; \(H\)-term; genericityReferences:
| [1] | Achtziger, W., Kočvara, M.: Structural topology optimization with eigenvalues. SIAM J. Optim. 18(4), 1129-1164 (2007) · Zbl 1149.74044 · doi:10.1137/060651446 |
| [2] | Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77(2, Ser. B), 111-128 (1997) · Zbl 0890.90141 |
| [3] | Allende, G.B., Still, G.: Solving bilevel programs with the KKT-approach. Math. Program. 138(1-2), 309-332 (2012) · Zbl 1280.90113 |
| [4] | Anand, C.K., Sotirov, R., Terlaky, T., Zheng, Z.: Magnetic resonance tissue quantification using optimal bssfp pulse-sequence design. Optim. Eng. 8(2), 215-238 (2007) · Zbl 1175.78032 · doi:10.1007/s11081-007-9009-z |
| [5] | Anjos, M.F., Lasserre, J.B. (eds.): Handbook on Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science, vol. 166. Springer, Berlin (2012) · Zbl 1235.90002 |
| [6] | Bolte, J., Daniilidis, A., Lewis, A.S.: Generic optimality conditions for semialgebraic convex programs. Math. Oper. Res. 36(1), 55-70 (2012) · Zbl 1218.90189 · doi:10.1287/moor.1110.0481 |
| [7] | Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2000) · Zbl 0966.49001 · doi:10.1007/978-1-4612-1394-9 |
| [8] | Boyd, S., Vandenberghe, L.: Semidefinite programming. SIAM Rev. 38(1), 49-95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003 |
| [9] | de Klerk, E.: Aspects of Semidefinite Programming. Interior Point Algorithms and Selected Applications. Applied Optimization, vol. 65. Kluwer, Dordrecht (2002) · Zbl 0991.90098 |
| [10] | de Klerk, E.: Exploiting special structure in semidefinite programming: a survey of theory and applications. Eur. J. Operat. Res. 201(1), 1-10 (2010) · Zbl 1177.90315 · doi:10.1016/j.ejor.2009.01.025 |
| [11] | Diehl, M., Jarre, F., Vogelbusch, C.H.: Loss of superlinear convergence for an SQP-type method with conic constraints. SIAM J. Optim. 16(4), 1201-1210 (2006) · Zbl 1131.90058 · doi:10.1137/050625977 |
| [12] | Dorsch, D.: Stratified Optimality Theory: A Tool for the Theoretical Justification of Assumptions in Finite-Dimensional Optimization. Berichte aus der Mathematik. Shaker Verlag, Aachen (2014) · Zbl 1296.90001 |
| [13] | Dorsch, D., Shikhman, V., Stein, O.: MPVC: Critical point theory. J. Glob. Optim. 52(3), 591-605 (2012) · Zbl 1254.90224 · doi:10.1007/s10898-011-9805-z |
| [14] | Forsgren, A.: Optimality conditions for nonconvex semidefinite programming. Math. Program. 88(1, Ser. A), 105-128 (2000) · Zbl 0988.90046 · doi:10.1007/PL00011370 |
| [15] | Freund, R.W., Jarre, F., Vogelbusch, C.H.: Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling. Math. Program. 109(2-3 B), 581-611 (2007) · Zbl 1147.90030 · doi:10.1007/s10107-006-0028-x |
| [16] | Haslinger, J., Kovčvara, M., Leugering, G., Stingl, M.: Multidisciplinary free material optimization. SIAM J. Appl. Math. 70(7), 2709-2728 (2010) · Zbl 1429.74079 · doi:10.1137/090774446 |
| [17] | Hirsch, M.W.: Differential topology. Springer, New York, (1976). Graduate Texts in Mathematics, No. 33 · Zbl 0356.57001 |
| [18] | Jargalsaikhan, B.: Linear conic programming: genericity and stability, University of Groningen, Groningen (2015) |
| [19] | Jarre, F.: Elementary optimality conditions for Nonlinear SDP. Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science 166(2), 455-470 (2012) · Zbl 1334.90106 · doi:10.1007/978-1-4614-0769-0_16 |
| [20] | Jongen, HTh, Jonker, P., Triesch, E.: Optimization Theory. Kluwer, Boston (2004) · Zbl 1059.90101 |
| [21] | Jongen, HTh, Jonker, P., Twilt, F.: Nonlinear Optimization in Finite Dimensions. Kluwer, Dordrecht (2000) · Zbl 0985.90083 |
| [22] | Jongen, HTh, Shikhman, V.: Bilevel optimization: on the structure of the feasible set. Math. Program. 136(1), 65-89 (2012) · Zbl 1286.90150 · doi:10.1007/s10107-012-0551-x |
| [23] | Kanno, Y., Takewaki, I.: Sequential semidefinite program for maximum robustness design of structures under load uncertainty. J. Optim. Theory Appl. 130(2), 265-287 (2006) · Zbl 1278.90300 · doi:10.1007/s10957-006-9102-z |
| [24] | Kočvara, M., Stingl, M.: Solving nonconvex SDP problems of structural optimization with stability control. Optim. Methods Softw. 19(5), 595-609 (2004) · Zbl 1135.49304 · doi:10.1080/10556780410001682844 |
| [25] | Kočvara, M., Stingl, M.: Free material optimization for stress constraints. Struct. Multidiscip. Optim. 33(4-5), 323-335 (2007) · Zbl 1245.74059 · doi:10.1007/s00158-007-0095-5 |
| [26] | Kočvara, M., Stingl, M.: Solving stress constrained problems in topology and material optimization. Struct. Multidiscip. Optim. 46(1), 1-15 (2012) · Zbl 1274.74355 · doi:10.1007/s00158-012-0762-z |
| [27] | Kočvara, M., Stingl, M., Zowe, J.: Free material optimization: recent progress. Optimization 57(1), 79-100 (2008) · Zbl 1132.74035 · doi:10.1080/02331930701778908 |
| [28] | Nemirovskii, A., Nesterov, Y.: Interior-point polynomial algorithms in convex programming. SIAM Stud. Appl. Math. 13, SIAM Philadelphia, (1994) · Zbl 0824.90112 |
| [29] | Robinson, S.M.: First order conditions for general nonlinear optimization. SIAM J. Appl. Math. 30(4), 597-607 (1976) · Zbl 0364.90093 · doi:10.1137/0130053 |
| [30] | Shapiro, A.: First and second order analysis of nonlinear semidefinite programs. Math. Program. 77(2, Ser. B), 301-320 (1997) · Zbl 0888.90127 |
| [31] | Stingl, M., Kočvara, M., Leugering, G.: Free material optimization with fundamental eigenfrequency constraints. SIAM J. Optim. 20(1), 525-547 (2009) · Zbl 1239.74011 |
| [32] | 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 · doi:10.1137/070711281 |
| [33] | Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515-560 (2001) · Zbl 1105.65334 · doi:10.1017/S0962492901000071 |
| [34] | Wolkowitz, H., Saigal, R., Vandenberghe, L. (eds). Handbook of Semidefinite Programming: Theory, Algorithms and Applications. Kluwer’s International Series in Operations Research and Management Science. Kluwer Academic Publishers, Boston, MA (2000) · Zbl 1239.74011 |
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.
