An inexact primal-dual path following algorithm for convex quadratic SDP. (English) Zbl 1136.90027
This is a follow-up to the paper [K. C. Toh, R. H. Tütüncü, M. J. Todd, Pac. J. Optim. 3, No. 1, 135-164 (2007; Zbl 1136.90026)] where the authors described interior-point algorithms for solving convex quadratic semidefinite programming (QSDP) problems, under a definiteness assumption on the quadratic objective function. In the paper under review, the author allows the objective function to be positive semidefinite (instead of positive definite), therefore covering problems such as the nearest Euclidean distance matrix problem. Under the assumption that the linear map appearing in the constraints is sparse or structured, the author focuses on preconditioning techniques applied to the large-scale linear system to be solved at each iteration of the interior-point algorithm. The study is illustrated with an extensive set of numerical experiments.
Reviewer: Didier Henrion (Toulouse)
MSC:
| 90C22 | Semidefinite programming |
| 90C51 | Interior-point methods |
| 65K10 | Numerical optimization and variational techniques |
Citations:
Zbl 1136.90026References:
| [1] | Alfakih A.Y., Khandani A. and Wolkowicz H. (1999). Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12: 13–30 · Zbl 1040.90537 · doi:10.1023/A:1008655427845 |
| [2] | Alizadeh F., Haeberly J.-P.A. and Overton M.L. (1997). Complementarity and nondegeneracy in semidefinite programming.. Math. Program. 77: 111–128 · Zbl 0890.90141 |
| [3] | Alizadeh F., Haeberly J.-P.A. and Overton M.L. (1998). Primal–dual interior-point methods for semidefinite programming: convergence results, stability and numerical results. SIAM J. Optim. 8: 746–768 · Zbl 0911.65047 · doi:10.1137/S1052623496304700 |
| [4] | Anjos, M.F., Higham, N.J., Takouda, P.L., Wolkowicz, H.: A semidefinite programming approach for the nearest correlation matrix problem. Research Report, Department of Combinatorics and Optimization, University of Waterloo (2003) |
| [5] | Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 1–137 (2005) · Zbl 1115.65034 |
| [6] | Benzi M. and Simoncini V. (2006). On the eigenvalues of a class of saddle point matrices. Numer. Math. 103: 173–196 · Zbl 1103.65033 · doi:10.1007/s00211-006-0679-9 |
| [7] | Bergamaschi L., Gondzio J. and Zilli G. (2004). Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28: 149–171 · Zbl 1056.90137 · doi:10.1023/B:COAP.0000026882.34332.1b |
| [8] | Berman H.M., Westbrook J., Feng Z., Gilliland G., Bhat T.N., Weissig H., Shindyalov I.N. and Bourne P.E. (2000). The protein data bank. Nucl. Acids Res. 28: 235–242 · doi:10.1093/nar/28.1.235 |
| [9] | Bhatia R. and Kittaneh F. (1990). Norm inequalities for partitioned operators and an application. Math. Ann. 287: 719–726 · Zbl 0688.47005 · doi:10.1007/BF01446925 |
| [10] | Burer S., Monteiro R.D.C. and Zhang Y. (2002). Solving a class of semidefinite programs via nonlinear programming. Math. Program. 93: 97–122 · Zbl 1007.90045 · doi:10.1007/s101070100279 |
| [11] | Freund, R.W., Nachtigal, N.M.: A new Krylov-subspace method for symmetric indefinite linear systems. In: Ames W.F. (ed.) Proceedings of the 14th IMACS World Congress on Computational and Applied Mathematics, Atlanta, USA, pp. 1253–1256 (1994) |
| [12] | Fujisawa K., Kojima M. and Nakata K. (1997). Exploiting sparsity in primal-dual interior-point method for semidefinite programming. Math. Program. 79: 235–253 · Zbl 0887.90156 |
| [13] | Halicka M., Roos C. and Klerk E. (2005). Limiting behaviour of the central path in semidefinite optimization. Optim. Methods Softw. 20: 99–113 · Zbl 1087.90057 · doi:10.1080/10556780410001727718 |
| [14] | Higham N.J. (2002). Computing the nearest correlation matrix–a problem from finance. IMA J. Numer. Anal. 22: 329–343 · Zbl 1006.65036 · doi:10.1093/imanum/22.3.329 |
| [15] | Horn, R., Johnson, C. Matrix Analysis. Cambridge University Press, Cambridge (1998) |
| [16] | Keller C., Gould N.I.M. and Wathen A.J. (2000). Constraint preconditioning for indefinite linear systems. Matrix Anal. Appl. 21: 1300–1317 · Zbl 0960.65052 · doi:10.1137/S0895479899351805 |
| [17] | Kojima M., Shindoh S. and Hara S. (1997). Interior-point methods for the monotone linear complementarity problem in symmetric matrices. SIAM J. Optim. 7: 86–125 · Zbl 0872.90098 · doi:10.1137/S1052623494269035 |
| [18] | Krislock N., Lang J., Varah J., Pai D.K. and Seidel H.-P. (2004). Local compliance estimation via positive semidefinite constrained least sqaures. IEEE Trans. Robot. 20: 1007–1011 · doi:10.1109/TRO.2004.832794 |
| [19] | Langville A.N. and Stewart W.J. (2004). A Kronecker product approximate preconditioner for SANs. Numer. Linear Algebra Appl. 11: 723–752 · Zbl 1164.65396 · doi:10.1002/nla.344 |
| [20] | Luo Z.-Q., Sturm J.F. and Zhang S. (1998). Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming. SIAM J. Optim. 8: 59–81 · Zbl 0910.90229 · doi:10.1137/S1052623496299187 |
| [21] | Malick J. (2004). A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26: 272–284 · Zbl 1080.65027 · doi:10.1137/S0895479802413856 |
| [22] | Monteiro R.D.C. and Zanjácomo P.R. (1999). Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants.. Optim. Methods Softw. 11(12): 91–140 · Zbl 0957.90105 · doi:10.1080/10556789908805749 |
| [23] | Nie J.W. and Yuan Y.X. (2001). A predictor-corrector algorithm for QSDP combining Dikin-type and Newton centering steps. Ann. Oper. Res. 103: 115–133 · Zbl 1169.90457 · doi:10.1023/A:1012994820412 |
| [24] | Phoon K.K., Toh K.C., Chan S.H. and Lee F.H. (2002). An efficient diagonal preconditioner for finite element solution of Biot’s consolidation equations. Int. J. Numer. Methods in Eng. 55: 377–400 · Zbl 1076.74558 · doi:10.1002/nme.500 |
| [25] | Qi H. and Sun D. (2006). A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28: 360–385 · Zbl 1120.65049 · doi:10.1137/050624509 |
| [26] | Saad Y. (1996). Iterative Methods for Sparse Linear Systems. PWS Publishing Company, Boston · Zbl 1031.65047 |
| [27] | Todd M.J., Toh K.C. and Tütüncü R.H. (1998). On the Nesterov-Todd direction in semidefinite programming.. SIAM J. Optim. 8: 769–796 · Zbl 0913.90217 · doi:10.1137/S105262349630060X |
| [28] | Toh K.C., Phoon K.K. and Chan S.H. (2004). Block preconditioners for symmetric indefinite linear systems. Int. J. Numer. Methods Eng. 60: 1361–1381 · Zbl 1065.65064 · doi:10.1002/nme.982 |
| [29] | Toh, K.C., Tütüncü, R.H., Todd, M.J.: Inexact primal–dual path-following algorithms for a special class of convex quadratic SDP and related problems. Pacific J. Optim. (in press) · Zbl 1136.90026 |
| [30] | Van Loan C.F. (2000). The ubiquitous Kronecker product. J. Comput. Appl. Math. 123: 85–100 · Zbl 0966.65039 · doi:10.1016/S0377-0427(00)00393-9 |
| [31] | Wathen, A.J., Fischer, B., Silvester, D.J.: The convergence of iterative solution methods for symmetric and indefinite linear systems. In: Griffiths, D.F., Watson, G.A., (eds.) Numerical Analysis 1997. Addison Wesley Longman, Harlow, pp. 230–243 (1997) · Zbl 0902.65012 |
| [32] | Zhou G.L. and Toh K.C. (2004). Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming. Math. Program. 99: 261–282 · Zbl 1098.90051 · doi:10.1007/s10107-003-0431-5 |
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.
