A Low-Rank ADMM Splitting Approach for Semidefinite Programming

References

• Alizadeh F (1991) Combinatorial optimization with interior point methods and semi-definite matrices. Unpublished PhD thesis, University of Minnesota, Minneapolis.Google Scholar
• Alizadeh F (1995) Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1):13–51.Crossref, Google Scholar
• Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J, Du Croz J, et al. (1999) LAPACK Users’ Guide, 3rd ed. (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Math. Programming 137(1–2):91–129.Crossref, Google Scholar
• Barvinok AI (1995) Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geometry 13(2):189–202.Crossref, Google Scholar
• Bellavia S, Gondzio J, Porcelli M (2021) A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion. J. Sci. Comput. 89(2):46.Crossref, Google Scholar
• Biswas P, Ye Y (2004) Semidefinite programming for ad hoc wireless sensor network. Proc. Third Internat. Sympos. Inform. Processing Sensor Networks (Association for Computing Machinery, New York), 46–54.Google Scholar
• Biswas P, Lian TC, Wang TC, Ye Y (2006) Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sensor Networks 2(2):188–220.Crossref, Google Scholar
• Blackford LS, Petitet A, Pozo R, Remington K, Whaley RC, Demmel J, Dongarra J, et al. (2002) An updated set of basic linear algebra subprograms (BLAS). ACM Trans. Math. Software 28(2):135–151.Crossref, Google Scholar
• Boumal N (2015) A Riemannian low-rank method for optimization over semidefinite matrices with block-diagonal constraints. Preprint, submitted June 1, https://arxiv.org/abs/1506.00575.Google Scholar
• Boyd S, Vandenberghe L (1997) Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization. Paulraj A, Roychowdhury V, Schaper CD, eds. Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath (Springer, New York), 279–287.Crossref, Google Scholar
• Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, vol. 3 (IEEE, Piscataway, NJ), 1–122.Google Scholar
• Burer S, Choi C (2006) Computational enhancements in low-rank semidefinite programming. Optim. Methods Software 21(3):493–512.Crossref, Google Scholar
• Burer S, Monteiro RD (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95(2):329–357.Crossref, Google Scholar
• Burer S, Monteiro RD (2005) Local minima and convergence in low-rank semidefinite programming. Math. Programming 103(3):427–444.Crossref, Google Scholar
• Chen Y, Goulart P (2023) Burer-Monteiro ADMM for large-scale SDPs. Preprint, submitted February 8, https://arxiv.org/abs/2302.04016.Google Scholar
• Erdogdu MA, Ozdaglar A, Parrilo PA, Vanli ND (2022) Convergence rate of block-coordinate maximization Burer–Monteiro method for solving large SDPs. Math. Programming 195(1–2):243–281.Crossref, Google Scholar
• Gao W, Ge D, Ye Y (2022) HDSDP: Software for semidefinite programming. Preprint, submitted July 28, https://arxiv.org/abs/2207.13862.Google Scholar
• Ge D, Huangfu Q, Wang Z, Wu J, Ye Y (2022) Cardinal optimizer (COPT) user guide. Preprint, submitted November 16, https://arxiv.org/pdf/2208.14314.Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Han Q, Li C, Lin Z, Chen C, Deng Q, Ge D, Liu H, Ye Y (2025) A low-rank ADMM splitting approach for semidefinite programming. https://doi.org/10.1287/ijoc.2024.07071.cd, https://github.com/INFORMSJoC/2024.0701.Google Scholar
• He BS, Yang H, Wang S (2000) Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106:337–356.Crossref, Google Scholar
• Journée M, Bach F, Absil PA, Sepulchre R (2010) Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim. 20(5):2327–2351.Crossref, Google Scholar
• Lan G, Lu Z, Monteiro RD (2011) Primal-dual first-order methods with iteration-complexity for cone programming. Math. Programming 126(1):1–29.Crossref, Google Scholar
• Lavaei J, Low SH (2011) Zero duality gap in optimal power flow problem. IEEE Trans. Power Systems 27(1):92–107.Crossref, Google Scholar
• Lei M, Zhang J, Ye Y (2023) Blessing of high-order dimensionality: From non-convex to convex optimization for sensor network localization. Preprint, submitted August 4, https://arxiv.org/abs/2308.02278.Google Scholar
• Li XP, Huang L, So HC, Zhao B (2019) A survey on matrix completion: Perspective of signal processing. Preprint, submitted January 25, https://arxiv.org/abs/1901.10885.Google Scholar
• Lin T, Ma S, Zhang S (2015) On the global linear convergence of the ADMM with multiblock variables. SIAM J. Optim. 25(3):1478–1497.Crossref, Google Scholar
• Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169:1042–1068.Crossref, Google Scholar
• Pataki G (1998) On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2):339–358.Link, Google Scholar
• Shamsi D, Taheri N, Zhu Z, Ye Y (2012) On sensor network localization using SDP relaxation. Preprint, submitted October 11, https://arxiv.org/abs/1010.2262.Google Scholar
• So AMC, Ye Y (2007) Theory of semidefinite programming for sensor network localization. Math. Programming 109(2–3):367–384.Crossref, Google Scholar
• So AMC, Ye Y, Zhang J (2008) A unified theorem on SDP rank reduction. Math. Oper. Res. 33(4):910–920.Link, Google Scholar
• Sun D, Toh KC, Yuan Y, Zhao XY (2019) SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Software 35(1):87–115.Google Scholar
• Tang T, Toh KC (2024) A feasible method for general convex low-rank SDP problems. SIAM J. Optim. 34(3):2169–2200.Crossref, Google Scholar
• Wang J, Hu L (2023) Solving low-rank semidefinite programs via manifold optimization. J. Sci. Comput. 104(1):33.Google Scholar
• Wang Y, Deng K, Liu H, Wen Z (2023) A decomposition augmented Lagrangian method for low-rank semidefinite programming. SIAM J. Optim. 33(3):1361–1390.Crossref, Google Scholar
• Wang Z, Zheng S, Ye Y, Boyd S (2008) Further relaxations of the semidefinite programming approach to sensor network localization. SIAM J. Optim. 19(2):655–673.Crossref, Google Scholar
• Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math. Programming 142(1–2):397–434.Crossref, Google Scholar
• Wen Z, Goldfarb D, Yin W (2010) Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Programming Comput. 2(3–4):203–230.Crossref, Google Scholar
• Xie Y, Wright SJ (2021) Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints. J. Sci. Comput. 86:38.Crossref, Google Scholar
• Yalçin B, Ma Z, Lavaei J, Sojoudi S (2023) Semidefinite programming versus Burer-Monteiro factorization for matrix sensing. Proc. AAAI Conf. Artificial Intelligence, vol. 37 (AAAI Press, Washington, DC), 10702–10710.Google Scholar
• Yang L, Sun D, Toh KC (2015) SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Programming Comput. 7(3):331–366.Crossref, Google Scholar
• Ye Y (2003) Gset. https://web.stanford.edu/∼yyye/yyye/Gset/.Google Scholar
• Yurtsever A, Udell M, Tropp J, Cevher V (2017) Sketchy decisions: Convex low-rank matrix optimization with optimal storage. Artificial Intelligence and Statistics (PMLR, New York), 1188–1196.Google Scholar
• Yurtsever A, Tropp JA, Fercoq O, Udell M, Cevher V (2021) Scalable semidefinite programming. SIAM J. Math. Data Sci. 3(1):171–200.Crossref, Google Scholar
• Zhao XY, Sun D, Toh KC (2010) A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4):1737–1765.Crossref, Google Scholar