×

Chordal decomposition in operator-splitting methods for sparse semidefinite programs. (English) Zbl 1434.90126

Summary: We employ chordal decomposition to reformulate a large and sparse semidefinite program (SDP), either in primal or dual standard form, into an equivalent SDP with smaller positive semidefinite (PSD) constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order operator-splitting methods, enabling the development of efficient and scalable algorithms. In particular, we apply the alternating direction method of multipliers (ADMM) to solve decomposed primal- and dual-standard-form SDPs. Each iteration of such ADMM algorithms requires a projection onto an affine subspace, and a set of projections onto small PSD cones that can be computed in parallel. We also formulate the homogeneous self-dual embedding (HSDE) of a primal-dual pair of decomposed SDPs, and extend a recent ADMM-based algorithm to exploit the structure of our HSDE. The resulting HSDE algorithm has the same leading-order computational cost as those for the primal or dual problems only, with the advantage of being able to identify infeasible problems and produce an infeasibility certificate. All algorithms are implemented in the open-source MATLAB solver CDCS. Numerical experiments on a range of large-scale SDPs demonstrate the computational advantages of the proposed methods compared to common state-of-the-art solvers.

MSC:

90C22 Semidefinite programming
90C25 Convex programming
49M27 Decomposition methods
49M29 Numerical methods involving duality

References:

