# A Two-Parametric Class of Merit Functions for the Second-Order

Authors: Xiaoni Chi; Zhongping Wan; Zijun Hao
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We propose a two-parametric class of merit
functions for the second-order cone complementarity problem (SOCCP)
based on the one-parametric class of complementarity functions. By
the new class of merit functions, the SOCCP can be reformulated as
an unconstrained minimization problem. The new class of merit
functions is shown to possess some favorable properties. In
particular, it provides a global error bound ifF and G have the
joint uniform Cartesian P-property. And it has bounded level sets
under a weaker condition than the most available conditions. Some
preliminary numerical results for solving the SOCCPs show the
effectiveness of the merit function method via the new class of
merit functions.


---

## Body

## 1. Introduction

We consider the following second-order cone complementarity problem (SOCCP) of finding(x,y,ζ)∈Rn×Rn×Rn such that
(1)〈x,y〉=0,x∈K,y∈K,x=F(ζ),y=G(ζ),
where 〈·,·〉 is the Euclidean inner product and F:Rn→Rn and G:Rn→Rn are continuously differentiable mappings. Here K⊂Rn is the Cartesian product of second-order cones (SOC); that is, K=Kn1×Kn2×⋯×Knm with m,n1,…,nm≥1, n=n1+n2+⋯+nm, and the ni-dimensional SOC defined by
(2)Kni:={xi=(xi1;xi2)∈R×Rni-1:xi1-∥xi2∥≥0},
with ∥·∥ denoting the Euclidean norm.Recently great attention has been paid to the SOCCP, since it has a variety of engineering and management applications, such as filter design, antenna array weight design, truss design, and grasping force optimization in robotics [1, 2]. Furthermore, the SOCCP contains a wide class of problems, such as nonlinear complementarity problems (NCP) and second-order cone programming (SOCP) [3, 4]. For example, the SOCCP with n1=n2=⋯=nm=1 and G(ζ)=ζ for any ζ∈Rn is the NCP, and the KKT conditions for the SOCP reduce to the SOCCP.There have been various methods for solving SOCCPs [5], such as interior point methods [6–8], (noninterior continuation) smoothing Newton methods [4, 9–12], and smoothing-regularization methods [13]. Recently, there is an alternative approach [14, 15] based on reformulating the SOCCP as an unconstrained smooth minimization problem. In that approach, it aims to find a smooth function ψ:Rn×Rn→R+ such that
(3)ψ(x,y)=0⟺〈x,y〉=0,x∈K,y∈K.
Such a ψ is called a merit function for the SOCCP. Thus the SOCCP is equivalent to the following unconstrained smooth (global) minimization problem:
(4)minζ∈Rnψ(F(ζ),G(ζ)).A popular choice ofψ is the Fischer-Burmeister (FB) merit function
(5)ψFB(x,y):=12∥ϕFB(x,y)∥2,
where ϕFB:Rn×Rn→Rn is the vector-valued FB function defined by
(6)ϕFB(x,y):=x2+y2-x-y,
with x2=x∘x denoting the Jordan product between x and itself and x being a vector such that (x)2=x. The function ψFB is shown to be a merit function for the SOCCP in [14].In this paper, we consider the two-parametric class of merit functions defined by(7)ψτ1,τ2(x,y):=τ1ψ0(x,y)+ψτ2(x,y),
where ψ0:Rn×Rn→R+ and ψτ:Rn×Rn→R+ are given, respectively, by
(8)ψ0(x,y):=12∥(x∘y)+∥2,(9)ψτ(x,y):=12∥ϕτ(x,y)+∥2,
with (·)+ denoting the metric projection on the second-order cone K, τ1>0 and τ2∈(0,4). Here ϕτ:Rn→Rn is the one-parametric class of SOC complementarity functions [16] defined by
(10)ϕτ(x,y):=x2+y2+(τ-2)(x∘y)-x-y,
where τ∈(0,4) is an arbitrary but fixed parameter. When τ=2, ϕτ reduces to the vector-valued FB function given by (6), and as τ→0, it becomes a multiple of the vector-valued residual function
(11)ϕNR(x,y):=x-(x-y)+.
Thus, the one-parametric class of vector-valued functions (10) covers two popular second-order cone complementarity functions. Hence the two-parametric class of merit functions defined as (7)–(10) includes a broad class of merit functions.We will show that the SOCCP can be reformulated as the following unconstrained smooth (global) minimization problem:(12)minζ∈Rnf(ζ):=ψτ1,τ2(F(ζ),G(ζ)).Ifτ1=1 and τ2=2, the function f in (12) induced by the new class of merit functions ψτ1,τ2 reduces to [17]
(13)fLT^(ζ):=ψ0(F(ζ),G(ζ))+12∥ϕFB(F(ζ),G(ζ))+∥2,
with ψ0 given as (8). It has been shown that fLT^ provides a global error bound if F and G are jointly strongly monotone, and it has bounded level sets if F and G are jointly monotone and a strictly feasible solution exists [17]. In contrast, the merit function ψFB lacks these properties.Motivated by these works, we aim to study the two-parametric class of merit functions for the SOCCP defined as (7)–(10) and its favorable properties in this paper. We also prove that the class of merit functions provides a global error bound if F and G have the joint uniform Cartesian P-property, which will play an important role in analyzing the convergence rate of some iterative methods for solving the SOCCP. And it has bounded level sets under a rather weak condition, which ensures that the sequence generated by a descent method has at least one accumulation point.The organization of this paper is as follows. In Section2, we review some preliminaries including the Euclidean Jordan algebra associated with SOC and some results about the one-parametric class of SOC complementarity functions. In Section 3, based on the one-parametric class of SOC complementarity functions, we propose a two-parametric class of merit functions for the second-order cone complementarity problem (SOCCP), which is shown to possess some favorable properties. In Section 4, we show that the class of merit functions provides a global error bound if F and G have the joint uniform Cartesian P-property, and it has bounded level sets under a rather weak condition. Some preliminary numerical results are reported in Section 5. And we close this paper with some conclusions in Section 6.In what follows, we denote the nonnegative orthant ofR by R+. We use the symbol ∥·∥ to denote the Euclidean norm defined by ∥x∥:=xTx for a vector x or the corresponding induced matrix norm. For simplicity, we often use x=(x1;x2) for the column vector x=(x1,x2T)T. For the SOC Kn, intKn, and bdKn mean the topological interior and the boundary of Kn, respectively.


