Journal article
Quadratic programs with hollows
Mathematical programming, Vol.170(2), pp.541-553
08/01/2018
DOI: 10.1007/s10107-017-1157-0
Abstract
Let
F
be a quadratically constrained, possibly nonconvex, bounded set, and let
E
1
,
…
,
E
l
denote ellipsoids contained in
F
with non-intersecting interiors. We prove that minimizing an arbitrary quadratic
q
(
·
)
over
G
:
=
F
\
∪
k
=
1
ℓ
int
(
E
k
)
is no more difficult than minimizing
q
(
·
)
over
F
in the following sense: if a given semidefinite-programming (SDP) relaxation for
min
{
q
(
x
)
:
x
∈
F
}
is tight, then the addition of
l
linear constraints derived from
E
1
,
…
,
E
l
yields a tight SDP relaxation for
min
{
q
(
x
)
:
x
∈
G
}
. We also prove that the convex hull of
{
(
x
,
x
x
T
)
:
x
∈
G
}
equals the intersection of the convex hull of
{
(
x
,
x
x
T
)
:
x
∈
F
}
with the same
l
linear constraints. Inspired by these results, we resolve a related question in a seemingly unrelated area, mixed-integer nonconvex quadratic programming.
Details
- Title: Subtitle
- Quadratic programs with hollows
- Creators
- Boshi Yang - Clemson UniversityKurt Anstreicher - University of IowaSamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.170(2), pp.541-553
- Publisher
- Springer Berlin Heidelberg
- DOI
- 10.1007/s10107-017-1157-0
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Language
- English
- Date published
- 08/01/2018
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380427402771
Metrics
6 Record Views