# A Globally Convergent Filter-Type Trust Region  Method for Semidefinite Programming

Authors: Aiqun Huang; Chengxian Xu
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

When using interior methods for solving semidefinite programming (SDP), one needs to solve a system of linear equations at each iteration. For problems of large size, solving the system of linear equations can be very expensive. In this paper, based on a semismooth equation reformulation using Fischer's function, we propose a filter method with trust region for solving large-scale SDP problems. At each iteration we perform a number of conjugate gradient iterations, but do not need to solve a system of linear equations. Under mild assumptions, the convergence of this algorithm is established. Numerical examples are given to illustrate the convergence results obtained.


---

## Body

## 1. Introduction

Semidefinite programming (SDP) is convex programming over positive semidefinite matrices. For early application, SDP has been widely used in control theory and combinatorial optimization (see, e.g., [1–3]). Since some algorithms for linear optimization can be extended to many general SDP problems, that aroused much interest in SDP. In the past decade, many algorithms have been proposed for solving SDP, including interior-point methods (IPMs) [4–7], augmented methods [8–10], new Newton-type methods [11], modified barrier methods [12], and regularization approaches [13].For small and medium sized SDP problems, IPMs are generally efficient. But for large-scale SDP problems, IPMs become very slow. In order to improve this shortcoming, [9, 14] proposed inexact IPMs using an iterative solver to compute a search direction at each iteration. More recently, [13] applied regularization approaches to solve SDP problems. All of these methods are first-order based on a gradient, or inexact second-order based on an approximation of Hessian matrix methods [15].In this paper, we will extend filter-trust-region methods for solving linear (or nonlinear) programming [16] to large-scale SDP problems and use Lipschitz continuity. Furthermore, the accuracy of this method is controlled by a forcing parameter. It is shown that, under mild assumptions, this algorithm is convergent.The paper is organized as follows. Some preliminaries are introduced in Section2. In Section 3, we propose a filter-trust-region method for solving SDP problems, and we study the convergence of this method in Section 4. In Section 5, some numerical examples are presented to demonstrate the convergence results obtained in this paper. Finally, we give some conclusions in Section 6.In this paper, we use the following common notation for SDP problems:𝒳n and ℛm denote the space of n×n real symmetric matrices and the space of vectors with m dimensions, respectively; X≽0(X≻0) denotes that X∈𝒳n is positive semidefinite (positive definite), and X⪯0(X≺0) is used to indicate that X∈𝒳n is negative semidefinite (negative definite). A superscript T represents transposes of matrices or vectors. For X,Y∈𝒳n, the standard scalar product on the space of 𝒳n is defined by
(1.1)〈X,Y〉:=X•Y=trace(XY)=∑i,j=1n‍Xi,jYi,j.
If X∈𝒳n and x∈ℛm, we denote that ∥X∥F is the Frobenius norm of X, that is, ∥X∥F=〈X,X〉=∑i,j=1nXi,j2 and ∥x∥2 is the 2-norm of x, that is, ∥x∥2=xTx=∑i=1mxi2, respectively. Let X be a p×q matrix. Then we denote by Vec(X) a pq vector made of columns of X stacked one by one, and the operator Mat(·) is the inverse of Vec(·), that is, Mat(Vec(X))=X. We also denote that I is identity matrix.


## 2. Preliminaries

