×

A globally convergent filter-type trust region method for semidefinite programming. (English) Zbl 1264.90169

Summary: When using interior methods for solving semidefinite programming (SDP), one needs to solve a system of linear equations at each iteration. For problems of large size, solving the system of linear equations can be very expensive. In this paper, based on a semismooth equation reformulation using Fischer’s function, we propose a filter method with trust region for solving large-scale SDP problems. At each iteration we perform a number of conjugate gradient iterations, but do not need to solve a system of linear equations. Under mild assumptions, the convergence of this algorithm is established. Numerical examples are given to illustrate the convergence results obtained.

MSC:

90C34 Semi-infinite programming

Software:

PENSDP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, vol. 15 of SIAM Studies in Applied Mathematics, SIAM, Philadelphia, Pa, USA, 1994. · Zbl 1153.91783 · doi:10.1007/BF00868008
[2] M. X. Goemans, “Semidefinite programming in combinatorial optimization,” Mathematical Programming, vol. 79, no. 1-3, pp. 143-161, 1997. · Zbl 0887.90139 · doi:10.1007/BF02614315
[3] H. Wolkowicz, R. Saigal, and L. Vandenberghe, Handbook of Semidefinite Programming, Kluwer Acadamic Publishers, Dordrecht, The Netherlands, 2000. · Zbl 0962.90001
[4] Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathrmatics, SIAM, Philadelphia, Pa, USA, 1994. · Zbl 0824.90112
[5] F. Alizadeh, J. Pierre, A. Haeberly, and M. L. Overton, “A new primal-dual interiorpoint method for semidefinite programming,” in Proceedings of the 5th SIAM Conference on Applied Linear Algebra, pp. 113-117, SIAM, Philadelphia, Pa, USA, 1994. · Zbl 0819.65098
[6] R. D. C. Monteiro, “Primal-dual path-following algorithms for semidefinite programming,” SIAM Journal on Optimization, vol. 7, no. 3, pp. 663-678, 1997. · Zbl 0913.65051 · doi:10.1137/S1052623495293056
[7] C. Helmberg, F. Rendl, R. J. Vanderbei, and H. Wolkowicz, “An interior-point method for semidefinite programming,” SIAM Journal on Optimization, vol. 6, no. 2, pp. 342-361, 1996. · Zbl 0853.65066 · doi:10.1137/0806020
[8] X.-Y. Zhao, D. Sun, and K.-C. Toh, “A Newton-CG augmented Lagrangian method for semidefinite programming,” SIAM Journal on Optimization, vol. 20, no. 4, pp. 1737-1765, 2010. · Zbl 1213.90175 · doi:10.1137/080718206
[9] K.-C. Toh, “Solving large scale semidefinite programs via an iterative solver on the augmented systems,” SIAM Journal on Optimization, vol. 14, no. 3, pp. 670-698, 2004. · Zbl 1071.90026 · doi:10.1137/S1052623402419819
[10] F. Jarre and F. Rendl, “An augmented primal-dual method for linear conic programs,” SIAM Journal on Optimization, vol. 19, no. 2, pp. 808-823, 2008. · Zbl 1173.90497 · doi:10.1137/070687128
[11] C. Kanzow and C. Nagel, “Semidefinite programs: new search directions, smoothing-type methods, and numerical results,” SIAM Journal on Optimization, vol. 13, no. 1, pp. 1-23, 2002. · Zbl 1029.90052 · doi:10.1137/S1052623401390525
[12] M. Ko\vcvara and M. Stingl, “On the solution of large-scale SDP problems by the modified barrier method using iterative solvers,” Mathematical Programming, vol. 109, no. 2-3, pp. 413-444, 2007. · Zbl 1177.90312 · doi:10.1007/s10107-006-0029-9
[13] J. Malick, J. Povh, F. Rendl, and A. Wiegele, “Regularization methods for semidefinite programming,” SIAM Journal on Optimization, vol. 20, no. 1, pp. 336-356, 2009. · Zbl 1187.90219 · doi:10.1137/070704575
[14] K.-C. Toh and M. Kojima, “Solving some large scale semidefinite programs via the conjugate residual method,” SIAM Journal on Optimization, vol. 12, no. 3, pp. 669-691, 2002. · Zbl 1008.90043 · doi:10.1137/S1052623400376378
[15] F. Leibfritz and E. M. E. Mostafa, “An interior point constrained trust region method for a special class of nonlinear semidefinite programming problems,” SIAM Journal on Optimization, vol. 12, no. 4, pp. 1048-1074, 2002. · Zbl 1035.90102 · doi:10.1137/S1052623400375865
[16] N. I. M. Gould, S. Leyffer, and P. L. Toint, “A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares,” SIAM Journal on Optimization, vol. 15, no. 1, pp. 17-38, 2004. · Zbl 1075.65075 · doi:10.1137/S1052623403422637
[17] C. Helmberg, Semidefinite Programming For Combinatorial Optimization, Konard-Zuse-Zent rum für informationstechnik, Berlin, Germany, 2000. · Zbl 0960.65074
[18] A. Fischer, “A special Newton-type optimization method,” Optimization, vol. 24, no. 3-4, pp. 269-284, 1992. · Zbl 0814.65063 · doi:10.1080/02331939208843795
[19] A. Fischer, “A Newton-type method for positive-semidefinite linear complementarity problems,” Journal of Optimization Theory and Applications, vol. 86, no. 3, pp. 585-608, 1995. · Zbl 0839.90121 · doi:10.1007/BF02192160
[20] P. Tseng, “Merit functions for semi-definite complementarity problems,” Mathematical Programming, vol. 83, no. 2, pp. 159-185, 1998. · Zbl 0920.90135 · doi:10.1016/S0025-5610(98)00004-5
[21] X. Chen and P. Tseng, “Non-interior continuation methods for solving semidefinite complementarity problems,” Mathematical Programming, vol. 95, no. 3, pp. 431-474, 2003. · Zbl 1023.90046 · doi:10.1007/s10107-002-0306-1
[22] D. Sun and J. Sun, “Semismooth matrix-valued functions,” Mathematics of Operations Research, vol. 27, no. 1, pp. 150-169, 2002. · Zbl 1082.49501 · doi:10.1287/moor.27.1.150.342
[23] H. Jiang, M. Fukushima, L. Qi, and D. Sun, “A trust region method for solving generalized complementarity problems,” SIAM Journal on Optimization, vol. 8, no. 1, pp. 140-157, 1998. · Zbl 0911.90324 · doi:10.1137/S1052623495296541
[24] W. Sun and Y. Yuan, Optimization Theory and Methods, Nonlinear Programming, Springer, New York, NY, USA, 2006. · Zbl 1129.90002
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.