×

Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion. (English) Zbl 1470.90070

Summary: Clique tree conversion solves large-scale semidefinite programs by splitting an \(n\times n\) matrix variable into up to \(n\) smaller matrix variables, each representing a principal submatrix of up to \(\omega \times \omega \). Its fundamental weakness is the need to introduce overlap constraints that enforce agreement between different matrix variables, because these can result in dense coupling. In this paper, we show that by dualizing the clique tree conversion, the coupling due to the overlap constraints is guaranteed to be sparse over dense blocks, with a block sparsity pattern that coincides with the adjacency matrix of a tree. We consider two classes of semidefinite programs with favorable sparsity patterns that encompass the MAXCUT and MAX \(k\)-CUT relaxations, the Lovasz Theta problem, and the AC optimal power flow relaxation. Assuming that \(\omega \ll n\), we prove that the per-iteration cost of an interior-point method is \(linear O(n)\) time and memory, so an \(\epsilon \)-accurate and \(\epsilon \)-feasible iterate is obtained after \(O(\sqrt{n}\log (1/\epsilon ))\) iterations in \(near-linear O(n^{1.5}\log (1/\epsilon ))\) time. We confirm our theoretical insights with numerical results on semidefinite programs as large as \(n=13,659\).

MSC:

90C22 Semidefinite programming
90C35 Programming involving graphs or networks
90C51 Interior-point methods
90C06 Large-scale problems in mathematical programming

References:

