# A Mixed Line Search Smoothing Quasi-Newton Method for Solving Linear Second-Order Cone Programming Problem

Authors: Zhuqing Gui; Chunyan Hu; Zhibin Zhu
Journal: ISRN Operations Research
 (2013)

---

## Abstract

Firstly, we give the Karush-Kuhn-Tucker (KKT) optimality
condition of primal problem and introduce Jordan algebra simply. On the basis of Jordan algebra, we extend smoothing Fischer-Burmeister (F-B) function to Jordan algebra and make the complementarity condition smoothing. So the first-order optimization condition can be reformed to a nonlinear system. Secondly, we use the mixed line search quasi-Newton method to solve this nonlinear system. Finally, we prove the globally and locally superlinear convergence of the algorithm.


---

## Body

## 1. Introduction

Linear second-order cone programming (SOCP) problems are convex optimization problems which minimize a linear function over the intersection of an affine linear manifold with the Cartesian product of second-order cones. Linear programming (LP), Linear second-order cone programming (SOCP), and semidefinite programming (SDP) all belong to symmetric cone analysis. LP is a special example of SOCP and SOCP is a special case of SDP. SOCP can be solved by the corresponding to the algorithm of SDP, and SOCP also has effectual solving method. Nesterov and Todd [1, 2] had an earlier research on primal-dual interior point method. In the rescent, it gives quick development about the solving method for SOCP. Many scholars concentrate on SOCP.The primal and dual standard forms of the linear SOCP are given by(1)PrimalDualmincTxmaxbTys.t.Ax=b,s.t.ATy+z=c,s.t.x≽K0,z≽K0,where the second-order coneK:
(2)K={(x0;x-)∈R×Rn-1∣x0≥∥x-∥},
where ∥·∥ refers to the standard Euclidean norm.In this paper, the vectorsx, c, and z and the matrix A are partitioned conformally, namely
(3)x=(x1;…;xr)xi∈Rni,c=(c1;…;cr)ci∈Rni,z=(z1;⋯;zr)zi∈Rni,A=(A1;⋯;Ar)Ai∈Rm×ni.Except for interior point method, semismoothing and smoothing Newton method can also be used to solve SOCP. In [3], the Karush-Kuhn-Tucker (KKT) optimality condition of primal-dual problem was reformulated to a semi-smoothing nonlinear system, which was solved by Newton method with central path. In [4], the KKT optimality condition of primal-dual problem was reformed to a smoothing nonlinear equations, then it was solved by combining Newton method with central path. References [3, 4] gave globally and locally quadratic convergent of the algorithm.


## 2. Preliminaries and Algorithm