We consider a SDP problem of the form(2.1)min⁡C•XsubjecttoA(X)=b,X⪰0,
where C∈𝒳n, A(i)∈𝒳n, i=1,2,…,m, and b=(b1,b2,…,bm)T∈ℛm are given dates; 𝒜 is a linear map from 𝒳n to ℛm given by
(2.2)A(X):=[A(1)•XA(2)•X⋮A(m)•X],X∈Xn.
The dual to the problem (2.1) is given by
(2.3)max⁡bTysubjecttoA*(y)+S=C,S⪰0,
where 𝒜* is an adjoint operator of 𝒜:ℛm→𝒳n given by
(2.4)A*(y)=∑i=1m‍yiA(i),y∈Rm.
Obviously, X∈𝒳n and (y,S)∈ℛm×𝒳n are the primal and dual variables, respectively.It is easily verified that the SDP problem (2.1) is convex. When (2.1) and (2.3) have strictly feasible points, then strong duality holds, see [5, 12]. In this case, a point (X,y,S) is optimal for SDP problems (2.1) and (2.3) if and only if
(2.5)A(X)=b,A*(y)+S=C,X⪰0,S⪰0,〈X,S〉=0.
In the sense that (X,y,S) solves SDP problems (2.1) and (2.3) if and only if (X,y,S) solves (2.5) when both SDP problems (2.1) and (2.3) have strictly feasible points.We now introduce some lemmas which will be used in the sequel.Lemma 2.1 (see [17]).
LetA,B∈𝒳n and let A≽0,B≽0. Then 〈A,B〉=0 if and only if AB=0.ForX,S∈𝒳n, we define a mapping ϕ:𝒳n×𝒳n→𝒳n given by
(2.6)ϕ(X,S):=X+S-X2+S2,
which is attributed by Fischer to Burmeister (see [18, 19]). This function is nondifferentiable and has a basic property.Lemma 2.2 (see [20, Lemma 6.1]).
Letϕ be the Fischer-Burmeister function defined in (2.6). Then
(2.7)ϕ(X,S)=0⟺X⪰0,S⪰0,XS=0.In addition, forτ>0 and X,S∈𝒳n, we define a mapping ϕτ:𝒳n×𝒳n→𝒳n by
(2.8)ϕτ(X,S):=X+S-X2+S2+2τ2I,
which is differentiable and has following results.Lemma 2.3 (see [11, Proposition  2.3]).
Letτ>0 be any positive number and let ϕτ be defined by (2.8). Then
(2.9)ϕτ(X,S)=0⟺X≻0,S≻0,XS=τ2I.Lemma 2.4.
Letτ>0 be any positive number, and let ϕτ be defined by (2.8). If τ→0, we would have
(2.10)ϕτ(X,S)=0⟺X⪰0,S⪰0,XS=0.Proof.
The proof can be obtained from Lemmas2.2 and 2.3.Lemma 2.5 (see [20, pages 170–171]).
For anyC≻0, define the linear operator LC by
(2.11)LC[X]:=CX+XC,X∈Xn.
Then LC is strictly monotone and so has an inverse LC-1.Lemma 2.6 (see [21, Lemma  2]).
LetX,S,U,V∈𝒳n, and let ϕτ be defined by (2.8). For any τ>0, we have that ϕτ is Fréchet-differentiable and
(2.12)∇ϕτ(X,S)(U,V)=U+V-LC-1[XU+UX+SV+VS],
where C:=X2+S2+2τ2I.Lemma 2.7 (see [22, Corollary 2.7]).
LetF be a map from 𝒳n to 𝒳n. If F is locally Lipschitzian on 𝒳n, then F is almost everywhere Fréchet-differentiable on 𝒳n.


## 3. The Algorithm

