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

Wednesday, March 17, 2021 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Ryan Cory-Wright

Affiliation

ORC

Zoom meeting id

975 1087 2986

Join Zoom meeting

https://mit.zoom.us/j/97510872986

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 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. 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. ArXiV link: https://arxiv.org/abs/2009.10395

 

Biography

Ryan Cory-Wright is a fourth-year Ph.D. candidate at the MIT Operations Research Center, advised by Dimitris Bertsimas. He is broadly interested in mathematical optimization and its applications in statistics, finance, and energy markets. His current research involves developing new methodological techniques for optimization problems which function at scale, in particular developing a suite of cutting-plane methods which address mixed-integer/low-rank problems. Prior to attending MIT, he received a B.E. (Hons) degree in Engineering Science from the University of Auckland. He is a recipient of the INFORMS George Nicholson Best Student Paper Award (2020), the INFORMS William Pierskalla Best Paper Award (2020), the INFORMS Computing Society Best Student Paper Award (2019), and the Operations Research Society of New Zealand Best Student Paper Award (2016).