TY - JOUR
T1 - Ideal formulations for constrained convex optimization problems with indicator variables
AU - Wei, Linchuan
AU - Gómez, Andrés
AU - Küçükyavuz, Simge
N1 - Funding Information:
We thank the AE and two referees whose comments expanded and improved our computational study, and also led to the result in Appendix 1.
Funding Information:
This research is supported, in part, by ONR grant N00014-19-1-2321, and NSF grants 1818700, 2006762, and 2007814.
Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2022/3
Y1 - 2022/3
N2 - Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a one-dimensional convex function and an affine function under arbitrary combinatorial constraints. As special cases of this result, we derive ideal convexifications for problems with hierarchy, multi-collinearity, and sparsity constraints. Moreover, we also give a short proof that for a separable objective function, the perspective reformulation is ideal independent from the constraints of the problem. Our computational experiments with sparse regression problems demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead.
AB - Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a one-dimensional convex function and an affine function under arbitrary combinatorial constraints. As special cases of this result, we derive ideal convexifications for problems with hierarchy, multi-collinearity, and sparsity constraints. Moreover, we also give a short proof that for a separable objective function, the perspective reformulation is ideal independent from the constraints of the problem. Our computational experiments with sparse regression problems demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead.
KW - Combinatorial constraints
KW - Convexification
KW - Indicator variables
KW - Perspective formulation
UR - http://www.scopus.com/inward/record.url?scp=85120536721&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85120536721&partnerID=8YFLogxK
U2 - 10.1007/s10107-021-01734-y
DO - 10.1007/s10107-021-01734-y
M3 - Article
AN - SCOPUS:85120536721
SN - 0025-5610
VL - 192
SP - 57
EP - 88
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -