AGGREGATIONS OF QUADRATIC INEQUALITIES AND HIDDEN HYPERPLANE CONVEXITY GRIGORIY BLEKHERMAN SANTANU S. DEY AND SHENGDING SUN

2025-04-27 0 0 558.96KB 27 页 10玖币

侵权投诉

AGGREGATIONS OF QUADRATIC INEQUALITIES AND HIDDEN

HYPERPLANE CONVEXITY

GRIGORIY BLEKHERMAN, SANTANU S. DEY, AND SHENGDING SUN

Abstract. We study properties of the convex hull of a set Sdescribed by quadratic inequalities.

A simple way of generating inequalities valid on Sis to take nonnegative linear combinations of the

deﬁning inequalities of S. We call such inequalities aggregations. Special aggregations naturally

contain the convex hull of S, and we give suﬃcient conditions for intersection of such aggregations

to deﬁne the convex hull. We introduce the notion of hidden hyperplane convexity (HHC), which is

related to the classical notion of hidden convexity of quadratic maps. We show that if the quadratic

map associated with Ssatisﬁes HHC, then the convex hull of Sis deﬁned by special aggregations. To

the best of our knowledge, this result generalizes all known results regarding aggregations deﬁning

convex hulls. Using this suﬃcient condition, we are able to recognize previously unknown classes of

sets where aggregations lead to convex hull. We show that the condition known as positive deﬁnite

linear combination for every triple of inequalities, together with hidden hyperplane convexity is

suﬃcient for ﬁnitely many aggregations to deﬁne the convex hull, answering a question raised in [8].

All the above results are for sets deﬁned using open quadratic inequalities. For closed quadratic

inequalities, we prove a new result regarding aggregations giving the convex hull, without topological

assumptions on S, which were needed in [14,8].

1. Introduction

The well-known Farkas lemma in linear programming states that any implied linear inequality for

a non-empty set deﬁned by ﬁnitely many linear inequalities, can be obtained by taking a nonnegative

weighted combination of the original inequalities. We call the procedure of obtaining implied

inequalities for a given set by rescaling the deﬁning constraints by nonnegative weights and then

adding the scaled constraints together as aggregation. Aggregations have also been studied in the

context of integer linear programming (for example, [2]) and mixed-integer nonlinear programming

(for example, [10]) to obtain better cutting-planes or improved dual bounds. In this paper, we

extend the study of aggregation [22,4,14,8] in the context of quadratic constraints. While sets

deﬁned by linear inequalities are always convex, sets deﬁned by quadratic inequalities are usually

not, and we address the question of when the convex hull can be found via aggregation.

Let S⊆Rnbe a set deﬁned by ﬁnitely many quadratic constraints. Since we are interested in

ﬁnding the convex hull of S, it makes sense to consider only “good aggregations”, which have at

most one negative eigenvalue, so that the set deﬁned by the aggregated constraint has at most two

connected components that are both convex, and furthermore contains the convex hull in one of its

connected components. It is known that the convex hull of Sis always described by intersection of

these “good aggregations” in the case where Sis deﬁned by two quadratic constraints [22]. In fact,

the convex hull of a set deﬁned by two quadratic inequalities can be obtained as the intersection of

two good aggregations. Henceforth, for simplicity, if it is clear from context we will drop the term

“good” and refer to good aggregation as aggregation.

The paper [8] extended the result of [22] to the case of a set Sdeﬁned using three quadratic

constraints, by showing that under an additional condition called positive deﬁnite linear combination

(PDLC), the convex hull of Sis obtained as the intersection of good aggregations. They also show

Date: May 31, 2023.

Grigoriy Blekherman and Shengding Sun were partially supported by NSF grant DMS-1901950.

arXiv:2210.01722v2 [math.OC] 29 May 2023

via examples that if PDLC does not hold, then the convex hull of Smay not be given by good

aggregations.

A key ingredient of the result in [22] is the S-lemma [15]. The main use of the PDLC condition

in [8] is also to prove a version of the homogeneous S-lemma for three quadratics under PDLC.

The result is an application of Calabi’s convexity theorem [6,16] which states that under PDLC

the image of Rnby three quadratic forms is a closed convex cone in R3. Convexity of the image of

quadratic maps is a classical mathematical problem in convex geometry and real algebraic geometry,

dating back to Dines’ theorem [9] and Brickman’s theorem [3]. Yakubovich’s S-lemma (also called

S-procedure) [20] connects this problem to the realm of polynomial optimization. Since then the

notion of hidden convexity has become a powerful tool to study quadratic programming [16,11].

See [19] for a mathematical treatment of convexity of quadratic maps and [15] for a survey of the

S-lemma.

The main goals of this paper are three-fold:

•General suﬃcient conditions for aggregations to yield convex hull: We establish a new suf-

ﬁcient condition for aggregations to deﬁne the convex hull, which we call hidden hyperplane

convexity (HHC). To the best of our knowledge, hidden hyperplane convexity gives the most

general result on convex hull of a region deﬁned by quadratic inequalities being given by

aggregations. In particular, we simultaneously generalize the results of [22] and [8], which

deal with two and three quadratic inequalities respectively. Furthermore, we give new ex-

amples of sets described by more than 3 quadratic inequalities where convex hull is given

by aggregations. We show that hidden hyperplane convexity is a stronger requirement than

hidden convexity, and in order for the convex hull of a set deﬁned by quadratic inequalities

to be given by aggregations, hidden convexity is not suﬃcient while HHC is not necessary.

•Finiteness of aggregations: While [22] shows that only two good aggregations suﬃce to

deﬁne the convex hull in the case of sets described by two quadratic inequalities, the pa-

per [8] only shows that the intersection of good aggregations yields the convex hull –leaving

the question of whether only a ﬁnite number of good aggregations are suﬃcient to obtain

the convex hull for three quadratic constraints satisfying PDLC, as an open problem. We

answer this question in the aﬃrmative in this paper, and we show that six aggregations

suﬃce to describe the convex hull for three quadratic constraints satisfying PDLC. Fur-

thermore, we establish a more general suﬃcient condition for ﬁniteness of aggregations in

Theorem 2.18.

•Closed quadratic inequalities: All of the above results are for the case of open quadratic

inequalities, whereas typically in mathematical programming we are interested in sets de-

ﬁned by closed quadratic inequalities. The situation with closed inequalities is much more

delicate, as we illustrate in Example 2.23. Much of the diﬃculty comes from the fact that

sets deﬁned by closed inequalities can have low-dimensional connected components. Pre-

viously known results make topological assumptions to avoid this situation. In particular,

it was shown in [14] that if the set deﬁned by closed inequalities has no lower-dimensional

connected components, then the closures of convex hulls of sets deﬁned by closed or open

inequalities are the same; this allows us to transfer results from the open case to the closed

case, under a topological assumption. Unfortunately, this assumption is hard to check

computationally, and it does not hold in some interesting cases. We show that if hidden

hyperplane convexity holds, and the zero matrix is not a non-trivial aggregation, then the

interior of the convex hull of the set given by closed quadratic inequalities is equal to the

interior of the intersection of aggregations (Theorem 2.24). While these are restrictive con-

ditions, they do not make topological assumptions on the set deﬁned by closed inequalities.

The rest of the papers is organized as follows: In Section 2we present all our main results. In

particular, in Section 2.1 we establish notation and preliminary results followed by Section 2.2-

Section 2.6 where all the results are stated and explained. Section 3presents conclusions and open

questions. Proofs of the results presented in Section 2are given in Sections 4-10.

2. Main Results

2.1. Notations and preliminaries. Given a positive integer n, we let [n] denote the set {1, . . . , n}.

Given a set U⊆Rn, we use dim(U), conv(U), int(U), U, and ∂U to represent the dimension of

