  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.
