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

arXiv: https://arxiv.org/abs/2009.10395 · HTML: https://mlsanity.com/paper/2009.10395/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2020.

## Built on by (most cited first, 13 of 13)

- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [Sparse PCA With Multiple Components](https://mlsanity.com/paper/2209.14790/) (2022)
- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (2024)
- [Disjunctive Branch-and-Bound for Certifiably Optimal Low-Rank Matrix Completion](https://mlsanity.com/paper/2305.12292/) (2023)
- [Robust support vector machines via conic optimization](https://mlsanity.com/paper/2402.01797/) (2024)
- [Predictive Low Rank Matrix Learning under Partial Observations: Mixed-Projection ADMM](https://mlsanity.com/paper/2407.13731/) (2024)
- [Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization](https://mlsanity.com/paper/2501.02942/) (2025)
- [Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness](https://mlsanity.com/paper/2508.00091/) (2025)
- [Compact Lifted Relaxations for Low-Rank Optimization](https://mlsanity.com/paper/2603.20228/) (2026)

## Abstract (arXiv)

We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy Y2=Y, the matrix analog of binary variables that satisfy z2=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.