TY - GEN
T1 - On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables
AU - Wei, Linchuan
AU - Gómez, Andrés
AU - Küçükyavuz, Simge
N1 - Funding Information:
Andrés Gómez is supported, in part, by grant 1930582 of the National Science Foundation. Simge Kü¸cükyavuz is supported, in part, by ONR grant N00014-19-1-2321.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
PY - 2020
Y1 - 2020
N2 - Motivated by modern regression applications, in this paper, we study the convexification of quadratic 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 objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic objective function, the perspective reformulation is ideal independent from the constraints of the problem. In contrast, while rank-one relaxations cannot be strengthened by exploiting information from k-sparsity constraint for [Formula Presented], they can be improved for other constraints arising in inference problems with hierarchical structure or multi-collinearity.
AB - Motivated by modern regression applications, in this paper, we study the convexification of quadratic 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 objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic objective function, the perspective reformulation is ideal independent from the constraints of the problem. In contrast, while rank-one relaxations cannot be strengthened by exploiting information from k-sparsity constraint for [Formula Presented], they can be improved for other constraints arising in inference problems with hierarchical structure or multi-collinearity.
KW - Combinatorial constraints
KW - Convexification
KW - Indicator variables
KW - Perspective formulation
KW - Quadratic optimization
UR - http://www.scopus.com/inward/record.url?scp=85083986783&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85083986783&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-45771-6_33
DO - 10.1007/978-3-030-45771-6_33
M3 - Conference contribution
AN - SCOPUS:85083986783
SN - 9783030457709
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 433
EP - 447
BT - Integer Programming and Combinatorial Optimization - 21st International Conference, IPCO 2020, Proceedings
A2 - Bienstock, Daniel
A2 - Zambelli, Giacomo
PB - Springer
T2 - 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020
Y2 - 8 June 2020 through 10 June 2020
ER -