A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation

Andrés Gómez; Weijun Xie

doi:10.1016/j.orl.2023.107059

A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation

Andrés Gómez^*
, Weijun Xie

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Citation (Scopus)

Abstract

In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we discover links between the convex hull of the set under study, and a family of polyhedral sets studied in the literature. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation. © 2023 Elsevier B.V.

Original language	English
Article number	107059
Journal	Operations Research Letters
Volume	52
DOIs	https://doi.org/10.1016/j.orl.2023.107059
Publication status	Published - 1 Jan 2024
Externally published	Yes

Funding

Andr\u00E9s G\u00F3mez was supported in part by grant 2006762 from the National Science Foundation , and by grant FA9550-22-1-0369 from the Air Force Office of Scientific Research . Weijun Xie was supported in part by grants 2246414 and 2246417 from the National Science Foundation and grant N00014-24-1-2066 ( Office of Naval Research ).

Research Keywords

Convexification
Mixed-integer optimization
Perspective relaxation
Quadratic optimization

Access Output

10.1016/j.orl.2023.107059

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{657ac22838264888b959bb7f398129cd,

title = "A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation",

abstract = "In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we discover links between the convex hull of the set under study, and a family of polyhedral sets studied in the literature. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation. {\textcopyright} 2023 Elsevier B.V.",

keywords = "Convexification, Mixed-integer optimization, Perspective relaxation, Quadratic optimization",

author = "Andr{\'e}s G{\'o}mez and Weijun Xie",

year = "2024",

month = jan,

day = "1",

doi = "10.1016/j.orl.2023.107059",

language = "English",

volume = "52",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A note on quadratic constraints with indicator variables

T2 - Convex hull description and perspective relaxation

AU - Gómez, Andrés

AU - Xie, Weijun

PY - 2024/1/1

Y1 - 2024/1/1

N2 - In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we discover links between the convex hull of the set under study, and a family of polyhedral sets studied in the literature. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation. © 2023 Elsevier B.V.

AB - In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we discover links between the convex hull of the set under study, and a family of polyhedral sets studied in the literature. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation. © 2023 Elsevier B.V.

KW - Convexification

KW - Mixed-integer optimization

KW - Perspective relaxation

KW - Quadratic optimization

UR - https://www.scopus.com/pages/publications/85182606124

UR - https://www.scopus.com/pages/publications/85182606124#tab=impact

U2 - 10.1016/j.orl.2023.107059

DO - 10.1016/j.orl.2023.107059

M3 - RGC 21 - Publication in refereed journal

SN - 0167-6377

VL - 52

JO - Operations Research Letters

JF - Operations Research Letters

M1 - 107059

ER -

A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation

Abstract

Funding

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this