Convexification of Constrained Nonlinear Optimization Problems with Indicator Variables

Indicator variables arise pervasively in optimization problems to enforce logical constraints. For example, in machine learning, indicator variables are used when imposing sparsity, which in turn leads to interpretable statistical models with improved out-of-sample performance. In finance, indicator variables are used to control the size of the portfolio, and are essential for modeling fixed transaction costs. Traditionally, indicator variables are encoded in mixed-integer optimization solvers via “big M” constraints, but such formulation may result in poor performance. Recently, there has been substantial progress in handling indicator variables, with most of the work based on the convexification of sets involving both indicator variable and separable nonlinear functions.

In this talk we present recent work in pushing beyond the simple structures previously studied in the literature. Specifically, we derive ideal convexifications for sets involving non-separable nonlinear functions, and with additional constraints on both the continuous variables and indicator constraints. We show that by including and exploiting additional constraints, it is indeed possible to obtain much better convex relaxations of mixed-integer problems arising in sparse regression and portfolio optimization.