U, the convex hull of U, the standard topological interior of U, the standard topological closure

of U, and the boundary of the set Urespectively. Given a linear subspace Lof Rn, we denote its

orthogonal complement by L⊥. For a square matrix M, we use det(M) to denote the determinant

of M. We use Into denote the n×nidentity matrix and eifor the i-th standard basis vector.

Our main goal is to study sets deﬁned by multiple open quadratic constraints:

S:= {x∈Rn:x⊤Aix+ 2b⊤

ix+ci<0, i ∈[m]},(1)

where m≥2 and n≥3. We also use the following notation:

(1) Let fi(x) = x⊤Aix+ 2b⊤

ix+cibe quadratic functions deﬁning (1) and Qi=Aibi

b⊤

icithe

corresponding matrices. We deﬁne homogenization fh

iof fito be the quadratic form given

by fh

i(x, xn+1) = (x, xn+1)⊤Qi(x, xn+1).

(2) The homogenized set Sh:

Sh:= n(x, xn+1)∈Rn×R1:x⊤Aix+ 2(b⊤

ix)xn+1 +cix2

n+1 <0, i ∈[m]o.

(3) The aggregation of constraints Sλand its homogenization (Sλ)h. For λ∈Rm

+, we let

Qλ=

i=1

λiQiand Fλ=

i=1

λifi

be the aggregated matrices and quadratic functions. Additionally we deﬁne:

Sλ:= {x∈Rn:Fλ<0},

(Sλ)h:= {(x, xn+1)∈Rn+1 :Fh

λ(x, xn+1)<0}.

Observe that S⊆Sλ, Sh⊆(Sλ)hfor any nonzero λ∈Rm

(4) Let

Ω = {λ∈Rm

+\ {0}: conv(S)⊆Sλand Qλhas at most one negative eigenvalue.}

Informally, Ω is the set of “good” aggregations where Sλconsists of one or two convex

connected components, and conv(S) lies entirely in one of them. We will formally state and

prove this equivalence in Lemma 5.2 in Section 5.

(5) Positive deﬁnite linear combination (PDLC): Given a set of symmetric matrices Q1, . . . Qm,

we say they satisfy PDLC if Pm

i=1 θiQi≻0 holds for some θ∈Rm.

The cases of m= 2 and m= 3 are studied in [22] and [8] respectively. If S̸=∅and conv(S)̸=Rn,

then in the case of two quadratic inequalities the convex hull is always given by aggregations in

Ω, and in the case of three quadratic inequalities we need the additional PDLC condition. Notice

that in the case of two quadratic inequalities, by taking Q3=−Ithe latter result implies the

former one1. The author of [22] also proved that for two quadratic inequalities, aggregations also

give certiﬁcates when S=∅or conv(S) = Rn. Moreover, [22] also showed at most two good

aggregations suﬃce to deﬁne the convex hull.

2.2. Hidden hyperplane convexity. We call a map φ:Rn→Rma quadratic map, if there exist

msymmetric matrices Q1,...Qmsuch that:

φ(x) = x⊤Q1x, . . . , x⊤Qmxfor all x∈Rn.

A quadratic map φ:Rn→Rmsatisﬁes hidden convexity if image (φ) = {φ(x) : x∈Rn} ⊆ Rm

is convex. We say that n×nsymmetric matrices Q1, . . . , Qmsatisfy hidden convexity if the map

x7→ (x⊤Q1x, . . . , x⊤Qmx) satisﬁes hidden convexity.

We now introduce a new notion of hidden hyperplane convexity of quadratic maps, which will

be our key assumption in proving that the convex hull of a set deﬁned by quadratic inequalities is

given by aggregations of these inequalities. We say H⊆Rnis a linear hyperplane if His a linear

subspace of Rnwith dim(H) = n−1.

Deﬁnition 2.1 (Hidden hyperplane convexity (HHC)).A quadratic map φ:Rn→Rmsatisﬁes

