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

Abstract

We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy $Y^2=Y$, the matrix analog of binary variables that satisfy $z^2=z$, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization problems over the non-convex set of orthogonal projection matrices. Furthermore, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality, compute lower bounds via their semidefinite relaxations, and provide near-optimal solutions through rounding and local search techniques. We implement these numerical ingredients and, for the first time, solve low-rank optimization problems to certifiable optimality. Using currently available spatial branch-and-bound codes, not tailored to projection matrices, we can scale our exact (resp. near-exact) algorithms to matrices with up to 30 (resp. 600) rows/columns. Our algorithms also supply certifiably near-optimal solutions for larger problem sizes and outperform existing heuristics, by deriving an alternative to the popular nuclear norm relaxation which generalizes the perspective relaxation from vectors to matrices. All in all, our framework, which we name Mixed-Projection Conic Optimization, solves low-rank problems to certifiable optimality in a tractable and unified fashion.

arXiv commentmajor revision submitted to Operations Research

References in corpus (12)

• Nearly unbiased variable selection under minimax concave penalty
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Strong SOCP Relaxations for the Optimal Power Flow Problem
• A Scalable Algorithm For Sparse Portfolio Selection
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• Rank-one Convexification for Sparse Regression
• Mixed-integer convex representability
• A unified approach to mixed-integer optimization problems with logical constraints
• On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems
• 2x2 convexifications for convex quadratic optimization with indicator variables

Cited by in corpus (4)

• A new perspective on low-rank optimization
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach
• Design of Coherent Passive Quantum Equalizers Using Robust Control Theory
• Compact extended formulations for low-rank functions with indicator variables