Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

References

• Achterberg T, Towle E (2020) Gurobi webinar: Non-convex quadratic optimization. Accessed February 9, 2021, https://www.gurobi.com/resource/non-convex-quadratic-optimization/.Google Scholar
• Ahmadi AA, Majumdar A (2019) DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geometry 3(2):193–230.Crossref, Google Scholar
• Aktürk MS, Atamtürk A, Gürel S (2009) A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37(3):187–191.Crossref, Google Scholar
• Atamtürk A, Gomez A (2019) Rank-one convexification for sparse regression. Preprint, submitted January 29, https://arxiv.org/abs/1901.10334.Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (2000) A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Programming 87(1):131–152.Crossref, Google Scholar
• Bai L, Mitchell JE, Pang J-S (2016) On conic QPCCs, conic QCQPs and completely positive programs. Math. Programming 159(1):109–136.Crossref, Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• Belotti P, Kirches C, Leyffer S, Linderoth J, Luedtke J, Mahajan A (2013) Mixed-Integer Nonlinear Optimization. Acta Numerica, vol. 22 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization, vol. 2 (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Bertsekas DP (2016) Nonlinear Programming, 3rd ed. (Athena Scientific, Belmont, MA).Google Scholar
• Bertsimas D, Cory-Wright R (2020) On polyhedral and second-order cone decompositions of semidefinite optimization problems. Oper. Res. Lett. 48(1):78–85.Crossref, Google Scholar
• Bertsimas D, Cory-Wright R (2022) A scalable algorithm for sparse portfolio selection. INFORMS J. Comput. 34(3):1489–1511.Google Scholar
• Bertsimas D, Copenhaver MS, Mazumder R (2017) Certifiably optimal low rank factor analysis. J. Machine Learn. Res. 18(1):907–959.Google Scholar
• Bertsimas D, Cory-Wright R, Pauphilet J (2021) A unified approach to mixed-integer optimization problems with logical constraints. SIAM J. Optim. 31(3):2340–2367.Crossref, Google Scholar
• Bertsimas D, Pauphilet J, van Parys B (2020) Sparse regression: Scalable algorithms and empirical performance. Statist. Sci. 35(4):555–578.Google Scholar
• Bhojanapalli S, Neyshabur B, Srebro N (2016) Global optimality of local search for low rank matrix recovery. Preprint, submitted May 23, https://arxiv.org/abs/1605.07221.Google Scholar
• Bi S, Pan S, Sun D (2020) A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery. Math. Programming Comput. 12(4):569–602.Crossref, Google Scholar
• Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite Optimization and Convex Algebraic Geometry (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Bonami P, Biegler LT, Conn AR, Cornuéjols G, Grossmann IE, Laird CD, Lee J, et al. (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim. 5(2):186–204.Crossref, Google Scholar
• Boumal N, Voroninski V, Bandeira A (2016) The non-convex Burer-Monteiro approach works on smooth semidefinite programs. Conf. Neural Inform. Processing Systems, 2757–2765.Google Scholar
• Boumal N, Voroninski V, Bandeira AS (2020) Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. Comm. Pure Appl. Math. 73(3):581–608.Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Boyd S, El Ghaoui L, Feron E, Balakrishnan V (1994) Linear Matrix Inequalities in System and Control Theory, vol. 15. (Society for Industrial and Applied Mathematics, Philadelphia).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
• Candès EJ, Plan Y (2010) Matrix completion with noise. Proc. IEEE 98(6):925–936.Crossref, Google Scholar
• Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Foundations Comput. Math. 9(6):717.Crossref, Google Scholar
• Chistov AL, Grigoriev DY (1984) Complexity of quantifier elimination in the theory of algebraically closed fields. Internat. Sympos. Math. Foundations Comput. Sci. Lecture Notes in Computer Science, vol. 176 (Springer Verlag, Berlin), 17–31.Google Scholar
• Cifuentes D (2019) Burer-Monteiro guarantees for general semidefinite programs. Preprint, submitted April 15, https://arxiv.org/abs/1904.07147.Google Scholar
• Coey C, Lubin M, Vielma JP (2020) Outer approximation with conic certificates for mixed-integer convex problems. Math. Programming Comput. 12:249–293.Crossref, Google Scholar
• Cox D, Little J, O’Shea D (2013) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (Springer Science & Business Media, New York).Google Scholar
• d’Aspremont A (2003) A semidefinite representation for some minimum cardinality problems. 42nd IEEE Internat. Conf. Decision Control, vol. 5 (IEEE), 4985–4990.Google Scholar
• d’Aspremont A, El Ghaoui L, Jordan MI, Lanckriet GR (2007) A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3):434–448.Crossref, Google Scholar
• Ding C, Sun D, Jane JY (2014) First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints. Math. Programming 147(1):539–579.Crossref, Google Scholar
• Dong H, Chen K, Linderoth J (2015) Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. Preprint, submitted October 20, https://arxiv.org/abs/1510.06083.Google Scholar
• Douglas J, Rachford HH (1956) On the numerical solution of heat conduction problems in two and three space variables. Trans. Amer. Math. Soc. 82(2):421–439.Crossref, Google Scholar
• Duran MA, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Programming 36(3):307–339.Crossref, Google Scholar
• Eckstein J, Bertsekas DP (1992) On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Programming 55(1):293–318.Crossref, Google Scholar
• Fan J, Li R (2001) Variable selection via nonconcave penalized likelihood and its oracle properties. J. Amer. Statist. Assoc. 96(456):1348–1360.Crossref, Google Scholar
• Fazel M (2002) Matrix rank minimization with applications. Unpublished PhD thesis, Stanford University, CA.Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2017) Redesigning Benders decomposition for large-scale facility location. Management Sci. 63(7):2146–2162.Link, Google Scholar
• Ge R, Lee JD, Ma T (2016) Matrix completion has no spurious local minimum. Preprint, submitted May 24, https://arxiv.org/abs/1605.07272.Google Scholar
• Glover F (1975) Improved linear integer programming formulations of nonlinear integer problems. Management Sci. 22(4):455–460.Link, 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
• Grossmann IE (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Engrg. 3(3):227–252.Crossref, Google Scholar
• Grötschel M, Wakabayashi Y (1989) A cutting plane algorithm for a clustering problem. Math. Programming 45(1–3):59–96.Crossref, Google Scholar
• Günlük O, Linderoth J (2012) Perspective reformulation and applications. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming (Springer, New York), 61–89.Crossref, Google Scholar
• Hazimeh H, Mazumder R, Saab A (2021) Sparse regression at scale: Branch-and-bound rooted in first-order optimization. Math. Programming, ePub ahead of print October 18, https://doi.org/10.1007/s10107-021-01712-4.Google Scholar
• Horn RA, Johnson CR (1985) Matrix Analysis (Cambridge University Press, New York).Crossref, Google Scholar
• Jain P, Netrapalli P, Sanghavi S (2013) Low-rank matrix completion using alternating minimization. Proc. 45th ACM Sympos. Theory Comput., 665–674.Google Scholar
• Kelley JE Jr (1960) The cutting-plane method for solving convex programs. J. Soc. Indust. Appl. Math. 8(4):703–712.Crossref, Google Scholar
• Kocuk B, Dey SS, Sun XA (2016) Strong SOCP relaxations for the optimal power flow problem. Oper. Res. 64(6):1177–1196.Link, Google Scholar
• Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.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
• Lee J, Zou B (2014) Optimal rank-sparsity decomposition. J. Global Optim. 60(2):307–315.Crossref, Google Scholar
• Linderoth J (2005) A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Programming 103(2):251–282.Crossref, Google Scholar
• Lubin M, Vielma JP, Zadik I (2021) Mixed-integer convex representability. Math Oper. Res., ePub ahead of print October 5, https://doi.org/10.1287/moor.2021.1146.Google Scholar
• Luo Z-Q, Pang J-S, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part i—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• Naldi S (2018) Solving rank-constrained semidefinite programs in exact arithmetic. J. Symbolic Comput. 85:206–223.Crossref, Google Scholar
• Nemirovski A, Roos C, Terlaky T (1999) On maximization of quadratic form over intersection of ellipsoids with common center. Math. Programming 86(3):463–473.Crossref, Google Scholar
• Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Crossref, Google Scholar
• Nesterov Y (2007) Smoothing technique and its applications in semidefinite optimization. Math. Programming 110(2):245–259.Crossref, Google Scholar
• Nguyen LT, Kim J, Shim B (2019) Low-rank matrix completion: A contemporary survey. IEEE Access 7:94215–94237.Crossref, Google Scholar
• Overton ML, Womersley RS (1992) On the sum of the largest eigenvalues of a symmetric matrix. SIAM J. Matrix Anal. Appl. 13(1):41–45.Crossref, Google Scholar
• Peng J, Wei Y (2007) Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim. 18(1):186–205.Crossref, Google Scholar
• Peng J, Xia Y (2005) A new theoretical framework for k-means-type clustering. Chu W, Lin TY, eds. Foundations and Advances in Data Mining (Springer, Berlin), 79–96.Google Scholar
• Pilanci M, Wainwright MJ, El Ghaoui L (2015) Sparse learning via Boolean relaxations. Math. Programming 151(1):63–87.Crossref, Google Scholar
• Quesada I, Grossmann IE (1992) An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput. Chemical Engrg. 16(10–11):937–947.Crossref, Google Scholar
• Recht B, Ré C (2013) Parallel stochastic gradient algorithms for large-scale matrix completion. Math. Programming Comput. 5(2):201–226.Crossref, Google Scholar
• Recht B, Fazel M, Parrilo P (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3):471–501.Crossref, Google Scholar
• Renegar J (1992) On the computational complexity and geometry of the first-order theory of the reals. Part I-III. J. Symbolic Comput. 13(3):255–352.Crossref, Google Scholar
• Sherali HD, Fraticelli BM (2002) Enhancing RLT relaxations via a new class of semidefinite cuts. J. Global Optim. 22(1–4):233–261.Crossref, Google Scholar
• Tu S, Boczar R, Simchowitz M, Soltanolkotabi M, Recht B (2016) Low-rank solutions of linear matrix equations via procrustes flow. Internat. Conf. Machine Learn. (PMLR), 964–973.Google Scholar
• Udell M, Horn C, Zadeh R, Boyd S (2016) Generalized low rank models. Foundations Trends Machine Learn. 9:1–118.Google Scholar
• Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev. 38(1):49–95.Crossref, Google Scholar
• Wen Z, Yin W, Zhang Y (2012) Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Programming Comput. 4(4):333–361.Crossref, Google Scholar
• Zhang C-H (2010) Nearly unbiased variable selection under minimax concave penalty. Ann. Statist. 38(2):894–942.Crossref, Google Scholar
• Zhang H, Lin Z, Zhang C (2013) A counterexample for the validity of using nuclear norm as a convex surrogate of rank. Euro. Conf. Machine Learn. Knowledge Discovery Databases (Springer, Berlin), 226–241.Google Scholar
• Zheng Q, Lafferty J (2015) A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements. Preprint, submitted June 19, https://arxiv.org/abs/1506.06081.Google Scholar
• Zheng X, Sun X, Li D (2014) Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach. INFORMS J. Comput. 26(4):690–703.Link, Google Scholar