Exploiting low-rank structure in semidefinite programming by approximate operator splitting. (English) Zbl 1486.90141
Summary: In contrast to many other convex optimization classes, state-of-the-art semidefinite programming solvers are still unable to efficiently solve large-scale instances. This work aims to reduce this scalability gap by proposing a novel proximal algorithm for solving general semidefinite programming problems. The key characteristic of the proposed algorithm is to be able to exploit the low-rank property inherent to several semidefinite programming problems. Exploiting the low-rank structure provides a substantial speedup and allows the operator splitting method to efficiently scale to larger instances. As opposed to other low-rank based methods, the proposed algorithm has convergence guarantees for general semidefinite programming problems. Additionally, an open-source semidefinite programming solver called ProxSDP is made available and its implementation details are discussed. Case studies are presented in order to evaluate the performance of the proposed methodology.
MSC:
| 90C22 | Semidefinite programming |
Keywords:
semidefinite programming; operator splitting methods; inexact fixed point iteration; approximate proximal point; convex optimization; low-rank matrix approximationSoftware:
Julia; Mosek; SDPLIB; LAPACK; ARPACK; SDPLR; SDPNAL+; MathOptInterface.jl; JuMP; SCS; ProxImaL; ProxSDPReferences:
| [1] | Raghavendra, P.Optimal algorithms and inapproximability results for every csp? In: Proceedings of the fortieth annual ACM symposium on Theory of computing; ACM; 2008. p. 245-254. · Zbl 1231.68142 |
| [2] | Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J Math Imaging Vis, 40, 1, 120-145 (2011) · Zbl 1255.68217 |
| [3] | Rontsis, N, Goulart, PJ, Nakatsukasa, Y.Efficient semidefinite programming with approximate admm. preprint arXiv:191202767. 2019. · Zbl 1484.90068 |
| [4] | 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, R2, 41-76 (1975) · Zbl 0368.65053 |
| [5] | Eckstein, J.; Bertsekas, DP., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math Program, 55, 1-3, 293-318 (1992) · Zbl 0765.90073 |
| [6] | Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM Rev, 38, 1, 49-95 (1996) · Zbl 0845.65023 |
| [7] | Wolkowicz, H.; Saigal, R.; Vandenberghe, L., Handbook of semidefinite programming: theory, algorithms, and applications, 27 (2012), Springer Science & Business Media |
| [8] | Vandenberghe, L.; Boyd, S., Applications of semidefinite programming, Appl Numer Math, 29, 3, 283-299 (1999) · Zbl 0956.90031 |
| [9] | Lur’e, AI., Some non-linear problems in the theory of automatic control (1957), Her Majesty’s Stationery Office |
| [10] | Kuindersma, S.; Deits, R.; Fallon, M., Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot, Auton Robots, 40, 3, 429-455 (2016) |
| [11] | Bellman, R.; Fan, K., On systems of linear inequalities in hermitian matrix variables, Convexity, 7, 1-11 (1963) · Zbl 0148.26001 |
| [12] | Vandenberghe, L.; Balakrishnan, VR; Wallin, R., Interior-point algorithms for semidefinite programming problems derived from the kyp lemma, Positive Polynomials Control, 195-238 (2005) · Zbl 1070.90083 |
| [13] | Boyd, S.; El Ghaoui, L.; Feron, E., Linear matrix inequalities in system and control theory (1994), SIAM · Zbl 0816.93004 |
| [14] | Scherer, C, Weiland, S.Linear matrix inequalities in control. The Netherlands:Delft; 2000. (Lecture Notes, Dutch Institute for Systems and Control; 3). |
| [15] | Lavaei, J.; Low, SH., Zero duality gap in optimal power flow problem, IEEE Trans Power Syst., 27, 1, 92-107 (2012) |
| [16] | Vandenberghe, L.; Boyd, S.; El Gamal, A., Optimizing dominant time constant in rc circuits, IEEE Trans Comput Aided Design Int Circuits Syst, 17, 2, 110-125 (1998) |
| [17] | Vandenberghe, L, Boyd, S, El Gamal, A.Optimal wire and transistor sizing for circuits with non-tree topology. In: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design; IEEE Computer Society; 1997. p. 252-259. |
| [18] | Ben-Tal, A.; Nemirovski, A., Robust truss topology design via semidefinite programming, SIAM J Optim, 7, 4, 991-1016 (1997) · Zbl 0899.90133 |
| [19] | Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math Oper Res, 23, 4, 769-805 (1998) · Zbl 0977.90052 |
| [20] | Zymler, S.; Kuhn, D.; Rustem, B., Distributionally robust joint chance constraints with second-order moment information, Math Program, 1-32 (2013) · Zbl 1286.90103 |
| [21] | 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 |
| [22] | Goemans, MX; Williamson, DP., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J ACM (JACM), 42, 6, 1115-1145 (1995) · Zbl 0885.68088 |
| [23] | Karloff, H, Zwick, U.A 7/8-approximation algorithm for max 3sat? In: Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on; IEEE; 1997. p. 406-415. |
| [24] | Cvetković, D, Čangalović, M, Kovačević-Vujčić, V.Semidefinite programming methods for the symmetric traveling salesman problem. In: International conference on integer programming and combinatorial optimization; Springer; 1999. p. 126-136. · Zbl 0948.90114 |
| [25] | Candes, EJ; Eldar, YC; Strohmer, T., Phase retrieval via matrix completion, SIAM Rev, 57, 2, 225-251 (2015) · Zbl 1344.49057 |
| [26] | Lovász, L.Semidefinite programs and combinatorial optimization. In: Recent advances in algorithms and combinatorics. Springer; 2003. p. 137-194. · Zbl 1040.90032 |
| [27] | De Bie, T.Deploying sdp for machine learning. In: ESANN; 2007. p. 205-210. |
| [28] | Candes, E.; Recht, B., Exact matrix completion via convex optimization, Commun ACM, 55, 6, 111-119 (2012) |
| [29] | Bennett, J, Lanning, S.The netflix prize. In: Proceedings of KDD cup and workshop; Vol. 2007; New York (NY); 2007. p. 35. |
| [30] | Wainwright, MJ; Jordan, MI., Log-determinant relaxation for approximate inference in discrete markov random fields, IEEE Trans Signal Process, 54, 6, 2099-2109 (2006) · Zbl 1374.94616 |
| [31] | Lanckriet, GR; Cristianini, N.; Bartlett, P., Learning the kernel matrix with semidefinite programming, J Mach Learn Res, 5, Jan, 27-72 (2004) · Zbl 1222.68241 |
| [32] | Lanckriet, GR; De Bie, T.; Cristianini, N., A statistical framework for genomic data fusion, Bioinformatics, 20, 16, 2626-2635 (2004) |
| [33] | Khot, S.On the power of unique 2-prover 1-round games. In: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing; ACM; 2002. p. 767-775. · Zbl 1192.68367 |
| [34] | Khot, S.; Minzer, D.; Safra, M., Pseudorandom sets in grassmann graph have near-perfect expansion, Electronic Colloquium Comput Complexity (ECCC), 25, 92-601 (2018) |
| [35] | Dinur, I, Khot, S, Kindler, G, et al. Towards a proof of the 2-to-1 games conjecture? In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing; ACM; 2018. p. 376-389. · Zbl 1429.68076 |
| [36] | Shor, NZ., Cut-off method with space extension in convex programming problems, Cybern Syst Anal, 13, 1, 94-96 (1977) |
| [37] | Iudin, D.; Nemirovskii, AS., Informational complexity and efficient methods for solving complex extremal problems, Matekon, 13, 3, 25-45 (1977) |
| [38] | Hiriart-Urruty, JB; Lemaréchal, C., Convex analysis and minimization algorithms I: fundamentals, 305 (2013), Springer Science & Business Media |
| [39] | Karmarkar, N.A new polynomial-time algorithm for linear programming. In: Proceedings of the sixteenth annual ACM symposium on Theory of computing; ACM; 1984. p. 302-311. · Zbl 0557.90065 |
| [40] | Adler, I.; Resende, MG; Veiga, G., An implementation of Karmarkar’s algorithm for linear programming, Math Program, 44, 1, 297-335 (1989) · Zbl 0682.90061 |
| [41] | Nesterov, Y.; Nemirovskii, A., Interior-point polynomial algorithms in convex programming (1994), SIAM · Zbl 0824.90112 |
| [42] | Alizadeh, F., Optimization over the positive-definite cone: interior point methods and combinatorial applications, Adv. Optim. Parallel Comput, 5, 1 (1992) · Zbl 0814.90071 |
| [43] | Helmberg, C.; Rendl, F.; Vanderbei, RJ, An interior-point method for semidefinite programming, SIAM J Optim, 6, 2, 342-361 (1996) · Zbl 0853.65066 |
| [44] | 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 |
| [45] | Mosek, A.The Mosek optimization software. 2010;54:2-1. Available from:http://www.mosek.com. |
| [46] | Boyd, S.; Parikh, N.; Chu, E., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations Trends \(####\) Mach Learn, 3, 1, 1-122 (2011) · Zbl 1229.90122 |
| [47] | Heide, F.; Diamond, S.; Nießner, M., Proximal: efficient image optimization using proximal algorithms, ACM Trans Graphics (TOG), 35, 4, 84 (2016) |
| [48] | O’Donoghue, B.; Chu, E.; Parikh, N., Conic optimization via operator splitting and homogeneous self-dual embedding, J Optim Theory Appl, 169, 3, 1042-1068 (2016) · Zbl 1342.90136 |
| [49] | 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 |
| [50] | Madani, R, Kalbat, A, Lavaei, J.Admm for sparse semidefinite programming with applications to optimal power flow problem. In: Decision and Control (CDC), 2015 IEEE 54th Annual Conference on; IEEE; 2015. p. 5932-5939. |
| [51] | Yang, L.; Sun, D.; Toh, KC., Sdpnal: a majorized semismooth newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints, Math Program Comput, 7, 3, 331-366 (2015) · Zbl 1321.90085 |
| [52] | Fukuda, M.; Kojima, M.; Murota, K., Exploiting sparsity in semidefinite programming via matrix completion i: general framework, SIAM J Optim, 11, 3, 647-674 (2001) · Zbl 1010.90053 |
| [53] | Nakata, K.; Fujisawa, K.; Fukuda, M., Exploiting sparsity in semidefinite programming via matrix completion ii: implementation and numerical results, Math Program, 95, 2, 303-327 (2003) · Zbl 1030.90081 |
| [54] | Vandenberghe, L.; Andersen, MS, Chordal graphs and semidefinite optimization, Foundations Trends \(####\) Optim, 1, 4, 241-433 (2015) |
| [55] | Pakazad, SK; Hansson, A.; Andersen, MS, Distributed semidefinite programming with application to large-scale system analysis, IEEE Trans Automat Control, 63, 4, 1045-1058 (2018) · Zbl 1390.90419 |
| [56] | Fujisawa, K, Sato, H, Matsuoka, S, et al. High-performance general solver for extremely large-scale semidefinite programming problems. In: 2012 International Conference for High Performance Computing, Networking, Storage and Analysis (SC); IEEE; 2012. p. 1-11. |
| [57] | Zhang, RY, Lavaei, J.Sparse semidefinite programs with near-linear time complexity. preprint arXiv:171003475; 2017. · Zbl 1470.90070 |
| [58] | Zhang, RY, Lavaei, J.Modified interior-point method for large-and-sparse low-rank semidefinite programs. preprint arXiv:170310973; 2017. |
| [59] | Zheng, Y.; Fantuzzi, G.; Papachristodoulou, A., Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Math Program, 180, 1, 489-532 (2020) · Zbl 1434.90126 |
| [60] | Ryu, EK; Boyd, S., Primer on monotone operator methods, Appl Comput Math, 15, 1, 3-43 (2016) · Zbl 1342.47066 |
| [61] | Eckstein, J.Splitting methods for monotone operators with applications to parallel optimization [dissertation]. Massachusetts Institute of Technology; 1989. |
| [62] | Combettes, PL., Solving monotone inclusions via compositions of nonexpansive averaged operators, Optimization, 53, 5-6, 475-504 (2004) · Zbl 1153.47305 |
| [63] | Combettes, PL; Wajs, VR., Signal recovery by proximal forward-backward splitting, Multiscale Model Simul, 4, 4, 1168-1200 (2005) · Zbl 1179.94031 |
| [64] | Combettes, PL, Pesquet, JC.Proximal splitting methods in signal processing. In: Fixed-point algorithms for inverse problems in science and engineering. New York (NY): Springer; 2011. p. 185-212. · Zbl 1242.90160 |
| [65] | Bauschke, HH; Combettes, PL., Convex analysis and monotone operator theory in hilbert spaces, 408 (2011), Springer · Zbl 1218.47001 |
| [66] | Rockafellar, RT., Convex analysis (2015), Princeton University Press |
| [67] | Bauschke, HH; Combettes, PL., Convex analysis and monotone operator theory in hilbert spaces, 2011 (2017), Springer · Zbl 1218.47001 |
| [68] | Pock, T, Cremers, D, Bischof, H, et al. An algorithm for minimizing the Mumford-Shah functional. In: IEEE 12th International Conference on Computer Vision, 2009; IEEE; 2009. p. 1133-1140. |
| [69] | Sidky, EY; Jørgensen, JH; Pan, X., Convex optimization problem prototyping for image reconstruction in computed tomography with the chambolle-pock algorithm, Phys Med Biol, 57, 10, 3065 (2012) |
| [70] | Vaiter, S.; Peyré, G.; Dossal, C., Robust sparse analysis regularization, IEEE Trans Inform Theory, 59, 4, 2001-2016 (2013) · Zbl 1364.94172 |
| [71] | Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J Imaging Sci, 2, 1, 183-202 (2009) · Zbl 1175.94009 |
| [72] | Parikh, N.; Boyd, SP., Proximal algorithms, Foundations Trends Optim, 1, 3, 127-239 (2014) |
| [73] | Moreau, JJ., Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement polaires, CR Acad Sci Paris, 225, 238-240 (1962) · Zbl 0109.08105 |
| [74] | Tseng, P., Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM J Control Optim, 29, 1, 119-138 (1991) · Zbl 0737.90048 |
| [75] | Barvinok, AI., Problems of distance geometry and convex properties of quadratic maps, Discrete Comput Geom, 13, 2, 189-202 (1995) · Zbl 0829.05025 |
| [76] | Pataki, G., On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Math Oper Res, 23, 2, 339-358 (1998) · Zbl 0977.90051 |
| [77] | Zhang, Y, Lu, Z.Penalty decomposition methods for rank minimization. In: Advances in neural information processing systems; 2011. p. 46-54. |
| [78] | Zhao, YB., An approximation theory of matrix rank minimization and its application to quadratic equations, Linear Algebra Appl, 437, 1, 77-93 (2012) · Zbl 1242.65086 |
| [79] | Yuan, G, Ghanem, B.A proximal alternating direction method for semi-definite rank minimization. In: AAAI; 2016. p. 2300-2308. |
| [80] | Burer, S.; Monteiro, RD., A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math Program, 95, 2, 329-357 (2003) · Zbl 1030.90077 |
| [81] | Shah, S, Yadav, AK, Castillo, CD, et al. Biconvex relaxation for semidefinite programming in computer vision. In: European Conference on Computer Vision; Springer; 2016. p. 717-735. |
| [82] | Wang, PW, Chang, WC, Kolter, JZ.The mixing method: coordinate descent for low-rank semidefinite programming. preprint arXiv:170600476; 2017. |
| [83] | Yurtsever, A, Udell, M, Tropp, JA.Sketchy decisions: convex low-rank matrix optimization with optimal storage. preprint arXiv:170206838; 2017. |
| [84] | Halko, N.; Martinsson, PG; Tropp, JA., Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev, 53, 2, 217-288 (2011) · Zbl 1269.65043 |
| [85] | Tropp, JA; Yurtsever, A.; Udell, M., Practical sketching algorithms for low-rank matrix approximation, SIAM J Matrix Anal Appl, 38, 4, 1454-1485 (2017) · Zbl 1379.65026 |
| [86] | Eckart, C.; Young, G., The approximation of one matrix by another of lower rank, Psychometrika, 1, 3, 211-218 (1936) · JFM 62.1075.02 |
| [87] | Golub, GH; Van Loan, CF., Matrix computations, 3 (2012), JHU Press |
| [88] | Higham, NJ.Matrix nearness problems and applications. University of Manchester, Department of Mathematics; 1988. · Zbl 0681.65029 |
| [89] | Lehoucq, RB; Sorensen, DC; Yang, C., Arpack users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, 6 (1998), Siam · Zbl 0901.65021 |
| [90] | Anderson, E.; Bai, Z.; Bischof, C., Lapack users’ guide (1999), SIAM · Zbl 0755.65028 |
| [91] | He, B, Yuan, X.Convergence analysis of primal-dual algorithms for total variation image restoration. Rapport technique, Citeseer; 2010. |
| [92] | Rockafellar, RT., Monotone operators and the proximal point algorithm, SIAM J Control Optim, 14, 5, 877-898 (1976) · Zbl 0358.90053 |
| [93] | Bezanson, J.; Edelman, A.; Karpinski, S., Julia: A fresh approach to numerical computing, SIAM Rev, 59, 1, 65-98 (2017) · Zbl 1356.68030 |
| [94] | Lawson, CL; Hanson, RJ; Kincaid, DR, Basic linear algebra subprograms for Fortran usage, ACM Trans Math Softw (TOMS), 5, 3, 308-323 (1979) · Zbl 0412.65022 |
| [95] | Anderson, E, Bai, Z, Dongarra, J, et al. Lapack: A portable linear algebra library for high-performance computers. In: Proceedings of the 1990 ACM/IEEE conference on Supercomputing; IEEE Computer Society Press; 1990. p. 2-11. |
| [96] | Legat, B, Dowson, O, Garcia, JD, et al. Mathoptinterface: a data structure for mathematical optimization problems. preprint arXiv:200203447. 2020. |
| [97] | Dunning, I.; Huchette, J.; Lubin, M., Jump: A modeling language for mathematical optimization, SIAM Rev, 59, 2, 295-320 (2017) · Zbl 1368.90002 |
| [98] | Chistov, AL, Grigor’ev, DY.Complexity of quantifier elimination in the theory of algebraically closed fields. In: International symposium on mathematical foundations of computer science; Springer; 1984. p. 17-31. · Zbl 0562.03015 |
| [99] | Karisch, SE; Rendl, F.; Clausen, J., Solving graph bisection problems with semidefinite programming, INFORMS J Comput, 12, 3, 177-191 (2000) · Zbl 1040.90045 |
| [100] | Borchers, B., Sdplib 1.2, a library of semidefinite programming test problems, Optim Methods Soft, 11, 1-4, 683-690 (1999) · Zbl 0973.90522 |
| [101] | Alfakih, AY; Khandani, A.; Wolkowicz, H., Solving euclidean distance matrix completion problems via semidefinite programming, Comput Optim Appl, 12, 1-3, 13-30 (1999) · Zbl 1040.90537 |
| [102] | Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press · Zbl 1058.90049 |
| [103] | So, AMC; Ye, Y., Theory of semidefinite programming for sensor network localization, Math Program, 109, 2-3, 367-384 (2007) · Zbl 1278.90482 |
| [104] | Jaldén, J, Martin, C, Ottersten, B.Semidefinite programming for detection in linear systems-optimality conditions and space-time decoding. In: Acoustics, Speech, and Signal Processing, 2003. Proceedings.(ICASSP’03). 2003 IEEE International Conference on; Vol. 4; IEEE; 2003. p. IV-9. |
| [105] | Jaldén, J.; Ottersten, B., The diversity order of the semidefinite relaxation detector, IEEE Trans Inform Theory, 54, 4, 1406-1422 (2008) · Zbl 1328.94024 |
| [106] | Verdú, S., Computational complexity of optimum multiuser detection, Algorithmica, 4, 1, 303-312 (1989) · Zbl 0684.68066 |
| [107] | Dong, H., Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations, SIAM J Optim, 26, 3, 1962-1985 (2016) · Zbl 1348.90473 |
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.
