# Quadratic Program on a Structured Nonconvex Set

Authors: Yi Xu; Lili Han
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we focus on a special nonconvex quadratic program whose feasible set is a structured nonconvex set. To find an effective method to solve this nonconvex program, we construct a bilevel program, where the low-level program is a convex program while the upper-level program is a small-scale nonconvex program. Utilizing some properties of the bilevel program, we propose a new algorithm to solve this special quadratic program. Finally, numerical results show that our new method is effective and efficient.


---

## Body

## 1. Introduction

In this paper, we discuss the following structured quadratic program:(1)infxTAx+2aTxs.t.x∈Ω,where x∈ℝn, Sn×n∑A≻0,a∈ℝn, and Ω⊂ℝn is a set.Program (1) has been frequently exploited in optimization theory and practice [1–5]. If Ω is a closed convex set, program (1) is a convex program, which can be solved by many algorithms such as cutting plane method, projection method, and interior point method [1–3, 6–8]. However, in practice, program (1) is usually a nonconvex program since Ω is often a nonconvex set. As we know, a nonconvex program is difficult to solve since it is a NP-hard problem in general. However, there are still some special small-scale nonconvex problems which can be easily solved by some algorithms. For example, finding the roots of a continuous function fx in x∈a,b⊂ℝ has polynomial time computational complexity, although this problem is nonconvex. This motivates us to covert program (1) into a small-scale program.Note that for a bounded closed setΩ, by the Hein–Borel theorem, there exists a finite set Ξ⊂ℝn such that Ω can be covered by(2)∪xk∈Ξx∈ℝnx−xkTBkx−xk+ck≥0,where Bk≺0andck>0. This says that there exists a finite index set Γ such that Ω is covered by(3)∪t∈Γx∈ℝnxTBtx+2btTx+ct≥0,where Bt≺0 and ct−btTBt−1bt>0,∀t∈Γ.If(4)Ω=∪t∈Γx∈ℝnxTBtx+2btTx+ct≥0,where Bt∈Sn×n,bt∈ℝn,ct∈ℝ, and Γ is a finite set. Program (1) could be solved by the theory of S-procedure [9, 10] which is an important tool for solving programs with quadratic objective functions and quadratic constraints. We could separate program (1) into several parts, and each part is a program with quadratic objective function and quadratic constraints which could be solved by the theory of S-procedure. Then, we could find the global minimum value from all optimal values easily, since Γ is finite. But when Γ is not a finite set, this method is invalid and we need to find a new method. In this paper, we focus on a special case of program (1), where Ω has the same structure as program (3). For this special structure, we can try to turn program (1) into a solvable bilevel program.Some notions and symbols are introduced here.Notions and symbols:ℝn is the n-dimensional real Euler space; ℝn×n denotes the set of all n×n real matrices; xi is the ith element of x∈ℝn; Sn×n is the subset of ℝn×n, which is consisted of the symmetric real matrix; A≻0 A≺0 and A≽0 A≼0 mean that A is positive definite (negative definite) and positive semidefinite (negative semidefinite), respectively; I is the identify matrix with proper dimension; e=1,…,1T;and∂fx is the subgradient of fx.


## 2. Quadratic Program on a Structured Nonconvex Set

