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

Pauphilet, J, Bertsimas, D and Cory-Wright, R (2021) Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints. Operations Research. ISSN 0030-364X (Accepted)

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 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 semidenite 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. 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. 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. 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.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Date Deposited: 23 Aug 2021 10:49
Date of first compliant deposit: 23 Aug 2021
Subjects: P > Programming languages
Last Modified: 23 Aug 2021 10:50
URI: https://lbsresearch.london.edu/id/eprint/1923
More

Export and Share


Download

Accepted Version - Text
  • Restricted to Repository staff only

Statistics

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item