## 2. Preliminaries

In this section, we recall some preliminaries, which include Euclidean Jordan algebra [3, 18] associated with the SOC K and some results used in the subsequent analysis.Without loss of generality, we may assume thatm=1 and K=Kn in Sections 2 and 3.First, we recall the Euclidean Jordan algebra associated with the SOC and some useful definitions. The Euclidean Jordan algebra for the SOCKn is the algebra defined by
(14)x∘y=(xTy;x1y2+y1x2),∀x,y∈Rn,
with e=(1,0,…,0)∈Rn being its unit element. Given an element x=(x1;x2)∈R×Rn-1, we define
(15)L(x)=(x1x2Tx2x1I),
where I represents the (n-1)×(n-1) identity matrix. It is easy to verify that x∘y=L(x)y for any y∈Rn. Moreover, L(x) is symmetric positive definite (and hence invertible) if and only if x∈intKn.Now we give the spectral factorization of vectors inRn associated with the SOC Kn. Let x=(x1;x2)∈R×Rn-1. Then x can be decomposed as
(16)x=λ1u(1)+λ2u(2),
where λ1,λ2 and u(1),u(2) are the spectral values and the associated spectral vectors of x given by
(17)λi=x1+(-1)i∥x2∥,u(i)={12(1;(-1)ix2∥x2∥),ifx2≠0,12(1;(-1)iω),otherwise,
for i=1,2, with any ω∈Rn-1 such that ∥ω∥=1. It is obvious that ∥u(1)∥=∥u(2)∥=1/2. By the spectral factorization, a scalar function can be extended to a function for the SOC. For any x∈Rn, we define
(18)x2=λ12u(1)+λ22u(2).
Since both eigenvalues of any x∈Kn are nonnegative, we define
(19)x=λ1u(1)+λ2u(2).Lemma 1 (see [14]).
LetC be any closed convex cone in Rn. For each x∈Rn, let xC+ and xC- denote the nearest point (in the Euclidean norm) projection of x onto C and -C*, respectively. The following results hold.(i)
For anyx∈Rn, we have x=xC++xC- and ∥x∥2=∥xC+∥2+∥xC-∥2.(ii)
For anyx∈Rn and y∈C, we have 〈x,y〉≤〈xC+,y〉.Lemma 2 (see [19]).
Letx=(x1;x2)∈R×Rn-1 and y=(y1;y2)∈R×Rn-1. Then we have
(20)〈x,y〉≤2∥(x∘y)+∥.The following results, describing the special properties of the functionϕτ given as (10), will play an important role in the subsequent analysis.Lemma 3 (see [16]).
For anyx=(x1;x2), y=(y1;y2)∈R×Rn-1, if z=(z1;z2)=x2+y2+(τ-2)(x∘y)∉intKn, then
(21)x12=∥x2∥2,y12=∥y2∥2,x1y1=x2Ty2,x1y2=y1x2,x12+y12+(τ-2)x1y1=∥x1x2+y1y2+(τ-2)x1y2∥=∥x2∥2+∥y2∥2+(τ-2)x2Ty2.
If, in addition, (x,y)≠(0,0), then z2≠0, and furthermore,
(22)x2Tz2∥z2∥=x1,x1z2∥z2∥=x2,y2Tz2∥z2∥=y1,y1z2∥z2∥=y2.Lemma 4 (see [20]).
For anyx,y∈Rn, let ϕτ be defined as in (10). Then,
(23)2∥ϕτ(x,y)∥2≥2∥ϕτ(x,y)+∥2≥4-τ2[∥(-x)+∥2+∥(-y)+∥2].


## 3. A Two-Parametric Class of Merit Functions

In this section, we study the two-parametric class of merit functionsψτ1,τ2 given by (7)–(10). As we will see, ψτ1,τ2 has some favorable properties. The most important property is that the SOCCP can be reformulated as the global minimization of the function f(ζ) given as (12). Moreover, the function f provides a global error bound and bounded level sets under weak conditions, which will be shown in the next section.Proposition 5.
Letψτ be given by (9). Then,
(24)ψτ(x,y)=0,〈x,y〉≤0⟺〈x,y〉=0,x∈Kn,y∈Kn.Proof.
Supposex∈Kn, y∈Kn, and 〈x,y〉=0. Thus by Proposition 3.1 [16], we have ϕτ(x,y)=0 and therefore ψτ(x,y)=(1/2)∥ϕτ(x,y)+∥2=0, 〈x,y〉≤0. Conversely, we assume ψτ(x,y)=0 and 〈x,y〉≤0. Then ϕτ(x,y)+=0 implies ϕτ:=ϕτ(x,y)∈-Kn. From (10), we obtain
(25)x+y=x2+y2+(τ-2)(x∘y)-ϕτ.
Squaring both sides yields
(26)(4-τ)(x∘y)=-2(x2+y2+(τ-2)(x∘y)∘ϕτ)+(ϕτ)2.
Taking the trace of both sides and using the fact tr(x∘y)=2〈x,y〉, we have
(27)2(4-τ)〈x,y〉=-4〈x2+y2+(τ-2)(x∘y),ϕτ〉+2∥ϕτ∥2.
Since x2+y2+(τ-2)(x∘y)∈Kn and ϕτ∈-Kn, we obtain
(28)-4〈x2+y2+(τ-2)(x∘y),ϕτ〉≥0,
and thus the right hand side of (27) is nonnegative. Then by the assumption 〈x,y〉≤0, we have 〈x,y〉=0. This together with (27) implies ϕτ(x,y)=0. Therefore, it follows from Proposition 3.1 [16] that x∈Kn and y∈Kn.Proposition 6.
The functionψτ given by (9) is differentiable at any (x,y)∈Rn×Rn. Moreover, ∇xψτ(0,0)=∇yψτ(0,0)=0; if x2+y2+(τ-2)(x∘y)∈intKn, then
(29)∇xψτ(x,y)=(Lx+((τ-2)/2)yLz-1-I)ϕτ(x,y)+,∇yψτ(x,y)=(Ly+((τ-2)/2)xLz-1-I)ϕτ(x,y)+;
if (x,y)≠(0,0) and x2+y2+(τ-2)(x∘y)∉intKn, then x12+y12+(τ-2)x1y1≠0, and
(30)∇xψτ(x,y)=[x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)+,∇yψτ(x,y)=[y1+((τ-2)/2)x1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)+.Proof
Case 1. If (x,y)=(0,0), then for any h=(h1;h2), k=(k1;k2)∈R×Rn-1, let μ1≤μ2 be the spectral values of h2+k2+(τ-2)(h∘k) and let v(1),v(2) be the corresponding spectral vectors. Then,
(31)∥h2+k2+(τ-2)(h∘k)-h-k∥=∥μ1v(1)+μ2v(2)-h-k∥≤μ1∥v(1)∥+μ2∥v(2)∥+∥h∥+∥k∥≤2μ2+∥h∥+∥k∥.
It follows from the definition of spectral value that
(32)μ2=∥h∥2+∥k∥2+(τ-2)hTk+∥2(h1h2+k1k2)+(τ-2)(h1k2+k1h2)∥≤2∥h∥2+2∥k∥2+3|τ-2|∥h∥∥k∥≤5(∥h∥2+∥k∥2).
Combining (31) and (32) together with Lemma 4 yields that
(33)2[ψτ(h,k)-ψτ(0,0)]=∥ϕτ(h,k)+∥2≤∥ϕτ(h,k)∥2=∥h2+k2+(τ-2)(h∘k)-h-k∥2≤[10(∥h∥2+∥k∥2)+∥h∥+∥k∥]2=O(∥h∥2+∥k∥2).
This shows that ψτ(x,y) is differentiable at (0,0) with ∇xψτ(0,0)=∇yψτ(0,0)=0.
Case 2. If x2+y2+(τ-2)(x∘y)∈intKn, let g:Rn→R+ be defined by g(z)=(1/2)∥z+∥2 for any z∈Rn. By the proof of Proposition 3.2 [17], g(z) is continuously differentiable and ∇g(z)=z+. Since ψτ(x,y)=g(ϕτ(x,y)) and ϕτ(x,y) is differentiable at any (x,y) satisfying x2+y2+(τ-2)(x∘y)∈intKn by Proposition 3.2 [16], ψτ is differentiable in this case and
(34)∇xψτ(x,y)=∇xϕτ(x,y)∇g(ϕτ(x,y))=(Lx+((τ-2)/2)yLz-1-I)ϕτ(x,y)+,∇yψτ(x,y)=∇yϕτ(x,y)∇g(ϕτ(x,y))=(Ly+((τ-2)/2)xLz-1-I)ϕτ(x,y)+.
Case 3. If (x,y)≠(0,0) and x2+y2+(τ-2)(x∘y)∉intKn, it follows from Lemma 3 that
(35)x12+y12+(τ-2)x1y1=∥x1x2+y1y2+(τ-2)x1y2∥≠0.
In this case, direct calculations together with Lemma 3 yield
(36)ϕτ(x,y)=(x12+y12+(τ-2)x1y1-x1-y1x1x2+y1y2+((τ-2)/2)x1y2+((τ-2)/2)y1x2x12+y12+(τ-2)x1y1-x2-y2).
Thus, the bigger spectral value λ2 of ϕτ(x,y) and its corresponding spectral vector u(2) are given as
(37)λ2=x12+y12+(τ-2)x1y1-x1-y1+∥w2∥,u(2)=12(1;w2∥w2∥),
where
(38)w2=x1x2+y1y2+((τ-2)/2)x1y2+((τ-2)/2)y1x2x12+y12+(τ-2)x1y1-x2-y2.
By the spectral factorization, we have
(39)ϕτ(x,y)+=ϕτ(x,y)⟺ϕτ(x,y)∈Kn,ϕτ(x,y)+=0⟺ϕτ(x,y)∈-Kn,ϕτ(x,y)+=λ2u(2)⟺ϕτ(x,y)∉Kn∪-Kn.
Therefore, we prove the differentiability of ψτ in this case by considering the following three subcases.
(i) Ifϕτ(x,y)∉Kn∪-Kn, then ϕτ(x,y)+=λ2u(2), where λ2,u(2) are given by (37). Then we have
(40)ψτ(x,y)=12∥ϕτ(x,y)+∥2=14λ22=14[(x12+y12+(τ-2)x1y1-x1-y1)2+2(x12+y12+(τ-2)x1y1-x1-y1)∥w2∥+∥w2∥2(x12+y12+(τ-2)x1y1-x1-y1)2].
It is obvious that ψτ is differentiable in this case. Moreover, by Lemma 3, we have
(41)∇x1w2=[x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1(x2+τ-22y2)x12+y12+(τ-2)x1y1-(x1x2+y1y2+τ-22x1y2+τ-22y1x2)×x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1]×(x12+y12+(τ-2)x1y1)-1=[(x2+τ-22y2)(x12+y12+(τ-2)x1y1)-(x1x2+y1y2+τ-22x1y2+τ-22y1x2)×(x1+τ-22y1)]×(x12+y12+(τ-2)x1y1)-3=0,∇x2w2=x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1.
Therefore, the derivative of ψτ with respect to x1 is
(42)∂∂x1ψτ(x,y)=14[w2T∇x1w2∥w2∥w2T∇x1w2∥w2∥2(x12+y12+(τ-2)x1y1-x1-y1)×(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)+2(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)∥w2∥+2(x12+y12+(τ-2)x1y1-x1-y1)×w2T∇x1w2∥w2∥+2w2T∇x1w2]=12[(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)×(x12+y12+(τ-2)x1y1-x1-y1+∥w2∥)(x1+(τ-2/2)y1x12+y12+(τ-2)x1y1-1)],
and the gradient of ψτ with respect to x2 is
(43)∇x2ψτ(x,y)=14[∇x2w2·w2∥w2∥2(x12+y12+(τ-2)x1y1-x1-y1)×∇x2w2·w2∥w2∥+2∇x2w2·w2]=12[(x1+(τ-2/2)y1x12+y12+(τ-2)x1y1-1)(x12+y12+(τ-2)x1y1-x1-y1)×(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)w2∥w2∥+(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)w2]=12[(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)×(x12+y12+(τ-2)x1y1-x1-y1+∥w2∥)w2∥w2∥(x1+(τ-2/2)y1x12+y12+(τ-2)x1y1-1)].
Then it follows from (37), (42), and (43) that ∇xψτ can be rewritten as
(44)∇xψτ(x,y)=(∂∂x1ψτ(x,y)∇x2ψτ(x,y))=(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)λ2u(2)=(x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1)ϕτ(x,y)+.
Similarly, we can show that
(45)∇yψτ(x,y)=(y1+((τ-2)/2)x1x12+y12+(τ-2)x1y1-1)ϕτ(x,y)+.
(ii) Ifϕτ(x,y)∈Kn, we have ϕτ(x,y)+=ϕτ(x,y) and thus ψτ(x,y)=(1/2)∥ϕτ(x,y)∥2. Then by Proposition 3.2 [16], the gradient of ψτ is
(46)∇xψτ(x,y)=[x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)=[x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)+,∇yψτ(x,y)=[y1+((τ-2)/2)x1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)=[y1+((τ-2)/2)x1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)+.
If there exists (x′,y′) such that ϕτ(x′,y′)∉Kn∪-Kn and ϕτ(x′,y′)→ϕτ(x,y), it follows from (44)–(46) that
(47)∇xψτ(x′,y′)⟶∇xψτ(x,y),∇yψτ(x′,y′)⟶∇yψτ(x,y).
Therefore, ψτ is differentiable in this subcase.
(iii) Ifϕτ(x,y)∈-Kn, we have ϕτ(x,y)+=0 and thus ψτ(x,y)=(1/2)∥ϕτ(x,y)+∥2=0. Then it is obvious that the gradient of ψτ is
(48)∇xψτ(x,y)=0=[x1+((τ-2)/2)y1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)+,∇yψτ(x,y)=0=[y1+((τ-2)/2)x1x12+y12+(τ-2)x1y1-1]ϕτ(x,y)+.
If there exists (x′,y′) such that ϕτ(x′,y′)∉Kn∪-Kn and ϕτ(x′,y′)→ϕτ(x,y), it follows from (44), (45), and (48) that
(49)∇xψτ(x′,y′)⟶0=∇xψτ(x,y),∇yψτ(x′,y′)⟶0=∇yψτ(x,y).
Therefore, ψτ is differentiable in this subcase.Proposition 7.
Letψτ be given by (9). For any x=(x1,x2), y=(y1,y2)∈R×Rn-1, we have
(50)〈x,∇xψτ(x,y)〉+〈y,∇yψτ(x,y)〉=∥ϕτ(x,y)+∥2,(51)〈∇xψτ(x,y),∇yψτ(x,y)〉≥0,
and the equality in (51) holds whenever ψτ(x,y)=0.Proof.
By following the proof of Lemma 4.1 [16] and using Proposition 6, we can show that the desired results hold.Proposition 8.
Letf:Rn→R+ be given by (7)–(10) and (12). Then, the following results hold.(i)
For allζ∈Rn, we have f(ζ)≥0 and f(ζ)=0 if and only if ζ solves the SOCCP.(ii)
IfF and G are differentiable, the function f is differentiable with
(52)∇f(ζ)=τ1[∇F(ζ)LG(ζ)+∇G(ζ)LF(ζ)](F(ζ)∘G(ζ))++∇F(ζ)∇xψτ2(F(ζ),G(ζ))+∇G(ζ)∇yψτ2(F(ζ),G(ζ)).Proof.
(i) It is obvious thatf(ζ)≥0 for all ζ∈Rn. Now we prove f(ζ)=0 if and only if ζ solves the SOCCP. Suppose f(ζ)=0. Then we have ψτ2(x,y)=0, and ψ0(x,y)=0 which implies x∘y∈-Kn and therefore 〈x,y〉≤0. By Proposition 5, the last relation together with ψτ2(x,y)=0 yields 〈x,y〉=0, x∈Kn, y∈Kn. Therefore, ζ solves the SOCCP. On the other hand, suppose that ζ solves the SOCCP. Then 〈x,y〉=0,  x∈Kn,  y∈Kn, which are equivalent to x∘y=0, x∈Kn,y∈Kn [4]. By Proposition 5, (7), (8), and (12), we have ψτ2(x,y)=0, ψ0(x,y)=0, and therefore f(ζ)=0.
(ii) From Lemma 3.1 [19], we have that the function ψ0 is differentiable for all (x,y)∈Rn×Rn with ∇xψ0(x,y)=Ly·(x∘y)+ and ∇yψ0(x,y)=Lx·(x∘y)+. Then, by the chain rule and direct calculations, the result follows.


## 4. Error Bound and Bounded Level Sets

By Proposition8, we see that the SOCCP is equivalent to the global minimization of the function f(ζ). In this section, we show that the function f provides a global error bound for the solution of the SOCCP and has bounded level sets, under rather weak conditions.In this section, we consider the general case thatK⊂Rn is the Cartesian product of SOCs; that is, K=Kn1×Kn2×⋯×Knm with m,n1,…,nm≥1, n=n1+n2+⋯+nm. Thus, we obtain
(53)ψτ1,τ2(x,y)=∑i=1m‍ψτ1,τ2(xi,yi),f(ζ)=∑i=1m‍ψτ1,τ2(Fi(ζ),Gi(ζ)),
and therefore the results in Sections 2 and 3 can be easily extended to the general case.First, we discuss under what condition the functionf provides a global error bound for the solution of the SOCCP. To this end, we need the concepts of Cartesian P-properties introduced in [21] for a nonlinear transformation, which are natural extensions of the P-properties on Cartesian products in Rn established by Facchinei and Pang [22]. Recently, the Cartesian P-properties are extended to the context of general Euclidean Jordan algebra associated with symmetric cones [20].Definition 9.
The mappingsF=(F1,…,Fm) and G=(G1,…,Gm) are said to have(i)
the joint uniform CartesianP-property if there exists a constant ρ>0 such that, for every ζ,ξ∈Rn, there is an index i∈{1,2,…,m} such that
(54)〈Fi(ζ)-Fi(ξ),Gi(ζ)-Gi(ξ)〉≥ρ∥ζ-ξ∥2;(ii)
the joint CartesianP-property if, for every ζ,ξ∈Rn with ζ≠ξ, there is an index i∈{1,2,…,m} such that
(55)ζi≠ξi,〈Fi(ζ)-Fi(ξ),Gi(ζ)-Gi(ξ)〉>0.Now we show that the functionf provides a global error bound for the solution of the SOCCP if F and G have the joint uniform Cartesian P-property.Proposition 10.
Letf be given by (7)–(10) and (12). Suppose that F and G have the joint uniform Cartesian P-property and the SOCCP has a solution ζ*. Then there exists a constant κ>0 such that, for any ζ∈Rn,
(56)κ∥ζ-ζ*∥2≤(2τ1+44-τ2)f(ζ)1/2.Proof.
SinceF and G have the joint uniform Cartesian P-property, there exists a constant ρ>0 such that, for any ζ∈Rn, there is an index i∈{1,2,…,m} such that
(57)ρ∥ζ-ζ*∥2≤〈Fi(ζ)-Fi(ζ*),Gi(ζ)-Gi(ζ*)〉=〈Fi(ζ),Gi(ζ)〉+〈Fi(ζ*),-Gi(ζ)〉+〈-Fi(ζ),Gi(ζ*)〉≤〈Fi(ζ),Gi(ζ)〉+〈Fi(ζ*),(-Gi(ζ))+〉+〈(-Fi(ζ))+,Gi(ζ*)〉≤2∥(Fi(ζ)∘Gi(ζ))+∥+∥Fi(ζ*)∥∥(-Gi(ζ))+∥+∥(-Fi(ζ))+∥∥Gi(ζ*)∥≤max{2,∥Fi(ζ*)∥,∥Gi(ζ*)∥}×[∥(Fi(ζ)∘Gi(ζ))+∥+∥(-Fi(ζ))+∥+∥(-Gi(ζ))+∥]≤max{2,∥F(ζ*)∥,∥G(ζ*)∥}×[∥(Fi(ζ)∘Gi(ζ))+∥+∥(-Fi(ζ))+∥+∥(-Gi(ζ))+∥]≤max{2,∥F(ζ*)∥,∥G(ζ*)∥}×[∥(F(ζ)∘G(ζ))+∥+∥(-F(ζ))+∥+∥(-G(ζ))+∥],
where the second inequality is due to Lemma 1(ii) and the third inequality follows from Lemma 2. Setting κ:=ρ/max{2,∥F(ζ*)∥,∥G(ζ*)∥}, we obtain
(58)κ∥ζ-ζ*∥2≤∥(F(ζ)∘G(ζ))+∥+∥(-G(ζ))+∥+∥(-F(ζ))+∥.
By (7), (8), and (12), we have
(59)∥(F(ζ)∘G(ζ))+∥=2ψ0(F(ζ),G(ζ))1/2≤2τ1f(ζ)1/2.
Moreover, we obtain from Lemma 4 that
(60)∥(-F(ζ))+∥+∥(-G(ζ))+∥≤2[∥(-F(ζ))+∥2+∥(-G(ζ))+∥2]1/2≤44-τ2ψτ2(F(ζ),G(ζ))1/2≤44-τ2f(ζ)1/2.
Combining (58), (59),  and (60) yields the desired result.To guarantee the boundedness of the level sets(61)Lf(γ):={ζ∈Rn∣f(ζ)≤γ}
for any γ≥0, we give the following condition.Condition 11.
For any sequence{ζk}⊆Rn such that
(62)∥ζk∥⟶+∞,∥(-F(ζk))+∥<+∞,∥(-G(ζk))+∥<+∞,
there holds that
(63)max1≤i≤mλmax[(Fi(ζk)∘Gi(ζk))+]⟶+∞.Proposition 12.
If the mappingsF and G satisfy Condition 11, then the level sets Lf(γ) of f for any γ≥0 are bounded.Proof.
On the contrary, we assume that there exists an unbounded sequence{ζk}⊆Lf(γ^) for some γ^≥0. Thus ∥ζk∥→+∞ and ψτ2(F(ζk),G(ζk))≤f(ζk)≤γ^ for all k. Then by Lemma 4, we have for all k that
(64)∥(-F(ζk))+∥2+∥(-G(ζk))+∥2≤44-τ2∥ϕτ2(F(ζk),G(ζk))∥2=84-τ2ψτ2(F(ζk),G(ζk))≤84-τ2γ^,
which implies ∥(-F(ζk))+∥<+∞ and ∥(-G(ζk))+∥+∞. Therefore, from Condition 11, there is j∈{1,2,…,m} such that λmax[(Fj(ζk)∘Gj(ζk))+]→+∞. It follows from (7), (8), and (12) that
(65)λmax[(Fj(ζk)∘Gj(ζk))+]≤2∥(Fj(ζk)∘Gj(ζk))+∥=2ψ0(Fj(ζk),Gj(ζk))1/2≤2τ1f(ζk)1/2,
and hence f(ζk)→+∞. This contradicts the fact that {ζk}⊆Lf(γ^).It should be noted that Condition11 is rather weak to guarantee the boundedness of level sets of f. As far as we know, the weakest condition available to ensure the boundedness of level sets is the following condition given by [20].Condition 13 (see [20]).
For any sequence{ζk}⊆Rn such that
(66)∥ζk∥→+∞,∥(-F(ζk))+∥<+∞,∥(-G(ζk))+∥<+∞,
there holds that
(67)max1≤i≤mλmax[Fi(ζk)∘Gi(ζk)]⟶+∞.
It is obvious thatλmax[Fi(ζk)∘Gi(ζk)]≤λmax[(Fi(ζk)∘Gi(ζk))+] for any i∈{1,2,…,m}, and therefore Condition 13 implies Condition 11. It has been shown that the symmetric cone complementarity problem (SCCP) with the jointly monotone mappings and a strictly feasible point, or the SCCP with joint Cartesian R02-property [23], all imply Condition 13 [20]. Hence they all implies Condition 11, since the SCCP includes the SOCCP. Therefore, Condition 11 is a weaker condition than the most available conditions to guarantee the boundedness of level sets.


## 5. Numerical Results

In this section, we employ the merit function method based on the unconstrained minimization reformulation (12) to solve the SOCCPs (1). All the experiments were performed on a desktop computer with Intel Pentium Dual T2390 CPU 1.86 GHz and 1.00 GB memory. The operating system was Windows XP and the implementations were done in MATLAB 7.0.1.We adopt the L-BFGS method [24], a limited-memory quasi-Newton method, with 5 limited-memory vector-updates to solve the unconstrained minimization reformulation (12) where the two-parametric class of merit functions ψτ1,τ2 is given as (7)–(10). For the scaling matrix H0=γI in the L-BFGS, we adopt γ=pTq/qTq as recommended by [25], where
(68)p:=ζ-ζold,q:=∇ψτ1,τ2(ζ)-∇ψτ1,τ2(ζold).
In the L-BFGS, we revert to the steepest descent direction -∇ψτ1,τ2(ζ) whenever pTq≤10-5∥p∥∥q∥. In addition, we use the nonmonotone line search [26] to seek a suitable steplength. In detail, we compute the smallest nonnegative integer lk such that
(69)ψτ1,τ2(ζk+ρlkdk)≤Wk+σρlk∇ψτ1,τ2(ζk)Tdk,
where dk denotes the direction in the kth iteration generated by the L-BFGS, ρ and σ are parameters in (0,1), and Wk is given by
(70)Wk=maxj=k-mk,…,kψτ1,τ2(ζj),
where, for a given nonnegative integer m^ and s, we set
(71)mk={0,ifk≤s,min{mk-1+1,m^}otherwise.
Throughout the numerical experiments, we choose the following parameters:
(72)ρ=0.8,σ=0.01,m^=5,s=5.
The algorithm is stopped whenever the number of function evaluations for ψτ1,τ2 is over 10000 or max{ψτ1,τ2(ζ),|〈F(ζ),G(ζ)〉|}≤10-6 as the stopping criterion.The test problems are the randomly generated linear SOCCPs (1), where
(73)F(ζ)=ζ,G(ζ)=Mζ+q,
with M∈Rn×n and q∈Rn. In detail, we generate a random matrix N=rand(n,n) and a random vector q=rand(n,1), and then let M:=NTN. Since the matrix M is semidefinite positive, the generated problems (1) are the monotone linear SOCCPs. In the tables of test results, n denotes the size of problems; NF denotes the (average) number of iterations; CPU(s) denotes the (average) CPU time in seconds; and Gap denotes the (average) value of |〈F(ζ),G(ζ)〉| when the algorithm terminates.We solve the linear SOCCPs of different dimensions with sizen from 50 to 1000 and m=1. The random problems of each size are generated 10 times, and the test results with different parameters τ1>0 and τ2∈(0,4) are listed in Tables 1, 2, and 3. From the results of these tables, we give several observations.(i)
All the random problems have been solved in very short CPU time.(ii)
The problem size slightly affects the number of iterations.(iii)
For the same dimension of linear SOCCPs, choices of different parametersτ1>0 and τ2∈(0,4) generally do not affect the number of iterations and the CPU time.Table 1
Numerical results for SOCCPs with(τ1,τ2)=(0.1,0.1).
n
NF
CPU (s)
Gap
50
155.1
0.063
1.44929
e
-
6
100
162.0
0.078
8.38541
e
-
6
150
166.0
0.171
6.41033
e
-
5
200
168.1
0.297
5.46509
e
-
6
250
170.3
0.563
5.80518
e
-
6
300
172.2
0.953
4.95267
e
-
6
350
174.2
1.453
4.18082
e
-
6
400
175.0
2.094
3.67026
e
-
6
450
176.0
2.875
3.32159
e
-
4
500
177.0
3.766
3.48330
e
-
7
550
178.0
4.984
3.25888
e
-
6
600
178.2
6.234
3.57938
e
-
5
650
179.1
7.938
3.16528
e
-
5
700
180.3
9.687
2.82810
e
-
6
750
181.6
11.594
2.54843
e
-
6
800
181.0
14.297
3.17068
e
-
6
850
182.7
16.625
2.18459
e
-
6
900
182.6
19.703
2.59598
e
-
5
950
183.0
22.922
2.35290
e
-
7
1000
183.2
26.438
2.41060
e
-
6Table 2
Numerical results for SOCCPs with(τ1,τ2)=(1,2.0).
n
NF
CPU (s)
Gap
50
156.0
0.062
1.29445
e
-
6
100
162.1
0.078
7.64185
e
-
6
150
166.1
0.172
6.51732
e
-
6
200
169.2
0.313
5.83238
e
-
6
250
171.6
0.547
4.96726
e
-
5
300
172.3
0.953
4.72040
e
-
7
350
174.5
1.469
4.43086
e
-
6
400
175.6
2.094
4.02729
e
-
5
450
176.8
2.859
3.28247
e
-
5
500
177.0
3.781
3.49543
e
-
6
550
178.0
4.984
3.22618
e
-
6
600
178.2
6.250
3.29624
e
-
6
650
179.0
7.891
3.23443
e
-
6
700
180.5
9.765
3.21537
e
-
4
750
181.2
11.687
2.73740
e
-
6
800
181.0
14.266
3.06024
e
-
6
850
182.1
16.609
2.85270
e
-
7
900
182.0
19.563
3.09099
e
-
5
950
183.0
23.000
2.55965
e
-
6
1000
183.0
26.360
2.86313
e
-
6Table 3
Numerical results for SOCCPs with(τ1,τ2)=(10,3.5).
n
NF
CPU (s)
Gap
50
157.0
0.063
1.27879
e
-
5
100
162.1
0.094
1.12054
e
-
6
150
166.1
0.172
8.69632
e
-
4
200
169.0
0.328
6.57170
e
-
6
250
171.2
0.562
4.73086
e
-
6
300
172.2
0.969
6.76156
e
-
6
350
174.3
1.437
3.97485
e
-
6
400
175.0
2.125
4.16500
e
-
7
450
176.0
2.875
5.02327
e
-
6
500
177.3
3.781
3.87474
e
-
6
550
178.2
4.937
4.14691
e
-
5
600
178.5
6.266
5.16964
e
-
5
650
179.6
7.829
4.40620
e
-
7
700
180.2
9.641
3.52956
e
-
5
750
181.0
11.625
3.10725
e
-
5
800
181.0
14.312
3.48511
e
-
6
850
182.0
16.610
3.21915
e
-
6
900
182.0
19.578
3.39945
e
-
4
950
183.0
22.922
2.72912
e
-
6
1000
183.1
26.390
3.36630
e
-
6


## 6. Conclusions

In this paper, we have studied a two-parametric class of merit functions for the second-order cone complementarity problem based on the one-parametric class of complementarity functions. The new proposed class of merit functions includes a broad class of merit functions, since the one-parametric class of complementarity functions is closely related to the famous natural residual function and Fischer-Burmeister function. The new class of merit functions has been shown to possess some favorable properties. In particular, it provides a global error bound ifF and G have the joint uniform Cartesian P-property. And it has bounded level sets under a weaker condition than the most available conditions [20, 23]. Some preliminary numerical results for solving the SOCCPs show the effectiveness of the merit function method via the new class of merit functions.



---

*Source: 571927-2013-06-13.xml*