# A Smoothing Method with Appropriate Parameter Control Based on Fischer-Burmeister Function for Second-Order Cone Complementarity Problems

Authors: Yasushi Narushima; Hideho Ogasawara; Shunsuke Hayashi
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We deal with complementarity problems over second-order cones. The complementarity problem is an important class of problems in the real world and involves many optimization problems. The complementarity problem can be reformulated as a nonsmooth system of equations. Based on the smoothed Fischer-Burmeister function, we construct a smoothing Newton method for solving such a nonsmooth system. The proposed method controls a smoothing parameter appropriately. We show the global and quadratic convergence of the method. Finally, some numerical results are given.


---

## Body

## 1. Introduction

In this paper, we consider the second-order cone complementarity problem (SOCCP) of the following form:(1)find(x,y,p)∈Rn×Rn×Rℓsuchthatx∈𝒦,y∈𝒦,〈x,y〉=0,F(x,y,p)=0,
where 〈·,·〉 denotes the Euclidean inner product, ℓ≥0, n≥1, F:Rn×Rn×Rℓ→Rn+ℓ is a continuously differentiable function, and 𝒦 denotes the Cartesian product of several second-order cones (SOCs), that is, 𝒦=𝒦n1×⋯×𝒦nm⊂Rn with m,n1,…,nm≥1, n=n1+⋯+nm, and
(2)𝒦ni:={{(z1,z2)∈R×Rni-1∣z1≥∥z2∥2}⊂Rni(ni≥2),R+={z1∈R∣z1≥0}(ni=1).The SOCCP is a wide class of complementarity problems. For example, it involves the mixed complementarity problem (MCP) and the nonlinear complementarity problem (NCP) [1] as subclasses, since 𝒦=R+n when ni=1 for each i=1,…,m(=n). Moreover, the second-order cone programming (SOCP) problem can be reformulated as an SOCCP by using the Karush-Kuhn-Tucker (KKT) conditions. Apart from them, some practical problems in the game theory [2, 3] and the architecture [4] can be reformulated as the SOCCP.Much theoretical and algorithmic research has been made so far for solving the SOCCP. Fukushima et al. [5] showed that the natural residualfunction, also called the min function, and the Fischer-Burmeister function for the NCP can be extended to the SOCCP by using the Jordan algebra. They further constructed the smoothing functions for those SOC complementarity (C-) functions and analyzed the properties of their Jacobian matrices. Hayashi et al. [6] proposed a smoothing method based on the natural residual and showed its global and quadratic convergence. On the other hand, Chen et al. [7] proposed another smoothing method with the natural residual in which the smoothing parameter is treated as a variable in contrast to [6]. Moreover, they showed the global and quadratic convergence of their method. Similar to Chen et al., Narushima et al. [8] proposed a smoothing method treating a smoothing parameter as a variable. They used the Fischer-Burmeister function instead of the natural residual function and also provided the global and quadratic convergence of the method.In the present paper, we propose a smoothing method with the Fischer-Burmeister function for solving SOCCP (1). The main difference from the existing methods is twofold. (i)
We do not assume the special structure on the functionF in SOCCP (1). In [6, 7, 9, 10], the authors focused on the following type of SOCCP:
(3)x∈𝒦,y∈𝒦,〈x,y〉=0,y=f(x),
which is a special case of SOCCP (1) with
(4)ℓ=0,F(x,y,p)=f(x)-y
for some continuously differentiable function f:Rn→Rn. In [11–13], the authors studied the following type of SOCCP:
(5)x∈𝒦,y∈𝒦,〈x,y〉=0,x=f(p),y=g(p),
which is obtained by letting
(6)ℓ=n,F(x,y,p)=[f(p)-xg(p)-y],
where f and g:Rn→Rn are continuously differentiable functions. However, we assume neither (4) nor (6). Therefore, our method is applicable to a wider class of SOCCPs.(ii)
In contrast to [8], we do not incorporate the smoothing parameter into the decision variable. We control the smoothing parameter appropriately in each iteration.This paper is organized as follows. In Section2, we give some preliminaries, which will be used in the subsequent analysis. In Section 3, we review the SOC C-function. In particular, we recall the property of the (smoothed) Fischer-Burmeister function. In Section 4, we propose an algorithm for solving the SOCCP and discuss its global and local convergence properties. In Section 5, we report some preliminary numerical results.Throughout the paper, we use the following notations. LetR+ and R++ be the sets of nonnegative and positive reals. For a symmetric matrix A, we write A≽O (resp., A≻O) if A is positive semidefinite (resp., positive definite). For any x, y∈Rn, we write x≽y (resp., x≻y) if x-y∈𝒦n (resp., x-y∈int𝒦n), and we denote by 〈x,y〉 the Euclidean inner product, that is, 〈x,y〉:=x⊤y. We use the symbol ∥·∥ to denote the usual ℓ2-norm of a vector or the corresponding induced matrix norm. We often write x=(x1,x2)∈R×Rn-1 (possibly x2 vacuous), instead of x=(x1,x2⊤)⊤∈Rn. In addition, we often regard Rp×Rq as Rp+q. We sometimes divide a vector x∈Rn according to the Cartesian structure of 𝒦, that is, x=(x1,…,xm)∈Rn1×⋯×Rnm=Rn with xi∈Rni. For any Fréchet-differentiable function G:Rn→Rm, we denote its transposed Jacobian matrix at x∈Rn by ∇G(x)∈Rn×m. For a given set S⊂Rn, intS, bd S, and conv S mean the interior, the boundary, and the convex hull of S in Rn, respectively.


## 2. Some Preliminaries

In this section, we recall some background materials and preliminary results used in the subsequent sections.First, we review the Jordan algebra associated with SOCs. For anyx=(x1,x2)∈R×Rn-1 and y=(y1,y2)∈R×Rn-1(n≥1), the Jordan product associated with 𝒦n is defined as
(7)x∘y:=(x⊤y,y1x2+x1y2).
When n=1, that is, the second components x2 and y2 are vacuous, we interpret that the second component in (7) is also vacuous. We will write x2 to mean x∘x and write x+y to mean the usual componentwise addition of vectors x and y. For the Jordan product, the identity element e∈Rn is defined by e:=(1,0,…,0)⊤. It is easily seen that x∘e=e∘x=x for any x∈Rn. For any x∈𝒦n, we define x1/2 as
(8)x1/2:={(ς,x22ς),ς=12(x1+x12-∥x2∥2)ifx≠0,0ifx=0.
Note that (x1/2)2=x1/2∘x1/2=x and that for n=1, x∘y=x1y1, e=1, and x1/2=ς=x1. Although the Jordan product is not associative, associativity holds under the inner product in the sense that
(9)〈x,y∘z〉=〈y,z∘x〉=〈z,x∘y〉foranyx,y,z∈Rn.
In addition, it follows readily from the definition of 𝒦n that 〈x,y〉≥0 (resp., 〈x,y〉>0) for any x, y≽0 (resp., x,y≻0).For eachx=(x1,x2)∈R×Rn-1(n≥1), we define the symmetric matrix Lx by
(10)Lx:=[x1x2⊤x2x1I],
which can be viewed as a linear mapping having the following properties.Property 1.
There holds that(a)
Lxy=x∘y=y∘x=Lyx and Lx+y=Lx+Ly for any x,y∈Rn;(b)
x≽0⇔Lx≽O, and x≻0⇔Lx≻O;(c)
Lx is invertible whenever x∈int𝒦n with
(11)Lx-1=1det(x)[x1-x2⊤-x2det(x)x1I+x2x2⊤x1],where det(x):=x12-∥x2∥2 denotes the determinant of x.An important character of the Jordan algebra is its spectral factorization. By the spectral factorization associated with SOC, anyx=(x1,x2)∈R×Rn-1(n≥1) can be decomposed as
(12)x=λ1(x)s{1}+λ2(x)s{2},
where λ1(x), λ2(x) and s{1}, s{2} are the spectral values and the associated spectral vectors of x given by
(13)λj(x):=x1+(-1)j∥x2∥,s{j}:={12(1,(-1)jx2∥x2∥)ifx2≠0,12(1,(-1)js-2)ifx2=0,
for j=1,2, with s-2 being any vector in Rn-1 satisfying ∥s-2∥=1. If x2≠0, the decomposition (12) is unique. We note again that when n=1 (viz., x=x1), we have λ1(x)=λ2(x)=x1, s{1}=s{2}=1/2. The spectral factorization associated with SOC leads to a number of interesting properties, some of which are as follows.Property 2.
For anyx=(x1,x2)∈R×Rn-1(n≥1), let λ1(x), λ2(x) and s{1}, s{2} be the spectral values and the associated spectral vectors at x. Then the following statements hold.(a)
x∈𝒦n⇔λ1(x)≥0, x∈int𝒦n⇔λ1(x)>0, x∈bd𝒦n⇔λ1(x)=0.(b)
x2=λ1(x)2s{1}+λ2(x)2s{2}∈𝒦n.(c)
Letx∈𝒦n. Then x1/2=λ1(x)s{1}+λ2(x)s{2}∈𝒦n. Moreover, x∈int𝒦n⇔x1/2∈int𝒦n, x∈bd𝒦n⇔x1/2∈bd𝒦n.In what follows, we recall some definitions for functions and matrices. The semismoothness is a generalized concept of the smoothness, which was originally introduced by Mifflin [14] for functionals, and extended to vector-valued functions by Qi and Sun [15]. For vector-valued functions associated with SOC, see also the work of Chen et al. [16]. Now we give the definition of the Clarke subdifferential [17].Definition 1.
LetH:Rn→Rm be a locally Lipschitzian function. The Clarke subdifferential of H at x is defined by
(14)∂H(x):=conv{limx^→x∇H(x^)∣x^∈𝒟H},
where 𝒟H is the set of points at which H is differentiable.Note that ifH is continuously differentiable at x, then ∂H(x)={∇H(x)}. We next give the definitions of the semismoothness and the strong semismoothness.Definition 2.
A directionally differentiable and locally Lipschitzian functionH:Rn→Rm is said to be semismooth at x if
(15)H′(x;d)-V⊤d=o(∥d∥)
for any sufficiently small d∈Rn∖{0} and V∈∂H(x+d), where
(16)H′(x;d):=limτ→+0H(x+τd)-H(x)τ
is the directional derivative of H at x along the direction d. In particular, if o(∥d∥) can be replaced by O(∥d∥2), then function H is said to be strongly semismooth.It is known that ifH is (strongly) semismooth, then
(17)∥H′(x;d)-(H(x+d)-H(x))∥=o(∥d∥)(O(∥d∥2))
holds (see [18], e.g.).The definitions below for a function can be found in [10, 13, 19].Definition 3 (see [10, 13]).
A functionF=(F1,…,Fm) with Fi:Rn→Rni is said to have (a)
the CartesianP0-property, if for any x=(x1,…,xm), y=(y1,…,ym)∈Rn1×⋯×Rnm with x≠y, there exists an index ν∈{1,…,m} such that xν≠yν and 〈xν-yν,Fν(x)-Fν(y)〉≥0;(b)
the uniform CartesianP-property, if there exists a constant ρ>0 such that, for any x=(x1,…,xm), y=(y1,…,ym)∈Rn1×⋯×Rnm, there exists an index ν∈{1,…,m} such that 〈xν-yν,Fν(x)-Fν(y)〉≥ρ∥x-y∥2.
By the definitions, it is clear that the CartesianP-property implies the Cartesian P0-property. Definition 3 is associated with SOCCP (3), while the following definitions are associated with SOCCP (5).Definition 4 (see [19]).
LetF:Rn→Rn and G:Rn→Rn be functions such that F=(F1,…,Fm), G=(G1,…,Gm) with Fi:Rn→Rni and Gi:Rn→Rni. Then, F and G are said to have (a)
the joint uniform JordanP-property, if there exists a constant ρ>0 such that
(18)λ2((F(x)-F(y))∘(G(x)-G(y)))≥ρ∥x-y∥2foranyx,y∈Rn;(b)
the joint Cartesian weak coerciveness, if there exists a vectorx-∈Rn such that
(19)lim∥x∥→∞max1≤i≤m〈Fi(x),Gi(x)-Gi(x-)〉∥x-x-∥=+∞.Next we recall the concept of linear growth of a function, which is weaker than the global Lipschitz continuity.Definition 5 (see [19]).
A functionF:Rn→Rn is said to have linear growth, if there exists a constant C>0 such that ∥F(x)∥≤∥F(0)∥+C∥x∥ for any x∈Rn.The following definitions for a matrix are originally given in [8], which is a generalization of the mixed P0-property [1].Definition 6 (see [8]).
LetM∈R(n+ℓ)×(2n+ℓ) be a matrix partitioned as follows:
(20)M=[M1M2M3],
where M1, M2∈R(n+ℓ)×n and M3∈R(n+ℓ)×ℓ. Then, M is said to have (a)
the Cartesian mixedP0-property, if the following statements hold:
(1)
M3 has full column rank;(2)
for anyx=(x1,…,xm), y=(y1,…,ym)∈Rn1×⋯×Rnm with (x,y)≠0 and p∈Rℓ such that M1x+M2y+M3p=0, there exists an index ν∈{1,…,m} such that (xν,yν)≠0 and 〈xν,yν〉≥0;(b)
the Cartesian mixedP-property, if (1) of (a) and the following statement hold:
(2′)
for anyx=(x1,…,xm), y=(y1,…,ym)∈Rn1×⋯×Rnm with (x,y)≠0 and p∈Rℓ such that M1x+M2y+M3p=0, there exists an index ν∈{1,…,m} such that 〈xν,yν〉>0.
In the caseℓ=0 (i.e., M3 is vacuous) and M=[M1-I], M has the Cartesian mixed P0 (P)-property if and only if M1 has the Cartesian P0 (P)-property (see [10, 13], e.g.). By the definitions, it is clear that the Cartesian mixed P-property implies the Cartesian mixed P0-property. Moreover, when n1=⋯=nm=1, the Cartesian mixed P0-property reduces to the mixed P0-property (see [1, page 1013]).
We now introduce the Cartesian mixed JordanP0 (P)-property.Definition 7.
LetM∈R(n+ℓ)×(2n+ℓ) be a matrix partitioned as follows:
(21)M=[M1M2M3],
where M1, M2∈R(n+ℓ)×n and M3∈R(n+ℓ)×ℓ. Then, M is said to have (a)
the Cartesian mixed JordanP0-property, if the following statements hold:
(1)
M3 has full column rank;(2)
for anyx=(x1,…,xm), y=(y1,…,ym)∈Rn1×⋯×Rnm with (x,y)≠0 and p∈Rℓ such that M1x+M2y+M3p=0, there exists an index ν∈{1,…,m} such that (xν,yν)≠0 and xν∘yν≽0;(b)
the Cartesian mixed JordanP-property, if (1) of (a) and the following statement hold:
(2′)
for anyx=(x1,…,xm), y=(y1,…,ym)∈Rn1×⋯×Rnm with (x,y)≠0 and p∈Rℓ such that M1x+M2y+M3p=0, there exists an index ν∈{1,…,m} such that xν∘yν≻0.
Note that the relationxν∘yν≽0 (resp., xν∘yν≻0) can be rewritten as λ1(xν∘yν)≥0 (resp., λ1(xν∘yν)>0). By the definitions, it is clear that the Cartesian mixed Jordan P-property implies the Cartesian mixed Jordan P0-property, and that the Cartesian mixed Jordan P0 (P)-property implies the Cartesian mixed P0 (P)-property. Similar to the Cartesian mixed P0-property, in the case n1=⋯=nm=1, the Cartesian mixed Jordan P0-property also reduces to the mixed P0-property.


## 3. SOC C-Function and Its Smoothing Function

In this section, we introduce the SOC C-function and its smoothing function. In Section3.1, we give the concept of the SOC C-function to transform the SOCCP into a system of equations. We focus on the Fischer-Burmeister function as an SOC C-function and review some properties of the smoothed Fischer-Burmeister function in Section 3.2.


### 3.1. SOC C-Function

First, we recall the concept of the SOC C-function.Definition 8.
A functionϕ:Rr×Rr→Rr is said to be an SOC complementarity (C-) function, if the following holds:
(22)ϕ(x,y)=0⟺x∈𝒦r,y∈𝒦r,〈x,y〉=0.
Letϕ^:Rn×Rn→Rn be defined as
(23)ϕ^(x,y):=[ϕ1(x1,y1)⋮ϕm(xm,ym)],
where x and y∈Rn are divided as x=(x1,…,xm) and y=(y1,…,ym) with xi, yi∈Rni, i=1,…,m, and ϕi:Rni×Rni→Rni are SOC C-functions. Then it follows from (22) that
(24)ϕ^(x,y)=0⟺x∈𝒦,y∈𝒦,〈x,y〉=0.
Accordingly, SOCCP (1) is reformulated as a system of equations H^(x,y,p)=0, where H^:Rn×Rn×Rℓ→R2n+ℓ is defined by
(25)H^(x,y,p):=[ϕ^(x,y)F(x,y,p)].
Moreover, we also give a merit function Ψ^:Rn×Rn×Rℓ→R defined by
(26)Ψ^(x,y,p):=12∥H^(x,y)∥2=12∥ϕ^(x,y)∥2+12∥F(x,y,p)∥2.
Note that Ψ^(x,y,p)≥0 for any (x,y,p)∈Rn×Rn×Rℓ, and that Ψ^(x,y,p)=0 if and only if (x,y,p) is a solution of SOCCP (1).
There are many kinds of SOC C-functions. The natural residual functionϕNRi:Rni×Rni→Rni and the Fischer-Burmeister function ϕFBi:Rni×Rni→Rni are respectively defined by
(27)ϕNRi(xi,yi):=xi-[xi-yi]+,(28)ϕFBi(xi,yi):=xi+yi-((xi)2+(yi)2)1/2,
where [z]+ denotes the projection of z onto the SOC 𝒦ni. Fukushima et al. [5] showed that (22) holds for functions ϕNRi and ϕFBi. Chen et al. [7] and Hayashi et al. [6] proposed methods for solving SOCCP based on the natural residual function (27), whereas Narushima et al. [8] proposed methods for solving SOCCP based on the Fischer-Burmeister function (28).
In what follows, functionsϕFB, HFB, and ΨFB denote ϕ^, H^, and Ψ^ with ϕFBi, respectively. Also, functions ϕNR, HNR, and ΨNR denote ϕ^, H^, and Ψ^ with ϕNRi, respectively.
Recently, Bi et al. [20] showed the following inequality:
(29)(2-2)∥ϕNRi(xi,yi)∥≤∥ϕFBi(xi,yi)∥≤(2+2)∥ϕNRi(xi,yi)∥foranyxi,yi∈Rni.
We see from (29) that the level-boundedness of ΨFB is equivalent to that of ΨNR.


### 3.2. Smoothed FB Function and Its Properties

In this section, we consider the smoothing function associated with the Fischer-Burmeister function and give its properties and Jacobian matrix.SinceHFB is not differentiable in general, we cannot apply conventional methods such as Newton’s method or Newton-based methods. We therefore consider the smoothed Fischer-Burmeister function ϕt:R2n→Rn, which was originally proposed by Kanzow [21] for solving NCP and generalized by Fukushima et al. [5] to SOCCP. Let ϕti:R2ni→Rni be defined by
(30)ϕti(x,y):=xi+yi-(2t2ei+(xi)2+(yi)2)1/2
for each i=1,…,m, where t is a smoothing parameter and ei:=(1,0,…,0)⊤∈Rni. Then, the smoothed Fischer-Burmeister function ϕt:R2n→Rn is defined as
(31)ϕt(x,y):=[ϕt1(x1,y1)⋮ϕtm(xm,ym)].
Also, the smoothing function Ht:R2n+ℓ→R2n+ℓ and the merit function Ψt:R2n+ℓ→R are defined as
(32)Ht(x,y,p):=[ϕt(x,y)F(x,y,p)],(33)Ψt(x,y,p)≔12∥Ht(x,y,p)∥2=12∥ϕt(x,y)∥2+12∥F(x,y,p)∥2,
respectively. Clearly, ϕ0(x,y)≡ϕFB(x,y), and so H0(x,y,p)≡HFB(x,y,p) and Ψ0(x,y,p)≡ΨFB(x,y,p). We note that
(34)∥ϕti(xi,yi)-ϕFBi(x,y)∥≤2|t|
holds for any t∈R and (xi,yi)∈R2ni (see [5] or [22]). From definition (32) of Ht and (34), it follows that
(35)∥Ht(x,y,p)-HFB(x,y,p)∥=∥ϕt(x,y)-ϕFB(x,y)∥=(∑i=1m‍∥ϕti(xi,yi)-ϕFBi(xi,yi)∥2)1/2≤2m|t|
for any t∈R and (x,y,p)∈R2n+ℓ.In what follows, we writexi=((xi)1,(xi)2)∈R×Rni-1 for any vector xi∈Rni. Moreover, for convenience, we use the following notation. For any xi, yi∈Rni and any t∈R, we write zi=(xi,yi)∈R2ni and define the functions wti, uti:R2ni→R×Rni-1 by
(36)wti=((wti)1,(wti)2)≔2t2ei+(xi)2+(yi)2,uti=((uti)1,(uti)2):=(2t2ei+(xi)2+(yi)2)1/2.
Furthermore, we drop the subscript for t=0 for simplicity, and thus,
(37)wi=((wi)1,(wi)2)≔(xi)2+(yi)2,ui=((ui)1,(ui)2):=((xi)2+(yi)2)1/2.
Direct calculation yields
(38)(wti)1=2t2+∥xi∥2+∥yi∥2=2t2+(wi)1,(wti)2=2((xi)1(xi)2+(yi)1(yi)2)=(wi)2.
Note that (wti)2 is actually independent of t, so that hereafter we will write wti=((wti)1,(wi)2). We also easily get, for j=1,2,
(39)λj(wti)=2t2+∥xi∥2+∥yi∥2+2(-1)j∥(xi)1(xi)2+(yi)1(yi)2∥s{j}=12(1,(-1)j(w-i)2),
where λ1(wti), λ2(wti) and s{1}, s{2} are the spectral values and the associated spectral vectors of wti, respectively, with (w-i)2:=(wi)2/∥(wi)2∥ if (wi)2≠0, and otherwise, (w-i)2 being any vector in Rni-1 satisfying ∥(w-i)2∥=1.Now we review some propositions needed to establish convergence properties of the smoothing Newton method. The following proposition gives explicit expression of the transposed Jacobian matrix witht≠0.Proposition 9 (see [5]).
For anyt≠0, Ht is continuously differentiable on R2n+ℓ, and its transposed Jacobian matrix is given by
(40)∇Ht(x,y,p)=[diag{∇xiϕti(xi,yi)}i=1m∇xF(x,y,p)diag{∇yiϕti(xi,yi)}i=1m∇yF(x,y,p)O∇pF(x,y,p)],
where diag{Di}i=1m denotes the block-diagonal matrix with block elements Di∈Rni×ni, and
(41)∇xiϕti(xi,yi)=I-LxiLuti-1,∇yiϕti(xi,yi)=I-LyiLuti-1,Luti-1=[bti-cti(w-i)2⊤-cti(w-i)2atiI+(bti-ati)(w-i)2(w-i)2⊤]
with
(42)ati:=2λ1(wti)+λ2(wti),bti:=12(1λ1(wti)+1λ2(wti)),cti:=12(1λ1(wti)-1λ2(wti)).In order to obtain the Newton step, the nonsingularity of∇Ht is important. The next proposition establishes the nonsingularity of ∇Ht.Proposition 10 (see [8]).
Lett be an arbitrary nonzero number and let (x,y,p)∈R2n+ℓ be an arbitrary triple such that the Jacobian matrix ∇F(x,y,p)⊤ has the Cartesian mixed P0-property at (x,y,p), that is, ∇pF(x,y,p) satisfies
(43)rank∇pF(x,y,p)=ℓ,
and
(44)∇F(x,y,p)⊤(ξ,η,φ)=0,(ξ,η)≠0,φ∈Rℓξ=(ξ1,…,ξm),η=(η1,…,ηm)∈Rn1×⋯×Rnm}⟹thereexistsanindexν∈{1,…,m}suchthat(ξν,ην)≠0,〈ξν,ην〉≥0.
Then, the matrix ∇Ht(x,y,p) given by (40) is nonsingular.The local Lipschitz continuity and the (strong) semismoothness ofHFB play a significant role in establishing locally rapid convergence.Proposition 11.
The functionHFB is locally Lipschitzian on R2n+ℓ and, moreover, is semismooth on R2n+ℓ. In addition, if ∇F is locally Lipschitzian, then HFB is strongly semismooth on R2n+ℓ.Proof.
It follows from [23, Corollary 3.3] that ϕFBi is globally Lipschitzian and strongly semismooth. Since F is a continuously differentiable function, HFB is locally Lipschitzian on R2n+ℓ. Also, the (strong) semismoothness of HFB can be easily shown from the strong semismoothness of ϕFBi and the (local Lipschitz) continuity of ∇F.We define functionΘi:R2ni→R+ by Θi(xi,yi):=∥LxiLyi∥. It is easily seen that Θi(xi,yi)=0 if and only if (xi,yi)=(0,0). Now we partition R2ni as R2ni=𝒵1i∪𝒵2i∪{(0,0)}, where
(45)𝒵1i:={zi=(xi,yi)∈R2ni∣wi=(xi)2+(yi)2∈int𝒦ni},𝒵2i:={(xi)2zi=(xi,yi)∈R2ni∣wi=(xi)2+(yi)2∈bd𝒦ni,wi≠0}.
In order to achieve locally rapid convergence of the method, we need to control the parameter t so that the distance between ∇Ht and ∂HFB is sufficiently small. The following proposition is helpful to control the parameter t appropriately.Proposition 12 (see [22]).
Let(x,y,p) be any point in R2n+ℓ. Let θi(xi,yi) be any function such that Θi(xi,yi)≤θi(xi,yi). Let δ>0 be given. Let t-:R2n×R+→R+∪{+∞} be defined by
(46)t-(x,y,δ):=min{t-i(xi,yi,δ)∣i=1,…,m},
where
(47)t-i(xi,yi,δ):={λ1(wi)δ2(θi(zi)2-λ1(wi)δ2)ifzi=(xi,yi)∈𝒵1i,δ<θi(zi)λ1(wi),(wi)1δ2θi(zi)(2θi(zi)-δ2(wi)1)ifzi=(xi,yi)∈𝒵2i,δ<2θi(zi)2(wi)1,+∞otherwise.
Then, for any t∈R such that 0<|t|≤t-(x,y,δ),
(48)dist(∇Ht(x,y,p),∂HFB(x,y,p))<δ,
where dist(X,S) denotes min{∥X-Y∥∣Y∈S}.


## 3.1. SOC C-Function

First, we recall the concept of the SOC C-function.Definition 8.
A functionϕ:Rr×Rr→Rr is said to be an SOC complementarity (C-) function, if the following holds:
(22)ϕ(x,y)=0⟺x∈𝒦r,y∈𝒦r,〈x,y〉=0.
Letϕ^:Rn×Rn→Rn be defined as
(23)ϕ^(x,y):=[ϕ1(x1,y1)⋮ϕm(xm,ym)],
where x and y∈Rn are divided as x=(x1,…,xm) and y=(y1,…,ym) with xi, yi∈Rni, i=1,…,m, and ϕi:Rni×Rni→Rni are SOC C-functions. Then it follows from (22) that
(24)ϕ^(x,y)=0⟺x∈𝒦,y∈𝒦,〈x,y〉=0.
Accordingly, SOCCP (1) is reformulated as a system of equations H^(x,y,p)=0, where H^:Rn×Rn×Rℓ→R2n+ℓ is defined by
(25)H^(x,y,p):=[ϕ^(x,y)F(x,y,p)].
Moreover, we also give a merit function Ψ^:Rn×Rn×Rℓ→R defined by
(26)Ψ^(x,y,p):=12∥H^(x,y)∥2=12∥ϕ^(x,y)∥2+12∥F(x,y,p)∥2.
Note that Ψ^(x,y,p)≥0 for any (x,y,p)∈Rn×Rn×Rℓ, and that Ψ^(x,y,p)=0 if and only if (x,y,p) is a solution of SOCCP (1).
There are many kinds of SOC C-functions. The natural residual functionϕNRi:Rni×Rni→Rni and the Fischer-Burmeister function ϕFBi:Rni×Rni→Rni are respectively defined by
(27)ϕNRi(xi,yi):=xi-[xi-yi]+,(28)ϕFBi(xi,yi):=xi+yi-((xi)2+(yi)2)1/2,
where [z]+ denotes the projection of z onto the SOC 𝒦ni. Fukushima et al. [5] showed that (22) holds for functions ϕNRi and ϕFBi. Chen et al. [7] and Hayashi et al. [6] proposed methods for solving SOCCP based on the natural residual function (27), whereas Narushima et al. [8] proposed methods for solving SOCCP based on the Fischer-Burmeister function (28).
In what follows, functionsϕFB, HFB, and ΨFB denote ϕ^, H^, and Ψ^ with ϕFBi, respectively. Also, functions ϕNR, HNR, and ΨNR denote ϕ^, H^, and Ψ^ with ϕNRi, respectively.
Recently, Bi et al. [20] showed the following inequality:
(29)(2-2)∥ϕNRi(xi,yi)∥≤∥ϕFBi(xi,yi)∥≤(2+2)∥ϕNRi(xi,yi)∥foranyxi,yi∈Rni.
We see from (29) that the level-boundedness of ΨFB is equivalent to that of ΨNR.


## 3.2. Smoothed FB Function and Its Properties

In this section, we consider the smoothing function associated with the Fischer-Burmeister function and give its properties and Jacobian matrix.SinceHFB is not differentiable in general, we cannot apply conventional methods such as Newton’s method or Newton-based methods. We therefore consider the smoothed Fischer-Burmeister function ϕt:R2n→Rn, which was originally proposed by Kanzow [21] for solving NCP and generalized by Fukushima et al. [5] to SOCCP. Let ϕti:R2ni→Rni be defined by
(30)ϕti(x,y):=xi+yi-(2t2ei+(xi)2+(yi)2)1/2
for each i=1,…,m, where t is a smoothing parameter and ei:=(1,0,…,0)⊤∈Rni. Then, the smoothed Fischer-Burmeister function ϕt:R2n→Rn is defined as
(31)ϕt(x,y):=[ϕt1(x1,y1)⋮ϕtm(xm,ym)].
Also, the smoothing function Ht:R2n+ℓ→R2n+ℓ and the merit function Ψt:R2n+ℓ→R are defined as
(32)Ht(x,y,p):=[ϕt(x,y)F(x,y,p)],(33)Ψt(x,y,p)≔12∥Ht(x,y,p)∥2=12∥ϕt(x,y)∥2+12∥F(x,y,p)∥2,
respectively. Clearly, ϕ0(x,y)≡ϕFB(x,y), and so H0(x,y,p)≡HFB(x,y,p) and Ψ0(x,y,p)≡ΨFB(x,y,p). We note that
(34)∥ϕti(xi,yi)-ϕFBi(x,y)∥≤2|t|
holds for any t∈R and (xi,yi)∈R2ni (see [5] or [22]). From definition (32) of Ht and (34), it follows that
(35)∥Ht(x,y,p)-HFB(x,y,p)∥=∥ϕt(x,y)-ϕFB(x,y)∥=(∑i=1m‍∥ϕti(xi,yi)-ϕFBi(xi,yi)∥2)1/2≤2m|t|
for any t∈R and (x,y,p)∈R2n+ℓ.In what follows, we writexi=((xi)1,(xi)2)∈R×Rni-1 for any vector xi∈Rni. Moreover, for convenience, we use the following notation. For any xi, yi∈Rni and any t∈R, we write zi=(xi,yi)∈R2ni and define the functions wti, uti:R2ni→R×Rni-1 by
(36)wti=((wti)1,(wti)2)≔2t2ei+(xi)2+(yi)2,uti=((uti)1,(uti)2):=(2t2ei+(xi)2+(yi)2)1/2.
Furthermore, we drop the subscript for t=0 for simplicity, and thus,
(37)wi=((wi)1,(wi)2)≔(xi)2+(yi)2,ui=((ui)1,(ui)2):=((xi)2+(yi)2)1/2.
Direct calculation yields
(38)(wti)1=2t2+∥xi∥2+∥yi∥2=2t2+(wi)1,(wti)2=2((xi)1(xi)2+(yi)1(yi)2)=(wi)2.
Note that (wti)2 is actually independent of t, so that hereafter we will write wti=((wti)1,(wi)2). We also easily get, for j=1,2,
(39)λj(wti)=2t2+∥xi∥2+∥yi∥2+2(-1)j∥(xi)1(xi)2+(yi)1(yi)2∥s{j}=12(1,(-1)j(w-i)2),
where λ1(wti), λ2(wti) and s{1}, s{2} are the spectral values and the associated spectral vectors of wti, respectively, with (w-i)2:=(wi)2/∥(wi)2∥ if (wi)2≠0, and otherwise, (w-i)2 being any vector in Rni-1 satisfying ∥(w-i)2∥=1.Now we review some propositions needed to establish convergence properties of the smoothing Newton method. The following proposition gives explicit expression of the transposed Jacobian matrix witht≠0.Proposition 9 (see [5]).
For anyt≠0, Ht is continuously differentiable on R2n+ℓ, and its transposed Jacobian matrix is given by
(40)∇Ht(x,y,p)=[diag{∇xiϕti(xi,yi)}i=1m∇xF(x,y,p)diag{∇yiϕti(xi,yi)}i=1m∇yF(x,y,p)O∇pF(x,y,p)],
where diag{Di}i=1m denotes the block-diagonal matrix with block elements Di∈Rni×ni, and
(41)∇xiϕti(xi,yi)=I-LxiLuti-1,∇yiϕti(xi,yi)=I-LyiLuti-1,Luti-1=[bti-cti(w-i)2⊤-cti(w-i)2atiI+(bti-ati)(w-i)2(w-i)2⊤]
with
(42)ati:=2λ1(wti)+λ2(wti),bti:=12(1λ1(wti)+1λ2(wti)),cti:=12(1λ1(wti)-1λ2(wti)).In order to obtain the Newton step, the nonsingularity of∇Ht is important. The next proposition establishes the nonsingularity of ∇Ht.Proposition 10 (see [8]).
Lett be an arbitrary nonzero number and let (x,y,p)∈R2n+ℓ be an arbitrary triple such that the Jacobian matrix ∇F(x,y,p)⊤ has the Cartesian mixed P0-property at (x,y,p), that is, ∇pF(x,y,p) satisfies
(43)rank∇pF(x,y,p)=ℓ,
and
(44)∇F(x,y,p)⊤(ξ,η,φ)=0,(ξ,η)≠0,φ∈Rℓξ=(ξ1,…,ξm),η=(η1,…,ηm)∈Rn1×⋯×Rnm}⟹thereexistsanindexν∈{1,…,m}suchthat(ξν,ην)≠0,〈ξν,ην〉≥0.
Then, the matrix ∇Ht(x,y,p) given by (40) is nonsingular.The local Lipschitz continuity and the (strong) semismoothness ofHFB play a significant role in establishing locally rapid convergence.Proposition 11.
The functionHFB is locally Lipschitzian on R2n+ℓ and, moreover, is semismooth on R2n+ℓ. In addition, if ∇F is locally Lipschitzian, then HFB is strongly semismooth on R2n+ℓ.Proof.
It follows from [23, Corollary 3.3] that ϕFBi is globally Lipschitzian and strongly semismooth. Since F is a continuously differentiable function, HFB is locally Lipschitzian on R2n+ℓ. Also, the (strong) semismoothness of HFB can be easily shown from the strong semismoothness of ϕFBi and the (local Lipschitz) continuity of ∇F.We define functionΘi:R2ni→R+ by Θi(xi,yi):=∥LxiLyi∥. It is easily seen that Θi(xi,yi)=0 if and only if (xi,yi)=(0,0). Now we partition R2ni as R2ni=𝒵1i∪𝒵2i∪{(0,0)}, where
(45)𝒵1i:={zi=(xi,yi)∈R2ni∣wi=(xi)2+(yi)2∈int𝒦ni},𝒵2i:={(xi)2zi=(xi,yi)∈R2ni∣wi=(xi)2+(yi)2∈bd𝒦ni,wi≠0}.
In order to achieve locally rapid convergence of the method, we need to control the parameter t so that the distance between ∇Ht and ∂HFB is sufficiently small. The following proposition is helpful to control the parameter t appropriately.Proposition 12 (see [22]).
Let(x,y,p) be any point in R2n+ℓ. Let θi(xi,yi) be any function such that Θi(xi,yi)≤θi(xi,yi). Let δ>0 be given. Let t-:R2n×R+→R+∪{+∞} be defined by
(46)t-(x,y,δ):=min{t-i(xi,yi,δ)∣i=1,…,m},
where
(47)t-i(xi,yi,δ):={λ1(wi)δ2(θi(zi)2-λ1(wi)δ2)ifzi=(xi,yi)∈𝒵1i,δ<θi(zi)λ1(wi),(wi)1δ2θi(zi)(2θi(zi)-δ2(wi)1)ifzi=(xi,yi)∈𝒵2i,δ<2θi(zi)2(wi)1,+∞otherwise.
Then, for any t∈R such that 0<|t|≤t-(x,y,δ),
(48)dist(∇Ht(x,y,p),∂HFB(x,y,p))<δ,
where dist(X,S) denotes min{∥X-Y∥∣Y∈S}.


## 4. Smoothing Newton Method and Its Convergence Properties

In this section, we first propose an algorithm of the smoothing Newton method based on the Fischer-Burmeister function and its smoothing function. We then prove its global andQ-superlinear (Q-quadratic) convergence.


### 4.1. Algorithm

We provide the smoothing Newton algorithm based on the Fischer-Burmeister function. In what follows, we writev(k)=(x(k),y(k),p(k)) and z(k)=(x(k),y(k)) for simplicity.Algorithm 13.
Step   0. Choose η, ρ∈(0,1), η-∈(0,η], σ∈(0,1/2), r>1, κ>0, and κ^>0.
Choosev(0)=(x(0),y(0),p(0))∈R2n+ℓ and β0∈(0,∞). Let t0:=∥HFB(v(0))∥. Set k:=0.
Step   1.If a stopping criterion, such as ∥HFB(v(k))∥=0, is satisfied, then stop.
Step   2.
Step   2.0. Set v^(0):=v(k) and j:=0.
Step   2.1. Compute d^(j)∈R2n+ℓ by solving (49)Htk(v^(j))+∇Htk(v^(j))⊤d^(j)=0.
Step   2.2. If ∥Htk(v^(j)+d^(j))∥≤βk, then let v(k+1):=v^(j)+d^(j) and go to Step 3. Otherwise, go to Step 2.3.
Step   2.3. Let lj be the smallest nonnegative integer l satisfying
(50)Ψtk(v^(j)+ρld^(j))≤(1-2σρl)Ψtk(v^(j)).
Letτj:=ρlj and v^(j+1):=v^(j)+τjd^(j).
Step   2.4. If
(51)∥Htk(v^(j+1))∥≤βk,
then let v(k+1):=v^(j+1) and go to Step 3. Otherwise, set j:=j+1 and go back to Step 2.1.
Step    3. Update the parameters as follows:
(52)δk+1:=∥HFB(v(k+1))∥,tk+1:=min{κδk+1r,t0η-k+1,t-(z(k+1),κ^δk+1)},βk+1:=β0ηk+1.
Step   4. Set k:=k+1. Go back to Step 1.
Note that the proposed algorithm consists of the outer iteration steps and the inner iteration steps. Step 2 is the inner iteration steps with the variablev^ and the counter j, while the outer iteration steps have the variable v and the counter k.
From Step 3 of Algorithm13 and (48), the following inequality holds:
(53)min{∥∇Htk(v(k))-Y∥∣Y∈∂HFB(v(k))}≤κ^∥HFB(v(k))∥.
Letting v* be a solution of SOCCP (1), we have HFB(v*)=0. Therefore, from (53) and the local Lipschitz continuity of HFB, the following holds:
(54)min{∥∇Htk(v(k))-Y∥∣Y∈∂HFB(v(k))}≤κ^∥HFB(v(k))-HFB(v*)∥=O(∥v(k)-v*∥).
In the rest of this section, we consider convergence properties of Algorithm13. In Section 4.2, we prove the global convergence of the algorithm, and in Section 4.3, we investigate local behavior of the algorithm. For this purpose, we make the following assumptions.Assumption 1.
(A1)
The solution set𝒮 of  SOCCP (1) is nonempty and bounded.
(A2)
The functionΨFB is level-bounded, that is, for any v-∈R2n+ℓ, the level set {v∈R2n+ℓ∣ΨFB(v)≤ΨFB(v-)} is bounded.
(A3)
For anyt>0 and v∈R2n+ℓ, ∇Ht(v) is nonsingular.From Proposition10, Assumption (A3) holds if ∇F(v)⊤ has the Cartesian mixed P0-property for any v∈R2n+ℓ. The following remarks correspond to SOCCPs (3) and (5).Remark 14.
The case of  SOCCP (3). If ∇f(x)⊤ has the Cartesian P0-property, then ∇F(x,y,p)⊤ with F in (4) has the Cartesian mixed P0-property and vice versa. Note that ∇f(x)⊤ has the Cartesian P0-property at any x∈Rn if f has the Cartesian P0-property (see [10, 13] for the definition of the Cartesian P0-property for a matrix).Remark 15.
The case of  SOCCP (5). If ∇f(p) is nonsingular and (∇f(p)-1∇g(p))⊤ has the Cartesian P0-property, then ∇F(x,y,p)⊤ with F in (6) has the Cartesian mixed P0-property.Note that Assumption (A2) is equivalent to the coerciveness in the sense that(55)lim∥v∥→∞ΨFB(v)=+∞.
We now give some sufficient conditions for Assumption (A2) in the case of SOCCP (3) or (5).Lemma 16.
Consider SOCCP (5). Let Ψ~FB:Rn→R be a function such that Ψ~FB(p):=(1/2)∥ϕFB(f(p),g(p))∥2 for any p∈Rn. Then Ψ~FB is level-bounded if and only if Ψ~FB is level-bounded.Proof.
We use below condition (55) equivalent to the level-boundedness. We first assume that Ψ~FB is level-bounded and claim that ΨFB is level-bounded. Suppose the contrary. Then, we can find a sequence {v(k)}={(x(k),y(k),p(k))}⊂R3n such that the sequence {ΨFB(v(k))} is bounded and ∥v(k)∥→∞. If {∥p(k)∥} is bounded, then we must have ∥(x(k),y(k))∥→∞. Thus, from the inequality
(56)2ΨFB(v(k))≥∥(f(p(k))-x(k),g(p(k))-y(k))∥≥∥(x(k),y(k))∥-∥(f(p(k)),g(p(k)))∥
and from the continuity of f and g, we have ΨFB(v(k))→∞. Since this is not possible, {∥p(k)∥} is unbounded. By taking a subsequence if necessary, we may assume that ∥p(k)∥→∞ as k→∞. Since ϕFB is globally Lipschitzian by [23, Corollary 3.3], we have from (33) that, for any (x,y,p)∈R3n,
(57)2Ψ~FB(p)=∥ϕFB(f(p),g(p))∥≤∥ϕFB(f(p),g(p))-ϕFB(x,y)∥+∥ϕFB(x,y)∥≤L∥(f(p),g(p))-(x,y)∥+∥ϕFB(x,y)∥≤L2+1∥(f(p)-x,g(p)-y)∥2+∥ϕFB(x,y)∥2=L2+12ΨFB(x,y,p),
where L>0 is a Lipschitz constant. Then, it follows from (57) and the level-boundedness of Ψ~FB that limk→∞ΨFB(v(k))=+∞, contradicting the boundedness of {ΨFB(v(k))}. This proves the level-boundedness of ΨFB.
We next assume thatΨFB is level-bounded. Let {p(k)}⊂Rn be an arbitrary sequence such that ∥p(k)∥→∞ and let x(k):=f(p(k)) and y(k):=g(p(k)). Then we have
(58)2ΨFB(x(k),y(k),p(k))=∥ϕFB(x(k),y(k))∥2+∥f(p(k))-x(k)∥2+∥g(p(k))-y(k)∥2=∥ϕFB(f(p(k)),g(p(k)))∥2=2Ψ~FB(p(k)).
Thus, from ∥(x(k),y(k),p(k))∥≥∥p(k)∥→∞ and the level-boundedness of ΨFB, we have limk→∞Ψ~FB(p(k))=+∞. Therefore, Ψ~FB is level-bounded.Remark 17.
Consider  SOCCP (3). Let Ψ~FB:Rn→R be a function such that Ψ~FB(x):=(1/2)∥ϕFB(x,f(x))∥2 for any x∈Rn. Then, in the same way as in Lemma 16, we can show that Ψ~FB is level-bounded if and only if Ψ~FB is level-bounded (we have only to consider g(p)≡p).We now provide some sufficient conditions under which Assumption (A2) holds.Proposition 18.
Consider SOCCP (5). Assume that f and g have linear growth. Assume further that f and g satisfy one of the following statements: (a)
f and g have the joint uniform Jordan P-property;(b)
f and g have the joint Cartesian weak coerciveness. Then ΨFB is level-bounded.Proof.
It follows from [19] that Ψ~NR(p):=(1/2)∥ϕNR(f(p),g(p))∥2 is level-bounded for each case. Thus from Lemma 16 and (29), we have desired results.The following condition was given by Pan and Chen [13] to establish the level-boundedness property of the merit function Ψ~FB(x) defined in Remark 17.Condition A. Consider SOCCP (3). For any sequence {ξk}⊂Rn satisfying ∥ξk∥→∞ with ξki∈Rni, if there exists an index ν∈{1,…,m} such that {λ1(ξkν)} and {λ1(fν(ξk))} are bounded below, and λ2(ξkν),λ2(fν(ξk))→∞, then
(59)limsupk→∞〈ξkν∥ξkν∥,fν(ξk)∥fν(ξk)∥〉>0.
Under Condition A, we have the following proposition, which corresponds to Proposition 5.2 of [13].Proposition 19.
Consider SOCCP (3). Assume that f has the uniform Cartesian P-property and satisfies Condition A. Then ΨFB is level-bounded.


### 4.2. Global Convergence

In this section, we show the global convergence of Algorithm13. We first give the well-definedness of the algorithm.Lemma 20.
Suppose that Assumption (A3) holds. Lett be any fixed positive number. Every stationary point vt* of Ψt satisfies Ψt(vt*)=0.Proof.
For each stationary pointvt* of Ψt, ∇Ψt(vt*)=∇Ht(vt*)H(vt*)=0 holds. Since, from t>0 and Assumption (A3), ∇Ht(vt*) is nonsingular, we have Ht(vt*)=0, and thus, Ψt(vt*)=0.It follows from (35) that
(60)2ΨFB(v^)≤∥Ht(v^)∥+∥HFB(v^)-Ht(v^)∥≤2Ψt(v^)+2mt
for any v^∈R2n+ℓ, and hence we have, from Assumption (A2) and (55), that Ψt is level-bounded for any fixed t>0. Therefore, there exists at least one stationary point of Ψt. Thus from Lemma 20, the system Ht(v)=0 has at least one solution, and hence, there exists a point v satisfying ∥Htk(v)∥<βk in Step 2 at each iteration.We are now ready to show the well-definedness of the algorithm.Proposition 21.
Suppose that Assumptions (A2) and (A3) hold. Then Algorithm13 is well-defined.Proof.
To establish the well-definedness of Algorithm13, we only need to prove the well-definedness and the finite termination property of Step 2 at each iteration. Now we fix k and tk>0. Since ∇Htk(v^(j)) is nonsingular for any v^(j)∈R2n+ℓ by tk>0 and Assumption (A3), d^(j) is uniquely determined for any j≥0. In addition, we have
(61)∇Ψtk(v^(j))⊤d^(j)=-Htk(v^(j))⊤∇Htk(v^(j))⊤∇Htk(v^(j))-⊤Htk(v^(j))=-∥Htk(v^(j))∥2≤0.
If ∥Htk(v^(j)+d^(j))∥≤βk, then Step 2 terminates in Step 2.2. If ∥Htk(v^(j)+d^(j))∥>βk, then integer l satisfying (50) can be found at Step 2.3, because d^(j)≠0 and ∇Ψtk(v^(j))⊤d^(j)<0. Thus, Step 2 is well-defined at each iteration.
Next we prove the finite termination property of Step 2. To prove by contradiction, we assume that Step 2 never stops and then(62)∥Htk(v^(j))∥>βk>0
holds for all j≥0. We consider two cases. (i)
The case where there exists a subsequenceJ such that limj∈J,j→∞τj=0. From the boundedness of the level set of Ψtk at v^(0) and the line search rule (50), {v^(j)} is bounded. In addition, from the continuous differentiability of Ψtk and Assumption (A3), {d^(j)} is also bounded. Thus, there exists a subsequence J′⊂J such that
(63)limj∈J′,j→∞v^(j)=v^*,limj∈J′,j→∞d^(j)=d^*.
Now τj≠1 holds for all sufficiently large j∈J′, and hence, we have
(64)Ψtk(v^(j)+ρlj-1d^(j))-Ψtk(v^(j))ρlj-1>-2σΨtk(v^(j)).
Passing to the limit j→∞ with j∈J′ on the above inequality and taking (62) into account, we have
(65)∇Ψtk(v^*)⊤d^*≥-2σΨtk(v^*)>-2Ψtk(v^*).
On the other hand, it follows from (61) that ∇Ψtk(v^*)⊤d^*=-2Ψtk(v^*), which contradicts (65).(ii)
The case where there existsτ->0 such that τj>τ- for all j. It follows from (50) that
(66)Ψtk(v^(j))≤(1-2στ-)jΨtk(v^(0)),
which implies ∥Htk(v^(j))∥≤βk holds for sufficiently large j. This contradicts (62). Therefore, the proof is complete.In order to show the global convergence of the proposed method, we recall the mountain pass theorem (see [24], e.g.), which is as follows.Lemma 22.
Letφ:Rn→R be a continuously differentiable and level-bounded function. Let 𝒞⊂Rn be a nonempty and compact set and let φ- be the minimum value of φ on bd 𝒞, that is,
(67)φ-:=minx∈bd𝒞φ(x).
Assume that there exist vectors ξ∈𝒞 and η∉𝒞 such that φ(ξ)<φ- and φ(η)<φ-. Then, there exists a vector ζ∈Rn such that ∇φ(ζ)=0 and φ(ζ)≥φ-.By using the mountain pass theorem, we can show the following global convergence property.Theorem 23.
Suppose that Assumptions (A1)–(A3) hold. Then, any accumulation point of the sequence{v(k)} generated by Algorithm 13 is bounded, and hence, at least one accumulation point exists, and any such point is a solution of SOCCP (1).Proof.
From the choices oftk and βk in Step 3 of Algorithm 13, tk and βk converge to zero. Since βk→0, we have limk→∞∥Htk(v(k))∥=0. Thus, it follows from tk→0 and (35) that limk→∞∥HFB(v(k))∥=0. It implies from the continuity of HFB that any accumulation point of the sequence {v(k)} is a solution of HFB(v)=0, and hence, it suffices to prove the boundedness of {v(k)}. To the contrary, we assume {v(k)} is unbounded. Then there exist an index set K and a subsequence {v(k)}k∈K such that limk∈K,k→∞∥v(k)∥=∞. Since, by Assumption (A1), the solution set 𝒮 is bounded, there exists a compact neighborhood 𝒞 of 𝒮 such that 𝒮⊂int𝒞. From the boundedness of 𝒞, v(k)∉𝒞 for all k sufficiently large k∈K. In addition, from 𝒮⊂int𝒞, we have
(68)φ^:=minv∈bd𝒞ΨFB(v)>0,
for otherwise, there would exist v∈bd𝒞 with ΨFB(v)=0, that is, v∈𝒮∩bd𝒞, which contradicts 𝒮⊂int𝒞. Since tk is small enough for all sufficiently large k, it follows from (35) that
(69)-φ^2<Ψtk(v)-ΨFB(v)<φ^2
holds for any v∈𝒞. Now we take v-∈𝒮⊂𝒞. Then (69) yields
(70)|Ψtk(v-)-ΨFB(v-)|=Ψtk(v-)<φ^2.
Letting
(71)v~(k)∈argminv∈bd𝒞Ψtk(v),
we have from (68) and v~(k)∈bd𝒞 that φ^≤ΨFB(v~(k)). Therefore, it follows from (69) and (70) that, for all sufficiently large k,
(72)minv∈bd𝒞Ψtk(v)=Ψtk(v~(k))>-φ^2+ΨFB(v~(k))≥-φ^2+φ^=φ^2.
On the other hand, since 0≤∥Htk(v(k+1))∥≤βk and βk→0, we get
(73)Ψtk(v(k+1))<φ^2
for all k sufficiently large.
Now we choose sufficiently largek^ satisfying all the above arguments with k^+1∈K and apply Lemma 22 with
(74)φ=Ψtk^,ξ=v-∈𝒞,η=v(k^+1)∉𝒞,φ-=minv∈bd𝒞Ψtk^(v)>φ^2.
Then there exists ζ∈R2n+ℓ satisfying
(75)∇Ψtk^(ζ)=0,Ψtk^(ζ)≥φ->φ^2>0,
which contradicts Lemma 20, and therefore the proof is complete.


### 4.3. LocalQ-Superlinear and Q-Quadratic Convergence

In Section4.2, we have shown that the sequence {v(k)} is bounded, and any accumulation point of {v(k)} is a solution of SOCCP (1). In this section, we prove that {v(k)} is superlinearly convergent, or more strongly, quadratically convergent if ∇F is locally Lipschitzian. In order to establish the superlinear (quadratic) convergence of the algorithm, we need an assumption that every accumulation point of {∇Htk(v(k))} is nonsingular. We first consider a sufficient condition for this assumption to hold.Let{v(k)} and {tk} be the sequences generated by Algorithm 13, and let v*=(x*,y*,p*) be any accumulation point of {v(k)}. Then, by Theorem 23, v* is a solution of SOCCP (1). We call the following condition nondegeneracy of a solution of the SOCCP (see also [13, 25]).Definition 24.
Letv*=(x*,y*,p*)∈R2n+ℓ be a solution of  SOCCP (1) with x*=(x*1,…,x*m), y*=(y*1,…,y*m)∈Rn1×⋯×Rnm. Then we say that v* is nondegenerate if x*+y*≻0, or equivalently, x*i+y*i≻0 for all i=1,…,m.For a nondegenerate solution, we have the next lemma.Lemma 25.
Letv*=(x*,y*,p*)∈R2n+ℓ be a nondegenerate solution of  SOCCP (1), and put zi=(xi,yi), z*i=(x*i,y*i)∈R2ni for i=1,…,m. Let t∈R be a nonzero number. Then, for each i, the following holds:
(76)lim(t,zi)→(0,z*i)∇xiϕti(xi,yi)=I-Lx*iLu*i-1,lim(t,zi)→(0,z*i)∇yiϕti(xi,yi)=I-Ly*iLu*i-1,
where
(77)Lu*i-1=[b*i-c*i(w-*i)2⊤-c*i(w-*i)2a*iI+(b*i-a*i)(w-*i)2(w-*i)2⊤]
with
(78)a*i:=2λ1(w*i)+λ2(w*i),b*i≔12(1λ1(w*i)+1λ2(w*i)),c*i:=12(1λ1(w*i)-1λ2(w*i)).
Here w*i and u*i are defined by (37) with x*i and y*i. We also write w*i=((w*i)1,(w*i)2)∈R×Rni-1, and set (w-*i)2:=(w*i)2/∥(w*i)2∥ if (w*i)2≠0, and otherwise, set (w-*i)2 to any vector in Rni-1 satisfying ∥(w-*i)2∥=1.Proof.
Sincev* is a solution of SOCCP (1), it follows from [5, Propsition 4.2] that x*i+y*i-((x*i)2+(y*i)2)1/2=0 for all i=1,…,m. Hence, from the nondegeneracy of v*, we have
(79)u*i=((x*i)2+(y*i)2)1/2=x*i+y*i≻0.
By Property 1(c), this implies that Lu*i is nonsingular. In order to prove this lemma, it suffices to show
(80)lim(t,zi)→(0,z*i)Luti-1=Lu*i-1.
Since (36) yields lim(t,zi)→(0,z*i)uti=u*i, (80) follows from Property 1(c).The following proposition gives a sufficient condition for the nonsingularity of accumulation points of{∇Htk(v(k))}.Proposition 26.
Suppose that Assumptions (A1)–(A3) hold. Let{v(k)} be a sequence generated by Algorithm 13 and let v* be any accumulation point of it. Moreover, assume that v* is nondegenerate and the Jacobian matrix ∇F(v*)⊤ has the Cartesian mixed Jordan P-property, that is, rank∇pF(v*)=ℓ and
(81)∇F(v*)⊤(ξ,η,φ)=0,(ξ,η)≠0,φ∈Rℓξ=(ξ1,…,ξm),η=(η1,…,ηm)∈Rn1×⋯×Rnm⟹thereexistsanindexνsuchthatξν∘ην≻0.Then, every accumulation point of{∇Htk(v(k))}is nonsingular.Proof.
By Theorem23, the sequence {v(k)} is bounded and has at least one accumulation point v*. Hence, we may assume that {v(k)} converges to v* without loss of generality. It follows from Lemma 25 and tk→0 that any accumulation point of {∇Htk(v(k))}, say J0, is given in the following form:
(82)J0:=[diag{I-Lx*iLu*i-1}i=1m∇xF(v*)diag{I-Ly*iLu*i-1}i=1m∇yF(v*)O∇pF(v*)].
In order to prove that J0 is nonsingular, suppose that J0⊤(ξ,η,φ)=0, where (ξ,η,φ)∈R2n+ℓ. We will show that (ξ,η,φ)=0. It follows from (82) that
(83)∇F(v*)⊤(ξ,η,φ)=0,(84)(I-Lu*i-1Lx*i)ξi+(I-Lu*i-1Ly*i)ηi=0,i=1,…,m,
where ξ=(ξ1,…,ξm), η=(η1,…,ηm)∈Rn1×⋯×Rnm. Multiplying both sides of the above equations by Lu*i from the left-hand side, we get
(85)(Lu*i-Lx*i)ξi+(Lu*i-Ly*i)ηi=Lu*i-x*iξi+Lu*i-y*iηi=Ly*iξi+Lx*iηi=0
for all i=1,…,m, where the second equality uses the fact u*i=x*i+y*i (see (79)). Suppose on the contrary that (ξ,η)≠0. Then from (83) and the assumption (81), we have that
(86)ξν∘ην≻0
for some ν∈{1,…,m}. Since x*ν, y*ν≽0, by Property 1(b), we have Lx*ν≽O and Ly*ν≽O. By using Property 1(a), (85) can be rewritten equivalently as
(87)Ly*νξν+x*ν∘ην=0ory*ν∘ξν+Lx*νην=0.
Multiplying both sides of the first equation in (87) by (ξν)⊤ from the left, we have
(88)(ξν)⊤Ly*νξν+〈ξν,x*ν∘ην〉=(ξν)⊤Ly*νξν+〈x*ν,ξν∘ην〉=0.
Since Ly*ν is positive semidefinite, we have 〈x*ν,ξν∘ην〉≤0. Similarly, multiplying both sides of the second equation in (87) by (ην)⊤ from the left, we have 〈y*ν,ξν∘ην〉≤0. Adding these two inequalities yields
(89)〈x*ν+y*ν,ξν∘ην〉≤0.
On the other hand, by the nondegeneracy of v*, we have x*ν+y*ν≻0. This together with (86) yields
(90)〈x*ν+y*ν,ξν∘ην〉>0,
which contradicts (89), and hence, we must have (ξ,η)=0. Then, since the matrix ∇pF(v*)⊤∈R(n+ℓ)×ℓ has full column rank, we also have from (83) that φ=0. Therefore, J0 is nonsingular.Next, we show the local convergence properties of the sequence{v(k)} generated by Algorithm 13. The following lemma plays a key role in proving such properties.Lemma 27.
Suppose that Assumptions (A1)–(A3) hold. Let{v(k)} be a sequence generated by Algorithm 13 and let v* be any accumulation point of it. In addition, assume that every accumulation point of {∇Htk(v(k))} is nonsingular. Then, for v(k) sufficiently close to v*,
(91)∥v(k)+d(k)-v*∥=o(∥v(k)-v*∥)
holds, where d(k) is defined by -∇Htk(v(k))-⊤Htk(v(k)). Moreover, if ∇F is locally Lipschitzian and r≥2, then
(92)∥v(k)+d(k)-v*∥=O(∥v(k)-v*∥2)
holds.Proof.
From Theorem23, {v(k)} is bounded, and hence, there exists at least one accumulation point, and any such point v* satisfies HFB(v*)=0. Since every accumulation point of {∇Htk(v(k))} is nonsingular, we have, from Assumption (A3), that there exists a constant c1>0 such that
(93)∥∇Htk(v(k))-⊤∥≤c1
for all k. Let Vk∈∂HFB(v(k)) such that
(94)Vk∈argminV∈∂HFB(v(k))∥∇Htk(v(k))-V∥.
Note that Vk exists for all k, because ∂HFB(v(k)) is compact [17, page 70]. We have from (93) and HFB(v*)=0 that
(95)∥v(k)+d(k)-v*∥=∥v(k)-∇Htk(v(k))-⊤Htk(v(k))-v*∥≤∥∇Htk(v(k))-⊤∥∥∇Htk(v(k))⊤(v(k)-v*)-Htk(v(k))∥≤c1{∥(∇Htk(v(k))-Vk)⊤(v(k)-v*)∥+∥Vk⊤(v(k)-v*)-HFB′(v*;v(k)-v*)∥+∥HFB′(v*;v(k)-v*)-(HFB(v(k))-HFB(v*))∥+∥HFB(v(k))-Htk(v(k))∥(∇Htk(v(k))-Vk)⊤}.
It follows from (54) that, for v(k) sufficiently close to v*,
(96)∥(∇Htk(v(k))-Vk)⊤(v(k)-v*)∥≤∥∇Htk(v(k))-Vk∥∥v(k)-v*∥=O(∥v(k)-v*∥2).
From (35), the inequality tk≤κδkr=κ∥HFB(v(k))∥r by Step 3 of Algorithm 13, and the local Lipschitz continuity of HFB, we get
(97)∥HFB(v(k))-Htk(v(k))∥≤2mtk≤2mκ∥HFB(v(k))∥r=2mκ∥HFB(v(k))-HFB(v*)∥r=O(∥v(k)-v*∥r).
Since, by Proposition 11, HFB is semismooth, we have from (15) and (17) that
(98)∥Vk⊤(v(k)-v*)-HFB′(v*;v(k)-v*)∥+∥HFB′(v*;v(k)-v*)-(HFB(v(k))-HFB(v*))∥=o(∥v(k)-v*∥).
Therefore, from (95)–(97) and r>1, we obtain (91). Moreover, if ∇F is locally Lipschitzian, then, by Proposition 11, HFB is strongly semismooth, and hence, we have
(99)∥Vk⊤(v(k)-v*)-HFB′(v*;v(k)-v*)∥+∥HFB′(v*;v(k)-v*)-(HFB(v(k))-HFB(v*))∥=O(∥v(k)-v*∥2).
Therefore, from (95)–(97) and r≥2, we obtain (92).Using Lemma27, we obtain the local Q-superlinear (Q-quadratic) convergence result.Theorem 28.
Suppose that Assumptions (A1)–(A3) hold. Let{v(k)} be a sequence generated by Algorithm 13. If every accumulation point of {∇Htk(v(k))} is nonsingular, then the following statements hold. (a)
For allk sufficiently large, ∥HFB(v^(j)+d^(j))∥≤βk is satisfied at j=0 in Step 2.2 of Algorithm 13. Moreover, for all k sufficiently large, v(k+1)=v(k)+d(k) holds, where d(k)=-∇Htk(v(k))-⊤Htk(v(k)).(b)
The whole sequence{v(k)} converges Q-superlinearly to a solution v* of SOCCP (1). Moreover, if ∇F is locally Lipschitz continuous and r≥2, then the sequence {v(k)} converges Q-quadratically.Proof.
Since (b) is directly obtained from (a) and Lemma27, it suffices to prove (a). Namely, we prove that ∥Htk(v(k)+d(k))∥≤βk=β0ηk for all k sufficiently large. We have from (93) that
(100)∥d(k)∥=∥-∇Htk(v(k))-⊤Htk(v(k))∥≤c1∥Htk(v(k))∥,
and hence, it follows from the boundedness of {v(k)} and the continuity of Htk that {d(k)} is bounded. Let v* be any accumulation point of v(k), and let v(k) be sufficiently close to v*. By Theorem 23, v* is a solution of SOCCP (1), and thus, HFB(v*)=0. From the local Lipschitz continuity of HFB, we may assume that ∥HFB(v(k))∥ is small enough. By Lemma 27 and (100), there exists a constant c2∈(0,1) such that
(101)∥v(k)-v*∥≤∥-d(k)∥+∥v(k)+d(k)-v*∥≤c1∥Htk(v(k))∥+o(∥v(k)-v*∥)≤c1∥Htk(v(k))∥+c2∥v(k)-v*∥.
Therefore, we have from (35) with tk≤κ∥HFB(v(k))∥r≤κ∥HFB(v(k))∥ that
(102)∥v(k)-v*∥≤c11-c2∥Htk(v(k))∥≤c11-c2(∥Htk(v(k))-HFB(v(k))∥+∥HFB(v(k))∥)≤c11-c2(2mtk+∥HFB(v(k))∥)=O(∥HFB(v(k))∥).
This together with Lemma 27 and the local Lipschitz continuity of HFB yields that
(103)∥HFB(v(k)+d(k))∥=∥HFB(v(k)+d(k))-HFB(v*)∥=O(∥v(k)+d(k)-v*∥)=o(∥v(k)-v*∥)=o(∥HFB(v(k))∥).
Therefore, it follows again from (35) with tk≤κ∥HFB(v(k))∥r that
(104)∥Htk(v(k)+d(k))∥≤∥Htk(v(k)+d(k))-HFB(v(k)+d(k))∥+∥HFB(v(k)+d(k))∥≤2mtk+∥HFB(v(k)+d(k))∥=o(∥HFB(v(k))∥).
From (35), the choices of tk and βk in Step 3 of Algorithm 13, and 0<η-≤η<1, we get
(105)∥HFB(v(k))∥≤∥HFB(v(k))-Htk-1(v(k))∥+∥Htk-1(v(k))∥≤2mtk-1+βk-1≤2mt0ηk-1+β0ηk-1=c3ηk,
where c3=η-1(2mt0+β0), and hence, (104) yields ∥Htk(v(k)+d(k))∥=o(ηk). This implies that ∥Htk(v(k)+d(k))∥≤βk=β0ηk. Taking into account v^(0)=v(k) and d^(0)=d(k), we have ∥HFB(v^(0)+d^(0))∥≤βk and v(k+1)=v(k)+d(k). Since, by Lemma 27, v(k+1) remains in the neighborhood of v*, the desired results are obtained.


## 4.1. Algorithm

We provide the smoothing Newton algorithm based on the Fischer-Burmeister function. In what follows, we writev(k)=(x(k),y(k),p(k)) and z(k)=(x(k),y(k)) for simplicity.Algorithm 13.
Step   0. Choose η, ρ∈(0,1), η-∈(0,η], σ∈(0,1/2), r>1, κ>0, and κ^>0.
Choosev(0)=(x(0),y(0),p(0))∈R2n+ℓ and β0∈(0,∞). Let t0:=∥HFB(v(0))∥. Set k:=0.
Step   1.If a stopping criterion, such as ∥HFB(v(k))∥=0, is satisfied, then stop.
Step   2.
Step   2.0. Set v^(0):=v(k) and j:=0.
Step   2.1. Compute d^(j)∈R2n+ℓ by solving (49)Htk(v^(j))+∇Htk(v^(j))⊤d^(j)=0.
Step   2.2. If ∥Htk(v^(j)+d^(j))∥≤βk, then let v(k+1):=v^(j)+d^(j) and go to Step 3. Otherwise, go to Step 2.3.
Step   2.3. Let lj be the smallest nonnegative integer l satisfying
(50)Ψtk(v^(j)+ρld^(j))≤(1-2σρl)Ψtk(v^(j)).
Letτj:=ρlj and v^(j+1):=v^(j)+τjd^(j).
Step   2.4. If
(51)∥Htk(v^(j+1))∥≤βk,
then let v(k+1):=v^(j+1) and go to Step 3. Otherwise, set j:=j+1 and go back to Step 2.1.
Step    3. Update the parameters as follows:
(52)δk+1:=∥HFB(v(k+1))∥,tk+1:=min{κδk+1r,t0η-k+1,t-(z(k+1),κ^δk+1)},βk+1:=β0ηk+1.
Step   4. Set k:=k+1. Go back to Step 1.
Note that the proposed algorithm consists of the outer iteration steps and the inner iteration steps. Step 2 is the inner iteration steps with the variablev^ and the counter j, while the outer iteration steps have the variable v and the counter k.
From Step 3 of Algorithm13 and (48), the following inequality holds:
(53)min{∥∇Htk(v(k))-Y∥∣Y∈∂HFB(v(k))}≤κ^∥HFB(v(k))∥.
Letting v* be a solution of SOCCP (1), we have HFB(v*)=0. Therefore, from (53) and the local Lipschitz continuity of HFB, the following holds:
(54)min{∥∇Htk(v(k))-Y∥∣Y∈∂HFB(v(k))}≤κ^∥HFB(v(k))-HFB(v*)∥=O(∥v(k)-v*∥).
In the rest of this section, we consider convergence properties of Algorithm13. In Section 4.2, we prove the global convergence of the algorithm, and in Section 4.3, we investigate local behavior of the algorithm. For this purpose, we make the following assumptions.Assumption 1.
(A1)
The solution set𝒮 of  SOCCP (1) is nonempty and bounded.
(A2)
The functionΨFB is level-bounded, that is, for any v-∈R2n+ℓ, the level set {v∈R2n+ℓ∣ΨFB(v)≤ΨFB(v-)} is bounded.
(A3)
For anyt>0 and v∈R2n+ℓ, ∇Ht(v) is nonsingular.From Proposition10, Assumption (A3) holds if ∇F(v)⊤ has the Cartesian mixed P0-property for any v∈R2n+ℓ. The following remarks correspond to SOCCPs (3) and (5).Remark 14.
The case of  SOCCP (3). If ∇f(x)⊤ has the Cartesian P0-property, then ∇F(x,y,p)⊤ with F in (4) has the Cartesian mixed P0-property and vice versa. Note that ∇f(x)⊤ has the Cartesian P0-property at any x∈Rn if f has the Cartesian P0-property (see [10, 13] for the definition of the Cartesian P0-property for a matrix).Remark 15.
The case of  SOCCP (5). If ∇f(p) is nonsingular and (∇f(p)-1∇g(p))⊤ has the Cartesian P0-property, then ∇F(x,y,p)⊤ with F in (6) has the Cartesian mixed P0-property.Note that Assumption (A2) is equivalent to the coerciveness in the sense that(55)lim∥v∥→∞ΨFB(v)=+∞.
We now give some sufficient conditions for Assumption (A2) in the case of SOCCP (3) or (5).Lemma 16.
Consider SOCCP (5). Let Ψ~FB:Rn→R be a function such that Ψ~FB(p):=(1/2)∥ϕFB(f(p),g(p))∥2 for any p∈Rn. Then Ψ~FB is level-bounded if and only if Ψ~FB is level-bounded.Proof.
We use below condition (55) equivalent to the level-boundedness. We first assume that Ψ~FB is level-bounded and claim that ΨFB is level-bounded. Suppose the contrary. Then, we can find a sequence {v(k)}={(x(k),y(k),p(k))}⊂R3n such that the sequence {ΨFB(v(k))} is bounded and ∥v(k)∥→∞. If {∥p(k)∥} is bounded, then we must have ∥(x(k),y(k))∥→∞. Thus, from the inequality
(56)2ΨFB(v(k))≥∥(f(p(k))-x(k),g(p(k))-y(k))∥≥∥(x(k),y(k))∥-∥(f(p(k)),g(p(k)))∥
and from the continuity of f and g, we have ΨFB(v(k))→∞. Since this is not possible, {∥p(k)∥} is unbounded. By taking a subsequence if necessary, we may assume that ∥p(k)∥→∞ as k→∞. Since ϕFB is globally Lipschitzian by [23, Corollary 3.3], we have from (33) that, for any (x,y,p)∈R3n,
(57)2Ψ~FB(p)=∥ϕFB(f(p),g(p))∥≤∥ϕFB(f(p),g(p))-ϕFB(x,y)∥+∥ϕFB(x,y)∥≤L∥(f(p),g(p))-(x,y)∥+∥ϕFB(x,y)∥≤L2+1∥(f(p)-x,g(p)-y)∥2+∥ϕFB(x,y)∥2=L2+12ΨFB(x,y,p),
where L>0 is a Lipschitz constant. Then, it follows from (57) and the level-boundedness of Ψ~FB that limk→∞ΨFB(v(k))=+∞, contradicting the boundedness of {ΨFB(v(k))}. This proves the level-boundedness of ΨFB.
We next assume thatΨFB is level-bounded. Let {p(k)}⊂Rn be an arbitrary sequence such that ∥p(k)∥→∞ and let x(k):=f(p(k)) and y(k):=g(p(k)). Then we have
(58)2ΨFB(x(k),y(k),p(k))=∥ϕFB(x(k),y(k))∥2+∥f(p(k))-x(k)∥2+∥g(p(k))-y(k)∥2=∥ϕFB(f(p(k)),g(p(k)))∥2=2Ψ~FB(p(k)).
Thus, from ∥(x(k),y(k),p(k))∥≥∥p(k)∥→∞ and the level-boundedness of ΨFB, we have limk→∞Ψ~FB(p(k))=+∞. Therefore, Ψ~FB is level-bounded.Remark 17.
Consider  SOCCP (3). Let Ψ~FB:Rn→R be a function such that Ψ~FB(x):=(1/2)∥ϕFB(x,f(x))∥2 for any x∈Rn. Then, in the same way as in Lemma 16, we can show that Ψ~FB is level-bounded if and only if Ψ~FB is level-bounded (we have only to consider g(p)≡p).We now provide some sufficient conditions under which Assumption (A2) holds.Proposition 18.
Consider SOCCP (5). Assume that f and g have linear growth. Assume further that f and g satisfy one of the following statements: (a)
f and g have the joint uniform Jordan P-property;(b)
f and g have the joint Cartesian weak coerciveness. Then ΨFB is level-bounded.Proof.
It follows from [19] that Ψ~NR(p):=(1/2)∥ϕNR(f(p),g(p))∥2 is level-bounded for each case. Thus from Lemma 16 and (29), we have desired results.The following condition was given by Pan and Chen [13] to establish the level-boundedness property of the merit function Ψ~FB(x) defined in Remark 17.Condition A. Consider SOCCP (3). For any sequence {ξk}⊂Rn satisfying ∥ξk∥→∞ with ξki∈Rni, if there exists an index ν∈{1,…,m} such that {λ1(ξkν)} and {λ1(fν(ξk))} are bounded below, and λ2(ξkν),λ2(fν(ξk))→∞, then
(59)limsupk→∞〈ξkν∥ξkν∥,fν(ξk)∥fν(ξk)∥〉>0.
Under Condition A, we have the following proposition, which corresponds to Proposition 5.2 of [13].Proposition 19.
Consider SOCCP (3). Assume that f has the uniform Cartesian P-property and satisfies Condition A. Then ΨFB is level-bounded.


## 4.2. Global Convergence

In this section, we show the global convergence of Algorithm13. We first give the well-definedness of the algorithm.Lemma 20.
Suppose that Assumption (A3) holds. Lett be any fixed positive number. Every stationary point vt* of Ψt satisfies Ψt(vt*)=0.Proof.
For each stationary pointvt* of Ψt, ∇Ψt(vt*)=∇Ht(vt*)H(vt*)=0 holds. Since, from t>0 and Assumption (A3), ∇Ht(vt*) is nonsingular, we have Ht(vt*)=0, and thus, Ψt(vt*)=0.It follows from (35) that
(60)2ΨFB(v^)≤∥Ht(v^)∥+∥HFB(v^)-Ht(v^)∥≤2Ψt(v^)+2mt
for any v^∈R2n+ℓ, and hence we have, from Assumption (A2) and (55), that Ψt is level-bounded for any fixed t>0. Therefore, there exists at least one stationary point of Ψt. Thus from Lemma 20, the system Ht(v)=0 has at least one solution, and hence, there exists a point v satisfying ∥Htk(v)∥<βk in Step 2 at each iteration.We are now ready to show the well-definedness of the algorithm.Proposition 21.
Suppose that Assumptions (A2) and (A3) hold. Then Algorithm13 is well-defined.Proof.
To establish the well-definedness of Algorithm13, we only need to prove the well-definedness and the finite termination property of Step 2 at each iteration. Now we fix k and tk>0. Since ∇Htk(v^(j)) is nonsingular for any v^(j)∈R2n+ℓ by tk>0 and Assumption (A3), d^(j) is uniquely determined for any j≥0. In addition, we have
(61)∇Ψtk(v^(j))⊤d^(j)=-Htk(v^(j))⊤∇Htk(v^(j))⊤∇Htk(v^(j))-⊤Htk(v^(j))=-∥Htk(v^(j))∥2≤0.
If ∥Htk(v^(j)+d^(j))∥≤βk, then Step 2 terminates in Step 2.2. If ∥Htk(v^(j)+d^(j))∥>βk, then integer l satisfying (50) can be found at Step 2.3, because d^(j)≠0 and ∇Ψtk(v^(j))⊤d^(j)<0. Thus, Step 2 is well-defined at each iteration.
Next we prove the finite termination property of Step 2. To prove by contradiction, we assume that Step 2 never stops and then(62)∥Htk(v^(j))∥>βk>0
holds for all j≥0. We consider two cases. (i)
The case where there exists a subsequenceJ such that limj∈J,j→∞τj=0. From the boundedness of the level set of Ψtk at v^(0) and the line search rule (50), {v^(j)} is bounded. In addition, from the continuous differentiability of Ψtk and Assumption (A3), {d^(j)} is also bounded. Thus, there exists a subsequence J′⊂J such that
(63)limj∈J′,j→∞v^(j)=v^*,limj∈J′,j→∞d^(j)=d^*.
Now τj≠1 holds for all sufficiently large j∈J′, and hence, we have
(64)Ψtk(v^(j)+ρlj-1d^(j))-Ψtk(v^(j))ρlj-1>-2σΨtk(v^(j)).
Passing to the limit j→∞ with j∈J′ on the above inequality and taking (62) into account, we have
(65)∇Ψtk(v^*)⊤d^*≥-2σΨtk(v^*)>-2Ψtk(v^*).
On the other hand, it follows from (61) that ∇Ψtk(v^*)⊤d^*=-2Ψtk(v^*), which contradicts (65).(ii)
The case where there existsτ->0 such that τj>τ- for all j. It follows from (50) that
(66)Ψtk(v^(j))≤(1-2στ-)jΨtk(v^(0)),
which implies ∥Htk(v^(j))∥≤βk holds for sufficiently large j. This contradicts (62). Therefore, the proof is complete.In order to show the global convergence of the proposed method, we recall the mountain pass theorem (see [24], e.g.), which is as follows.Lemma 22.
Letφ:Rn→R be a continuously differentiable and level-bounded function. Let 𝒞⊂Rn be a nonempty and compact set and let φ- be the minimum value of φ on bd 𝒞, that is,
(67)φ-:=minx∈bd𝒞φ(x).
Assume that there exist vectors ξ∈𝒞 and η∉𝒞 such that φ(ξ)<φ- and φ(η)<φ-. Then, there exists a vector ζ∈Rn such that ∇φ(ζ)=0 and φ(ζ)≥φ-.By using the mountain pass theorem, we can show the following global convergence property.Theorem 23.
Suppose that Assumptions (A1)–(A3) hold. Then, any accumulation point of the sequence{v(k)} generated by Algorithm 13 is bounded, and hence, at least one accumulation point exists, and any such point is a solution of SOCCP (1).Proof.
From the choices oftk and βk in Step 3 of Algorithm 13, tk and βk converge to zero. Since βk→0, we have limk→∞∥Htk(v(k))∥=0. Thus, it follows from tk→0 and (35) that limk→∞∥HFB(v(k))∥=0. It implies from the continuity of HFB that any accumulation point of the sequence {v(k)} is a solution of HFB(v)=0, and hence, it suffices to prove the boundedness of {v(k)}. To the contrary, we assume {v(k)} is unbounded. Then there exist an index set K and a subsequence {v(k)}k∈K such that limk∈K,k→∞∥v(k)∥=∞. Since, by Assumption (A1), the solution set 𝒮 is bounded, there exists a compact neighborhood 𝒞 of 𝒮 such that 𝒮⊂int𝒞. From the boundedness of 𝒞, v(k)∉𝒞 for all k sufficiently large k∈K. In addition, from 𝒮⊂int𝒞, we have
(68)φ^:=minv∈bd𝒞ΨFB(v)>0,
for otherwise, there would exist v∈bd𝒞 with ΨFB(v)=0, that is, v∈𝒮∩bd𝒞, which contradicts 𝒮⊂int𝒞. Since tk is small enough for all sufficiently large k, it follows from (35) that
(69)-φ^2<Ψtk(v)-ΨFB(v)<φ^2
holds for any v∈𝒞. Now we take v-∈𝒮⊂𝒞. Then (69) yields
(70)|Ψtk(v-)-ΨFB(v-)|=Ψtk(v-)<φ^2.
Letting
(71)v~(k)∈argminv∈bd𝒞Ψtk(v),
we have from (68) and v~(k)∈bd𝒞 that φ^≤ΨFB(v~(k)). Therefore, it follows from (69) and (70) that, for all sufficiently large k,
(72)minv∈bd𝒞Ψtk(v)=Ψtk(v~(k))>-φ^2+ΨFB(v~(k))≥-φ^2+φ^=φ^2.
On the other hand, since 0≤∥Htk(v(k+1))∥≤βk and βk→0, we get
(73)Ψtk(v(k+1))<φ^2
for all k sufficiently large.
Now we choose sufficiently largek^ satisfying all the above arguments with k^+1∈K and apply Lemma 22 with
(74)φ=Ψtk^,ξ=v-∈𝒞,η=v(k^+1)∉𝒞,φ-=minv∈bd𝒞Ψtk^(v)>φ^2.
Then there exists ζ∈R2n+ℓ satisfying
(75)∇Ψtk^(ζ)=0,Ψtk^(ζ)≥φ->φ^2>0,
which contradicts Lemma 20, and therefore the proof is complete.


## 4.3. LocalQ-Superlinear and Q-Quadratic Convergence

In Section4.2, we have shown that the sequence {v(k)} is bounded, and any accumulation point of {v(k)} is a solution of SOCCP (1). In this section, we prove that {v(k)} is superlinearly convergent, or more strongly, quadratically convergent if ∇F is locally Lipschitzian. In order to establish the superlinear (quadratic) convergence of the algorithm, we need an assumption that every accumulation point of {∇Htk(v(k))} is nonsingular. We first consider a sufficient condition for this assumption to hold.Let{v(k)} and {tk} be the sequences generated by Algorithm 13, and let v*=(x*,y*,p*) be any accumulation point of {v(k)}. Then, by Theorem 23, v* is a solution of SOCCP (1). We call the following condition nondegeneracy of a solution of the SOCCP (see also [13, 25]).Definition 24.
Letv*=(x*,y*,p*)∈R2n+ℓ be a solution of  SOCCP (1) with x*=(x*1,…,x*m), y*=(y*1,…,y*m)∈Rn1×⋯×Rnm. Then we say that v* is nondegenerate if x*+y*≻0, or equivalently, x*i+y*i≻0 for all i=1,…,m.For a nondegenerate solution, we have the next lemma.Lemma 25.
Letv*=(x*,y*,p*)∈R2n+ℓ be a nondegenerate solution of  SOCCP (1), and put zi=(xi,yi), z*i=(x*i,y*i)∈R2ni for i=1,…,m. Let t∈R be a nonzero number. Then, for each i, the following holds:
(76)lim(t,zi)→(0,z*i)∇xiϕti(xi,yi)=I-Lx*iLu*i-1,lim(t,zi)→(0,z*i)∇yiϕti(xi,yi)=I-Ly*iLu*i-1,
where
(77)Lu*i-1=[b*i-c*i(w-*i)2⊤-c*i(w-*i)2a*iI+(b*i-a*i)(w-*i)2(w-*i)2⊤]
with
(78)a*i:=2λ1(w*i)+λ2(w*i),b*i≔12(1λ1(w*i)+1λ2(w*i)),c*i:=12(1λ1(w*i)-1λ2(w*i)).
Here w*i and u*i are defined by (37) with x*i and y*i. We also write w*i=((w*i)1,(w*i)2)∈R×Rni-1, and set (w-*i)2:=(w*i)2/∥(w*i)2∥ if (w*i)2≠0, and otherwise, set (w-*i)2 to any vector in Rni-1 satisfying ∥(w-*i)2∥=1.Proof.
Sincev* is a solution of SOCCP (1), it follows from [5, Propsition 4.2] that x*i+y*i-((x*i)2+(y*i)2)1/2=0 for all i=1,…,m. Hence, from the nondegeneracy of v*, we have
(79)u*i=((x*i)2+(y*i)2)1/2=x*i+y*i≻0.
By Property 1(c), this implies that Lu*i is nonsingular. In order to prove this lemma, it suffices to show
(80)lim(t,zi)→(0,z*i)Luti-1=Lu*i-1.
Since (36) yields lim(t,zi)→(0,z*i)uti=u*i, (80) follows from Property 1(c).The following proposition gives a sufficient condition for the nonsingularity of accumulation points of{∇Htk(v(k))}.Proposition 26.
Suppose that Assumptions (A1)–(A3) hold. Let{v(k)} be a sequence generated by Algorithm 13 and let v* be any accumulation point of it. Moreover, assume that v* is nondegenerate and the Jacobian matrix ∇F(v*)⊤ has the Cartesian mixed Jordan P-property, that is, rank∇pF(v*)=ℓ and
(81)∇F(v*)⊤(ξ,η,φ)=0,(ξ,η)≠0,φ∈Rℓξ=(ξ1,…,ξm),η=(η1,…,ηm)∈Rn1×⋯×Rnm⟹thereexistsanindexνsuchthatξν∘ην≻0.Then, every accumulation point of{∇Htk(v(k))}is nonsingular.Proof.
By Theorem23, the sequence {v(k)} is bounded and has at least one accumulation point v*. Hence, we may assume that {v(k)} converges to v* without loss of generality. It follows from Lemma 25 and tk→0 that any accumulation point of {∇Htk(v(k))}, say J0, is given in the following form:
(82)J0:=[diag{I-Lx*iLu*i-1}i=1m∇xF(v*)diag{I-Ly*iLu*i-1}i=1m∇yF(v*)O∇pF(v*)].
In order to prove that J0 is nonsingular, suppose that J0⊤(ξ,η,φ)=0, where (ξ,η,φ)∈R2n+ℓ. We will show that (ξ,η,φ)=0. It follows from (82) that
(83)∇F(v*)⊤(ξ,η,φ)=0,(84)(I-Lu*i-1Lx*i)ξi+(I-Lu*i-1Ly*i)ηi=0,i=1,…,m,
where ξ=(ξ1,…,ξm), η=(η1,…,ηm)∈Rn1×⋯×Rnm. Multiplying both sides of the above equations by Lu*i from the left-hand side, we get
(85)(Lu*i-Lx*i)ξi+(Lu*i-Ly*i)ηi=Lu*i-x*iξi+Lu*i-y*iηi=Ly*iξi+Lx*iηi=0
for all i=1,…,m, where the second equality uses the fact u*i=x*i+y*i (see (79)). Suppose on the contrary that (ξ,η)≠0. Then from (83) and the assumption (81), we have that
(86)ξν∘ην≻0
for some ν∈{1,…,m}. Since x*ν, y*ν≽0, by Property 1(b), we have Lx*ν≽O and Ly*ν≽O. By using Property 1(a), (85) can be rewritten equivalently as
(87)Ly*νξν+x*ν∘ην=0ory*ν∘ξν+Lx*νην=0.
Multiplying both sides of the first equation in (87) by (ξν)⊤ from the left, we have
(88)(ξν)⊤Ly*νξν+〈ξν,x*ν∘ην〉=(ξν)⊤Ly*νξν+〈x*ν,ξν∘ην〉=0.
Since Ly*ν is positive semidefinite, we have 〈x*ν,ξν∘ην〉≤0. Similarly, multiplying both sides of the second equation in (87) by (ην)⊤ from the left, we have 〈y*ν,ξν∘ην〉≤0. Adding these two inequalities yields
(89)〈x*ν+y*ν,ξν∘ην〉≤0.
On the other hand, by the nondegeneracy of v*, we have x*ν+y*ν≻0. This together with (86) yields
(90)〈x*ν+y*ν,ξν∘ην〉>0,
which contradicts (89), and hence, we must have (ξ,η)=0. Then, since the matrix ∇pF(v*)⊤∈R(n+ℓ)×ℓ has full column rank, we also have from (83) that φ=0. Therefore, J0 is nonsingular.Next, we show the local convergence properties of the sequence{v(k)} generated by Algorithm 13. The following lemma plays a key role in proving such properties.Lemma 27.
Suppose that Assumptions (A1)–(A3) hold. Let{v(k)} be a sequence generated by Algorithm 13 and let v* be any accumulation point of it. In addition, assume that every accumulation point of {∇Htk(v(k))} is nonsingular. Then, for v(k) sufficiently close to v*,
(91)∥v(k)+d(k)-v*∥=o(∥v(k)-v*∥)
holds, where d(k) is defined by -∇Htk(v(k))-⊤Htk(v(k)). Moreover, if ∇F is locally Lipschitzian and r≥2, then
(92)∥v(k)+d(k)-v*∥=O(∥v(k)-v*∥2)
holds.Proof.
From Theorem23, {v(k)} is bounded, and hence, there exists at least one accumulation point, and any such point v* satisfies HFB(v*)=0. Since every accumulation point of {∇Htk(v(k))} is nonsingular, we have, from Assumption (A3), that there exists a constant c1>0 such that
(93)∥∇Htk(v(k))-⊤∥≤c1
for all k. Let Vk∈∂HFB(v(k)) such that
(94)Vk∈argminV∈∂HFB(v(k))∥∇Htk(v(k))-V∥.
Note that Vk exists for all k, because ∂HFB(v(k)) is compact [17, page 70]. We have from (93) and HFB(v*)=0 that
(95)∥v(k)+d(k)-v*∥=∥v(k)-∇Htk(v(k))-⊤Htk(v(k))-v*∥≤∥∇Htk(v(k))-⊤∥∥∇Htk(v(k))⊤(v(k)-v*)-Htk(v(k))∥≤c1{∥(∇Htk(v(k))-Vk)⊤(v(k)-v*)∥+∥Vk⊤(v(k)-v*)-HFB′(v*;v(k)-v*)∥+∥HFB′(v*;v(k)-v*)-(HFB(v(k))-HFB(v*))∥+∥HFB(v(k))-Htk(v(k))∥(∇Htk(v(k))-Vk)⊤}.
It follows from (54) that, for v(k) sufficiently close to v*,
(96)∥(∇Htk(v(k))-Vk)⊤(v(k)-v*)∥≤∥∇Htk(v(k))-Vk∥∥v(k)-v*∥=O(∥v(k)-v*∥2).
From (35), the inequality tk≤κδkr=κ∥HFB(v(k))∥r by Step 3 of Algorithm 13, and the local Lipschitz continuity of HFB, we get
(97)∥HFB(v(k))-Htk(v(k))∥≤2mtk≤2mκ∥HFB(v(k))∥r=2mκ∥HFB(v(k))-HFB(v*)∥r=O(∥v(k)-v*∥r).
Since, by Proposition 11, HFB is semismooth, we have from (15) and (17) that
(98)∥Vk⊤(v(k)-v*)-HFB′(v*;v(k)-v*)∥+∥HFB′(v*;v(k)-v*)-(HFB(v(k))-HFB(v*))∥=o(∥v(k)-v*∥).
Therefore, from (95)–(97) and r>1, we obtain (91). Moreover, if ∇F is locally Lipschitzian, then, by Proposition 11, HFB is strongly semismooth, and hence, we have
(99)∥Vk⊤(v(k)-v*)-HFB′(v*;v(k)-v*)∥+∥HFB′(v*;v(k)-v*)-(HFB(v(k))-HFB(v*))∥=O(∥v(k)-v*∥2).
Therefore, from (95)–(97) and r≥2, we obtain (92).Using Lemma27, we obtain the local Q-superlinear (Q-quadratic) convergence result.Theorem 28.
Suppose that Assumptions (A1)–(A3) hold. Let{v(k)} be a sequence generated by Algorithm 13. If every accumulation point of {∇Htk(v(k))} is nonsingular, then the following statements hold. (a)
For allk sufficiently large, ∥HFB(v^(j)+d^(j))∥≤βk is satisfied at j=0 in Step 2.2 of Algorithm 13. Moreover, for all k sufficiently large, v(k+1)=v(k)+d(k) holds, where d(k)=-∇Htk(v(k))-⊤Htk(v(k)).(b)
The whole sequence{v(k)} converges Q-superlinearly to a solution v* of SOCCP (1). Moreover, if ∇F is locally Lipschitz continuous and r≥2, then the sequence {v(k)} converges Q-quadratically.Proof.
Since (b) is directly obtained from (a) and Lemma27, it suffices to prove (a). Namely, we prove that ∥Htk(v(k)+d(k))∥≤βk=β0ηk for all k sufficiently large. We have from (93) that
(100)∥d(k)∥=∥-∇Htk(v(k))-⊤Htk(v(k))∥≤c1∥Htk(v(k))∥,
and hence, it follows from the boundedness of {v(k)} and the continuity of Htk that {d(k)} is bounded. Let v* be any accumulation point of v(k), and let v(k) be sufficiently close to v*. By Theorem 23, v* is a solution of SOCCP (1), and thus, HFB(v*)=0. From the local Lipschitz continuity of HFB, we may assume that ∥HFB(v(k))∥ is small enough. By Lemma 27 and (100), there exists a constant c2∈(0,1) such that
(101)∥v(k)-v*∥≤∥-d(k)∥+∥v(k)+d(k)-v*∥≤c1∥Htk(v(k))∥+o(∥v(k)-v*∥)≤c1∥Htk(v(k))∥+c2∥v(k)-v*∥.
Therefore, we have from (35) with tk≤κ∥HFB(v(k))∥r≤κ∥HFB(v(k))∥ that
(102)∥v(k)-v*∥≤c11-c2∥Htk(v(k))∥≤c11-c2(∥Htk(v(k))-HFB(v(k))∥+∥HFB(v(k))∥)≤c11-c2(2mtk+∥HFB(v(k))∥)=O(∥HFB(v(k))∥).
This together with Lemma 27 and the local Lipschitz continuity of HFB yields that
(103)∥HFB(v(k)+d(k))∥=∥HFB(v(k)+d(k))-HFB(v*)∥=O(∥v(k)+d(k)-v*∥)=o(∥v(k)-v*∥)=o(∥HFB(v(k))∥).
Therefore, it follows again from (35) with tk≤κ∥HFB(v(k))∥r that
(104)∥Htk(v(k)+d(k))∥≤∥Htk(v(k)+d(k))-HFB(v(k)+d(k))∥+∥HFB(v(k)+d(k))∥≤2mtk+∥HFB(v(k)+d(k))∥=o(∥HFB(v(k))∥).
From (35), the choices of tk and βk in Step 3 of Algorithm 13, and 0<η-≤η<1, we get
(105)∥HFB(v(k))∥≤∥HFB(v(k))-Htk-1(v(k))∥+∥Htk-1(v(k))∥≤2mtk-1+βk-1≤2mt0ηk-1+β0ηk-1=c3ηk,
where c3=η-1(2mt0+β0), and hence, (104) yields ∥Htk(v(k)+d(k))∥=o(ηk). This implies that ∥Htk(v(k)+d(k))∥≤βk=β0ηk. Taking into account v^(0)=v(k) and d^(0)=d(k), we have ∥HFB(v^(0)+d^(0))∥≤βk and v(k+1)=v(k)+d(k). Since, by Lemma 27, v(k+1) remains in the neighborhood of v*, the desired results are obtained.


## 5. Numerical Experiments

In this section, we show some numerical results for Algorithm13. The program was coded in MATLAB 7, and computations were carried out on a machine with Intel Core i7-3770 K CPU (3.50 GHz×2) and 8.0 GB RAM. We set the parameters η=η-=0.1, ρ=0.66, σ=0.1, r=2, κ=1, κ^=0.2, and β0=2. We also set the function t-i as follows (see [22] for details):
(106)t-i(zi,δ):={∥zi∥δ2(1-δ2)ifzi≠(0,0)∈R2,δ<1,1010otherwise
for ni=1, and
(107)t-i(zi,δ):={λ1(wi)δ2(2(wi)1-λ1(wi)δ2)ifzi∈𝒵1i,δ<2(wi)1λ1(wi),δ(wi)122(2-δ)ifzi∈𝒵2i,δ<2,1010otherwise
for ni≥2. For all problems, we randomly chose the initial point (x(0),y(0),p(0))∈R2n+ℓ whose components were distributed on the interval [0,1], by using rand command of MATLAB. The stopping criterion in Step 1 is relaxed to
(108)∥HFB(v(k))∥≤10-8.We first solve the following second-order cone programming (SOCP) problem:(109)minimizec⊤xsubjecttoAx+b=0,x∈𝒦,
which is reformulated as SOCCP (1) with
(110)F(x,y,p):=[O-IA⊤AOO][xyp]+[cb]
equivalently. We generate one hundred test problems randomly such that there exist primal and dual strictly feasible solutions. Specifically, we first choose matrix A∈Rℓ×n whose components are distributed on [-100,100], vectors x-,y-∈int𝒦 and p-∈Rℓ randomly, and then set b:=-Ax- and c:=-A⊤p-+y-. Here, each component of (x-i)2 is distributed on [-100,100] and (x-i)1 is set to (x-i)1:=∥(x-i)2∥+α, where α∈(0,100] is chosen randomly, and y- is also generated similarly, while each component of p- is distributed on [0,1]. In order to compare our method with another method, we solve SOCP (109) by SDPT3 [26, 27], which is the software of interior point methods for solving semidefinite, second-order cone, and linear programming problems. We use SDPT3 with the default parameter and option settings. The obtained results are shown in Table 1, in which “Iter” and “CPU” denote the average values of the number of iterations and the CPU time in seconds, respectively. In particular, the value of “Iter” in “our method” denotes the number of times that the Newton equations (49) have been solved. In the column of 𝒦, (𝒦5)3 denotes 𝒦5×𝒦5×𝒦5, for example. Since SDPT3 failed to solve some test problems when 𝒦=(𝒦5)3×(𝒦2)2×R+, the average values in this case were taken over the successful trials only. We see from Table 1 that our method is superior to or at least comparable with SDPT3 from the viewpoint of the number of iterations. On the other hand, from the viewpoint of CPU time, our method is also superior to SDPT3 for small-scale problems. However, SDPT3 outperforms our method for middle- or large-scale problems. We believe that this is because SDPT3 is coded to reduce the computational costs by means of some fundamental techniques on matrix computation and so forth. For further development of our method, we will need more appropriate tuning of our code. However, it is not the purpose of this paper.Table 1
Numerical comparison of our method with SDPT3.
𝒦
n
ℓ
Our method
SDPT3
Iter
CPU
Iter
CPU
(
𝒦
5
)
3
×
(
𝒦
2
)
2
×
R
+
20
5
8.99
0.063
8.84
0.070
(
𝒦
10
)
5
50
10
8.28
0.058
9.82
0.078
(
𝒦
100
)
3
×
(
𝒦
50
)
2
400
100
7.02
1.521
10.19
0.291
𝒦
500
×
𝒦
200
×
(
𝒦
100
)
3
1000
200
7.01
8.253
14.85
2.512In order to confirm the local behaviors of the sequence generated by Algorithm13, we list the value of ∥HFB(v^(j))∥ at each outer iteration k in Table 2. In addition, to investigate how the parameter r affects the rate of convergence, we performed the algorithm with r=1,1.5,2. We also investigate the relation between the choices of r and the behavior of {tk}; we list the behaviors of {tk}. We chose one of the above test problems in the case 𝒦=𝒦500×𝒦200×(𝒦100)3. We note that 2.66e-09 means 2.66×10-9, for example. We see from Table 2 that the sequence generated by Algorithm 13 seems to converge Q-quadratically and the parameter r does not affect the convergence of the sequence. On the other hand, we find that the choices of r affect the behavior of {tk}.Table 2
Numerical behaviors of∥HFB(v^(j))∥.
r
=
1
r
=
1.5
r
=
2
k
j
t
k
∥
H
FB
(
v
^
(
j
)
)
∥
k
j
t
k
∥
H
FB
(
v
^
(
j
)
)
∥
k
j
t
k
∥
H
FB
(
v
^
(
j
)
)
∥
1
0
1.00e + 00
1.62e + 06
1
0
1.00e + 00
1.62e + 06
1
0
1.00e + 00
1.62e + 06
1
1
1.00e + 00
4.35e + 03
1
1
1.00e + 00
3.80e + 03
1
1
1.00e + 00
3.77e + 03
1
2
1.00e + 00
8.03e + 02
1
2
1.00e + 00
7.38e + 02
1
2
1.00e + 00
7.32e + 02
1
3
1.00e + 00
1.37e + 02
1
3
1.00e + 00
1.27e + 02
1
3
1.00e + 00
1.27e + 02
1
4
1.00e + 00
1.38e + 01
1
4
1.00e + 00
1.30e + 01
1
4
1.00e + 00
1.30e + 01
1
5
1.00e + 00
1.38e + 01
1
5
1.00e + 00
1.30e + 01
1
5
1.00e + 00
1.30e + 01
2
1
1.00e − 01
2.85e − 01
2
1
1.00e − 01
2.54e − 01
2
1
6.57e − 02
2.56e − 01
3
1
1.17e − 04
1.17e − 04
3
1
8.80e − 07
9.19e − 05
3
1
9.71e − 09
9.86e − 05
4
1
2.66e − 09
2.66e − 09
4
1
1.20e − 13
2.43e − 09
4
1
5.39e − 18
2.32e − 09The next experiment is an application of Algorithm13 to the robust Nash equilibrium problem in the game theory. The robust Nash equilibrium [2, 3, 28, 29] is a new solution concept for noncooperative games with uncertain information. In this model, it is assumed that each player’s cost (pay-off) function and/or the opponents’ strategies are uncertain, but they belong to some uncertainty sets and each player chooses his strategy by taking the worst possible case into consideration. In other words, each player makes decision according to the robust optimization policy. In this experiment, we focus on the following 2-person robust Nash game with quadratic cost functions:
(111)Player1:minimizex1maxδx2∈D2{12(x1)⊤A11x1+(x1)⊤A12(x2+δx2)}subjecttox1≥0,e^⊤x1=1;(112)Player2:minimizex2maxδx1∈D1{12(x2)⊤A22x2+(x2)⊤A21(x1+δx1)}subjecttox2≥0,e^⊤x2=1,
where Aij∈Rmi×mj for (i,j)∈{1,2}×{1,2} are given matrices, e^ is the vector of ones of appropriate dimension, and x1∈Rm1 and x2∈Rm2 denote the mixed strategies for Players 1 and 2, respectively. Moreover, δx1 and δx2 mean the estimation error or noise, and each player knows that they belong to the uncertainty sets D1 and D2, respectively. Under this situation, the tuple (x1,x2) is called a robust Nash equilibrium when x1 and x2 solve (111) and (112) simultaneously. In this experiment, we set
(113)A11:=[30-12-3-513151923],A12:=[-113-10-8-15-23-1-6],A21:=[3-111006-166],A22:=[319612464829],D1:={δx1∣∥δx1∥≤ρ1,e^⊤δx1=0},D2:={δx2∣∥δx2∥≤ρ2,e^⊤δx2=0}
and change the values of ρ1 and ρ2 variously. Since D1 and D2 are defined by means of Euclidean norm, the robust Nash equilibrium problem can be reformulated as an SOCCP equivalently (the reformulated SOCCP is explicitly written in Section  5.1.1 of [3]. We thus omit the details here). Here, we emphasize that the reformulated SOCCP cannot be expressed as any SOCP, and hence existing software such as SDPT3 cannot be applied. Moreover, if the reformulated SOCCP is rewritten of the form (1), then it satisfies neither (4) nor (6). The obtained results are summarized in Table 3, in which x1 and x2 denote the obtained robust Nash equilibria for various choices of uncertainty radiuses ρ1 and ρ2. For all problems, we could calculate the robust Nash equilibria correctly. Moreover, as is discussed in the existing papers, we can observe that the robust Nash equilibria move smoothly as the values of ρ1 and ρ2 change gradually.Table 3
Robust Nash equilibria with various choices of uncertainty radiuses.
Iter
CPU
ρ
1
ρ
2
x
1
x
2
8
0.078
0.2
0.2
(
0.3916
,
0.6083
,
0
)
(
0.3247
,
0.3625
,
0.3128
)
8
0.094
0.4
0.4
(
0.4168
,
0.5832
,
0
)
(
0.3354
,
0.3152
,
0.3495
)
7
0.078
0.6
0.6
(
0.4292
,
0.5708
,
0
)
(
0.3477
,
0.2821
,
0.3702
)
7
0.078
0.8
0.8
(
0.4017
,
0.5065
,
0.0918
)
(
0.3686
,
0.2503
,
0.3812
)
9
0.078
1.0
1.0
(
0.3627
,
0.4589
,
0.1784
)
(
0.3891
,
0.2258
,
0.3851
)


## 6. Conclusion

In this paper, we have proposed a smoothing Newton method with appropriate parameter control based on the Fischer-Burmeister function for solving the SOCCP. We have shown its global andQ-quadratic convergence properties under some assumptions. In addition, we have considered some sufficient conditions for the assumptions. In numerical experiments, we have confirmed the effectiveness of the proposed methods.



---

*Source: 830698-2013-07-01.xml*