Accelerated first-order methods for a class of semidefinite programs
Tóm tắt
This paper introduces a new storage-optimal first-order method, CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs, is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a certificate of strict complementarity to construct a low-dimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. From an algorithmic standpoint, we show how to construct the necessary certificate and how to solve the minimax problem efficiently. Our algorithms for strongly convex minimax problems with inexact prox maps may be of independent interest. We accompany our theoretical results with preliminary numerical experiments suggesting that CertSDP significantly outperforms current state-of-the-art methods on large sparse exact QMP-like SDPs.
Từ khóa
Tài liệu tham khảo
Abbe, E., Bandeira, A.S., Hall, G.: Exact recovery in the stochastic block model. IEEE Trans. Inform. Theory 62(1), 471–487 (2015)
Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13–51 (1995)
Alizadeh, F., Haeberly, J.A., Overton, M.L.: Complementarity and nondegeneracy in semidefinite programming. Math. Program. 77, 111–128 (1997)
Argue, C.J., Kılınç-Karzan, F., Wang, A.L.: Necessary and sufficient conditions for rank-one generated cones. Math. Oper. Res. 48(1), 100–126 (2023)
Baes, M., Burgisser, M., Nemirovski, A.: A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems. SIAM J. Optim. 23(2), 934–962 (2013)
Beck, A.: Quadratic matrix programming. SIAM J. Optim. 17(4), 1224–1238 (2007)
Beck, A., Drori, Y., Teboulle, M.: A new semidefinite programming relaxation scheme for a class of quadratic matrix problems. Oper. Res. Lett. 40(4), 298–302 (2012)
Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization, volume 2 of MPS-SIAM Series on Optimization. SIAM (2001)
Ben-Tal, A., Nemirovski, A.: Solving large scale polynomial convex problems on \(\ell _1\)/nuclear norm balls by randomized first-order algorithms. In: CoRR (2012)
Boumal, N., Voroninski, V., Bandeira, A.: The non-convex Burer–Monteiro approach works on smooth semidefinite programs. In: Advances in Neural Information Processing Systems, vol. 29 (2016)
Burer, S., Kılınç-Karzan, F.: How to convexify the intersection of a second order cone and a nonconvex quadratic. Math. Program. 162, 393–429 (2017)
Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329–357 (2003)
Burer, S., Yang, B.: The trust region subproblem with non-intersecting linear constraints. Math. Program. 149, 253–264 (2014)
Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math. Program. 181, 1–17 (2019)
Candès, E.J., Eldar, Y.C., Strohmer, T., Voroninski, V.: Phase retrieval via matrix completion. SIAM Rev. 57(2), 225–251 (2015)
Carmon, Y., Duchi, J.C.: Analysis of Krylov subspace solutions of regularized nonconvex quadratic problems. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 10728–10738 (2018)
Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Math. Program. 159, 253–287 (2016)
Cifuentes, D.: On the Burer–Monteiro method for general semidefinite programs. Opt. Lett. 15(6), 2299–2309 (2021)
Cifuentes, D., Moitra, A.: Polynomial time guarantees for the Burer–Monteiro method. Adv. Neural. Inf. Process. Syst. 35, 23923–23935 (2022)
d’Aspremont, A., El Karoui, N.: A stochastic smoothing algorithm for semidefinite programming. SIAM J. Optim. 24(3), 1138–1177 (2014)
de Carli-Silva, M.K., Tunçel, L.: Strict complementarity in semidefinite optimization with elliptopes including the maxcut SDP. SIAM J. Optim. 29(4), 2650–2676 (2019)
Devolder, O., Glineur, F., Nesterov, Y.: First-Order Methods with Inexact Oracle: The Strongly Convex Case. Technical Report 2013016 (2013)
Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146(1), 37–75 (2014)
Ding, L., Udell, M.: On the simplicity and conditioning of low rank semidefinite programs. SIAM J. Optim. 31(4), 2614–2637 (2021)
Ding, L., Wang, A.L.: Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery (2023). arXiv:2307.06873
Ding, L., Yurtsever, A., Cevher, V., Tropp, J.A., Udell, M.: An optimal-storage approach to semidefinite programming using approximate complementarity. SIAM J. Optim. 31(4), 2695–2725 (2021)
Ding, L., Yurtsever, A., Cevher, V., Tropp, J.A., Udell, M.: An optimal-storage approach to semidefinite programming using approximate complementarity. SIAM J. Optim. 31(4), 2695–2725 (2021)
Drusvyatskiy, D., Lewis, A.S.: Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3), 919–948 (2018)
Fradkov, A.L., Yakubovich, V.A.: The S-procedure and duality relations in nonconvex problems of quadratic programming. Vestnik Leningrad Univ. Math. 6, 101–109 (1979)
Friedlander, M.P., Macêdo, I.: Low-rank spectral optimization via gauge duality. SIAM J. Sci. Comput. 38(3), A1616–A1638 (2016)
Garber, D., Kaplan, A. A.: On the efficient implementation of the matrix exponentiated gradient algorithm for low-rank matrix optimization. Math. Oper. Res. (2022)
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
Goldfarb, D., Scheinberg, K.: Interior point trajectories in semidefinite programming. SIAM J. Optim. 8(4), 871–886 (1998)
Hamedani, E.Y., Aybat, N.C.: A primal–dual algorithm with line search for general convex–concave saddle point problems. SIAM J. Optim. 31(2), 1299–1329 (2021)
Hazan, E., Koren, T.: A linear-time algorithm for trust region problems. Math. Program. 158, 363–381 (2016)
Ho-Nguyen, N., Kılınç-Karzan, F.: A second-order cone based approach for solving the Trust Region Subproblem and its variants. SIAM J. Optim. 27(3), 1485–1512 (2017)
Jeyakumar, V., Li, G.Y.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Program. 147, 171–206 (2014)
Jiang, R., Li, D.: Novel reformulations and efficient algorithms for the Generalized Trust Region Subproblem. SIAM J. Optim. 29(2), 1603–1633 (2019)
Juditsky, A., Nemirovski, A.: First order methods for non-smooth convex large-scale optimization, ii: utilizing problems structure. Optim. Mach. Learn. 30(9), 149–183 (2011)
Kılınç-Karzan, F., Wang, A.L.: Exactness in SDP relaxations of QCQPs: theory and applications. Tut. Oper. Res. Informs (2021)
Lan, G., Lu, Z., Monteiro, R.D.C.: Primal–dual first-order methods with \(o(1/\epsilon )\) iteration-complexity for cone programming. Math. Program. 126, 1–29 (2011)
Laurent, M., Poljak, S.: On a positive semidefinite relaxation of the cut polytope. Linear Algebra Appl. 223–224, 439–461 (1995)
Levy, K.Y., Yurtsever, A., Cevher, V.: Online adaptive methods, universality and acceleration. In: Advances in Neural Information Processing Systems (2018)
Locatelli, M.: Exactness conditions for an SDP relaxation of the extended trust region problem. Oper. Res. Lett. 10(6), 1141–1151 (2016)
Locatelli, M.: KKT-based primal–dual exactness conditions for the Shor relaxation. J. Glob. Optim. 86(2), 285–301 (2023)
Lu, Z., Nemirovski, A., Monteiro, R.D.C.: Large-scale semidefinite programming via a saddle point mirror-prox algorithm. Math. Program. 109, 211–237 (2007)
Majumdar, A., Hall, G., Ahmadi, A.A.: Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Annu. Rev. Control Robot. Auton. Syst. 3, 331–360 (2020)
Mixon, D.G., Villar, S., Ward, R.: Clustering subgaussian mixtures by semidefinite programming. Inf. Inference J. IMA 6(4), 389–415 (2017)
Moré, J.J.: Generalizations of the Trust Region Problem. Optim. Methods Softw. 2(3–4), 189–209 (1993)
Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983)
Nemirovski, A.: Prox-method with rate of convergence o(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex–concave saddle point problems. SIAM J. Optim. 15(1), 229–251 (2004)
Nesterov, Y.: Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16(1), 235–249 (2005)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127–152 (2005)
Nesterov, Y.: Lectures on convex optimization. Springer Optimization and Its Applications, vol. 137. Springer (2018)
Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)
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)
Ouyang, Y., Xu, Y.: Lower complexity bounds of first-order methods for convex–concave bilinear saddle-point problems. Math. Program. 185, 1–35 (2021)
Palaniappan, B., Bach, F.: Stochastic variance reduction methods for saddle-point problems. In: Advances in Neural Information Processing Systems, vol. 29 (2016)
Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 245–254 (2008)
Rujeerapaiboon, N., Schindler, K., Kuhn, D., Wiesemann, W.: Size matters: cardinality-constrained clustering and outlier detection via conic optimization. SIAM J. Optim. 29(2), 1211–1239 (2019)
Sard, A.: The measure of the critical values of differentiable maps. Bull. Am. Math. Soc. 48(12), 883–890 (1942)
Shinde, N., Narayanan, V., Saunderson, J.: Memory-efficient structured convex optimization via extreme point sampling. SIAM J. Math. Data Sci. 3(3), 787–814 (2021)
Shor, N.Z.: Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25, 163–168 (1990)
Sion, M.: On general minimax theorems. Pac. J. Math. 8(1), 171–176 (1958)
Souto, M., Garcia, J.D., Veiga, Á.: Exploiting low-rank structure in semidefinite programming by approximate operator splitting. Optimization 1–28 (2020)
Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2), 246–267 (2003)
Tseng, P.: On accelerated proximal gradient methods for convex–concave optimization (2008)
Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49–95 (1996)
Waldspurger, I., Waters, A.: Rank optimality for the Burer–Monteiro factorization. SIAM J. Optim. 30(3), 2577–2602 (2020)
Wang, A.L., Kılınç-Karzan, F.: A geometric view of SDP exactness in QCQPs and its applications (2020). arXiv:2011.07155
Wang, A.L., Kılınç-Karzan, F.: The generalized trust region subproblem: solution complexity and convex hull results. Math. Program. 191(2), 445–486 (2022)
Wang, A.L., Kılınç-Karzan, F.: On the tightness of SDP relaxations of QCQPs. Math. Program. 193(1), 33–73 (2022)
Wang, A.L., Lu, Y., Kılınç-Karzan, F.: Implicit regularity and linear convergence rates for the generalized trust-region subproblem. SIAM J. Optim. 33(2), 1250–1278 (2023)
Yang, H., Liang, L., Carlone, L., Toh, K.: An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization. Math. Program. 201(1–2), 409–472 (2023)
Yurtsever, A., Fercoq, O., Cevher, V.: A conditional-gradient-based augmented Lagrangian framework. In: International Conference on Machine Learning, pp. 7272–7281 (2019)
Yurtsever, A., Tropp, J.A., Fercoq, O., Udell, M., Cevher, V.: Scalable semidefinite programming. SIAM J. Math. Data Sci. 3(1), 171–200 (2021)