[1] Agler, J.; Helton, W.; Mccullough, S.; Rodman, L., Positive semidefinite matrices with a given sparsity pattern, Linear Algebra Appl., 107, 101-149 (1988) · Zbl 0655.15016 · doi:10.1016/0024-3795(88)90240-6
[2] Alizadeh, F.; Haeberly, Jpa; Overton, Ml, Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results, SIAM J. Optim., 8, 3, 746-768 (1998) · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[3] Andersen, M., Dahl, J., Liu, Z., Vandenberghe, L.: Interior-point methods for large-scale cone programming. In: Sra, S., Nowozin, S., Wright, S.J. (eds.) Optimization for Machine Learning, pp. 55-83. MIT Press (2011)
[4] Andersen, Ms; Dahl, J.; Vandenberghe, L., Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, Math. Program. Comput., 2, 3-4, 167-201 (2010) · Zbl 1230.90006 · doi:10.1007/s12532-010-0016-2
[5] Banjac, G., Goulart, P., Stellato, B., Boyd, S.: Infeasibility detection in the alternating direction method of multipliers for convex optimization. optimization-online.org. http://www.optimization-online.org/DB_HTML/2017/06/6058.html (2017). Accessed July 2017 · Zbl 1429.90050
[6] Blair, J.R., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1-29. Springer (1993) · Zbl 0803.68081
[7] Borchers, B., SDPLIB 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11, 1-4, 683-690 (1999) · Zbl 0973.90522 · doi:10.1080/10556789908805769
[8] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory (1994), Philadelphia: SIAM, Philadelphia · Zbl 0816.93004
[9] Boyd, Stephen, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends® in Machine Learning, 3, 1, 1-122 (2010) · Zbl 1229.90122 · doi:10.1561/2200000016
[10] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[11] Burer, S., Semidefinite programming in the space of partial positive semidefinite matrices, SIAM J. Optim., 14, 1, 139-172 (2003) · Zbl 1075.90059 · doi:10.1137/S105262340240851X
[12] Dall’Anese, E.; Zhu, H.; Giannakis, Gb, Distributed optimal power flow for smart microgrids, IEEE Trans. Smart Grid, 4, 3, 1464-1475 (2013) · doi:10.1109/TSG.2013.2248175
[13] Davis, T., Direct Methods for Sparse Linear Systems (2006), Philadelphia: SIAM, Philadelphia · Zbl 1119.65021
[14] Davis, Ta; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Softw., 38, 1, 1 (2011) · Zbl 1365.65123
[15] Fält, M., Giselsson, P.: Line search for generalized alternating projections. arXiv preprint arXiv:1609.05920 (2016)
[16] Fujisawa, K., Kim, S., Kojima, M., Okamoto, Y., Yamashita, M.: User’s manual for SparseCoLO: conversion methods for sparse conic-form linear optimization problems. Tech. rep., Research Report B-453, Tokyo Institute of Technology, Tokyo 152-8552, Japan (2009)
[17] Fukuda, M.; Kojima, M.; Murota, K.; Nakata, K., Exploiting sparsity in semidefinite programming via matrix completion I: general framework, SIAM J. Optim., 11, 3, 647-674 (2001) · Zbl 1010.90053 · doi:10.1137/S1052623400366218
[18] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 1, 17-40 (1976) · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[19] Ghadimi, E.; Teixeira, A.; Shames, I.; Johansson, M., Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems, IEEE Trans. Autom. Control, 60, 3, 644-658 (2015) · Zbl 1360.90182 · doi:10.1109/TAC.2014.2354892
[20] Glowinski, R.; Marroco, A., Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires. Revue française d’automatique, informatique, recherche opérationnelle, Analyse Numérique, 9, 2, 41-76 (1975) · Zbl 0368.65053 · doi:10.1051/m2an/197509R200411
[21] Godsil, C.; Royle, Gf, Algebraic Graph Theory (2013), Berlin: Springer, Berlin
[22] Griewank, A.; Toint, Pl, On the existence of convex decompositions of partially separable functions, Math. Program., 28, 1, 25-49 (1984) · Zbl 0561.65045 · doi:10.1007/BF02612711
[23] Grone, R.; Johnson, Cr; Sá, Em; Wolkowicz, H., Positive definite completions of partial hermitian matrices, Linear Algebra Appl., 58, 109-124 (1984) · Zbl 0547.15011 · doi:10.1016/0024-3795(84)90207-6
[24] Helmberg, C.; Rendl, F.; Vanderbei, Rj; Wolkowicz, H., An interior-point method for semidefinite programming, SIAM J. Optim., 6, 2, 342-361 (1996) · Zbl 0853.65066 · doi:10.1137/0806020
[25] Kakimura, N., A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices, Linear Algebra Appl., 433, 4, 819-823 (2010) · Zbl 1196.15026 · doi:10.1016/j.laa.2010.04.012
[26] Kalbat, A., Lavaei, J.: A fast distributed algorithm for decomposable semidefinite programs. In: Proc. 54th IEEE Conf. Decis. Control, pp. 1742-1749 (2015)
[27] Kim, S.; Kojima, M.; Mevissen, M.; Yamashita, M., Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, Math. Program., 129, 1, 33-68 (2011) · Zbl 1229.90116 · doi:10.1007/s10107-010-0402-6
[28] Liu, Y., Ryu, E.K., Yin, W.: A new use of douglas-rachford splitting and ADMM for identifying infeasible, unbounded, and pathological conic programs. arXiv preprint arXiv:1706.02374 (2017) · Zbl 1515.47098
[29] Lofberg, J.: YALMIP: A toolbox for modeling and optimization in MATLAB. In: IEEE International Symposium on Computer Aided Control System Design, pp. 284-289. IEEE (2004)
[30] Madani, R., Kalbat, A., Lavaei, J.: ADMM for sparse semidefinite programming with applications to optimal power flow problem. In: Proceedings of 54th IEEE Conference on Decision and Control, pp. 5932-5939 (2015)
[31] Malick, J.; Povh, J.; Rendl, F.; Wiegele, A., Regularization methods for semidefinite programming, SIAM J. Optim., 20, 1, 336-356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575
[32] O’Donoghue, B.; Chu, E.; Parikh, N.; Boyd, S., Conic optimization via operator splitting and homogeneous self-dual embedding, J. Optim. Theory Appl., 169, 3, 1042-1068 (2016) · Zbl 1342.90136 · doi:10.1007/s10957-016-0892-3
[33] O’Donoghue, B., Chu, E., Parikh, N., Boyd, S.: SCS: splitting conic solver, version 1.2.6. https://github.com/cvxgrp/scs (2016). Accessed Sept 2016 · Zbl 1342.90136
[34] Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., Parrilo, P.: SOSTOOLS version 3.00 sum of squares optimization toolbox for MATLAB. arXiv preprint arXiv:1310.4716 (2013)
[35] Raghunathan, A.U., Di Cairano, S.: Alternating direction method of multipliers for strictly convex quadratic programs: optimal parameter selection. In: Proceedings of the American Control Conference, pp. 4324-4329. IEEE (2014)
[36] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelphia: SIAM, Philadelphia · Zbl 1002.65042
[37] Sturm, Jf, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 1-4, 625-653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[38] Sun, Y.; Andersen, Ms; Vandenberghe, L., Decomposition in conic optimization with partially separable structure, SIAM J. Optim., 24, 2, 873-897 (2014) · Zbl 1297.90111 · doi:10.1137/130926924
[39] Sun, Y.; Vandenberghe, L., Decomposition methods for sparse matrix nearness problems, SIAM J. Matrix Anal. Appl., 36, 4, 1691-1717 (2015) · Zbl 1342.90128 · doi:10.1137/15M1011020
[40] Tarjan, Re; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 3, 566-579 (1984) · Zbl 0545.68062 · doi:10.1137/0213035
[41] Themelis, A., Patrinos, P.: SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators. arXiv preprint arXiv:1609.06955 (2016) · Zbl 1482.49019
[42] Vandenberghe, Lieven; Andersen, Martin S., Chordal Graphs and Semidefinite Optimization, Foundations and Trends® in Optimization, 1, 4, 241-433 (2015) · doi:10.1561/2400000006
[43] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev., 38, 1, 49-95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[44] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented lagrangian methods for semidefinite programming, Math. Program. Comput., 2, 3-4, 203-230 (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1
[45] Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 165-194. Springer (2016) · Zbl 1372.65186
[46] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Algebr. Discrete Methods, 2, 77-79 (1981) · Zbl 0496.68033 · doi:10.1137/0602010
[47] Ye, Y., Interior Point Algorithms: Theory and Analysis (2011), Hoboken: Wiley, Hoboken
[48] Ye, Y.; Todd, Mj; Mizuno, S., An \(\cal{O}\sqrt{n} l \)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 1, 53-67 (1994) · Zbl 0799.90087 · doi:10.1287/moor.19.1.53
[49] Zhao, Xy; Sun, D.; Toh, Kc, A Newton-CG augmented lagrangian method for semidefinite programming, SIAM J. Optim., 20, 4, 1737-1765 (2010) · Zbl 1213.90175 · doi:10.1137/080718206
[50] Zheng, Y.; Fantuzzi, G.; Papachristodoulou, A., Exploiting sparsity in the coefficient matching conditions in sum-of-squares programming using ADMM, IEEE Control Syst. Lett., 1, 1, 80-85 (2017) · doi:10.1109/LCSYS.2017.2706941
[51] Zheng, Y.; Fantuzzi, G.; Papachristodoulou, A.; Goulart, P.; Wynn, A., Fast ADMM for homogeneous self-dual embedding of sparse SDPs, IFAC PapersOnLine, 50, 1, 8411-8416 (2017) · doi:10.1016/j.ifacol.2017.08.1569
[52] Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Fast ADMM for semidefinite programs with chordal sparsity. In: Proceedings of the American Control Conference, pp. 3335-3340. IEEE (2017)
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.