Details
Department of Industrial & Systems Engineering Seminar Series
Speaker: Andrés Gómez (University of Southern California)
Abstract: Mixed-integer quadratic optimization with on/off decisions (MIQO) arises in finance, statistics, and control. In finance, such problems arise when selecting a sparse portfolio with high return and low variance; in this setting, the matrix defining the quadratic term is often low rank. In statistics, when fitting sparse models with time series data, the resulting MIQO problems have a banded matrix. In hybrid model predictive control, in which the system under study can switch modes of operation, natural formulations result in MIQO problems with a matrix with a sparse inverse. Unfortunately, for most MIQO problems considered, standard formulations ignore most of the structure of this matrix and rely on big-M formulations, resulting in weak relaxations and poor algorithms.
In this talk, I will present a unified approach based on decision diagrams, which encode discrete choices as paths through a graph. The same construction supports optimization and produces ideal conic quadratic extended formulations of the closed convex hull of quadratic epigraphs with indicator constraints. It also accommodates combinatorial restrictions that admit tractable dynamic programs. While the proposed approach yields algorithms with exponential runtimes in general, we show that it has polynomial runtime when the matrix is low-rank, sparse or its inverse is sparse.
Joint work with: Soobin Choi, Salar Fattahi, Shaoning Han, and Leonardo Lozano
Bio: Andrés Gómez is an Associate Professor and the Epstein Family Early Career Chair in the Daniel J. Epstein Department of Industrial and Systems Engineering at the University of Southern California. His research combines discrete and nonlinear optimization to develop methods for problems in machine learning, statistics, and finance, with an emphasis on strong convex relaxations. He received his Ph.D. in Industrial Engineering and Operations Research from the University of California, Berkeley, in 2017 and previously served on the faculty at the University of Pittsburgh. His honors include the INFORMS Computing Society Prize, the AFOSR Young Investigator Award, and a Google Research Scholar award.