[1] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021
[2] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[3] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3, 3, 411-430 (1990) · Zbl 0712.90050
[4] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 2, 166-190 (1991) · Zbl 0754.90039
[5] Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 293-303, Springer, Berlin (2001) · Zbl 1010.90515
[6] Laurent, M., A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming, Math. Oper. Res., 28, 3, 470-496 (2003) · Zbl 1082.90084
[7] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 3, 796-817 (2001) · Zbl 1010.90061
[8] Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)
[9] Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course (2013), Berlin: Springer, Berlin · Zbl 1086.90045
[10] 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
[11] Molzahn, DK; Holzer, JT; Lesieutre, BC; DeMarco, CL, Implementation of a large-scale optimal power flow solver based on semidefinite programming, IEEE Trans. Power Syst., 28, 4, 3987-3998 (2013)
[12] Madani, R.; Sojoudi, S.; Lavaei, J., Convex relaxation for optimal power flow problem: Mesh networks, IEEE Trans. Power Syst., 30, 1, 199-211 (2015)
[13] Madani, R.; Ashraphijuo, M.; Lavaei, J., Promises of conic relaxation for contingency-constrained optimal power flow problem, IEEE Trans. Power Syst., 31, 2, 1297-1307 (2016)
[14] Eltved, A.; Dahl, J.; Andersen, MS, On the robustness and scalability of semidefinite relaxation for optimal power flow problems, Optim. Eng., 21, 375-392 (2020) · Zbl 1447.90069 · doi:10.1007/s11081-019-09427-4
[15] Vandenberghe, L.; Andersen, MS, Chordal graphs and semidefinite optimization, Found. Trends Optim., 1, 4, 241-433 (2015)
[16] 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
[17] Andersen, MS; Hansson, A.; Vandenberghe, L., Reduced-complexity semidefinite relaxations of optimal power flow problems, IEEE Trans. Power Syst., 29, 4, 1855-1863 (2014)
[18] Löfberg, J., Dualize it: software for automatic primal and dual conversions of conic programs, Optim. Methods Softw., 24, 3, 313-325 (2009) · Zbl 1173.90546
[19] Griewank, A.; Toint, PL, Partitioned variable metric updates for large structured optimization problems, Numerische Mathematik, 39, 1, 119-137 (1982) · Zbl 0482.65035
[20] Andersen, M., Dahl, J., Vandenberghe, L.: CVXOPT: A Python package for convex optimization. abel.ee.ucla.edu/cvxopt. (2013)
[21] Löfberg, J.: Yalmip: A toolbox for modeling and optimization in matlab. In: Proceedings of the CACSD Conference, 3. Taipei, Taiwan (2004)
[22] Fujisawa, K., Kim, S., Kojima, M., Okamoto, Y., Yamashita, M.: User’s manual for SparseCoLO: Conversion methods for sparse conic-form linear optimization problems. Technical report, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, (2009). Research Report B-453
[23] 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
[24] Andersen, M.S.: Opfsdr v0.2.3 (2018)
[25] Madani, R., Kalbat, A., Lavaei, J.: ADMM for sparse semidefinite programming with applications to optimal power flow problem. In: IEEE 54th Annual Conference on Decision and Control (CDC), pp. 5932-5939. IEEE (2015)
[26] Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Program. 180, 489-532 (2020). doi:10.1007/s10107-019-01366-3 · Zbl 1434.90126
[27] Annergren, M., Pakazad, S.K., Hansson, A., Wahlberg, B.: A distributed primal-dual interior-point method for loosely coupled problems using ADMM. arXiv preprint arXiv:1406.2192 (2014)
[28] Khoshfetrat Pakazad, S.; Hansson, A.; Andersen, MS, Distributed interior-point method for loosely coupled problems, IFAC Proc. Volumes, 47, 3, 9587-9592 (2014)
[29] Zhang, RY; White, JK, Gmres-accelerated ADMM for quadratic objectives, SIAM J. Optim., 28, 4, 3025-3056 (2018) · Zbl 1402.49025
[30] Andersen, MS; Dahl, J.; Vandenberghe, L., Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, Math. Program. Comput., 2, 3, 167-201 (2010) · Zbl 1230.90006
[31] Duff, IS; Reid, JK, The multifrontal solution of indefinite sparse symmetric linear, ACM Trans. Math. Softw. (TOMS), 9, 3, 302-325 (1983) · Zbl 0515.65022
[32] Liu, JW, The multifrontal method for sparse matrix solution: theory and practice, SIAM Rev., 34, 1, 82-109 (1992) · Zbl 0919.65019
[33] Pakazad, S. Khoshfetrat; Hansson, A.; Andersen, MS; Nielsen, I., Distributed primal-dual interior-point methods for solving tree-structured coupled convex problems using message-passing, Optim. Methods Softw., 32, 3, 401-435 (2017) · Zbl 1364.90357
[34] Khoshfetrat Pakazad, S.; Hansson, A.; Andersen, MS; Rantzer, A., Distributed semidefinite programming with application to large-scale system analysis, IEEE Trans. Autom. Control, 63, 4, 1045-1058 (2017) · Zbl 1390.90419
[35] Alizadeh, F.; Haeberly, J-PA; Overton, ML, Complementarity and nondegeneracy in semidefinite programming, Math. Program., 77, 1, 111-128 (1997) · Zbl 0890.90141
[36] Arnborg, S.; Corneil, DG; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, 8, 2, 277-284 (1987) · Zbl 0611.05022
[37] Ye, Y.; Todd, MJ; Mizuno, S., An \(O(\sqrt{nL})\)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 1, 53-67 (1994) · Zbl 0799.90087
[38] Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Springer Science & Business Media (2012) · Zbl 0962.90001
[39] Permenter, F.; Friberg, HA; Andersen, ED, Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach, SIAM J. Optim., 27, 3, 1257-1282 (2017) · Zbl 1368.90123
[40] Frieze, A.; Jerrum, M., Improved approximation algorithms for MAX k-CUT and MAX BISECTION, Algorithmica, 18, 1, 67-81 (1997) · Zbl 0873.68078
[41] Pataki, G., Stefan S.: The DIMACS library of semidefinite-quadratic-linear programs. Technical Report. Preliminary draft, Computational Optimization Research Center, Columbia University, New York (2002)
[42] Borchers, B., Sdplib 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11, 1-4, 683-690 (1999) · Zbl 0973.90522
[43] Sun, Y.: Decomposition methods for semidefinite optimization. Ph.D. thesis, UCLA (2015)
[44] Liu, JW, The role of elimination trees in sparse factorization, SIAM J. Matrix Anal. Appl., 11, 1, 134-172 (1990) · Zbl 0697.65013
[45] Bodlaender, HL; Gilbert, JR; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms, 18, 2, 238-255 (1995) · Zbl 0818.68118
[46] Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 422-431. IEEE (1988)
[47] Klein, P., Stein, C., Tardos, E.: Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities. In: Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 310-321. ACM (1990)
[48] George, A.; Liu, JW, The evolution of the minimum degree ordering algorithm, SIAM Rev., 31, 1, 1-19 (1989) · Zbl 0671.65024
[49] Lipton, RJ; Rose, DJ; Tarjan, RE, Generalized nested dissection, SIAM J. Numer. Anal., 16, 2, 346-358 (1979) · Zbl 0435.65021
[50] Rose, DJ; Tarjan, RE; Lueker, GS, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 2, 266-283 (1976) · Zbl 0353.65019
[51] George, A.; Liu, JW, Computer Solution of Large Sparse Positive Definite Systems (1981), Englewood Cliffs, NJ: Prentice Hall, Englewood Cliffs, NJ · Zbl 0516.65010
[52] 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
[53] Dancis, J., Positive semidefinite completions of partial hermitian matrices, Linear Algebra Appl., 175, 97-114 (1992) · Zbl 0760.15019
[54] Laurent, M.; Varvitsiotis, A., A new graph parameter related to bounded rank positive semidefinite matrix completions, Math. Program., 145, 1-2, 291-325 (2014) · Zbl 1293.05238
[55] Madani, R.; Sojoudi, S.; Fazelnia, G.; Lavaei, J., Finding low-rank solutions of sparse linear matrix inequalities using convex optimization, SIAM J. Optim., 27, 2, 725-758 (2017) · Zbl 1365.90185
[56] Jiang, X.: Minimum rank positive semidefinite matrix completion with chordal sparsity pattern. Master’s thesis, UCLA (2017)
[57] Kobayashi, K.; Kim, S.; Kojima, M., Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP, Appl. Math. Optim., 58, 1, 69-88 (2008) · Zbl 1191.90032
[58] Parter, S., The use of linear graphs in Gauss elimination, SIAM Rev., 3, 2, 119-130 (1961) · Zbl 0102.11302
[59] 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
[60] Andersen, E.D.: Handling free variables in primal-dual interior-point methods using a quadratic cone. In: Proceedings of the SIAM Conference on Optimization, Toronto (2002)
[61] Sturm, JF, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, Optim. Methods Softw., 17, 6, 1105-1154 (2002) · Zbl 1032.90021
[62] Andersen, ED; Roos, C.; Terlaky, T., On implementing a primal-dual interior-point method for conic quadratic optimization, Math. Program., 95, 2, 249-277 (2003) · Zbl 1030.90137
[63] Goldfarb, D.; Scheinberg, K., Product-form Cholesky factorization in interior point methods for second-order cone programming, Math. Program., 103, 1, 153-179 (2005) · Zbl 1079.90157
[64] Guo, J.; Niedermeier, R., Exact algorithms and applications for Tree-like Weighted Set Cover, J. Discrete Algorithms, 4, 4, 608-622 (2006) · Zbl 1110.68173
[65] Lewis, JG; Peyton, BW; Pothen, A., A fast algorithm for reordering sparse matrices for parallel factorization, SIAM J. Sci. Stat. Comput., 10, 6, 1146-1173 (1989) · Zbl 0693.65032
[66] Pothen, A., Sun, C.: Compact clique tree data structures in sparse matrix factorizations. In: Coleman, T.F., Li, Y. (eds.) Large-Scale Numerical Optimization, pp. 180-204. SIAM (1990) · Zbl 0727.90087
[67] Andersen, MS; Dahl, J.; Vandenberghe, L., Logarithmic barriers for sparse matrix cones, Optim. Methods Softw., 28, 3, 396-423 (2013) · Zbl 1266.65045
[68] George, A., Gilbert, J.R., Liu, J.W.H. (eds.): Graph Theory and Sparse Matrix Computation. Springer Science & Business Media (2012)
[69] Zimmerman, RD; Murillo-Sánchez, CE; Thomas, RJ, MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education, IEEE Trans. Power Syst., 26, 1, 12-19 (2011)
[70] Josz, C., Fliscounakis, S., Maeght, J., Panciatici, P.: AC power flow data in MATPOWER and QCQP format: iTesla, RTE snapshots, and PEGASE. arXiv preprint arXiv:1603.01533 (2016)
[71] Mittelmann, HD, An independent benchmarking of SDP and SOCP solvers, Math. Program., 95, 2, 407-430 (2003) · Zbl 1030.90080
[72] Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.): High Performance Optimiztion. Springer Science & Business Media (2013)
[73] Amestoy, PR; Davis, TA; Duff, IS, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Trans. Math. Softw. (TOMS), 30, 3, 381-388 (2004) · Zbl 1070.65534
[74] Lavaei, J.; Low, SH, Zero duality gap in optimal power flow problem, IEEE Trans. Power Syst., 27, 1, 92 (2012)
[75] Nakata, K.; Fujisawa, K.; Fukuda, M.; Kojima, M.; Murota, K., Exploiting sparsity in semidefinite programming via matrix completion II: implementation and numerical results, Math. Program., 95, 2, 303-327 (2003) · Zbl 1030.90081
[76] 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
[77] Vanderbei, RJ, Linear Programming: Foundations and Extensions (2015), Berlin: Springer, Berlin · Zbl 0899.90129
[78] Nesterov, YE; Todd, MJ, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim., 8, 2, 324-364 (1998) · Zbl 0922.90110
[79] Sturm, JF; Zhang, S., Symmetric primal-dual path-following algorithms for semidefinite programming, Appl. Numer. Math., 29, 3, 301-315 (1999) · Zbl 0956.90027
[80] Sturm, JF; Zhang, S., On a wide region of centers and primal-dual interior point algorithms for linear programming, Math. Oper. Res., 22, 2, 408-431 (1997) · Zbl 0883.90093
[81] Todd, MJ; Toh, K-C; Tütüncü, RH, On the nesterov-todd direction in semidefinite programming, SIAM J. Optim., 8, 3, 769-796 (1998) · Zbl 0913.90217
[82] Alizadeh, F.; Haeberly, J-PA; 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
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.