hidden hyperplane convexity (HHC) if for all linear hyperplanes H⊆Rn, image (φ|H) = {φ(x) :

x∈H} ⊆ Rmis a convex set. Let Q1, . . . , Qmbe n×nsymmetric matrices. We say Q1, . . . , Qm

satisfy HHC if the map x7→ (x⊤Q1x, . . . , x⊤Qmx) satisﬁes HHC.

We present some properties of hidden hyperplane convexity.

Remark 2.2.If the matrices Qiare linearly independent, then we must have n≥mfor hidden

convexity, and n−1≥mfor hidden hyperplane convexity. For hidden convexity, suppose n < m,

and consider the span of the image of the quadratic map φ. Since the image is convex, the span

has the same dimension as the image, and it is at most n. This means for all x∈Rnwe have

there exist λi, not all zero, such that Pλix⊤Qix=Px⊤λiQix= 0, and therefore Qiare linearly

dependent. Contradiction.

For hidden hyperplane convexity, suppose n−1< m, and consider the span of the image of φ

restricted to a hyperplane. For a general hyperplane Hthe restrictions of Qito Hwill be linearly

independent and then the argument is same as for hyperplane convexity.

More generally, we must have dim(span{Q1, . . . , Qm})≤n(resp. n−1) for hidden convexity

(resp. hyperplane hidden convexity) to hold. The proofs are the same as the ones outlined above.

We now observe that hidden hyperplane convexity implies hidden convexity.

Observation 2.3.Hidden hyperplane convexity implies the usual hidden convexity as long as n≥3.

Given x, y ∈Rnwe may pick some hyperplane Hcontaining both xand y, and the segment between

φ(x) and φ(y) in Rmis then contained in image(φ|H)⊆image φ.

On the other hand, HHC is a strictly stronger condition than hidden convexity as the next

example illustrates.

Example 2.4 (Hidden convexity does not imply hidden hyperplane convexity).Consider a diagonal

quadratic map φ:Rn→Rm,φ(x) = x⊤D1x, . . . , x⊤Dmx,where D1, . . . , Dmare diagonal

matrices; such a map is also sometimes referred to as a separable quadratic map. Any diagonal

quadratic map φis known to satisfy hidden convexity (see Proposition 3.7 in [16]), and we include

a quick proof here. Given x, y ∈Rnand λ∈[0,1], let z∈Rnbe deﬁned as

zj=qλx2

j+ (1 −λ)y2

j, j ∈[n].

1If any aggregation uses a non-zero weight on the quadratic constraint corresponding to −I, then we can obtain a

tighter aggregated constraint by setting the weight on this constraint to zero.

Then it is straightforward to verify that

λφ(x) + (1 −λ)φ(y) = φ(z),

that is, image (φ) is convex.

On the other hand, we show that a diagonal quadratic map may not satisfy hidden hyper-

plane convexity: Let φ:R4→R3be given by f1=x2

1,f2=x2

2and f3=x2

3. The image

of R4is the non-negative orthant in R3. Now let’s consider restrictions of φto a linear hy-

perplane H. It is clear that in this speciﬁc example, {φ(x) : x∈H}={φ(x) : x∈π(H)},

where π:R4→R3, π(x1, x2, x3, x4) = (x1, x2, x3,0) is the linear projection that forgets the

last coordinate. If Hdoes not contain the vector (0,0,0,1), then π(H) = R3, and {φ(x) :

x∈H}is the non-negative orthant in R3, and hidden hyperplane convexity on Hholds. If

Hdoes contain (0,0,0,1), then the image of Hunder φmay not be convex. For instance,

let H= span{(1,1,0,0),(1,0,1,0),(0,0,0,1)}={(s+t, s, t, u)⊆R4:s, t, u ∈R}. Then

A= image φ|H={((s+t)2, s2, t2)⊆R3:s, t ∈R}is not convex, since (4,1,1),(0,1,1) ∈A