Definition 1.
We call a setΩ as a structured set generated by Γ, denoted by SSΓ, if it satisfies(5)Ω=∪t∈Γx∈ℝnxTBtx+2btTx+ct≥0,where Γ is a subset in ℝl, l<n, Bt∈Sn×n,Bt≺0, bt∈ℝn,ct∈ℝ,and∀t∈Γ. We call Γ as a generator of Ω.
Usually, the dimension ofΓ is far smaller than the dimension of Ω. Γ may be a finite set, such as 0,1, a countable infinite set, such as ℤ, or an uncountable infinite subset of ℝn. In fact, there are a lot of SSΓ sets, such as circle, sphere, donut, and crescent. Here are some examples.Example 1.
.(a)
x∈ℝn−xTx+1≥0∪x∈ℝn−xTx+4eTx+1−4n≥0, where Γ=0,1, Bt=−I, and bt=0t=02et=1,ct=1t=01−4nt=1(b)
∪t∈ℤx∈ℝn−xTx+2teTx+1−t2n≥0, where Γ=ℤ, Bt=−I, bt=te, and ct=1−t2n(c)
∪t∈0.1,1x∈ℝ2−1/txTx+22tTx+1−t+t3≥0, where Γ=0.1,1, Bt=−1/tI, bt=1t, and ct=1−t+t3.
Example1 shows that a SSΓ set is not a convex set in general. (a) is just a union set of two separated spheres, (b) is the union of a series of spheres, and (c) is a horn.
If∃t∗∈Γ such that(6)ct∗−bt∗TBt∗−1bt∗<0,then(7)x∈ℝnxTBt∗x+2bt∗Tx+ct∗≥0is empty. And if ∃t∗∈Γ such that(8)ct∗−bt∗TBt∗−1bt∗=0,then(9)x∈ℝnxTBt∗x+2bt∗Tx+ct∗≥0is just(10)x∈ℝnx=−Bt∗−1bt∗.
For avoiding the above two simple cases, we make an assumption as follows.Assumption 1.
(11)
c
t
−
b
t
T
B
t
−
1
b
t
>
0
,
∀
t
∈
Γ
.
We call this assumption as regular assumption.
Now, we consider program (1) with a SSΓ constraint:(12)infxTAx+2aTxs.t.x∈∪t∈Γx∈ℝnxTBtx+2btTx+ct≥0.
We rewrite program (12) into a simpler formulation as follows:(13)infyTAys.t.y∈∪t∈Γy∈ℝnyTBtx+2b^tTy+c^t≥0,where b^t=bt−BtA−1a,c^t=ct−2btTA−1a+aTA−1BtA−1a, and y=A−1x+a.
Then, the following lemma is true.Lemma 1.
If regular assumption holds for program (12), then it still holds for program (13).Proof.
(14)
c
^
t
−
b
^
t
T
B
t
−
1
b
^
t
=
c
t
−
2
b
t
T
A
−
1
a
+
a
T
A
−
1
B
t
A
−
1
a
−
b
t
−
B
t
A
−
1
a
T
B
t
−
1
b
t
−
B
t
A
−
1
a
=
c
t
−
b
t
T
B
t
−
1
b
t
>
0.
Now, we just need to focus on program (13).
The following lemma is called as S-Lemma, which presents the relationship between a biquadratic program and a semidefinite program. S-Lemma plays an important role in our analysis.Lemma 2.
(see S-Lemma [9, 10]). If x∈ℝnxTBx+2bTx+c≥0 has nonempty interior points, then the following two statements are equivalent:(a)
xTAx+2aTx+d≥0, for all x∈x∈ℝnxTBx+2bTx+c≥0(b)
there existsλ≥0 satisfying AaaTd±λBbbTc
By Lemma2, for each t∈Γ, we will find the minimum dt such that(15)yTAy+dt≥0,∀y∈y∈ℝnyTBty+2b^tTy+c^t≥0,first. Then, we solve program supt∈Γdt to obtain the optimal value of program (13). Summarizing the above discussion, we get the following theorem.Theorem 1.
If regular assumption holds andA≻0 for program (13), then the optimal value of program (13) is same as that of the following program:(16)sup−ds.t.∀t∈Γ,∃λt≥0such  thatA00d±λtBtb^tb^tTc^t.Proof.
If−d∗ is the optimal value of program (13), then(17)yTAy≥−d∗,y∈∪t∈Γy∈ℝnyTBty+2b^tTy+c^t≥0,which means for all t∈Γ,(18)yTAy+d∗≥0,y∈y∈ℝnyTBty+2b^tTy+c^t≥0.
By Lemma2, for all t∈Γ, there exists λt≥0, such that(19)A00d∗≽λtBtb^tb^tTc^t,so d∗ is a feasible point of program (16), and the optimal value of program (13) is not smaller than −d∗.
On the other hand, if the optimal value of program (16) is −d∗∗; then, for all t∈Γ, there exists λt≥0, such that(20)A00d∗∗≽λtBtb^tb^tTc^t.
By Lemma2, for all t∈Γ,(21)yTAy≥−d∗∗,for all(22)y∈y∈ℝnyTBty+2b^tTy+c^t≥0,so(23)yTAy≥−d∗∗,where(24)y∈∪t∈Γy∈ℝnyTBty+2b^tTy+c^t≥0,which means that −d∗∗ is a low bound of the optimal value of program (13). Hence, the optimal value of program (13) and program (16) are the same.
By Theorem1, we could solve program (16) instead of solving program (13). Noticing that(25)A00d≽λtBtb^tb^tTc^t⟺A−λtBt−λtb^t−λtb^tTd−λtc^t≽0.
SinceA≻0, Bt≺0, and λ≥0, then(26)A−λBt−λb^t−λb^tTd−λc^t≽0⟺A−λBt≽0d−λc^t−λ2b^tTA−λBt−1b^t.
So program (16) can be rewritten as the following program:(27)sup−ds.t.∀t∈Γ,λ≥0A−λBt±0d−λc^t−λ2b^tTA−λBt−1b^t≥0has a solutionλ.
Noticing that the feasible set of program (27) is just ∀t∈Γ,(28)λ≥0,d−λc^t−λ2b^tTA−λBt−1b^t≥0has a solutionλ,since A≻0andBt≺0. It is still too complex to solve program (27) directly. In the following theorem, we turn program (27) into a bilevel program.Theorem 2.
The optimal value of program (27) is opposite to that of(29)supt∈Γinfλ≥0φλ,t=λc^t+λ2b^tTA−λBt−1b^t.Proof.
The infimumd of program (27) satisfies that(30)∀t∈Γ,λ≥0,d−λc^t−λ2b^tTA−λBt−1b^t≥0has a solutionλ.
Noticing that for eacht∈Γ, if dt is an infimum satisfying (28), then (28) holds for any d≥dt. Hence, we just need to find the infimum dt satisfying (28) for each t∈Γ firstly and then find the supremum dt in t∈Γ.
For eacht∈Γ, we reconsider (28) and let(31)φλ,t=λc^t+λ2b^tTA−λBt−1b^t,(32)ϑt=infλ≥0φλ,t,then ϑt must be the infimum dt of (28), since if dt<ϑt, it is impossible to find λ∈0,+∞ such that dt≥φλ,t≥ϑt; if dt>ϑt, by the definition of ϑt, there must exist λ such that φλ,t≤ϑt+dt/2<dt, which contradicts the definition of dt. Summarizing the above discussion, we have that the optimal value of program (27) is opposite to that of program (29).
By Theorem2, we just need to solve program (29). However, program (29) is not easy to solve since it is a sup-inf program. Fortunately, φλ,t has some good properties.Property 1.
(a)
φλ,t is a convex function with respect to λ∈0,+∞,∀t∈Γ.(b)
∂φλ,t/∂λ=c^t+2λb^tTMb^t+λ2b^tTMBtMb^t, ∀λ≥0,t∈Γ, where M=A−λBt−1.(c)
Ifc^t,b^t and Bt are differentiable on Γ, then(33)∂ϑt=λ∗c^′t+2λ∗2b^′tTMb^t+λ∗3b^tTMB′tMb^tλ∗∈arginfλ≥0φλ,t,where M=A−λ∗Bt−1and ϑt is defined in (32).Proof.
(a):∀t∈Γ; since λ≥0 and A−λBt≻0, there is an invertible matrix P such that PTAP=X±0 and PT−BtP=Y≻0, where XandY are the diagonal matrices. Then,(34)λ2b^tTA−λBt−1b^t=λ2b^TtP−TX+λY−1P−1b^t.
Letq=P−1b^t; then,(35)λ2b^tTA−λBt−1b^t=λ2∑i=1nqi2Xii+λYii.
Here,(36)λ2Xii+λYii=1Yii2Xii+λYii−2Xii+Xii2Xii+λYii.
Whenλ≥0, every term of the above equation is a convex function, so(37)λ2b^tTA−λBt−1b^t,λc^t+λ2b^tTA−λBt−1b^t
are convex functions with respect toλ≥0.
(b) and (c): it is obvious from [11].Remark 1.
(a)
Since the convexity ofφλ,t,(38)ϑt=infλ≥0φλ,t
is an easy solvable program for everyt∈Γ.
(b)
If there ist∗∈Γ satisfying b^t∗=0, then the optimal value of the low-level program is(39)infλ≥0φλ,t∗=0,c^t∗≥0,−∞,c^t∗<0.
(c)
If regular assumption holds, thenc^t∗>0 when b^t∗=0.
(d)
λ
=
0 is always a feasible point of (38), so(40)infλ≥0φλ,t≤0,∀t∈Γ,
which means that if there existst∗ satisfying infλ≥0φλ,t∗=0, then(41)supt∈Γinfλ≥0φλ,t=0.
(e)
By the above discussion, if regular assumption holds, and∃t∗∈T such that b^t∗=0, then the value of program (12) is 0.