In this section, we will present a filter-trust-region method for solving SDP problems (2.1) and (2.3). Firstly, for a parameter τ>0, we construct a function:
(3.1)Hτ(X,y,S):=(τA(X)-bA*(y)+S-CX+S-X2+S2+2τ2I),
where (X,y,S)∈𝒳n×ℛm×𝒳n.According to Lemmas2.1, 2.3 and 2.4, the following theorem is obvious.Theorem 3.1.
Letτ>0 and let Hτ(X,y,S) be defined by (3.1). If SDP problems (2.1) and (2.3) have strictly feasible points, then
(3.2)Hτ(X*,y*,S*)=0⟹(X*,y*,S*)solves(2.5).In what follows, we will study properties of the functionHτ(X,y,S). For simplicity, in the remaining sections of this paper, we denote Z:=(X,y,S), Zk:=(Xk,yk,Sk) and ΔZ:=(ΔX,Δy,ΔS).Theorem 3.2.
LetHτ(Z) be defined by (3.1). For any Z,ΔZ∈𝒳n×ℛm×𝒳n and τ>0, then Hτ(Z) is Fréchet-differentiable and
(3.3)∇Hτ(Z)(ΔZ)=(ΔτA(ΔX)-bA*(Δy)+ΔS-CΔX+ΔS-LC-1[XΔX+ΔXX+SΔS+ΔSS]),
where Δτ>0 and C:=X2+S2+2τ2I.Proof.
For anyZ∈𝒳n×ℛm×𝒳n, since 𝒜(X)-b and 𝒜*(y)+S-C are linear functions and continuous differentiable, it follows that they are also locally Lipschitz continuous. Then, from Lemma 2.7, 𝒜(X)-b and 𝒜*(y)+S-C are Fréchet-differentiable. Furthermore, X+S-X2+S2+2τ2I is Fréchet-differentiable from Lemma 2.6. Thus, Hτ(Z) is Fréchet-differentiable and has the form of (3.3). We complete the proof.We endow the variableZ with the following norm:
(3.4)‖Z‖=‖(X,y,S)‖:=(‖X‖F2+‖y‖22+‖S‖F2)1/2.
In addition, we set
(3.5)h(Z)=(h1(Z),h2(Z),h3(Z),h4(Z))T,
where
(3.6)h1(Z)=‖A(X)-b‖2,h2(Z)=‖A*(y)+S-C‖F,h3(Z)=‖X+S-X2+S2+2τ2I‖Fh4(Z)=|τ|.
We also define the function Hτ(Z) and the vector h(Z) with the following norm:
(3.7)‖Hτ(Z)‖=‖h(Z)‖=(∑i=14‍hi(Z)2)1/2=(‖A(X)-b‖22+‖A*(y)+S-C‖F2+‖X+S-X2+S2+2τ2I‖F2+τ2)1/2.Now, for anyτ>0, we define the merit function Ψ:𝒳n×ℛm×𝒳n→ℛ by
(3.8)Ψτ(Z):=12‖Hτ(Z)‖2.Lemma 3.3.
For anyτ>0 and Z∈𝒳n×ℛm×𝒳n, if X and S are nonsingular, then Ψτ(Z) is locally Lipschitz continuous and twice Fréchet-differentiable at every Z∈𝒳n×ℛm×𝒳n.Proof.
For anyτ>0, since Ψτ(Z) is convex and continuously differentiable, it follows that Ψτ(Z) is also locally Lipschitz continuous.
In addition, for anyZ∈𝒳n×ℛm×𝒳n, from [20, pages 173–175], h3(Z)2 is twice Fréchet-differentiable. Furthermore, h1(Z)2, h2(Z)2, and h4(Z)2 are continuous at every Z∈𝒳n×ℛm×𝒳n when τ>0, which, together with Lemma 2.7, Ψτ(Z) is twice Fréchet-differentiable. The proof is completed.Lemma 3.4.
LetHτ(Z) and Ψτ(Z) be defined by (3.1) and (3.8), respectively. For any τ>0, we have
(3.9)Ψτ(Z)=0⟺Hτ(Z)=0.Proof.
The proof can be immediately obtained from the definition ofHτ(Z) and Ψτ(Z).We follow the classical method for solvingΨτ(Z)=0, which consists some norm of the residual. For any τ>0, we consider
(3.10)min⁡Ψτ(Z),
where Z∈𝒳n×ℛm×𝒳n. Thus, for any τ>0, we want to find a minimizer Z* of Ψτ(Z). Furthermore, if Ψτ(Z*)=0, then Z* is also a solution of Hτ(Z).In order to state our method for solving (3.10), we consider using a filter mechanism to accept a new point. Just as [16, pages 19–20], the notation of filter is based on that of dominance.Definition 3.5.
For anyτ>0 and any Z1,Z2∈𝒳n×ℛm×𝒳n, a point Z1 dominates a point Z2 if and only if
(3.11)hi(Z1)≤hi(Z2)∀i=1,2,3,4.Thus, if iterateZ1 dominates iterate Z2,  the latter is of no real interest to us since Z1 is at least as good as Z2 for each of the components of h(Z). All we need to do is remember iterates that are no dominated by other iterates by using a structure called a filter.Definition 3.6.
LetF(k) be a set of  4-tuples of the following form:
(3.12)(h1(Zk),h2(Zk),h3(Zk),h4(Zk)).
We define F(k) as a filter if h(Zk) and h(Zl) belong to F(k), when k≠l, then
(3.13)hi(Zk)<hi(Zl)foratleastonei∈{1,2,3,4}.Definition 3.7.
A new pointZk+ is acceptable for the filter F(k) if and only if
(3.14)∀h(Zk)∈F(k)∃i∈{1,2,3,4}:hi(Zk+)≤hi(Zk)-α‖h(Zk)‖,
where α∈(0,1/4) is a small constant.Now, we formally present our trust region algorithm by using filter techniques.Algorithm 3.8.
The Filter-Trust-Region Algorithm
Step0. Choose an initial point Z0=(X0,y0,S0)∈𝒳n×ℛm×𝒳n, ε>0, 0<α<1/4 and τ0=〈X0,S0〉/2n. The constants η1, η2, η3, μ, γ, γ1, and γ2 are also given and satisfy
(3.15)0<η1≤η2≤η3<1,0<μ<1,0<γ<γ1<1≤γ2.
ComputeΨτ0(Z0), set Δ0=0.5∥∇Ψτ0(Z0)∥, k=0 and only (μ,-∞,μ,μ) in the filter F(0).
Step1. If ∇Ψτk(Zk)<ε, stop.
Step2. Compute ΔZk by solving the following problem:
(3.16)min⁡φk(ΔZ)s.t.‖ΔZ‖≤Δk,
where
(3.17)φk(ΔZ)=12‖Hτk(Zk)+∇Hτk(Zk)(ΔZ)‖2=Ψτk(Zk)+Hτk(Zk)T∇Hτk(Zk)(ΔZ)+12(ΔZ)T∇Hτk(Zk)T∇Hτk(Zk)(ΔZ).
If∥ΔZk∥<ε, stop.
Otherwise, computer the trial pointZk+=Zk+ΔZk.
Step3. Compute Ψτk(Zk+) and define the following ratio:
(3.18)rk=Ψτk(Zk)-Ψτk(Zk+)φk(0)-φk(ΔZk).
Step4. If rk≥η1, set Zk+1=Zk+.
Ifrk<η1 but Zk+ satisfies (3.14), then add h(Zk+) to the filter F(k) and remove all points from F(k) dominated by h(Zk+). At the same time, set Zk+1=Zk+.
Else, setZk+1=Zk.
Step5. Update τk by choosing
(3.19)τk+1∈{γτkifZk+1=Zk+,τkelse;
and update trust-region radius Δk by choosing
(3.20)Δk+1:={γΔk,ifrk<η1,γ1Δk,ifrk∈[η1,η2],Δk,ifrk∈(η2,η3),γ2Δk,ifrk≥η3.
Step6. Set k:=k+1 and go to Step 1.Remark 3.9.
Algorithm3.8 can be started any τ>0. In fact, in order to increase the convergent speed greatly, we always choose τ0=〈X0,S0〉/2n. In addition, in this algorithm, we fix τ at first, then search Z for Ψτ(Z)=0 to update Z. At last we update τ and repeat.The following lemma is a generalized case of Proposition 3.1 in [23].Lemma 3.10.
Algorithm3.8 is well defined, that is, the inner iteration (Step 2) terminates finitely.For the purpose of our analysis, in the sequence of points generated by Algorithm3.8, we denote 𝒜={k∣rk≥η1},ℬ={k|h(Zk+)isaddedtothefilterF(k)}, and 𝒞={k|Zk+1=Zk+ΔZk}. It is clear that, 𝒞=𝒜⋃‍ℬ.Remark 3.11.
Lemma3.3 implies that there exists a constant 0<M≤1 such that
(3.21)hi(Zk)≤M,‖∇2hi(Zk)‖≤M,‖∇2φk(ΔZ)‖≤M
for all k∈𝒞 and i∈{1,2,3,4}. The second of above inequalities ensures that the constant 0<M≤1 can also be chosen such that
(3.22)‖∇2Ψτk(Zk)‖≤M.


## 4. Convergence of Analysis

In this section, we present a proof of global convergence of Algorithm3.8. First, we make the following assumptions.Some lemmas will be presented to be used in the subsequent analysis.(S1)
φk(0)-φk(ΔZk)≥1/2∥∇Ψτk(Zk)∥min{Δk,∥∇Ψτk(Zk)∥/∥∇Hτk(Zk)T∇Hτk(Zk)∥}, where ΔZk is a solution of (3.16).(S2)
The iterations generated by Algorithm3.8 remain in a close, bounded domain.Lemma 4.1 (see [24]).
Let assumptions (S1) and (S2) hold. If there existsl0>0 such that ∥∇Ψτk(Zk)∥≥l0>0 for all k; then there exists l1>0 such that Δk≥l1.Lemma 4.2.
Let{τk} be the infinite sequence generated by the Algorithm 3.8. Then
(4.1)lim⁡k→∞τk=0.Proof.
Since|𝒞|=|𝒜|=+∞, from Steps 4 and 5 of Algorithm 3.8, τk+1=γτk and 0<γ<τ0<1. Therefore, τk+1=γkτ0. Moreover,
(4.2)lim⁡k→∞τk=lim⁡k→∞γkτ0=0
for 0<γ<τ0<1, which completes the proof.Theorem 4.3.
Let|𝒞|<+∞, assumptions (S1) and (S2) hold. Then there exists k∈𝒞 such that
(4.3)∇Ψτk(Zk)=0.Proof.
Suppose that∇Ψτk(Zk)≠0 for all k∈𝒞. Then there exists ω0>0 such that
(4.4)‖∇Ψτk(Zk)‖≥ω0>0.
From Lemma 4.1, there exists ω1>0 such that
(4.5)Δk≥ω1>0.
On the other hand,|𝒞|<+∞, let N be the last successful iteration, then ZN+1=ZN+2=⋯=ZN+j(j≥1) are unsuccessful iterations. From Steps 4 and 5 of Algorithm 3.8, rN+j<η1, for sufficiently large N, we have
(4.6)lim⁡N→∞ΔN+j=0,
which contradicts (4.5). The proof is completed.We now consider what happens if the set𝒜 is infinite in the course of Algorithm 3.8.Theorem 4.4.
Suppose that|𝒞|=|𝒜|=+∞, assumptions (S1) and (S2) hold. For any τ>0 and Z∈𝒳n×ℛm×𝒳n, if X and S are nonsingular, then each accumulation point of the infinite sequences generated by Algorithm 3.8 is a stationary point of Ψτ(Z).Proof.
The proof is by contradiction. Suppose that{Zk} is an infinite sequence generated by Algorithm 3.8, and any accumulation point of {Zk} is not a stationary point of Ψτ(Z). Suppose furthermore that Z* and τ* are the accumulation points of {Zk} and {τk}, respectively. Since Z* is not a stationary point of Ψτ(Z), then
(4.7)∇Ψτ*(Z*)≠0
and there exists ϵ0>0 such that
(4.8)‖∇Ψτ*(Z*)‖>ϵ0>0.
For some ϵ*>0, let 𝒩(Z*,ϵ*) be a neighborhood of Z*. From (4.8), there exists {Zk}k∈K∈𝒩(Z*,ϵ*) such that
(4.9)‖∇Ψτk(Zk)‖≥ϵ0>0,
where K⊆𝒜.
Form,m+ν∈K, because
(4.10)Ψτk(Zk)-Ψτk+1(Zk+1)≥η1[φk(0)-φk(ΔZk)],
we obtain that
(4.11)Ψτm(Zm)-Ψτm+ν(Zm+ν)=∑i=m∈Km+ν‍[Ψτi(Zi)-Ψτi+1(Zi+1)]≥η1∑i=m∈Km+ν‍[φk(0)-φk(ΔZk)]≥η1∑i=m∈Km+ν‍12‖∇Ψτk(Zk)‖min⁡{Δk,‖∇Ψτk(Zk)‖‖∇Hτk(Zk)T∇Hτk(Zk)‖}≥η1∑i=m∈Km+ν‍12ϵ0min⁡{Δk,ϵ0‖∇Hτk(Zk)T∇Hτk(Zk)‖}.
From (4.10), we know that Ψτk(Zk) is monotone decreasing and bounded below, which implies that Ψτm(Zm)-Ψτm+n(Zm+ν)→0 for m→∞,m∈K. Thus,
(4.12)η1∑i=m∈Km+ν‍12ϵ0min⁡{Δk,ϵ0‖∇Hτk(Zk)T∇Hτk(Zk)‖}⟶0.
As a result, we have
(4.13)lim⁡k→∞,k∈KΔk=0.
By the update rule of Δk, there exists an infinite subsequence K⋆⊆K, and we have that
(4.14)ri≤η1,lim⁡i→∞Δi=0,i∈K⋆.
which contradicts k∈K⊆𝒜. This completes the proof.In what follows, we investigate the case where the number of iterations added to the filterF(k) in the course of Algorithm 3.8 is infinite.Theorem 4.5.
Suppose that|𝒞|=|ℬ|=+∞ but |A|<+∞, SDP problems (2.1) and (2.3) have strictly feasible points. Suppose furthermore that assumptions (S1) and (S2) hold. For any τ>0 and Z∈𝒳n×ℛm×𝒳n, if X and S are nonsingular, then
(4.15)lim⁡k→∞‖Hτ(Zk)‖=lim⁡k→∞‖∇Ψτk(Zk)‖=0.Proof.
First let{τk} be the sequence generated by Algorithm 3.8. From Lemma 4.2, we have
(4.16)lim⁡k→∞τk=0,
which, together with assumption (S2), the desired result follows from [16, Lemma  3.1].


## 5. Numerical Experiments

In this section, we describe the results of some numerical experiments with the Algorithm3.8 for the random sparse SDP considered in [13]. All programs are written in Matlab code and all computations are tested under Matlab 7.1 on Pentium 4.In addition, in the computations, the following values are assigned to the parameters in the Algorithm:η1=0.1, η2=0.5, η3=0.8, μ=0.1, γ=0.2, γ1=0.5, and γ2=2. We also use the stopping criteria is being of ε=10-8.In the following Table1, the first two columns give the size of the matrix C and the dimension of the variable y. In the middle columns, “F-time” denotes the computing time (in seconds), “F-it.” denotes the numbers iteration, and “F-obj.” defines the value of Ψτk(Zk) when our stopping criteria is satisfied. Some numerical results of [13] are shown in the last two columns.Table 1
n
m
F-time
F-it.
F-obj.
R-time
R-it.
300
20000
30
20
3.2566
e
-
12
63
27
300
25000
72
23
5.1697
e
-
13
127
29
400
30000
63
25
0.2212
e
-
12
118
32
400
40000
152
31
6.2008
e
-
14
202
46
500
30000
176
35
8.5216
e
-
16
201
39
500
40000
108
41
9.1535
e
-
15
198
52
600
20000
321
47
8.9660
e
-
17
485
58
600
60000
298
38
3.5722
e
-
16
345
56As shown in Table1, all test problems have been solved just few iterations compared with [13]. Furthermore, this algorithm is less sensitive to the size of SDP problems. Comparatively speaking, our method is attractive and suitable for solving large-scale SDP problems.


## 6. Conclusions

In this paper, we have proposed a filter-trust-region method for SDP problems. Such a method offers a trade-off between the accuracy of solving the subproblems and the amount of work for solving them. Furthermore, numerical results show that our algorithm is attractive for large-scale SDP problems.



---

*Source: 819607-2012-08-26.xml*