Abstract
This paper is concerned with a primal–dual interior point method for solving nonlinear semidefinite programming problems. The method consists of the outer iteration (SDPIP) that finds a KKT point and the inner iteration (SDPLS) that calculates an approximate barrier KKT point. Algorithm SDPLS uses a commutative class of Newton-like directions for the generation of line search directions. By combining the primal barrier penalty function and the primal–dual barrier function, a new primal–dual merit function is proposed. We prove the global convergence property of our method. Finally some numerical experiments are given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alizadeh F., Haeberly J.A., Overton M.L.: Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8, 746–768 (1998)
Borchers B.: SDPLIB 1.2, a library of semidefinite programming test problems. Optim. Methods Softw. 11 & 12, 683–690 (1999)
Boyd S., Vandenberghe L.: Convex Optimization. Cambridge University Press, Cambridge (2004)
Correa R., Ramirez C.H.: A global algorithm for nonlinear semidefinite programming. SIAM J. Optim. 15, 303–318 (2004)
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, 348–360 (2001)
Fares B., Noll D., Apkarian P.: Robust control via sequential semidefinite programming. SIAM J. Control Optim. 40, 1791–1820 (2002)
Freund R.W., Jarre F., Vogelbusch C.H.: Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling. Math. Program. 109, 581–611 (2007)
Helmberg C., Rendl F., Vanderbei R.J., Wolkowicz H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6, 342–361 (1996)
Jarre F.: An interior method for nonconvex semidefinite programs. Optim. Eng. 1, 347–372 (2000)
Kanzow C., Nagel C., Kato H., Fukushima M.: Successive linearization methods for nonlinear semidefinite programs. Comput. Optim. Appl. 31, 251–273 (2005)
Kojima M., Shindoh S., Hara S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86–125 (1997)
Konno H., Kawadai N., Wu D.: Estimation of failure probability using semi-definite logit model. Comput. Manage. Sci. 1, 59–73 (2003)
Kocvara M., Stingl M.: PENNON: a code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18, 317–333 (2003)
Leibfritz, F., Lipinski, W.: Description of the benchmark examples in COMPl e ib 1.0. Technical Report, Department of Mathematics, University of Trier, D-54286, Trier, Germany (2003)
Monteiro R.D.C.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7, 663–678 (1997)
Nesterov Y.E., Todd M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22, 1–42 (1997)
Nesterov Y.E., Todd M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324–364 (1998)
Qi H., Sun D.: A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28, 360–385 (2006)
Stingl, M.: On the solution of nonlinear semidefinite programs by augmented Lagrangian methods, Doctoral Thesis. University of Erlangen (2005)
Todd M.J.: Semidefinite optimization. Acta Numer. 10, 515–560 (2001)
Todd M.J., Toh K.C., Tütüncü R.H.: On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8, 769–796 (1998)
Tseng P.: Convergent infeasible interior-point trust-region methods for constrained minimization. SIAM J. Optim. 13, 432–469 (2002)
Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)
Vandenberghe L., Boyd S., Wu S.-P.: Determinant maximization with linear matrix inequality constraints. SIAM J. Matrix Anal. Appl. 19, 499–533 (1998)
Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds): Handbook of Semidefinite Programming: Theory, Algorithms and Applications, Kluwer International Series in Operations Research and Management Science. Kluwer, Boston (2000)
Yamashita H.: A globally convergent primal–dual interior point method for constrained optimization. Optim. Methods Softw. 10, 443–469 (1998)
Yamashita H., Yabe H.: A primal-dual interior point method for nonlinear semidefinite programming. Inst. Stat. Math. Cooper. Res. Report 203, 296–317 (2007)
Yamashita, H., Yabe, H.: Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming. Math. Program. (2011). doi:10.1007s10107-010-354-x
Yamashita H., Yabe H., Tanabe T.: A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization. Math. Program. 102, 111–151 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yamashita, H., Yabe, H. & Harada, K. A primal–dual interior point method for nonlinear semidefinite programming. Math. Program. 135, 89–121 (2012). https://doi.org/10.1007/s10107-011-0449-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0449-z
Keywords
- Nonlinear semidefinite programming
- Primal–dual interior point method
- Barrier penalty function
- Primal–dual merit function
- Global convergence