×

Efficient semidefinite programming with approximate ADMM. (English) Zbl 1484.90068

Summary: Tenfold improvements in computation speed can be brought to the alternating direction method of multipliers (ADMM) for Semidefinite Programming with virtually no decrease in robustness and provable convergence simply by projecting approximately to the Semidefinite cone. Instead of computing the projections via “exact” eigendecompositions that scale cubically with the matrix size and cannot be warm-started, we suggest using state-of-the-art factorization-free, approximate eigensolvers, thus achieving almost quadratic scaling and the crucial ability of warm-starting. Using a recent result from [P. J. Goulart et al., Linear Algebra Appl. 594, 177–192 (2020; Zbl 1436.65036)], we are able to circumvent the numerical instability of the eigendecomposition and thus maintain tight control on the projection accuracy. This in turn guarantees convergence, either to a solution or a certificate of infeasibility, of the ADMM algorithm. To achieve this, we extend recent results from [G. Banjac et al., J. Optim. Theory Appl. 183, No. 2, 490–519 (2019; Zbl 1429.90050)] to prove that reliable infeasibility detection can be performed with ADMM even in the presence of approximation errors. In all of the considered problems of SDPLIB that “exact” ADMM can solve in a few thousand iterations, our approach brings a significant, up to 20x, speedup without a noticeable increase in ADMM’s iterations.

MSC:

