On polyhedral and second-order cone decompositions of semidefinite optimization problems. (English) Zbl 1525.90320
Summary: We study a cutting-plane method for semidefinite optimization problems and supply a proof of the method’s convergence under a boundedness assumption. By relating the method’s rate of convergence to an initial outer approximation’s diameter, we argue the method performs well when initialized with a second-order cone approximation instead of a linear approximation. We invoke the method to provide bound gaps of 0.5–6.5% for sparse PCA problems with 1000s of covariates, and solve nuclear norm problems over \(500 \times 500\) matrices.
MSC:
| 90C22 | Semidefinite programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Ahmadi, A. A.; Majumdar, A., Dsos and sdsos optimization: more tractable alternatives to sum of squares and semidefinite optimization, SIAM J. Appl. Algebr. Geom., 3, 2, 193-230 (2019) · Zbl 1465.90061 |
| [2] | Berk, L.; Bertsimas, D., Certifiably optimal sparse principal component analysis, Math. Program. Comput., 1-40 (2019) · Zbl 1435.62214 |
| [3] | Bertsekas, D. P., Nonlinear programming, (Athena Scientific (1999)) · Zbl 1015.90077 |
| [4] | Bertsimas, D.; Cory-Wright, R.; Pauphilet, J., A unified approach to mixed-integer optimization: Nonlinear formulations and scalable algorithms (2019) |
| [5] | Braun, G.; Fiorini, S.; Pokutta, S.; Steurer, D., Approximation limits of linear programs (beyond hierarchies), Math. Oper. Res., 40, 3, 756-772 (2015) · Zbl 1343.68308 |
| [6] | Dantzig, G.; Fulkerson, R.; Johnson, S., Solution of a large-scale traveling-salesman problem, J. Oper. Res. Soc. Am., 2, 4, 393-410 (1954) · Zbl 1414.90372 |
| [7] | A. d’Aspremont, L. El Ghaoui, M. Jordan, G. Lanckriet, A direct formulation for sparse pca using semidefinite programming, in: NIPS, 2005, pp. 41-48. |
| [8] | Dunning, I.; Huchette, J.; Lubin, M., Jump: A modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320 (2017) · Zbl 1368.90002 |
| [9] | Fischetti, M.; Ljubić, I.; Sinnl, M., Redesigning benders decomposition for large-scale facility location, Manage. Sci., 63, 7, 2146-2162 (2016) |
| [10] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1990) · Zbl 0704.15002 |
| [11] | Kelley, J. E., The cutting-plane method for solving convex programs, J. Soc. Ind. Appl. Math., 8, 4, 703-712 (1960) · Zbl 0098.12104 |
| [12] | Kim, S.; Kojima, M., Second order cone programming relaxation of nonconvex quadratic optimization problems, Optim. Methods Softw., 15, 3-4, 201-224 (2001) · Zbl 1109.90327 |
| [13] | Kocuk, B.; Dey, S. S.; Sun, X. A., Strong socp relaxations for the optimal power flow problem, Oper. Res., 64, 6, 1177-1196 (2016) · Zbl 1354.90154 |
| [14] | Krishnan, K.; Mitchell, J. E., A unifying framework for several cutting plane methods for semidefinite programming, Optim. Methods Softw., 21, 1, 57-74 (2006) · Zbl 1181.90215 |
| [15] | Lichman, M., Uci machine learning repository (2013), https://archive.ics.uci.edu/ml/datasets.html |
| [16] | Mutapcic, A.; Boyd, S., Cutting-set methods for robust convex optimization with pessimizing oracles, Optim. Methods Softw., 24, 3, 381-406 (2009) · Zbl 1173.90502 |
| [17] | Permenter, F.; Parrilo, P., Partial facial reduction: simplified equivalent sdps via approximations of the psd cone, Math. Program., 171, 1-54 (2018) · Zbl 1405.90098 |
| [18] | Ramana, M. V., An exact duality theory for semidefinite programming and its complexity implications, Math. Program., 77, 1, 129-162 (1997) · Zbl 0890.90144 |
| [19] | Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321 |
| [20] | Ryan, J. A., quantmod: Quantitative financial modelling framework, (R Package (2008)) |
| [21] | Sivaramakrishnan, K. K., Linear Programming Approaches to Semidefinite Programming Problems (2002), RPI, (Ph.D. thesis) |
| [22] | Wolkowicz, H.; Styan, G., Bounds for eigenvalues using traces, Linear Algebr. Appl., 29, 471-506 (1980) · Zbl 0435.15015 |
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.
