Skip to main content

Please enter a keyword and click the arrow to search the site

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

Journal

Operations Research

Subject

Management Science and Operations

Authors / Editors

Bertsimas D;Cory-Wright R;Pauphilet J

Biographies

Publication Year

2021

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.

Available on ECCH

No


Select up to 4 programmes to compare

Select one more to compare
×
subscribe_image_desktop 5949B9BFE33243D782D1C7A17E3345D0

Sign up to receive our latest news and business thinking direct to your inbox

×

Sign up to receive our latest course information and business thinking

Leave your details above if you would like to receive emails containing the latest thought leadership, invitations to events and news about courses that could enhance your career. If you would prefer not to receive our emails, you can still access the case study by clicking the button below. You can opt-out of receiving our emails at any time by visiting: https://london.edu/my-profile-preferences or by unsubscribing through the link provided in our emails. View our Privacy Policy for more information on your rights.