In this section, we introduce the Jordan algebra and give the nonlinear system, which comes from the Karush-Kuhn-Tucker (KKT) optimality condition. At last, we introduce two kinds of derivative-free line search rules.Associated with each vectorx∈Rn, there is an arrow-shaped matrix Arw(x) which is defined as follows:
(4)Arw(x)=(x0x-Tx-x0I).Euclidean Jordan algebra is associated with second-order cones. For now we assume that all vectors consist of a single blockx=(x0;x-)∈Rn. For two vectors x and y, define the following multiplication:
(5)x∘z=(xTz;x0z-+z0x-)=Arw(x)z=Arw(x)Arw(z)e.So, “+”, “∘” with e=(1;0)∈R×Rn-1 give rise to a Jordan algebra associated with second-order cone K.It is well known that the vectorx∈Rn has a spectral decomposition as
(6)x=λ1c1+λ2c2,
where λ1, λ2 and c1, c2 are the spectral values and spectral vectors of x given by
(7)λi=x0+(-1)i∥x-∥,ci={12(1;(-1)ix-∥x-∥),ifx-≠0,12(1;(-1)iω),ifx-=0,
where i=1,2, and ω is any vector in Rn-1 satisfying ∥ω∥=1.The KKT optimality condition of problem (1) is written as follows:
(8)Ax-b=0,ATy+z-c=0,x,z∈K,x∘z=0.Interior point methods typically deal with the following perturbation of the optimality condition (8):
(9)Ax-b=0,ATy+z-c=0,x,z∈K,x∘z=μ2e.In this paper, we structure a nonlinear system that is equivalent to (9). Then the nonlinear system is solved by quasi-Newton method to get the optimum solution of (1). Here, we introduce a smoothing function φ(x,z,μ):Rn×Rn×R→Rn,
(10)φ(x,z,μ)=x+z-x2+z2+2μ2e.Reference [5] gives some properties of smoothing function (10).Proposition 1.
φ
(
x
,
z
,
0
)
=
0 if and only if x≽K0, z≽K0 and x∘z=0.Proposition 2.
For anyμ>0, φ(x,z,μ)=0 if and only if x≻K0, z≻K0 and x∘z=μ2e.LetF:Rn×Rm×Rn×R→Rm×Rn×Rn×R,
(11)F(x,y,z,μ)=(Ax-bATy+z-cφ(x,z,μ)μ).Apparently,F(x,y,z,μ)=0 is equivalent to (8). Let (x,y,z,μ)=u, then F(x,y,z,μ)=F(u). So, the KKT optimality condition is equivalent to the following:
(12)F(u)=0.Next, we solve (12) by using Broyden rank one quasi-Newton method. When we solve the problem (12) with quasi-Newton method, the gradient or Jacobian does not appear. It can reduce the amount of calculation. While it is not suitable to use the usual line search such as Wolf or Powll rules. Thus, we suggest two kinds of derivative-free line search rule.In 1986, Griewank [6] put forward a kind of monotonous line search. Set
(13)qk(α)=-F(uk)T(F(uk+αdk)-F(uk))∥F(uk+αdk)-F(uk)∥2.Letαk satisfy the following inequality:
(14)qk(α)≥12+ε,
where ε∈(0,1/6) is a constant.Due to (13) and (14), we obtain
(15)∥F(uk+αdk)∥2≤∥F(uk)∥2-2ε∥F(uk+αdk)-F(uk)∥2≤∥F(uk)∥2.Clearly, the line search is a normal descent method.From the definition ofqk(α), the following conclusion holds. When F(uk)TF′(uk)dk≠0, (14) holds for all αk sufficiently small. When F(uk)TF′(uk)dk=0, (14) does not hold for any αk.Because there is a failure in the line search rule, many scholars put forward some kinds of different derivative-free line search rules. In [7], Li and Fukushima suggested a kind of nonmonotone derivative-free line search rules. The step αk satisfies the following inequality:
(16)∥F(uk+αkdk)∥2≤∥F(uk)∥2-σ1∥αkF(uk)∥2-σ2∥αkdk∥2+ηk∥F(uk)∥2,
where, σ1,σ2>0 are constants, and there exists a constant η>0, such that the positive sequence {ηk} satisfies
(17)∑k=0∞‍ηk≤η<∞.Obviously, (16) holds for all αk>0 sufficiently small. For any k, we have
(18)∥F(uk+αkdk)∥2≤(1+ηk)∥F(uk)∥2.According to the introduction, we know that there is a defect in the line search rule (15), but it is monotonically decreasing, namely, ∥F(uk+1)∥≤∥F(uk)∥. However (16) is non-monotone line search rule. In this paper, the reasonable combination of the two line search rules is given.In order to implement the mixed line search rules, we define the functionf:R→R(19)f(α)=∥F(uk+αdk)∥2-∥F(uk)∥2α.Apparently,limα→0f(α)=F(uk)TF′(uk)dk. When α and |f(α)| are too small, (14) does not hold. We will use the non-monotone line search.On the basis of the previous section, we will suggest a Broyden rank one quasi-Newton method for solving SOCP in this section. Now we present an algorithm for solving (12).Algorithm A.
Step0. Initialization and Date. Choose parameters λ, δ∈(0,1), σ1, σ2, σ3>0, ε, ε0>0. Fix a positive sequence {ηk} that satisfies (17). Fix a starting point u0∈R2n+m+1, and an initial matrix B0∈R(2n+m+1)×(2n+m+1). Set k=0.
Step1. Termination Conditions. If F(uk)=0, stop; otherwise, let dk be a solution of the linear equation
(20)Bkdk+F(uk)=0.
Step
2. The Line Search for Unit Step. If
(21)∥F(uk+dk)∥≤λ∥F(uk)∥-σ3∥dk∥2
holds, then set αk=1. Go to Step4.
Step3. Mixed Line Search Rule.(3.1)
Seti=0;(3.2)
Ifδi satisfies (14), set αk=δi; otherwise, if |f(δi)|≤ε0 holds, let αk be the maximum of the numbers {1,δ1,δ2,…} satisfying (16). Else, set i=i+1. Go back to Step (3.2).
Step4. Update. Set uk+1=uk+αkdk.
Step5. Computation ofBk+1. By the Broyden rank one correction formula, we obtain
(22)Bk+1=Bk+(yk-Bksk)skT∥sk∥2,
where sk=uk+1-uk, yk=F(uk+1)-F(uk), and Bk+1 is nonsingular.
Step6. Setk=k+1. Go back to Step1.


## 3. Global Convergence

In this section, we prove the global convergence of algorithm. For this reason, we define some variables in the algorithm and give some hypotheses.We define(23)Gk+1=∫01F′(uk+τsk)dτ,thenyk=Gk+1sk. Set
(24)ξk=∥yk-Bksk∥∥sk∥,then(25)ξk=∥(Gk+1-Bk)sk∥∥sk∥=∥(Gk+1-Bk)dk∥∥dk∥.Proposition 3.
The sequence{uk} which is generated by the algorithm satisfies
(26)∥F(uk)∥≤∥F(uk-1)∥,
then the level set(27)Ω={u∈R2n+m+1∣∥F(uk+1)∥2≤eη∥F(u0)∥2}
is bounded, whereη is the constant defined in (17).Proposition 4.
F
′
(
u
) is Lipschitz continuous on R2n+m+1; that is, there exists a constant L>0 such that
(28)∥F′(u)-F′(v)∥≤L∥u-v∥,∀u,v∈R2n+m+1.Proof.
By [5], ∇φ(x,z,μ) is continuously differentiable function, then there exists a constant L>0 such that
(29)∥∇φ(x1,z1,μ1)-∇φ(x2,z2,μ2)∥≤L∥(x1,z1,μ1)-(x2,z2,μ2)∥,∀x1,x2,z1,z2,μ1,μ2.
For anyu,v∈R2n+m+1, we have
(30)∥F′(u)-F′(v)∥=∥∇φ(xu,zu,μu)-∇φ(xv,zv,μv)∥∥F′(u)-F′(v)∥≤L∥(xu,zu,μu)-(xv,zv,μv)∥∥F′(u)-F′(v)∥≤L∥u-v∥.(H1)
The matrixA has full of row rank.From Proposition3, Proposition 4, and (H1), F′(u) is reversible for all u∈Ω. There exist constants t′, 0<t≤T, 0<T1≤T2, and 0<t~≤T3, such that
(31)t′∥u-v∥≤∥F(u)-F(v)∥≤T′∥u-v∥,(32)t~∥sk∥≤∥F′(uk)sk∥≤T3∥sk∥,(33)T1≤∥(F′(u))-1∥≤T2,(34)t≤∥F′(u)∥≤T.Lemma 5.
If the sequence{uk} is generated by the algorithm, then {uk}⊂Ω.Proof.
Ifαk is defined by Step2 or (14), then we have
(35)∥F(uk+1)∥≤∥F(uk)∥.
The above inequality and (18) imply
(36)∥F(uk+1)∥2≤(1+ηk)∥F(uk)∥2,
where the sequence {uk} is generated by the algorithm. According to (36), we have
(37)∥F(uk+1)∥2≤(1+ηk)∥F(uk)∥2≤⋯≤∥F(u0)∥2∏j=0k‍(1+ηj)≤∥F(u0)∥2(11+k∑j=0k‍(1+ηj))k+1=∥F(u0)∥2(1+11+k∑j=0k‍ηj)k+1≤∥F(u0)∥2(1+η1+k)k+1≤eη∥F(u0)∥2.
Hence,{uk}⊂Ω. The claim holds.Lemma 6.
If (H1) holds and the sequence{uk} is generated by the algorithm, then
(38)∑k=0∞‍∥sk∥2<∞.Proof.
Ifαk is determined by (16), it is clearly known that
(39)σ2∥sk∥2≤∥F(uk)∥2-∥F(uk+αkdk)∥2+ηk∥F(uk)∥2.
Ifαk is determined by Step2, from it can be known that
(40)σ3∥sk∥2≤∥F(uk)∥-∥F(uk+1)∥+ηk∥F(uk)∥2.
Ifαk is ascertained by (14), then from (32), we have
(41)∥F(uk+αkdk)∥2≤∥F(uk)∥2-2ε∥F(uk+αkdk)-F(uk)∥2≤∥F(uk)∥2-2εt′2∥sk∥2.
Thus we obtain(42)2εt′2∥sk∥2≤∥F(uk)∥2-∥F(uk+1)∥2+ηk∥F(uk)∥2.
Setσ0=min{σ2,2εt′2}. Then, from (39) and (42), we see that
(43)σ0∥sk∥2≤∥F(uk)∥2-∥F(uk+1)∥2+ηk∥F(uk)∥2=(∥F(uk)∥-∥F(uk+1)∥)×(∥F(uk)∥+∥F(uk+1)∥)+ηk∥F(uk)∥2≤2eη∥F(u0)∥×(∥F(uk)∥-∥F(uk+1)∥)+ηk∥F(uk)∥2.
Letσ-=min{σ0,σ3} and C=max{1,2eη∥F(u0)∥}. It follows directly from (40) and (43) that
(44)σ-∥sk∥2≤C(∥F(uk)∥-∥F(uk+1)∥)+ηk∥F(uk)∥2.
By summing both sides of the above inequality, we have(45)σ-∑k=0∞‍∥sk∥2≤C∥F(u0)∥+∑k=0∞‍ηk∥F(uk+1)∥2≤C∥F(u0)∥+eη∥F(u0)∥2∑k=0∞‍ηk≤C∥F(u0)∥+eηη∥F(u0)∥2.
This completes the proof.According to some results in [8, 9], we can obtain the following results.Lemma 7.
Let the positive sequence{ak} and {tk} satisfy ak+1≤(1+tk)ak+tk and ∑k=0∞‍tk<∞, then the sequence {ak} converges.Lemma 8.
Let the sequence{uk} be generated by the algorithm, then the sequence {∥F(uk)∥2} is convergent.Lemma 9.
Let (H1) hold. Let the sequence{ξk} be defined by (24) and let {uk} be generated by the algorithm. If
(46)∑k=0∞‍∥sk∥2<∞,
then(47)limk→∞1k∑j=0k-1‍ξj2=0.
Specifically, there is a subsequence of{ξk} which converges to zero. Moreover, if
(48)∑k=0∞‍∥sk∥<∞,
then(49)∑k=0∞‍ξk2<∞.
In particular, the whole sequence{ξk}→0.Lemma 10.
Let (H1) hold and the sequence{uk},{dk} be generated by the algorithm. There exist sthe subsequence {uk,dk}k∈B of {uk,dk} that converges to {u-,d-}, respectively. Furthermore, one has
(50)F′(u-)d-+F(u-)=0.Proof.
LetGk+1 and ξk be defined by (23) and (24), respectively. By Lemmas 6 and 9, there is a subsequence of {ξk} tending to zero, from which Lemma 5 implies that {uk}⊂Ω is bounded. Without loss of generality, we assume that there is a subsequence {uk} that converges to u-. Since Lemma 6 implies sk=uk+1-uk→0, then Gk+1=∫01‍F′(uk+τsk)dτ→F′(u-), (k→∞). Therefore, there exists a constant T4>0 such that ∥Gk+1-1∥≤T4 for all k∈N sufficiently large. Thus from (20) and (25), we obtain
(51)∥dk∥=∥dk-Gk+1-1(Bkdk+F(uk))∥=∥Gk+1-1((Gk+1-Bk)dk-F(uk))∥≤∥Gk+1-1∥(∥(Gk+1-Bk)dk∥+∥F(uk)∥)≤T4(ξk∥dk∥+∥F(uk)∥).
So there is a constantE such that, for all k∈B sufficiently large,
(52)∥dk∥≤E∥F(uk)∥.
Without loss of generality, we assume that{dk}k∈B converges to d- (necessarily, we can treat the sequence B as its some subsequence). By (25), we obtain ∥Bkdk-Gk+1dk∥=ξk∥dk∥. It follows that Bkdk→F′(u-)d- as k→∞ with k∈B. Thus, taking the limit in (20) as k→∞ with k∈B, yields (50). The proof is finished.Theorem 11.
Assume that (H1) holds, then the whole sequence{uk} generated by the algorithm converges to the unique solution of (12).Proof.
It is clear from Lemma8 that the sequence {∥F(uk)∥2} is convergent. Thus, it is sufficient to verify that there exists an accumulation point of {uk} that is the solution of (12).
(i)  We suppose that there are an infinite number ofk such that αks are determined by (21). Let B={j1,j2,…} be an index set with B={k|αkbeingdeterminedby(21)}. If k∈B, then ∥F(uk+1)∥≤λ∥F(uk)∥ holds.
Ifk∉B, then we have ∥F(uk+1)∥2≤(1+ηk)∥F(uk)∥2, in that way,  ∥F(uk+1)∥≤(1+ηk)∥F(uk)∥. This implies that ∥F(ujk+1)∥≤λkeη∥F(uj0)∥.  Hence, limk∈B∥F(ujk)∥=0.
(ii)  If there exists an infinite number ofk such that αks are determined by (14). Let B1 be an index set with B1={k|αkisdeterminedby(14)}. Since {αk} is bounded, there is a subsequence {αk}k∈B2⊂B1 of {αk}k∈B1 that tends to α-≥0, that is, limk∈B2αk=α-. If α-≠0, then α-d-=0 implies that d-=0. By (50), we obtain F(u-)=0.
Ifα-=0, then αk→0+ for k→∞ with k∈B2. By Step3 of the algorithm, α~k=αk/δ does not satisfy (14) for all k∈B2 large enough, namely,
(53)-F(uk)T(F(uk+α~kdk)-F(uk))≤(12+ε)∥F(uk+α~kdk)-F(uk)∥2.
Thus,(54)limk∈B2-F(uk)T(F(uk+α~kdk)-F(uk))α~k≤limk∈B2(12+ε)∥F(uk+α~kdk)-F(uk)α~k∥2α~k,
that is,(55)F(u-)TF′(u-)d-≥0.
By (50), we get F(u-)=0.
(iii)  According to (ii), without loss of generality, we suppose that allαks are determined by (16) for all k sufficiently large. Let B4 be an index set with B4={k∣αkis determinedby(16)}. Set
(56)limk∈B4,k→∞αk=α′,
thenα′≥0 and α′d-=0. If α>0, then d-=0. Thus from (50), we obtain F(u-)=0. Otherwise, α′=0, that is,
(57)limk∈B4,k→∞αk=0.
By usingStep3 of the algorithm, we know that α′=αk/δ does not satisfy (16) for all k∈B4 sufficiently large. Therefore, we have
(58)∥F(uk+αk′dk)∥2-∥F(uk)∥2>-σ1∥αk′F(uk)∥2-σ2∥αk′dk∥2+ηk∥F(uk)∥2>-σ1∥αk′F(uk)∥2-σ2∥αk′dk∥2.
Dividing the both sides byαk′ and then taking the limit as k→∞ with k∈B4, we get
(59)limk∈B4,k→∞∥F(uk+αk′dk)∥2-∥F(uk)∥2αk′≥limk∈B4,k→∞-σ1αk′∥F(uk)∥2-σ2αk′∥dk∥2,
that is,(60)F(u-)TF′(u-)d-≥0.
It is clear from (50) that F(u-)=0. Therefore the result holds.


## 4. Local Superlinear Convergence

In this section, we prove the local superlinear convergence of the algorithm.Lemma 12.
If (H1) holds and the sequence{uk} is generated by the algorithm, then there exist a constant ξ>0 and an index k- such that
(61)αk=1,
wheneverk≥k- and ξk≤ξ. Furthermore, the relation
(62)∥F(uk+dk)∥≤λ∥F(uk)∥-σ3∥dk∥2<λ∥F(uk)∥
holds for allk≥k- such that ξk≤ξ.Proof.
ByStep2 of the algorithm, there exists a constant ξ such that (62) holds whenever ξk≤ξ and for all k sufficiently large. It follows from Theorem 11 that the sequence {uk} converges to the unique solution of problem (12), and there exists a constant T4 such that ∥Gk+1-1∥≤T4 for all k large enough. Then, from (52), we see that there exist constant ξ′>0 and E->0 such that
(63)∥dk∥≤E-∥F(uk)∥,
wheneverξk≤ξ′ and for all k sufficiently large. Due to (20), we obtain
(64)Gk+1(uk+dk-u*)=Gk+1(uk+dk-u*)-(Bkdk+F(uk))=Gk+1(uk-u*)+(Gk+1-Bk)dk-F(uk)=(Gk+1-F′(u*))(uk-u*)+(Gk+1-Bk)dk-F(uk)+F′(u*)+F′(u*)(uk-u*).
Hence, we have(65)∥uk+dk-u*∥≤∥Gk+1-1∥(∥Gk+1-F′(u*)∥∥uk-u*∥+∥(Gk+1-Bk)dk∥+∥F(uk)-F′(u*)-F′(u*)+(uk-u*)∥∥Gk+1-F′(u*)∥∥uk-u*∥)≤T4(ξk∥dk∥+o(∥uk-u*∥))≤T4(ξkE-∥F(uk)∥+o(∥uk-u*∥))≤T4(E-T′ξk∥uk-u*∥+o(∥uk-u*∥)),
where the last inequality follows from (31). This implies that
(66)∥F(uk+dk)∥=∥F(uk+dk)-F(u*)∥≤T′∥uk+dk-u*∥≤T′T4(E-T′ξk∥uk-u*∥+o(∥uk-u*∥)).
Since{uk}→u* holds, from (33), there exists t~>0 such that
(67)∥F(uk)∥=∥F(uk)-F(u*)∥≥t~∥uk-u*∥
for allk large enough. Then by (63), (65), and (66), we obtain
(68)∥F(uk+dk)∥-λ∥F(uk)∥+σ3∥dk∥2≤T′T4(E-T′ξk∥uk-u*∥+o(∥uk-u*∥))-λt~∥uk-u*∥+σ3E-2T′2∥uk-u*∥2=σ3E-2T′2∥uk-u*∥2+T4E-T′2ξk∥uk-u*∥-λt~∥uk-u*∥+o(∥uk-u*∥)=-(λt~-Qξk)∥uk-u*∥+o(∥uk-u*∥),
where Q=T4E-T′2. Let ξ=min{ξ′,λt~/2Q}, then we have
(69)∥F(uk+dk)∥-λ∥F(uk)∥+σ3∥dk∥2≤-12λt~∥uk-u*∥+o(∥uk-u*∥),
wheneverξk≤ξ. Hence, when uk is sufficiently close to u* for all k large enough, αk=1 can satisfy (62), which prove the conclusion.Theorem 13.
Assume that (H1) holds, then the sequence{uk} generated by the algorithm converges superlinearly to the unique solution of (12).Proof.
From (65), it is sufficient to verify that the sequence {ξk}→0. Let ξ and k- be determined by Lemma 12. By Lemmas 6 and 9, we have
(70)limk→∞1k∑i=0k-1‍ξi2=0.
Then there exists an indexk~ such that
(71)1k∑i=0k-1‍ξi2≤12ξ2,
wheneverk≥k~. This implies that
(72)∑i=0k-1‍ξi2≤k2ξ2.
The above inequality implies that for anyk≥k~, there are at least k/2 many i≤k such that ξi2≤ξ2, that is, ξi≤ξ. Let k′=max{k-,k~}, then, by Lemma 12, for any k≥2k′, there exist at least [k/2]-k′ many i≤k such that αi=1 and
(73)∥F(ui+1)∥=∥F(ui+di)∥≤λ∥F(ui)∥.
Therefore, we have(74)∥F(ui+1)∥2≤λ2∥F(ui)∥2.
Letθk be the index set for which (74) holds, then |θk|≥k/2-k′-1. When i∉θk, αk is determined by Step3. Then by (15) and (18), we get
(75)∥F(ui+1)∥2≤(1+ηi)∥F(ui)∥2.
Leti={k′,k′+1,…,k}. From (74) and (18), we obtain
(76)∥F(ui+1)∥2≤λ2|θk|∥F(uk′)∥2∏i=k′k‍(1+ηi)≤λk-2k′eη∥F(uk′)∥2,
that is,(77)∥F(uk+1)∥≤λ(k/2)-k′eη/2∥F(uk′)∥.
Sinceλ∈(0,1),
(78)∑k=0∞‍∥F(uk)∥<∞.
Hence,(79)∑‍∥uk-u*∥≤1t~∑‍∥F(uk)-F(u*)∥.
Since∥sk∥=∥uk+1-uk∥≤∥uk+1-u*∥+∥uk-u*∥ implies that
(80)∑‍∥sk∥<∞.
Therefore,ξk→0 as k→∞. The proof is finished.


## 5. Numerical Experiments

In this section, we carry out a number of numerical experiments based on Algorithm A. The results show that Algorithm A is effective. The numerical experiments are implemented on MATLAB 7.8.0.The following parameter values were used:(81)λ=0.5,δ=0.5,σ1=0.5,σ2=0.5,σ3=0.5,ε=0.1,ε0=0.01,ηk=0.95k,μ=1.When the condition∥F(uk)∥≤10-7 holds, the algorithm stops.In the tables of test results,itr denotes the number of iterations, prec the final residual of ∥F(uk)∥ when the algorithm stops, Pval and Dval the optimal values of the primal and dual problems of the test problems, and gap the dual gap of primal-dual problems. For the first nine experiments, the elements of the vectors b, c, matrix A, and initial points x, y, z are random numbers from 0 to 10. B0 is the identity matrix.All of the following experiments are to solve the problem(82)PrimalDualmincTxmaxbTys.t.Ax=b,s.t.ATy+z=c,s.t.x≽K0,z≽K0.Example 14.
The coefficients were chosen as(83)A=[4.01812.39921.83914.17270.75971.23322.39950.4965],bT=[9.02729.4479],cT=[7.80253.89742.41694.0391],xT=[4.90864.89253.37729.0005],yT=[3.69251.1120],zT=[0.96451.31979.42059.5613],
and the initial point was(x,y,z,μ). Let r=1, K4⊂R4. The data of the result of the problem is listed in Table 1.Table 1
Itr
Prec
Time (s)
P
val
D
val
Gap
30
9.5303E − 04
0.2023
—
—
—
32
7.6490E − 05
0.2113
—
—
—
35
7.3088E − 06
0.2140
—
—
—
37
4.2229E − 07
0.2159
—
—
—
38
3.6169E − 08
0.2172
31.36476337
31.36476321
1.5364E − 07Example 15.
The coefficients were chosen as(84)A=[9.31940.55270.45001.15076.06099.93260.93327.57168.42032.71566.77477.57547.38784.63491.64713.14399.87642.7506],bT=[9.54014.11082.1662],cT=[8.37557.48425.83861.60575.28844.6267],xT=[6.29130.14870.43301.80262.00477.1936],yT=[4.42878.45493.8979],zT=[3.79540.93232.59153.35843.75111.4626],
and the initial point was(x,y,z,μ). Let r=2, K6=K2×K4. The data of the result of the problem is listed in the Table 2.Table 2
Itr
Prec
Time (s)
P
val
D
val
Gap
3
5
8.3226
E
-
04
0.2637
—
—
—
37
7.8771
E
-
05
0.2648
—
—
—
40
5.6015
E
-
06
0.2667
—
—
—
42
1.9562
E
-
07
0.2680
—
—
—
44
2.9281
E
-
08
0.2690
5.469380116
5.469380172
5.5606
E
-
08Example 16.
The coefficients were chosen as(85)A=[4.25921.48068.28106.28693.00499.59168.07891.18478.89037.14479.09269.18970.17373.06476.42816.23982.57580.88055.61323.54999.51305.17845.98162.44790.46218.78660.75051.08030.20934.02183.91491.1229],bT=[2.67202.66399.36081.8618]cT=[8.46786.59667.79663.58561.84140.10180.85913.2947],xT=[5.07441.47599.20709.29461.36758.71570.12367.2204],yT=[8.78593.87452.46431.1172]zT=[3.00835.06573.86619.37301.59547.79711.77468.0529]
and the initial point was(x,y,z,μ). Let r=3, K8=K2×K3×K3. The data of the result of the problem is listed in the Table 3.Table 3
Itr
Prec
Time (s)
P
val
D
val
Gap
5
0
7.8376
E
-
04
0.5057
—
—
—
53
2.9878
E
-
05
0.5100
—
—
—
56
3.8683
E
-
06
0.5130
—
—
—
58
2.2355
E
-
07
0.5157
—
—
—
59
3.0909
E
-
08
0.5167
0.605650674
0.605650683
9.4441
E
-
09In Table4, there are the final numerical results of the next six experiments, where the notations m,n mean the number of the row and column of the matrix A, respectively, and NO denotes the number of the numerical experiments. In these experiments, we let r=1.Table 4
NO
m
n
Itr
Prec
Time (s)
P
val
D
val
Gap
exa4
4
8
57
4.0804
E
-
08
0.3167
-
22.63388297
-
22.63388298
1.6941
E
-
08
exa5
5
10
59
6.9742
E
-
08
0.1825
15.969930092
15.969930032
6.0249
E
-
08
exa6
6
10
61
5.4271
E
-
08
0.2328
7.5547887021
7.5547887065
4.4554
E
-
09
exa7
6
12
70
8.3825
E
-
08
0.2794
1.4491206670
1.4491206331
3.3890
E
-
08
exa8
7
14
77
6.2247
E
-
08
0.2878
5.6139106732
5.6139106566
1.6642
E
-
08
exa9
8
16
110
3.8613
E
-
08
0.3463
0.7337261831
0.7337262035
2.0411
E
-
08The ultimately numerical results of the last experiments were given in Table5. All the matrices of A that are in the examples are sparse matrices. The elements of these matrices aii, ai,i+1, a1,j, am,j, i=1,2,…,m, j=m+1,…,n, are random numbers from 0 to 10. The rest elements of these matrices are zero. In exa10 and exa11, we let r=1. In exa12, we set r=2 and K40=K20×K20.Table 5
NO
m
n
Itr
Prec
Time (s)
P
val
D
val
Gap
exa10
10
20
94
8.8778
E
-
08
0.6551
31.514993173
31.514993151
2.2923
E
-
08
exa11
15
28
117
5.4030
E
-
08
0.9529
48.646522308
48.646522494
1.8531
E
-
07
exa12
20
40
198
8.3512
E
-
08
2.3777
107.25705492
107.25705487
5.3633
E
-
10From Table5, we can see Algorithm A in this paper is efficient. The algorithm not only can solve the case of dense coefficient matrix A, but also can solve the case of sparse coefficient matrix A. From Table 5, we know that the cone K, whether or not partitioned the algorithm, is efficient.



---

*Source: 230717-2013-03-27.xml*