×

Douglas-Rachford splitting method for semidefinite programming. (English) Zbl 1338.90250

Summary: In this paper, we study the Douglas-Rachford (DR) splitting method when applied to the standard semidefinite programming, and we introduce a new variant of this method and under weak assumptions prove its global convergence. At each iteration, it needs to solve two subproblems. First, project once onto the set of all symmetric positive semidefinite matrices. Then, solve one system of linear equations whose co-efficient matrix is symmetric positive definite. This is in sharp contrast to symmetric positive semi-definiteness of the corresponding co-efficient matrix in the boundary point method recently proposed by Povh et al. More importantly, we analyze the iteration complexity of the DR splitting method and derive the currently best result. Based on rigorous analysis in theory, we suggest an implementable version. Rudimentary numerical experiments confirm its efficiency and robustness on certain test problems with more than one million equality constraints.

MSC:

90C06 Large-scale problems in mathematical programming
90C22 Semidefinite programming
90C30 Nonlinear programming
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F.: Interior point methods in semi-definite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13-51 (1995) · Zbl 0833.90087 · doi:10.1137/0805002
[2] Nesterov, Y.E., Nemirovsky, A.S.: Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms. SIAM Publications, SIAM, Philadelphia (1994) · doi:10.1137/1.9781611970791
[3] Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49-95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[4] Todd, M.J.: Semi-definite optimization. Acta Numer. 10, 515-560 (2001) · Zbl 1105.65334 · doi:10.1017/S0962492901000071
[5] Burer, S., Vandenbussche, D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3), 726-750 (2006) · Zbl 1113.90100 · doi:10.1137/040609574
[6] Povh, J., Rendl, F., Wiegele, A.: A boundary point method to solve semi-definite programs. Computing 78, 277-286 (2006) · Zbl 1275.90055 · doi:10.1007/s00607-006-0182-2
[7] Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semi-definite programming. SIAM J. Optim. 20(1), 336-356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575
[8] Wen, Z.W., Goldfarb, D., Yin, W.T.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203-230 (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1
[9] Zhao, X.Y., Sun, D.F., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737-1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206
[10] Malick, J.: A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26, 272-284 (2004) · Zbl 1080.65027 · doi:10.1137/S0895479802413856
[11] Monteiro, R.D.C., Ortiz, C., Svaiter, B.F.: Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems. Comput. Optim. Appl. 6(2), 103-150 (2014) · Zbl 1312.90052
[12] Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964-979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071
[13] Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(3), 293-318 (1992) · Zbl 0765.90073 · doi:10.1007/BF01581204
[14] Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53, 475-504 (2004) · Zbl 1153.47305 · doi:10.1080/02331930412331327157
[15] Dong, Y.D., Fischer, A.: A family of operator splitting methods revisited. Nonlinear Anal. 72, 4307-4315 (2010) · Zbl 1201.65110 · doi:10.1016/j.na.2010.02.010
[16] Yu, Z.S.: Solving semidefinite programming problems via alternating direction methods. J. Comput. Appl. Math. 193, 437-445 (2006) · Zbl 1098.65069 · doi:10.1016/j.cam.2005.07.002
[17] Schwertman, N.C., Allen, D.M.: Smoothing an indefinite variance-covariance matrix. J. Stat. Comput. Simul. 9, 183-194 (1979) · doi:10.1080/00949657908810316
[18] Higham, N.: Computing a nearest symmetric positive semidefinite matrix. Linear Algebra Appl. 103, 103-118 (1988) · Zbl 0649.65026 · doi:10.1016/0024-3795(88)90223-6
[19] Malick, J., Sendov, H.S.: Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices. Set Valued Anal. 14, 273-293 (2006) · Zbl 1100.49033 · doi:10.1007/s11228-005-0005-1
[20] Helmberg, C.: Semidefinite Programming for Combinatorial Optimization. Habilitationsschrift TU, Berlin (2000) · Zbl 0960.65074
[21] Gafni, E.M., Bertsekas, D.P.: Two-metric projection methods for constrained optimization. SIAM J. Control Optim. 22(6), 936-964 (1984) · Zbl 0555.90086 · doi:10.1137/0322061
[22] Toint, P.H.L.: Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space. IMA J. Numer. Anal. 8(2), 231-252 (1988) · Zbl 0698.65043 · doi:10.1093/imanum/8.2.231
[23] Zhu, T., Yu, Z.G.: A simple proof for some important properties of the projection mapping. Math. Inequal. Appl. 7, 453-456 (2004) · Zbl 1086.49007
[24] Huang, Y.Y., Dong, Y.D.: New properties of forward-backward splitting and a practical proximal-descent algorithm. Appl. Math. Comput. 237, 60-68 (2014) · Zbl 1336.65101 · doi:10.1016/j.amc.2014.03.062
[25] Tseng, P.: Merit function for semidefinite complementarity problems. Math. Program. 83, 159-185 (1998) · Zbl 0920.90135
[26] He, B.S.: Inexact implicit methods for monotone general variational inequalities. Math. Program. 86, 199-217 (1999) · Zbl 0979.49006 · doi:10.1007/s101070050086
[27] Dong, Y.D.: The proximal point algorithm revisited. J. Optim. Theory Appl. 161, 478-489 (2014) · Zbl 1291.90307 · doi:10.1007/s10957-013-0351-3
[28] Sun, X.Z.: A descent property of implicit method for monotone variational inequality. Numer. Math. J. Chin. Univ. 32(1), 75-80 (2002) · Zbl 1003.65071
[29] Fountoulakis, K., Gondzio, J., Zhlobich, P.: Matrix-free interior point method for compressed sensing problems. Math. Program. Comput. 6(1), 1-31 (2014) · Zbl 1304.90137 · doi:10.1007/s12532-013-0063-6
[30] Moré, B.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization. ACM Trans. Math. Softw. 7, 17-41 (1981) · Zbl 0454.65049 · doi:10.1145/355934.355936
[31] Davi, T., Jarre, F.: High-accuracy solution of large-scale semidefinite programs. Optim. Methods Softw. 27(4-5), 655-666 (2012) · Zbl 1253.49019
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.