Yang, Li; Yu, Bo; Li, YanXi A homotopy method based on penalty function for nonlinear semidefinite programming. (English) Zbl 1353.90106 J. Glob. Optim. 63, No. 1, 61-76 (2015). Summary: This paper proposes a homotopy method based on a penalty function for solving nonlinear semidefinite programming problems. The penalty function is the composite function of an exponential penalty function, the eigenvalue function and a nonlinear operator mapping. Representations of its first and second order derivatives are given. Using the penalty function, a new homotopy is constructed. Global convergence of a smooth curve determined by the homotopy is proven under mild conditions. In the process of numerically tracing the curve, the method requires just the solution of a linear system of dimension \(n+2\), whereas a homotopy method proposed by L. Yang and B. Yu [Comput. Optim. Appl. 56, No. 1, 81–96 (2013; Zbl 1298.90067)] requires a system of dimension \(n+m(m+1)/2+1\) to be solved, where \(n\) is the number of variables while \(m\) is the order of constraint matrix. So, it is expected that the proposed method can improve the efficiency of the method proposed by Yang and Yu. Preliminary numerical experiments are presented and show that the considered algorithm is efficient for some nonlinear semidefinite programming problems. MSC: 90C22 Semidefinite programming 90C30 Nonlinear programming Keywords:homotopy method; global convergence; penalty function; nonlinear semidefinite programming Citations:Zbl 1298.90067 Software:PENNON; SeDuMi; SDPpack; SDPT3; PENBMI; SDMINMAX PDFBibTeX XMLCite \textit{L. Yang} et al., J. Glob. Optim. 63, No. 1, 61--76 (2015; Zbl 1353.90106) Full Text: DOI References: [1] Abraham, R., Robbin, J.: Transversal Mappings and Flows. W. A. Benjamin Inc, New York-Amsterdam (1967) · Zbl 0171.44404 [2] Alizadeh, F., Haeberly, J.P.A., Nayakkankuppam, M.V., Overton, M.L., Schmieta, S.: SDPPACK user’s guide. Tech. rep. Courant Institute of Mathematical Sciences, New York University, New York, NY (1997) · Zbl 1054.90087 [3] Alizadeh, F., Haeberly, J.P.A., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8(3), 746-768 (1998) · Zbl 0911.65047 [4] Allgower, E.L., Georg, K.: Numerical Path Following. North-Holland, Amsterdam (1997) [5] Allgower, E.L., Georg, K.: Introduction to Numerical Continuation Methods. Classics in Applied Mathematics, vol. 45. SIAM, Philadelphia, PA (2003) · Zbl 1036.65047 [6] Auslender, A.: Penalty and barrier methods: a unified framework. SIAM J. Optim. 10(1), 211-230 (1999) · Zbl 0953.90045 [7] Ben-Tal, A., Teboulle, M.: A smoothing technique for nondifferentiable optimization problems. In: Optimization (Varetz, 1988), Lecture Notes in Math., vol. 1405, pp. 1-11. Springer, Berlin (1989) · Zbl 0683.90078 [8] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer, New York (2000) · Zbl 0966.49001 [9] Chen, X., Qi, H., Qi, L., Teo, K.L.: Smooth convex approximation to the maximum eigenvalue function. J. Glob. Optim. 30(2), 253-270 (2004) · Zbl 1066.90081 [10] Chow, S.N., Mallet-Paret, J., Yorke, J.A.: Finding zeroes of maps: homotopy methods that are constructive with probability one. Math. Comput. 32(143), 887-899 (1978) · Zbl 0398.65029 [11] Correa, R., Ramirez, C.H.: A global algorithm for nonlinear semidefinite programming. SIAM J. Optim. 15(1), 303-318 (2004) · Zbl 1106.90057 [12] de Klerk, E.: Aspects of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 0991.90098 [13] Fares, B., Noll, D., Apkarian, P.: Robust control via sequential semidefinite programming. SIAM J. Control Optim. 40(6), 1791-1820 (2002) · Zbl 1009.93022 [14] Forsgren, A.: Optimality conditions for nonconvex semidefinite programming. Math. Program. 88(1), 105-128 (2000) · Zbl 0988.90046 [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), 581-611 (2007) · Zbl 1147.90030 [16] Gómez, W., Ramírez, H.: A filter algorithm for nonlinear semidefinite programming. Comput. Appl. Math. 29(2), 297-328 (2010) · Zbl 1247.90248 [17] Henrion, D., Löfberg, J., Kočvara, M., Stingl, M.: Solving polynomial static output feedback problems with PENBMI. In: In IEEE (ed.) Proceedings of the 44th IEEE Conference on Decision and Control, Sevilla, Spain, vol. 1, pp. 7581-7586 (2005) · Zbl 1124.90035 [18] Jarre, F.: An interior method for nonconvex semidefinite programs. Optim. Eng. 1(4), 347-372 (2000) · Zbl 1035.90055 [19] Kanzow, C., Nagel, C., Kato, H., Fukushima, M.: Successive linearization methods for nonlinear semidefinite programs. Comput. Optim. Appl. 31(3), 251-273 (2005) · Zbl 1122.90058 [20] Kočvara, M., Stingl, M.: Pennon: a code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18(3), 317-333 (2003) · Zbl 1037.90003 [21] Leibfritz, F., Mostafa, E.M.E.: An interior point constrained trust region method for a special class of nonlinear semidefinite programming problems. SIAM J. Optim. 12(4), 1048-1074 (2002) · Zbl 1035.90102 [22] Liqun Qi, P.T.: On almost smooth functions and piecewise smooth functions. Nonlinear Analysis: Theory, Methods & Applications 67(3), 773-794 (2007) · Zbl 1125.26019 [23] Liuzzi, G., Lucidi, S., Sciandrone, M.: A derivative-free algorithm for linearly constrained finite minimax problems. SIAM J. Optim. 16(4), 1054-1075 (2006) · Zbl 1131.90074 [24] Luo, H., Wu, H., Chen, G.: On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming. J. Glob. Optim. 54(3), 599-618 (2012) · Zbl 1261.90035 [25] Noll, D.: Local convergence of an augmented Lagrangian method for matrix inequality constrained programming. Optim. Methods Softw. 22(5), 777-802 (2007) · Zbl 1188.90254 [26] Noll, D., Apkarian, P.: Spectral bundle methods for non-convex maximum eigenvalue functions: second-order methods. Math. Program. 104(2-3), 729-747 (2005) · Zbl 1124.90035 [27] Overton, M.L.: Large-scale optimization of eigenvalues. SIAM J. Optim. 2(1), 88-120 (1992) · Zbl 0757.65072 [28] Overton, M.L., Womersley, R.S.: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices. Math. Program. 62(2, Ser. B), 321-357 (1993) · Zbl 0806.90114 [29] Shapiro, A.: First and second order analysis of nonlinear semidefinite programs. Math. Program. 77(2), 301-320 (1997) · Zbl 0888.90127 [30] Stingl, M.: On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods. Ph.D. thesis, Institute of Applied Mathematics II. Friedrich-Alexander University of Erlangen-Nuremberg (2006) · Zbl 1066.90081 [31] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1-4), 625-653 (1999) · Zbl 0973.90526 [32] 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 [33] Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515-560 (2001) · Zbl 1105.65334 [34] Tütüncü, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95(2), 189-217 (2003) · Zbl 1030.90082 [35] Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. International Series in Operations Research & Management Science, 27. Kluwer Academic Publishers, Boston, MA (2000) [36] Wu, H., Luo, H., Ding, X., Chen, G.: Global convergence of modified augmented lagrangian methods for nonlinear semidefinite programming. Comput. Optim. Appl. 56(3), 531-558 (2013) · Zbl 1311.90096 [37] Xiao, Y., Yu, B.: A truncated aggregate smoothing Newton method for minimax problems. Appl. Math. Comput. 216(6), 1868-1879 (2010) · Zbl 1194.65083 [38] Xiong, Hj, Yu, B.: An aggregate deformation homotopy method for min-max-min problems with max-min constraints. Comput. Optim. Appl. 47(3), 501-527 (2010) · Zbl 1208.90180 [39] Xu, S.: Smoothing method for minimax problems. Comput. Optim. Appl. 20(3), 267-279 (2001) · Zbl 1054.90087 [40] Yamashita, H., Yabe, H.: Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming. Math. Program. 132, 1-30 (2012) · Zbl 1262.90126 [41] Yamashita, H., Yabe, H., Harada, K.: A primal-dual interior point method for nonlinear semidefinite programming. Math. Program. 135, 89-121 (2012) · Zbl 1273.90150 [42] Yang, L., Yu, B.: A homotopy method for nonlinear semidefinite programming. Comput. Optim. Appl. 56(1), 81-96 (2013) · Zbl 1298.90067 [43] Zhao, X.Y., Sun, D., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737-1765 (2010) · Zbl 1213.90175 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.