but (2,1,1) /∈A. Thus we see that φsatisﬁes hidden convexity, but does not satisfy hidden

hyperplane convexity. This example is interesting in the sense that for a dense subset of linear

hyperplanes, the image of this quadratic map restricted to these hyperplanes is convex, and yet

this convexity does not hold for all linear hyperplanes.

We now show that hidden hyperplane convexity is preserved under the following two diﬀerent

operations.

Lemma 2.5. Suppose that Q1, . . . , Qmsatisfy HHC. Then the following matrices also satisfy HHC:

(1) P⊤Q1P, . . . , P ⊤QmPwhere Pis any invertible matrix.

(2) Q′

1, . . . , Q′

kwhere span(Q′

1, . . . , Q′

k)⊆span(Q1, . . . , Qm). (Equivalently, there exists a k×m

matrix Λsuch that Q′

i=Pm

j=1 Λij Qjfor all i∈[k].)

Proof. Let Hbe any hyperplane in Rn. For the ﬁrst statement, we have

U:= {(x⊤P⊤Q1P x, . . . , x⊤P⊤QmP x) : x∈H}={(x⊤Q1x, . . . , x⊤Qmx) : x∈H′},

where H′={P x :x∈H}=P H is also a hyperplane in Rn. Thus, by HHC of Q1, . . . , Qmthe set

Uis also convex.

For the second statement, since span(Q′

1, . . . , Q′

k)⊆span(Q1, . . . , Qm), there exists a k×m

matrix Λ such that Q′

i=Pm

j=1 Λij Qjfor all i∈[k]. Then we have {(x⊤Q′

1x, . . . , x⊤Q′

kx) : x∈

H}= Λ{(x⊤Q1x, . . . , x⊤Qmx) : x∈H}, which is convex since convexity is preserved under linear

transformations. □

The above result is important, especially (2), since it shows that hidden hyperplane convexity

is a property of linear subspaces of the space of symmetric matrices rather than a property that

holds for some arbitrary subset of quadratic maps.

Our next observation is that hidden hyperplane convexity can be formulated with matrices. Let

φ:Rn→Rmbe a quadratic map. Let Hbe any hyperplane of Rnand the columns of the matrix

WH∈Rn×(n−1) be any basis for H. Then note that:

image(φ|H) = {(x⊤Q1x, . . . , x⊤Qmx) : x∈H}

={(y⊤W⊤

HQ1WHy, . . . , y⊤W⊤

HQmWHy) : y∈Rn−1}

= image(φ(H)),

where φ(H) : Rn−1→Rmis the quadratic map: y→(y⊤W⊤

HQ1WHy, . . . , y⊤W⊤

HQmWHy). On the

other hand, the columns of any full rank n×(n−1) matrix form a basis for some linear hyperplane.

Thus, we arrive at the following equivalence.

Observation 2.6.Q1, . . . , Qmsatisfy HHC if and only if for all full-rank matrix W∈Rn×(n−1),

W⊤Q1W, . . . , W ⊤QmWsatisfy hidden convexity.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AGGREGATIONSOFQUADRATICINEQUALITIESANDHIDDENHYPERPLANECONVEXITYGRIGORIYBLEKHERMAN,SANTANUS.DEY,ANDSHENGDINGSUNAbstract.WestudypropertiesoftheconvexhullofasetSdescribedbyquadraticinequalities.AsimplewayofgeneratinginequalitiesvalidonSistotakenonnegativelinearcombinationsofthedefininginequalitiesofS.W...

展开>> 收起<<

AGGREGATIONS OF QUADRATIC INEQUALITIES AND HIDDEN HYPERPLANE CONVEXITY GRIGORIY BLEKHERMAN SANTANU S. DEY AND SHENGDING SUN.pdf

共27页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

AGGREGATIONS OF QUADRATIC INEQUALITIES AND HIDDEN HYPERPLANE CONVEXITY GRIGORIY BLEKHERMAN SANTANU S. DEY AND SHENGDING SUN

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: