×

zbMATH — the first resource for mathematics

An inexact dual logarithmic barrier method for solving sparse semidefinite programs. (English) Zbl 1431.90108
Summary: A dual logarithmic barrier method for solving large, sparse semidefinite programs is proposed in this paper. The method avoids any explicit use of the primal variable \(X\) and therefore is well-suited to problems with a sparse dual matrix \(S\). It relies on inexact Newton steps in dual space which are computed by the conjugate gradient method applied to the Schur complement of the reduced KKT system. The method may take advantage of low-rank representations of matrices \(A_i\) to perform implicit matrix-vector products with the Schur complement matrix and to compute only specific parts of this matrix. This allows the construction of the partial Cholesky factorization of the Schur complement matrix which serves as a good preconditioner for it and permits the method to be run in a matrix-free scheme. Convergence properties of the method are studied and a polynomial complexity result is extended to the case when inexact Newton steps are employed. A Matlab-based implementation is developed and preliminary computational results of applying the method to maximum cut and matrix completion problems are reported.
MSC:
90C22 Semidefinite programming
90C51 Interior-point methods
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bellavia, S.; Gondzio, J.; Morini, B., A matrix-free preconditioner for sparse symmetric positive definite systems and least-squares problems, SIAM J. Sci. Comput., 35, a192-a211, (2013) · Zbl 1264.65036
[2] Benson, Steven J.; Ye, Yinyu, Algorithm 875, ACM Transactions on Mathematical Software, 34, 1-20, (2008) · Zbl 1291.65173
[3] Benson, SJ; Ye, Y.; Zhang, X., Mixed linear and semidefinite programming for combinatorial and quadratic optimization, Optim. Methods Softw., 11, 515-544, (1999) · Zbl 0973.90055
[4] Benson, SJ; Ye, Y.; Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM J. Optim., 10, 443-461, (2000) · Zbl 0997.90059
[5] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772, (2009) · Zbl 1219.90124
[6] Choi, C., Ye, Y.: Solving large-scale sparse semidefinite programs using the dual scaling algorithm with an iterative solver. Tech. rep. (2000)
[7] Davis, TA; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1-25, (2011) · Zbl 1365.65123
[8] De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, vol. 65. Springer, Berlin (2006) · Zbl 0991.90098
[9] Eisenstat, SC; Walker, HF, Globally convergent inexact Newton methods, SIAM J. Optim., 4, 393-422, (1994) · Zbl 0814.65049
[10] Fountoulakis, K.; Gondzio, J., A second-order method for strongly convex l1-regularization problems, Math. Program. A, 156, 189-219, (2016) · Zbl 1364.90255
[11] Golub, G.H., Van Loan, C.: Matrix Computations, 2nd edn. The Johns Hopkins University Press, Baltimore (1989) · Zbl 0733.65016
[12] Gondzio, J., Matrix-free interior point method, Comput. Optim. Appl., 51, 457-480, (2012) · Zbl 1241.90179
[13] Gould, N., Scott, J.A.: The state-of-the-art of preconditioners for sparse linear least-squares problems. Tech. Rep. RAL-P-2015-010, Rutherford Appleton Laboratory, Chilton, England (2015) · Zbl 1380.65064
[14] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM J. Optim., 10, 673-696, (2000) · Zbl 0960.65074
[15] Kocvara, M.; Stingl, M., On the solution of large-scale SDP problems by the modified barrier method using iterative solvers, Math. Program., 109, 413-444, (2007) · Zbl 1177.90312
[16] Liesen, J., Strakos, Z.: Krylov Subspace Methods: Principles and Analysis. Oxford University Press, Oxford (2012) · Zbl 1307.65001
[17] Lin, CJ; Morè, JJ, Incomplete Cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21, 24-25, (1999) · Zbl 0941.65033
[18] Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501, (2010) · Zbl 1198.90321
[19] Scott, J.A., Tuma, M.: HSL_MI28: An efficient and robust limited-memory incomplete Cholesky factorization code. ACM Trans. Math. Softw. 40. Art. 24, 19 (2014) · Zbl 1371.65031
[20] Scott, JA; Tuma, M., On positive semidefinite modification schemes for incomplete Cholesky factorization, SIAM J. Sci. Comput., 36, a609-a633, (2014) · Zbl 1298.65049
[21] Todd, MJ, Semidefinite optimization, Acta Numer., 2001, 515-560, (2001) · Zbl 1105.65334
[22] Toh, KC, Solving large scale semidefinite programs via an iterative solver on the augmented systems, SIAM J. Optim., 14, 670-698, (2004) · Zbl 1071.90026
[23] Toh, KC; Kojima, M., Solving some large scale semidefinite programs via the conjugate residual method, SIAM J. Optim., 12, 669-691, (2002) · Zbl 1008.90043
[24] Tütüncü, RH; Toh, KC; Todd, MJ, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program., 95, 189-217, (2003) · Zbl 1030.90082
[25] Vandenberghe, L.; Andersen, MS, Chordal graphs and semidefinite optimization, Found. Trends Optim., 1, 241-433, (2015)
[26] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[27] Zhao, XY; Sun, D.; Toh, KC, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20, 1737-1765, (2010) · Zbl 1213.90175
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.