Mixed-projection conic optimization: A new paradigm for modeling rank constraints



Many central problems in optimization, machine learning, and control theory are equivalent to optimizing a low-rank matrix over a convex set. However, while rank constraints offer unparalleled modeling flexibility, no generic code currently solves these problems to certifiable optimality at even moderate sizes. In this talk, we propose such an approach. To model rank constraints, we introduce symmetric projection matrices that satisfy Y^2 = Y and model the row space of a matrix, the matrix analog of binary variables that satisfy z^2 = z, and model the sparsity of a vector. 

We demonstrate that this modeling paradigm yields tractable convex problems over the non-convex set of projection matrices. Further, we design outer-approximation algorithms to solve low-rank problems to certifiable optimality and demonstrate their efficacy on matrix completion problems. We also study the convex relaxations of low-rank problems, and propose a new preprocessing technique for obtaining strong yet computationally affordable relaxations. The technique leads to a class of new relaxations for several widely-used low-rank models, including matrix completion problems among others. 

Finally, we discuss an ongoing collaboration with OCP-a large Moroccan fertilizer manufacturer-to optimally decarbonize their production process by investing in an appropriate mixture of batteries, solar panels, and transmission lines. All papers mentioned in the talk are available at ryancorywright.github.io


Ryan Cory-Wright is a fifth-year Ph.D. candidate at MIT’s Operations Research Center, advised by Dimitris Bertsimas. His research interests lie at the intersection of optimization, machine learning and statistics, with a focus on their application in energy systems. His current research follows two different threads. First, developing a suite of algorithms that efficiently address interpretable (e.g., sparse or low-rank) optimization problems. Second, integrating renewables within energy markets to combat climate change. He is a recipient of the INFORMS Nicholson Prize (2020), the INFORMS Pierskalla Award (2020), the INFORMS Computing Society Student Paper Award (2019), and the INFORMS Data Mining Section Student Paper Award (2021).