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

Dimitris Bertsimas (), Ryan Cory-Wright () and Jean Pauphilet ()
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Ryan Cory-Wright: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
Jean Pauphilet: London Business School, London NW1 4SA, United Kingdom

Operations Research, 2022, vol. 70, issue 6, 3321-3344

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 convex optimization problems over the nonconvex 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, to our knowledge, 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. Using currently available spatial branch-and-bound codes, not tailored to projection matrices, we can scale our exact (respectively, near-exact) algorithms to matrices with up to 30 (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.

Keywords: Optimization; rank minimization; semidefinite optimization; global optimization; discrete optimization; outer approximation; regularization; perspective relaxation; matrix completion; nuclear norm (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2182 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:6:p:3321-3344

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().