90C22 Semidefinite programming
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aishima, K., Global convergence of the restarted Lanczos and Jacobi-Davidson methods for symmetric eigenvalue problems, Numer. Math., 131, 3, 405-423 (2015) · Zbl 1325.65050
[2] Baillon, JB; Bruck, RE; Reich, S., On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houst. J. Math., 4, 1, 1-9 (1978) · Zbl 0396.47033
[3] Banjac, G.; Goulart, PJ; Stellato, B.; Boyd, S., Infeasibility detection in the alternating direction method of multipliers for convex optimization, J. Optim. Theory Appl., 183, 2, 490-519 (2019) · Zbl 1429.90050
[4] Bauschke, H.; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2017), Cham: Springer, Cham · Zbl 1359.26003
[5] Benzi, M.; Golub, G.; Liesen, J., Numerical solution of saddle point problems, Acta Numer., 14, 1-137 (2005) · Zbl 1115.65034
[6] Boyd, S.; El Ghaoui, L.; Feron, E.; Balakrishnan, V., Linear Matrix Inequalities in System and Control Theory (1994), Philadelphia: SIAM, Philadelphia · Zbl 0816.93004
[7] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122
[8] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[9] d’Aspremont, A., El Ghaoui, L., Jordan, M.I., Lanckriet, G.R.G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3), 434-448 (2007). doi:10.1137/050645506 · Zbl 1128.90050
[10] Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (2000), Philadelphia: SIAM, Philadelphia · Zbl 0965.65058
[11] Eckstein, J.; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 1, 293-318 (1992) · Zbl 0765.90073
[12] Garstka, M.; Cannon, M.; Goulart, PJ, COSMO: a conic operator splitting method for convex conic problems, J. Optim. Theory Appl. (2021) · Zbl 1478.90087
[13] Giselsson, P., Fält, M., Boyd, S.: Line search for averaged operator iteration. ArXiv e-prints arXiv:1603.06772 (2016)
[14] Golub, GH; Van Loan, CF, Matrix Computations (2013), Baltimore: Johns Hopkins University Press, Baltimore · Zbl 1268.65037
[15] Goulart, PJ; Chernyshenko, S., Global stability analysis of fluid flows using sum-of-squares, Physica D, 241, 6, 692-704 (2012) · Zbl 1331.76050
[16] Goulart, PJ; Nakatsukasa, Y.; Rontsis, N., Accuracy of approximate projection to the semidefinite cone, Linear Algebra Appl., 594, 177-192 (2020) · Zbl 1436.65036
[17] Hernandez, V., Roman, J.E., Tomas, A., Vidal, V.: A survey of software for sparse eigenvalue problems. Tech. Rep. STR-6, Universitat Politècnica de València (2009). http://slepc.upv.es
[18] Ishikawa, S., Fixed points and iteration of a nonexpansive mapping in a Banach space, Proc. Am. Math. Soc., 59, 1, 65-71 (1976) · Zbl 0352.47024
[19] Knyazev, AV, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 2, 517-541 (2001) · Zbl 0992.65028
[20] Lanckriet, GRG; Cristianini, N.; Bartlett, P.; El Ghaoui, L.; Jordan, MI, Learning the kernel matrix with semidefinite programming, J. Mach. Learn. Res., 5, 27-72 (2004) · Zbl 1222.68241
[21] Lavaei, J.; Low, SH, Zero duality gap in optimal power flow problem, IEEE Trans. Power Syst., 27, 1, 92-107 (2012)
[22] Lehoucq, R., Sorensen, D., Yang, C.: ARPACK Users’ Guide. SIAM, Philadelphia (1998). doi:10.1137/1.9780898719628
[23] Lemon, A.; So, AMC; Ye, Y., Low-rank semidefinite programming: theory and applications, Found. Trends Optim., 2, 1-2, 1-156 (2016)
[24] Li, Y.; Liu, H.; Wen, Z.; Yuan, Y., Low-rank matrix iteration using polynomial-filtered subspace extraction, SIAM J. Sci. Comput., 42, 3, A1686-A1713 (2020) · Zbl 1452.65069
[25] MOSEK ApS: The MOSEK optimization toolbox for Python manual. http://www.mosek.com/
[26] Nakatsukasa, Y., Sharp error bounds for Ritz vectors and approximate singular vectors, Math. Comput., 89, 324, 1843-1866 (2020) · Zbl 1441.65038
[27] Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer, New York · Zbl 1104.65059
[28] 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). doi:10.1007/s10957-016-0892-3 · Zbl 1342.90136
[29] Orban, D., Arioli, M.: In: Iterative solution of symmetric quasi-definite linear systems, USA (2017). doi:10.1137/1.9781611974737 · Zbl 1409.65004
[30] Paige, CC, Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem, Linear Algebra Appl., 34, 235-258 (1980) · Zbl 0471.65017
[31] Parlett, BN, The Symmetric Eigenvalue Problem (1998), Philadelphia: SIAM, Philadelphia · Zbl 0885.65039
[32] Pazy, A., Asymptotic behavior of contractions in Hilbert space, Isr. J. Math., 9, 2, 235-240 (1971) · Zbl 0225.54032
[33] Prajna, S., Papachristodoulou, A., Parrilo, P.A.: Introducing SOSTOOLS: a general purpose sum of squares programming solver. In: Proceedings of the 41st IEEE Conference on Decision and Control, vol. 1, pp. 741-746 (2002). doi:10.1109/CDC.2002.1184594
[34] Rontsis, N.: Numerical optimization with applications to machine learning. Ph.D. thesis, University of Oxford (2019). https://ora.ox.ac.uk/objects/uuid:1d153c5b-deef-4082-bcea-cf2deb824997
[35] Saad, Y., Numerical Methods for Large Eigenvalue Problems (2011), Philadelphia: SIAM, Philadelphia · Zbl 1242.65068
[36] Souto, M.; Garcia, JD; Veiga, Á., Exploiting low-rank structure in semidefinite programming by approximate operator splitting, Optimization (2020)
[37] Stathopoulos, A.; McCombs, JR, PRIMME: preconditioned iterative multimethod eigensolver: methods and software description, ACM Trans. Math. Softw., 37, 2, 21:1-21:30 (2010) · Zbl 1364.65087
[38] Stellato, B.; Banjac, G.; Goulart, PJ; Bemporad, A.; Boyd, S., OSQP: an operator splitting solver for quadratic programs, Math. Program. Comput., 12, 4, 637-672 (2020) · Zbl 1452.90236
[39] Stewart, G.W.: Matrix Algorithms: Volume 1, Basic Decompositions. SIAM, Philadelphia (1998). doi:10.1137/1.9781611971408 · Zbl 0910.65012
[40] Toh, KC; Todd, MJ; Tütüncü, RH, SDPT3—a MATLAB software package for semidefinite programming, Optim. Methods Softw., 11, 545-581 (1998) · Zbl 0997.90060
[41] Wen, Z.; Goldfarb, D.; Yin, W., Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2, 3, 203-230 (2010) · Zbl 1206.90088
[42] Yamashita, M.; Fujisawa, K.; Kojima, M., Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0), Optim. Methods Softw., 18, 4, 491-505 (2003) · Zbl 1106.90366
[43] Zheng, Y.; Fantuzzi, G.; Papachristodoulou, A.; Goulart, PJ; Wynn, A., Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Math. Program., 180, 1, 489-532 (2020) · Zbl 1434.90126
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.