TY - JOUR

T1 - On the convex hull of convex quadratic optimization problems with indicators

AU - Wei, Linchuan

AU - Atamtürk, Alper

AU - Gómez, Andrés

AU - Küçükyavuz, Simge

N1 - Funding Information:
We thank the AE and three reviewers for their suggestions that improved the presentation. Alper Atamtürk is supported, in part, by NSF AI Institute for Advances in Optimization Award 2112533, and DOD ONR Grant 12951270. Andrés Gómez is supported, in part, by NSF Grant 2006762 and AFOSR grant FA9550-22-1-0369. Simge Küçükyavuz and Linchuan Wei are supported, in part, by NSF Grant 2007814, and DOD ONR Grants N00014-19-1-2321 and N00014-22-1-2602.
Publisher Copyright:
© 2023, The Author(s).

PY - 2023

Y1 - 2023

N2 - We consider the convex quadratic optimization problem in Rn with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an (n+ 1) × (n+ 1) positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.

AB - We consider the convex quadratic optimization problem in Rn with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an (n+ 1) × (n+ 1) positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.

UR - http://www.scopus.com/inward/record.url?scp=85161349941&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85161349941&partnerID=8YFLogxK

U2 - 10.1007/s10107-023-01982-0

DO - 10.1007/s10107-023-01982-0

M3 - Article

AN - SCOPUS:85161349941

SN - 0025-5610

JO - Mathematical Programming

JF - Mathematical Programming

ER -