Mixed-integer linear optimization (MILO) solvers have come a long way in the past couple of decades, enabling the solution of practical large-scale problems that were previously deemed unsolvable. Mixed-integer convex optimization (MICO) is the next frontier; however, it is not clear how polyhedral theory which has fueled the revolution in MILO solvers, can be leveraged for mixed-integer convex sets. To this end—motivated by recent applications in statistical learning—we consider a broad class of MICO problems which include indicator variables associated with continuous variables, and arbitrary constraints on indicators. First, we give a convexification scheme that simultaneously considers a nonlinear non-separable objective and combinatorial constraints on indicators. Second, for the convex quadratic case, we give a convex hull description of the epigraph formulation, which consists of a quadratic number of additional variables, a single positive semidefinite constraint, and linear constraints describing a polyhedral set in an extended formulation. The new theory presented here unifies and generalizes previously established results for special cases, e.g., perspective reformulation for separable functions. It also paves the path toward employing polyhedral methods to strengthen MICO models, thereby bridging the gap between MILO and MICO. We conclude with a novel decomposition method for convex quadratic optimization problems with indicator variables when the matrix defining the quadratic term in the objective is sparse. Our computational experiments with sparse structured regression problems demonstrate the effectiveness of the proposed approaches. 

Bio:   Simge Küçükyavuz is a Professor in the Industrial Engineering and Management Sciences Department at Northwestern University. She is an expert in mixed-integer, large-scale, and stochastic optimization. Her methodologies have applications in complex computational problems across numerous domains, including social networks, computing and energy infrastructure, statistical learning, and logistics. Her research has been supported by multiple grants from the National Science Foundation (NSF) and the Office of Naval Research (ONR). She is the recipient of the NSF CAREER Award and the INFORMS Computing Society (ICS) Prize. She is the past chair of ICS and serves on the editorial boards of Mathematics of Operations Research, Mathematical Programming, SIAM Journal on Optimization, and MOS-SIAM Optimization Book Series. She received her Ph.D. in Industrial Engineering and Operations Research from the University of California, Berkeley.