## 3. Algorithms

In this section, based on our main result, we present a method for solving program (12) by solving the bilevel program, where we use a linear search method for solving the low-level program and a feasible direction method in [12] for solving the upper-level program. Here, we suppose T=a,b (Algorithm 1):Algorithm 1: (solving the low-level program).
S0Given ε>0, γ>0, η∈0,1, t∗∈Γ, k=0;
S1Let λk=0, compute κk=∂φλ,t/∂λλk,t∗ ; If κk>0, then stop and return λk;
S2 Ifκk<ε, then stop and return λk;;
S3Let α=1;
S4If φλk−ακk,t∗≥φλk,t∗−αγκk2 or λk−ακk<0, α=ηα, goto S4; else λk+1=λk−ακk, k=k+1, goto S2;


## 4. Numerical Results

In this section, we demonstrate the efficiency and effectiveness of the proposed method by solving some illustrative numerical examples. All of our computations are conducted on a Windows machine, equipped with a dual core 2.4 GHz processor, using MATLAB 7.6 as the computational engine. Noticing that our method does not depend on the dimension ofx, we just test some examples for x∈ℝ2.Example 2.
(42)
inf
x
T
x
s
.
t
.
∪
t
∈
0.1
,
1
x
∈
ℝ
2
−
1
t
x
T
x
+
2
2
t
T
x
+
1
−
t
+
t
3
≥
0
.Example 3.
(43)
inf
x
T
x
s
.
t
.
∪
t
∈
1,2
x
∈
ℝ
2
−
x
T
x
+
2
t
2
t
2
T
x
+
t
−
t
2
−
t
4
≥
0
.Example 4.
(44)
inf
x
T
x
s
.
t
.
∪
t
∈
−
1,1
x
∈
ℝ
2
x
−
cos
t
+
1
t
T
2
1
1
2
+
t
2
I
x
−
cos
t
+
1
t
≤
1
.Example 5.
(45)
inf
x
T
x
s
.
t
.
∪
t
∈
0,2
x
∈
ℝ
2
x
−
cos
t
+
1
t
T
2
1
1
2
+
t
2
I
x
−
cos
t
+
1
t
≤
1
.
Computational results for solving the upper-level programs are provided in Table1, where time represents the average running time in second and NOI represents the number of iterations. t0 and err are set as l+u/2 and 10−5, respectively.
We choose the discretization method as the comparing algorithm since there are no other methods for program (12). We select finite different points ti in Γ and get their optimal values of(46)infxTAx+2aTxs.t.xTBtix+2btiTx+cti≥0,at ti, which is equal to the value of(47)sup−ds.t.λ≥0AaaTd≽λBtibtibtiTcti.Then, we could find out the minimum among these finite number of optimal values to approximate the optimal value of program (12). As for program (47), we use the interior point method [13] or the feasible direction method [12].
Computational results of the discretization method are shown in Table2, where time represents the average running time in second. For each example, we choose 20 points in Γ randomly and test 10 times.
From Table2, we can see that our method is more effective and efficient than the discretization method.Table 1
Numerical results for Algorithm2.
Time (s)
NOI
Optimal value of (12)
(42)
0.01
1
0
(43)
0.07
1
0.1716
(44)
0.03
5
1.2686
(45)
0.011
2
1.5069Algorithm 2: (solving the upper-level program).
S1Given ε>0, γ>0, η∈0,1, t0∈Γ, k=0;
S2Plug tk into the lower-level program to get λk;
S3Compute μk∈∂ϑtk and set t¯i=uiμki>0liμki<0ui+li/2μki=0,dk=t¯−tk;
IfμkTdk<ε, stop and return φλk,tk;
S4 Letα=1;
S5 Ifθtk+αdk<θtk+αγμk2, then α=ηα, goto S5; else tk+1=tk+αdk, k=k+1, goto S2.Table 2
Numerical results for the discretization method.
Time (s)
Average optimal value of (12)
(42)
0.11
0.0110
(43)
0.23
0.1787
(44)
0.31
1.2726
(45)
0.22
1.5311


## 5. Conclusion and Future Work

In this paper, we discuss a quadratic program on a structured nonconvex set. By S-lemma, we convert this program into a bilevel program, where the low-level program is a convex program. Under some assumptions, we develop an algorithm to solve the nonconvex program. Finally, we present the numerical results to show the effectiveness and efficiency of our new method.Note that we need to solve a lower-level program for eachtk. However, computational cost of A−λBtk−1 is expensive. Hence, how to avoid computing A−λBtk−1 is our future work.



---

*Source: 4318186-2020-03-12.xml*