Abstract
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 Yang and Yu (Comput Optim Appl 56(1):81–96, 2013) 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.
Similar content being viewed by others
References
Abraham, R., Robbin, J.: Transversal Mappings and Flows. W. A. Benjamin Inc, New York-Amsterdam (1967)
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)
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)
Allgower, E.L., Georg, K.: Numerical Path Following. North-Holland, Amsterdam (1997)
Allgower, E.L., Georg, K.: Introduction to Numerical Continuation Methods. Classics in Applied Mathematics, vol. 45. SIAM, Philadelphia, PA (2003)
Auslender, A.: Penalty and barrier methods: a unified framework. SIAM J. Optim. 10(1), 211–230 (1999)
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)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer Series in Operations Research. Springer, New York (2000)
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)
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)
Correa, R., Ramirez, C.H.: A global algorithm for nonlinear semidefinite programming. SIAM J. Optim. 15(1), 303–318 (2004)
de Klerk, E.: Aspects of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht (2002)
Fares, B., Noll, D., Apkarian, P.: Robust control via sequential semidefinite programming. SIAM J. Control Optim. 40(6), 1791–1820 (2002)
Forsgren, A.: Optimality conditions for nonconvex semidefinite programming. Math. Program. 88(1), 105–128 (2000)
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)
Gómez, W., Ramírez, H.: A filter algorithm for nonlinear semidefinite programming. Comput. Appl. Math. 29(2), 297–328 (2010)
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)
Jarre, F.: An interior method for nonconvex semidefinite programs. Optim. Eng. 1(4), 347–372 (2000)
Kanzow, C., Nagel, C., Kato, H., Fukushima, M.: Successive linearization methods for nonlinear semidefinite programs. Comput. Optim. Appl. 31(3), 251–273 (2005)
Kočvara, M., Stingl, M.: Pennon: a code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18(3), 317–333 (2003)
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)
Liqun Qi, P.T.: On almost smooth functions and piecewise smooth functions. Nonlinear Analysis: Theory, Methods & Applications 67(3), 773–794 (2007)
Liuzzi, G., Lucidi, S., Sciandrone, M.: A derivative-free algorithm for linearly constrained finite minimax problems. SIAM J. Optim. 16(4), 1054–1075 (2006)
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)
Noll, D.: Local convergence of an augmented Lagrangian method for matrix inequality constrained programming. Optim. Methods Softw. 22(5), 777–802 (2007)
Noll, D., Apkarian, P.: Spectral bundle methods for non-convex maximum eigenvalue functions: second-order methods. Math. Program. 104(2–3), 729–747 (2005)
Overton, M.L.: Large-scale optimization of eigenvalues. SIAM J. Optim. 2(1), 88–120 (1992)
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)
Shapiro, A.: First and second order analysis of nonlinear semidefinite programs. Math. Program. 77(2), 301–320 (1997)
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)
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)
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)
Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515–560 (2001)
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)
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)
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)
Xiao, Y., Yu, B.: A truncated aggregate smoothing Newton method for minimax problems. Appl. Math. Comput. 216(6), 1868–1879 (2010)
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)
Xu, S.: Smoothing method for minimax problems. Comput. Optim. Appl. 20(3), 267–279 (2001)
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)
Yamashita, H., Yabe, H., Harada, K.: A primal-dual interior point method for nonlinear semidefinite programming. Math. Program. 135, 89–121 (2012)
Yang, L., Yu, B.: A homotopy method for nonlinear semidefinite programming. Comput. Optim. Appl. 56(1), 81–96 (2013)
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)
Acknowledgments
The authors thank the anonymous referees, whose comments and suggestions led to an improved version of this article.
Author information
Authors and Affiliations
Corresponding author
Additional information
The work was supported by the National Natural Science Foundation of China (11301050, 11171051, 91230103, 71172136).
Appendix: The gradient and Hessian of \(g_\theta (x,\mu )\)
Appendix: The gradient and Hessian of \(g_\theta (x,\mu )\)
For the convenience of the reader, representations of the gradient and Hessian of \(g_\theta (x,\mu )\) will be derived below. From Theorem 2, we have that
where \(\varphi (\alpha )=\mathrm{exp}\,\alpha \), \(\alpha \in \mathbb {R}\). Consequently, the gradient and Hessian of \(g_\theta (x,\mu )\) about \(x\) and \(\mu \) are as follows:
where \(G_{ij}''(x)=\frac{\partial ^2 G(x)}{\partial x_ix_j}\).
Rights and permissions
About this article
Cite this article
Yang, L., Yu, B. & Li, Y. A homotopy method based on penalty function for nonlinear semidefinite programming. J Glob Optim 63, 61–76 (2015). https://doi.org/10.1007/s10898-015-0276-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-015-0276-5