×

zbMATH — the first resource for mathematics

A primal-dual interior point method for nonlinear semidefinite programming. (English) Zbl 1273.90150
The authors propose a primal-dual interior point method for solving nonlinear semidefinite programming problems. Two types of iterations are used: outer iterations for finding a KKT point and inner iterations for computing an approximate barrier KKT point. The inner method uses a commutative class of Newton-like directions for generating line search directions. Then a new primal-dual merit function is proposed combining the primal barrier penalty function with the primal-dual barrier function. The global convergence of the resulting method is proven and numerical experiments are displayed to show the practical efficiency of the method.

MSC:
90C22 Semidefinite programming
90C26 Nonconvex programming, global optimization
90C51 Interior-point methods
Software:
PENNON; SDPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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) · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[2] Borchers B.: SDPLIB 1.2, a library of semidefinite programming test problems. Optim. Methods Softw. 11 & 12, 683–690 (1999) · Zbl 0973.90522 · doi:10.1080/10556789908805769
[3] Boyd S., Vandenberghe L.: Convex Optimization. Cambridge University Press, Cambridge (2004) · Zbl 1058.90049
[4] Correa R., Ramirez C.H.: A global algorithm for nonlinear semidefinite programming. SIAM J. Optim. 15, 303–318 (2004) · Zbl 1106.90057 · doi:10.1137/S1052623402417298
[5] 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) · Zbl 1015.93016 · doi:10.1080/00207170010010605
[6] Fares B., Noll D., Apkarian P.: Robust control via sequential semidefinite programming. SIAM J. Control Optim. 40, 1791–1820 (2002) · Zbl 1009.93022 · doi:10.1137/S0363012900373483
[7] 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) · Zbl 1147.90030 · doi:10.1007/s10107-006-0028-x
[8] Helmberg C., Rendl F., Vanderbei R.J., Wolkowicz H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6, 342–361 (1996) · Zbl 0853.65066 · doi:10.1137/0806020
[9] Jarre F.: An interior method for nonconvex semidefinite programs. Optim. Eng. 1, 347–372 (2000) · Zbl 1035.90055 · doi:10.1023/A:1011562523132
[10] Kanzow C., Nagel C., Kato H., Fukushima M.: Successive linearization methods for nonlinear semidefinite programs. Comput. Optim. Appl. 31, 251–273 (2005) · Zbl 1122.90058 · doi:10.1007/s10589-005-3231-4
[11] 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) · Zbl 0872.90098 · doi:10.1137/S1052623494269035
[12] Konno H., Kawadai N., Wu D.: Estimation of failure probability using semi-definite logit model. Comput. Manage. Sci. 1, 59–73 (2003) · Zbl 1114.62353
[13] Kocvara M., Stingl M.: PENNON: a code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18, 317–333 (2003) · Zbl 1037.90003 · doi:10.1080/1055678031000098773
[14] 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)
[15] Monteiro R.D.C.: Primal-dual path-following algorithms for semidefinite programming. SIAM J. Optim. 7, 663–678 (1997) · Zbl 0913.65051 · doi:10.1137/S1052623495293056
[16] Nesterov Y.E., Todd M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22, 1–42 (1997) · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[17] Nesterov Y.E., Todd M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324–364 (1998) · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[18] Qi H., Sun D.: A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28, 360–385 (2006) · Zbl 1120.65049 · doi:10.1137/050624509
[19] Stingl, M.: On the solution of nonlinear semidefinite programs by augmented Lagrangian methods, Doctoral Thesis. University of Erlangen (2005)
[20] Todd M.J.: Semidefinite optimization. Acta Numer. 10, 515–560 (2001) · Zbl 1105.65334
[21] 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) · Zbl 0913.90217 · doi:10.1137/S105262349630060X
[22] Tseng P.: Convergent infeasible interior-point trust-region methods for constrained minimization. SIAM J. Optim. 13, 432–469 (2002) · Zbl 1049.90128 · doi:10.1137/S1052623499357945
[23] Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[24] Vandenberghe L., Boyd S., Wu S.-P.: Determinant maximization with linear matrix inequality constraints. SIAM J. Matrix Anal. Appl. 19, 499–533 (1998) · Zbl 0959.90039 · doi:10.1137/S0895479896303430
[25] 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) · Zbl 0962.90001
[26] Yamashita H.: A globally convergent primal–dual interior point method for constrained optimization. Optim. Methods Softw. 10, 443–469 (1998) · Zbl 0946.90110 · doi:10.1080/10556789808805723
[27] Yamashita H., Yabe H.: A primal-dual interior point method for nonlinear semidefinite programming. Inst. Stat. Math. Cooper. Res. Report 203, 296–317 (2007)
[28] 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 · Zbl 1262.90126
[29] 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) · Zbl 1062.90036 · doi:10.1007/s10107-004-0508-9
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.