# Nonsingularity Conditions for FB System of Reformulating Nonlinear Second-Order Cone Programming

Authors: Shaohua Pan; Shujun Bi; Jein-Shan Chen
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

This paper is a counterpart of Bi et al., 2011. For a locally optimal solution to the nonlinear second-order cone programming (SOCP), specifically, under Robinson’s constraint qualification, we establish the equivalence among the following three conditions: the nonsingularity of Clarke’s Jacobian of Fischer-Burmeister (FB) nonsmooth system for the Karush-Kuhn-Tucker conditions, the strong second-order sufficient condition and constraint nondegeneracy, and the strong regularity of the Karush-Kuhn-Tucker point.


---

## Body

## 1. Introduction

The nonlinear second-order cone programming (SOCP) problem can be stated as(1)minζ∈ℝnf(ζ)as.t.h(ζ)=0,minζ∈ℝng(ζ)∈𝒦,
where f:ℝn→ℝ, h:ℝn→ℝm, and g:ℝn→ℝn are given twice continuously differentiable functions, and 𝒦 is the Cartesian product of some second-order cones, that is,
(2)𝒦:=𝒦n1×𝒦n2×⋯×𝒦nr,
with n1+⋯+nr=n and 𝒦nj being the second-order cone (SOC) in ℝnj defined by
(3)𝒦nj:={(xj1,xj2)∈ℝ×ℝnj-1∣xj1≥∥xj2∥}.
By introducing a slack variable to the second constraint, the SOCP (1) is equivalent to
(4)minζ,x∈ℝnf(ζ)aas.t.h(ζ)=0,minζ,x∈ℝng(ζ)-x=0,x∈𝒦.
In this paper, we will concentrate on this equivalent formulation of problem (1).LetL:ℝn×ℝn×ℝm×ℝn×𝒦→ℝ be the Lagrangian function of problem (4)
(5)L(ζ,x,μ,s,y):=f(ζ)+〈μ,h(ζ)〉+〈g(ζ)-x,s〉-〈x,y〉,
and denote by 𝒩𝒦(x) the normal cone of 𝒦 at x in the sense of convex analysis [1]:
(6)𝒩𝒦(x)={{d∈ℝn:〈d,z-x〉≤0∀z∈𝒦},ifx∈𝒦,∅,ifx∉𝒦.
Then the Karush-Kuhn-Tucker (KKT) conditions for (4) take the following form:
(7)𝒥ζ,xL(ζ,x,μ,s,y)=0,h(ζ)=0,g(ζ)-x=0,-y∈𝒩𝒦(x),
where 𝒥ζ,xL(ζ,x,μ,s,y) is the derivative of L at (ζ,x,μ,s,y) with respect to (ζ,x). Recall that ϕsoc is an SOC complementarity function associated with the cone 𝒦 if
(8)ϕsoc(x,y)=0⟺x∈𝒦,y∈𝒦,〈x,y〉=0⟺-y∈𝒩𝒦(x).
With an SOC complementarity function ϕsoc associated with 𝒦, we may reformulate the KKT optimality conditions in (7) as the following nonsmooth system:
(9)E(ζ,x,μ,s,y):=[𝒥ζ,xL(ζ,x,μ,s,y)h(ζ)g(ζ)-xϕsoc(x,y)]=0.The most popular SOC complementarity functions include the vector-valued natural residual (NR) function and Fischer-Burmeister (FB) function, respectively, defined as(10)ϕNR(x,y):=x-Π𝒦(x-y),∀x,y∈ℝn,ϕFB(x,y):=(x+y)-x2+y2,∀x,y∈ℝn,
where Π𝒦(·) is the projection operator onto the closed convex cone 𝒦, x2=x∘x means the Jordan product of x and itself, and x denotes the unique square root of x∈𝒦. It turns out that the FB SOC complementarity function ϕFB enjoys almost all favorable properties of the NR SOC complementarity function ϕNR (see [2]). Also, the squared norm of ϕFB induces a continuously differentiable merit function with globally Lipschitz continuous derivative [3, 4]. This greatly facilitates the globalization of the semismooth Newton method [5, 6] for solving the FB nonsmooth system of KKT conditions:
(11)EFB(ζ,x,μ,s,y):=[𝒥ζ,xL(ζ,x,μ,s,y)h(ζ)g(ζ)-xϕFB(x,y)]=0.Recently, with the help of [7, Theorem 30] and [8, Lemma 11], Wang and Zhang [9] gave a characterization for the strong regularity of the KKT point of the SOCP (1) via the nonsingularity study of Clarke's Jacobian of the NR nonsmooth system
(12)ENR(ζ,x,μ,s,y):=[𝒥ζ,xL(ζ,x,μ,s,y)h(ζ)g(ζ)-xϕNR(x,y)]=0.
They showed that the strong regularity of the KKT point, the nonsingularity of Clarke's Jacobian of ENR at the KKT point, and the strong second-order sufficient condition and constraint nondegeneracy [7] are all equivalent. These nonsingularity conditions are better structured than those of [10] for the nonsingularity of the B-subdifferential of the NR system. Then, it is natural to ask the following: is it possible to obtain a characterization for the strong regularity of the KKT point by studying the nonsingularity of Clarke's Jacobian of EFB. Note that up till now one even does not know whether the B-subdifferential of the FB system is nonsingular or not without the strict complementarity assumption.In this work, for a locally optimal solution to the nonlinear SOCP (4), under Robinson's constraint qualification, we show that the strong second-order sufficient condition and constraint nondegeneracy introduced in [7], the nonsingularity of Clarke's Jacobian of EFB at the KKT point, and the strong regularity of the KKT point are equivalent to each other. This, on the one hand, gives a new characterization for the strong regularity of the KKT point and, on the other hand, provides a mild condition to guarantee the quadratic convergence rate of the semismooth Newton method [5, 6] for the FB system. Note that parallel results are obtained recently for the FB system of the nonlinear semidefinite programming (see [11]); however, we do not duplicate them. As will be seen in Sections 3 and 4, the analysis techniques here are totally different from those in [11]. It seems hard to put them together in a unified framework under the Euclidean Jordan algebra. The main reason causing this is due to completely different analysis when dealing with the Clarke Jacobians associated with FB SOC complementarity function and FB semidefinite cone complementarity function.Throughout this paper,I denotes an identity matrix of appropriate dimension, ℝn  (n>1) denotes the space of n-dimensional real column vectors, and ℝn1×⋯×ℝnr is identified with ℝn1+⋯+nr. Thus, (x1,…,xr)∈ℝn1×⋯×ℝnr is viewed as a column vector in ℝn1+⋯+nr. The notations int𝒦n, bd𝒦n, and bd+𝒦n denote the interior, the boundary, and the boundary excluding the origin of 𝒦n, respectively. For any x∈ℝn, we write x≽𝒦n0 (resp., x≻𝒦n0) if x∈𝒦n (resp., x∈int𝒦n). For any given real symmetric matrix A, we write A≽0 (resp., A≻0) if A is positive semidefinite (resp., positive definite). In addition, 𝒥ωf(ω) and 𝒥ωω2f(ω) denote the derivative and the second-order derivative, respectively, of a twice differentiable function f with respect to the variable ω.


## 2. Preliminary Results

First we recall from [12] the definition of Jordan product and spectral factorization.Definition 1.
The Jordan product ofx=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1 is given by
(13)x∘y:=(〈x,y〉,x1y2+y1x2).Unlike scalar or matrix multiplication, the Jordan product is not associative in general. The identity element under this product ise:=(1,0,…,0)T∈ℝn, that is, e∘x=x for all x∈ℝn. For each x=(x1,x2)∈ℝ×ℝn-1, we define the associated arrow matrix by
(14)Lx:=[x1x2Tx2x1I].
Then it is easy to verify that Lxy=x∘y for any x,y∈ℝn. Recall that each x=(x1,x2)∈ℝ×ℝn-1 admits a spectral factorization, associated with 𝒦n, of the form
(15)x=λ1(x)ux(1)+λ2(x)ux(2),
where λ1(x),λ2(x)∈ℝ and ux(1),ux(2)∈ℝn are the spectral values and the associated spectral vectors of x, respectively, with respect to the Jordan product, defined by
(16)λi(x):=x1+(-1)i∥x2∥,ux(i):=12(1(-1)ix~2),fori=1,2,
with x~2=x2/∥x2∥ if x2≠0 and otherwise being any vector in ℝn-1 satisfying ∥x~2∥=1.Definition 2.
The determinant of a vectorx∈ℝn is defined as det(x):=λ1(x)λ2(x), and a vector x is said to be invertible if its determinant det(x) is nonzero.By the formula of spectral factorization, it is easy to compute that the projection ofx∈ℝn onto the closed convex cone 𝒦n, denoted by Π𝒦n(x), has the expression
(17)Π𝒦n(x)=max(0,λ1(x))ux(1)+max(0,λ2(x))ux(2).
Define |x|:=2Π𝒦n(x)-x. Then, using the expression of Π𝒦n(x), it follows that
(18)|x|=|λ1(x)|ux(1)+|λ2(x)|ux(2).The spectral factorization of the vectorsx, x2, x and the matrix Lx have various interesting properties (see [13]). We list several properties that we will use later.Property 3.
For anyx=(x1,x2)∈ℝ×ℝn-1 with spectral factorization (15), we have the following.(a)
x2=λ12(x)ux(1)+λ22(x)ux(2)∈𝒦n.(b)
Ifx∈𝒦n, then 0≤λ1(x)≤λ2(x) and x=λ1(x)ux(1)+λ2(x)ux(2).(c)
Ifx∈int𝒦n, then 0<λ1(x)≤λ2(x) and Lx is invertible with
(19)Lx-1=1det(x)[x1-x2T-x2det(x)x1I+x2x2Tx1].(d)
Lx≽0 (resp., Lx≻0) if and only if x∈𝒦n (resp., x∈int𝒦n).The following lemma states a result for the arrow matrices associated withx,y∈ℝn and z≽𝒦nx2+y2, which will be used in the next section to characterize an important property for the elements of Clarke's Jacobian of ϕFB at a general point.Lemma 4.
For any givenx,y∈ℝn and z≻𝒦n0, if z2≽𝒦nx2+y2, then
(20)∥[Lz-1LxLz-1Ly]∥2≤1,
where ∥A∥2 means the spectral norm of a real matrix A. Consequently, it holds that
(21)∥Lz-1LxΔu+Lz-1LyΔv∥≤∥Δu∥2+∥Δv∥2,∀Δu,Δv∈ℝn.Proof.
LetA=[Lz-1LxLz-1Ly]. From [13, Proposition 3.4], it follows that
(22)AAT=Lz-1(Lx2+Ly2)Lz-1⪯Lz-1Lz2Lz-1=I.
This shows that ∥A∥2≤1, and the first part follows. Note that, for any ξ∈ℝ2n,
(23)∥Aξ∥2=ξTATAξ≤λmax(ATA)∥ξ∥2≤∥ξ∥2.
By letting ξ=(Δu,Δv)∈ℝn×ℝn, we immediately obtain the second part.The following two lemmas state the properties ofx,y with x2+y2∈bd𝒦n which are often used in the subsequent sections. The proof of Lemma 5 is given in [3, Lemma 2].Lemma 5.
For anyx=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1 with x2+y2∈bd𝒦n, one has
(24)x12=∥x2∥2,y12=∥y2∥2,x1y1=x2Ty2,x1y2=y1x2.Lemma 6.
For anyx=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1, let w=(w1,w2):=x2+y2.  (a)
Ifw∈bd𝒦n, then for any g=(g1,g2),h=(h1,h2)∈ℝ×ℝn-1, it holds that
(25)(x1x2+y1y2)T(x1g2+g1x2+y1h2+h1y2)=(x12+y12)(xTg+yTh).(b)
Ifw∈bd+𝒦n, then the following four equalities hold
(26)x1w2∥w2∥=x2,x2Tw2∥w2∥=x1,y1w2∥w2∥=y2,y2Tw2∥w2∥=y1;
and consequently the expression of ϕFB(x,y) can be simplified as
(27)ϕFB(x,y)=(x1+y1-x12+y12x2+y2-x1x2+y1y2x12+y12).Proof.
(a) The result is direct by the equalities of Lemma5 since x2+y2∈bd𝒦n.
(b) Sincew∈bd+𝒦n, we must have w2=2(x1x2+y1y2)≠0. Using Lemma 5, w2=2(x1x2+y1y2) and ∥w2∥=w1=2(x12+y12), we easily obtain the first part. Note that ϕFB(x,y)=(x+y)-w. Using Property 3(b) and Lemma 5 yields (27).Whenx,y∈bd𝒦n satisfies the complementary condition, we have the following result.Lemma 7.
For any givenx=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1, if x,y∈bd𝒦n and 〈x,y〉=0, then there exists a constant α>0 such that x1=αy1 and x2=-αy2.Proof.
Sincex,y∈bd𝒦n, we have that x1=∥x2∥ and y1=∥y2∥, and consequently,
(28)0=〈x,y〉=x1y1+x2Ty2=∥x2∥∥y2∥+x2Ty2.
This means that there exists α>0 such that x2=-αy2, and then x1=αy1.Next we recall from [14] the strong regularity for a solution of generalized equation
(29)0∈ϕ(z)+𝒩D(z),
where ϕ is a continuously differentiable mapping from a finite dimensional real vector space ℤ to itself, D is a closed convex set in ℤ, and 𝒩D(z) is the normal cone of D at z. As will be shown in Section 4, the KKT condition (7) can be written in the form of (29).Definition 8.
We say thatz- is a strongly regular solution of the generalized equation (29) if there exist neighborhood ℬ of the origin 0∈ℤ and 𝒱 of z- such that for every δ∈ℬ, the linearized generalized equation δ∈ϕ(z-)+𝒥zϕ(z-)(z-z-)+𝒩D(z) has a unique solution in 𝒱, denoted by z𝒱(δ), and the mapping z𝒱:ℬ→𝒱 is Lipschitz continuous.To close this section, we recall from [15] Clarke's (generalized) Jacobian of a locally Lipschitz mapping. Let S⊂ℝn be an open set and Ξ:S→ℝn a locally Lipschitz continuous function on S. By Rademacher's theorem, Ξ is almost everywhere F(réchet)-differentiable in S. We denote by SΞ the set of points in S where Ξ is F-differentiable. Then Clarke's Jacobian of Ξ at y is defined by ∂Ξ(y):=conv{∂BΞ(y)}, where “conv” means the convex hull, and B-subdifferential ∂BΞ(y), a name coined in [16], has the form
(30)∂BΞ(y):={V:V=limk→∞𝒥yΞ(yk),yk→y,yk∈SΞ}.
For the concept of (strong) semismoothness, please refer to the literature [5, 6].Unless otherwise stated, in the rest of this paper, for anyx∈ℝn  (n>1), we write x=(x1,x2), where x1 is the first component of x and x2 is a column vector consisting of the remaining n-1 entries of x. For any x=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1, let
(31)w=w(x,y)≔x2+y2,w~2≔w2∥w2∥,ifw2≠0,z=z(x,y)=w(x,y).


## 3. Directional Derivative andB-Subdifferential

The functionϕFB is directionally differentiable everywhere by [2, Corollary 3.3]. But, to the best of our knowledge, the expression of its directional derivative is not given in the literature. In this section, we derive its expression and then prove that the B-subdifferential of ϕFB at a general point coincides with that of its directional derivative function at the origin. Throughout this section, we assume that 𝒦=𝒦n.Proposition 9.
For any givenx=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1, the directional derivative ϕFB′((x,y);(g,h)) of ϕFB at (x,y) with the direction (g,h) has the following form.  (a)
If(x,y)=(0,0), then ϕFB′((x,y);(g,h))=ϕFB(g,h).(b)
Ifx2+y2∈int𝒦n, then ϕFB′((x,y);(g,h))=(I-Lz-1Lx)g+(I-Lz-1Ly)h.(c)
Ifx2+y2∈bd+𝒦n, then
(32)ϕFB′((x,y);(g,h))=(g+h)-φ(g,h)2(1-w~2)+x2Tg2+y2Th22x12+y12(0w~2)-12x12+y12(xTg+yTh2x1g2+g1x2+2y1h2+h1y2),
where g=(g1,g2),h=(h1,h2)∈ℝ×ℝn-1, and φ:ℝn×ℝn→ℝ is defined by
(33)φ(g,h):=(x1g1-x2Tg2+y1h1-y2Th2)2+∥x1h2-h1x2+g1y2-y1g2∥2x12+y12.Proof.
Part (a) is immediate by noting thatϕFB is a positively homogeneous function. Part (b) is due to [13, Proposition 5.2]. We next prove part (c) by two subcases as shown in the following. In the rest of proof, we let λ1,λ2 with λ1≤λ2 denote the spectral values of w. Since w=x2+y2∈bd+𝒦n, we have w2≠0, and from Lemma 6(b) it follows that
(34)w1=∥w2∥=2∥x1x2+y1y2∥=2∥x12w~2+y12w~2∥=2(x12+y12),λ1=w1-∥w2∥=0,λ2=w1+∥w2∥=4(x12+y12).
(c.1):(x+tg)2+(y+th)2∈bd+𝒦n for sufficiently small t>0. In this case, from Lemma 6(b), we know that ϕFB(x+tg,y+th) has the following expression:
(35)((x1+y1)+t(g1+h1)-(x1+tg1)2+(y1+th1)2(x2+y2)+t(g2+h2){(x1+tg1)2+(y1+th1)2}-(x1+tg1)(x2+tg2)+(y1+th1)(y2+th2)(x1+tg1)2+(y1+th1)2).
Let [ϕFB(x,y)]1 be the first element of ϕFB(x,y) and [ϕFB(x,y)]2 the vector consisting of the rest n-1 components of ϕFB(x,y). By the above expression of ϕFB(x+tg,y+th),
(36)limt↓0[ϕFB(x+tg,y+th)]1-[ϕFB(x,y)]1t=(g1+h1)-limt↓0(x1+tg1)2+(y1+th1)2-x12+y12t=(g1+h1)-x1g1+y1h1x12+y12,limt↓0[ϕFB(x+tg,y+th)]2-[ϕFB(x,y)]2t=(g2+h2)-limt↓0[(x1+tg1)(x2+tg2)+(y1+th1)(y2+th2)t(x1+tg1)2+(y1+th1)2aaaaaaaaaaaa-x1x2+y1y2tx12+y12]=(g2+h2)-g1x2+x1g2+y1h2+h1y2x12+y12-limt↓0[x1x2+y1y2t(x1+tg1)2+(y1+th1)2-x1x2+y1y2tx12+y12]=(g2+h2)-g1x2+x1g2+y1h2+h1y2x12+y12+(x1x2+y1y2)(x1g1+y1h1)(x12+y12)x12+y12=(g2+h2)-x1g2+y1h2x12+y12,
where the last equality is using x1y2=y1x2 by Lemma 5. The above two limits imply
(37)ϕFB′((x,y);(g,h))=(g+h)-x1x12+y12g-y1x12+y12h.
(c.2):(x+tg)2+(y+th)2∈int𝒦n for sufficiently small t>0. Let u=(u1,u2):=(x+tg)2+(y+th)2 with the spectral values μ1,μ2. An elementary calculation gives
(38)u1=∥x+tg∥2+∥y+th∥2=w1+2t(xTg+yTh)+t2(∥g∥2+∥h∥2),(39)u2=2(x1+tg1)(x2+tg2)+2(y1+th1)(y2+th2)=w2+2t(x1g2+g1x2+y1h2+h1y2)+2t2(g1g2+h1h2).
Also, since w2≠0, applying the Taylor formula of ∥·∥ at w2 and Lemma 6(a) yields
(40)∥u2∥=∥w2∥+w2T(u2-w2)∥w2∥+o(t)=∥w2∥+2t(xTg+yTh)+o(t).
Now using the definition of ϕFB and noting that λ1=0 and w2≠0, we have that
(41)ϕFB(x+tg,y+th)-ϕFB(x,y)=(x+tg+y+th)-u-(x+y)+w=t(g+h)-(μ1+μ2-λ22μ2-μ12u2∥u2∥-λ22w2∥w2∥),
which in turn implies that
(42)ϕFB′((x,y);(g,h))=(g+h)-(limt↓0μ1+μ2-λ22tlimt↓0(μ2-μ12tu2∥u2∥-λ22tw2∥w2∥)).
We first calculate limt↓0((μ2-λ2)/t). Using (38) and (40), it is easy to see that
(43)μ2-λ2=(u1-w1)+(∥u2∥-∥w2∥)=4t(xTg+yTh)+o(t),
and consequently,
(44)limt↓0μ2-λ2t=limt↓0μ2-λ2t·1μ2+λ2=xTg+yTh2λ2=xTg+yThx12+y12.
We next calculate limt↓0(μ1/t). Since w1-∥w2∥=0, using (38)-(39) and Lemma 6(a),
(45)μ1=(u1-w1)-(∥u2∥-∥w2∥)=(u1-w1)-∥u2∥2-∥w2∥2∥u2∥+∥w2∥=2t(xTg+yTh)-4tw2T(x1g2+g1x2+y1h2+h1y2)∥u2∥+∥w2∥+t2(∥g∥2+∥h∥2)-4t2∥g1x2+x1g2+y1h2+h1y2∥2∥u2∥+∥w2∥-4t2w2T(g1g2+h1h2)∥u2∥+∥w2∥+o(t2)=2t(xTg+yTh)-8t(x12+y12)(xTg+yTh)∥u2∥+∥w2∥+t2(∥g∥2+∥h∥2)+o(t2)-4t2∥g1x2+x1g2+y1h2+h1y2∥2∥u2∥+∥w2∥-8t2(x1x2+y1y2)T(g1g2+h1h2)∥u2∥+∥w2∥.
Using ∥w2∥=2(x12+y12) and (40), we simplify the sum of the first two terms in (45) as
(46)2t(xTg+yTh)-4t∥w2∥(xTg+yTh)∥u2∥+∥w2∥=2t(xTg+yTh)∥u2∥-∥w2∥∥u2∥+∥w2∥=4t2(xTg+yTh)2∥u2∥+∥w2∥+o(t2).
Then, from (45) and ∥w2∥=2(x12+y12), we obtain that
(47)limt↓0μ1t2=(x12+y12)(∥g∥2+∥h∥2)-∥g1x2+x1g2+y1h2+h1y2∥2x12+y12+(xTg+yTh)2-2(x1x2+y1y2)T(g1g2+h1h2)x12+y12.
We next make simplification for the numerator of the right hand side of (47). Note that
(48)(x12+y12)(∥g∥2+∥h∥2)-∥g1x2+x1g2+y1h2+h1y2∥2=(x12+y12)(∥g∥2+∥h∥2)-∥g1x2+x1g2∥2-∥y1h2+h1y2∥2-2(g1x2+x1g2)T(y1h2+h1y2)=x12∥h∥2+y12∥g∥2-2x1g1x2Tg2-2y1h1y2Th2-2(g1x2+x1g2)T(y1h2+h1y2),(xTg+yTh)2-2(x1x2+y1y2)T(g1g2+h1h2)=(x1g1+x2Tg2)2+(y1h1+y2Th2)2+2xTgyTh-2(x1x2+y1y2)T(g1g2+h1h2)=(x1g1)2+(x2Tg2)2+(y1h1)2+(y2Th2)2+2xTgyTh-2x1h1x2Th2-2g1y1g2Ty2.
Therefore, adding the last two equalities and using Lemma 5 yield that
(49)(x12+y12)(∥g∥2+∥h∥2)-∥g1x2+x1g2+y1h2+h1y2∥2+(xTg+yTh)2-2(x1x2+y1y2)T(g1g2+h1h2)=(x12∥h∥2-2x1h1x2Th2)+(y12∥g∥2-2g1y1g2Ty2)+((x1g1)2+(x2Tg2)2-2x1g1x2Tg2)+((y1h1)2+(y2Th2)2-2y1h1y2Th2)+2xTgyTh-2(g1x2+x1g2)T(y1h2+h1y2)=∥x1h2-h1x2∥2+∥g1y2-y1g2∥2+(x1g1-x2Tg2)2+(y1h1-y2Th2)2+2(g1x1+g2Tx2)(y1h1+y2Th2)-2(g1x2+x1g2)T(y1h2+h1y2)=∥x1h2-h1x2∥2+∥g1y2-y1g2∥2+(x1g1-x2Tg2)2+(y1h1-y2Th2)2+2(x1h2-h1x2)T(g1y2-g2y1)+2(x1g1-x2Tg2)(y1h1-y2Th2)=∥x1h2-h1x2+g1y2-y1g2∥2+(x1g1-x2Tg2+y1h1-y2Th2)2.
Combining this equality with (47) and using the definition of φ in (33), we readily get
(50)limt↓0μ1t=φ(g,h).
We next calculate limt↓0[((μ2-μ1)/2t)(u2/∥u2∥)-((λ2/2t)(w2/∥w2∥))]. To this end, we also need to take a look at ∥w2∥u2-∥u2∥w2. From (38)-(39) and (40), it follows that
(51)∥w2∥u2-∥u2∥w2=2t∥w2∥[(xTg+yTh)w~2(x1g2+g1x2+y1h2+h1y2)aaaaaaaaaaaaa-(xTg+yTh)w~2]+o(t).
Together with (44) and (50), we have that
(52)limt↓0[μ2-μ12tu2∥u2∥-λ22tw2∥w2∥]=-limt↓0μ12tu2∥u2∥+limt↓0[μ22tu2∥u2∥-λ22tw2∥w2∥]=-limt↓0μ12tu2∥u2∥+limt↓0μ2-λ22tu2∥u2∥+limt↓0λ2(∥w2∥u2-∥u2∥w2)2t∥u2∥∥w2∥=-φ(g,h)2w~2+x1g2+g1x2+y1h2+h1y2x12+y12-xTg+yTh2x12+y12w~2=-φ(g,h)2w~2+2x1g2+g1x2+2y1h2+h1y22x12+y12-x2Tg2+y2Th22x12+y12w~2,
where the last equality is using x1w~2=x2 and y1w~2=y2. Combining with (42), (44), and (50), a suitable rearrangement shows that ϕFB′((x,y);(g,h)) has the expression (32).
Finally, we show that, when(x+tg)2+(y+th)2∈bd+𝒦n for sufficiently small t>0, the formula in (32) reduces to the one in (37). Indeed, an elementary calculation yields
(53)λ1((x+tg)2+(y+th)2)=[∥x+tg∥2+∥y+th∥2]2-4∥(x1+tg1)(x2+tg2)+(y1+th1)(y2+th2)∥2=4t2φ(g,h)x12+y12+4t3(xTg+yTh)(∥g∥2+∥h∥2)-8t2(x1g2+g1x2+y1h2+h1y2)T(g1g2+h1h2)+t4[(∥g∥2+∥h∥2)2-2∥g1g2+h1h2∥2]=4t2φ(g,h)x12+y12+o(t2).
This implies that if (x+tg)2+(y+th)2∈bd+𝒦n for sufficiently small t>0, that is, λ1((x+tg)2+(y+th)2)=0 for sufficiently small t>0, then φ(g,h)=0, and hence x1g1+y1h1-(x2Tg2+y2Th2)=0. Thus, ϕFB′((x,y);(g,h)) in (32) can be simplified as
(54)(g+h)+x1g1+y1h12x12+y12(0w~2)-12x12+y12×(2x1g1+2y1h12x1g2+g1x2+2y1h2+h1y2)=(g+h)-x1x12+y12g-y1x12+y12h,
where the equality is using g1x2=g1x1w~2,h1y2=h1y1w~2. The proof is complete.As a consequence of Proposition9, we have the following sufficient and necessary characterizations for the (continuously) differentiable points of ϕFB and ϑ(x):=|x|.Corollary 10.
(
a
) The function ϕFB is (continuously) differentiable at (x,y)∈ℝn×ℝn if and only if z(x,y)∈int𝒦n, where z(x,y) is defined in (31). Also, when z(x,y)∈int𝒦n, one has
(55)𝒥ϕFB(x,y)=[I-Lz(x,y)-1LxI-Lz(x,y)-1Ly].
(
b
) The function ϑ(x):=|x| is (continuously) differentiable at x∈ℝn if and only if x is invertible. Also, when x is invertible, 𝒥ϑ(x)=L|x|-1Lx.Proof.
(a) The “if” part is direct by [13, Proposition 5.2]. We next prove the “only if” part. If ϕFB is differentiable at (x,y), then ϕFB′((x,y);(g,h)) is a linear function of (g,h), which by Proposition 9 holds only if z(x,y)∈int𝒦n. The formula of 𝒥ϕFB(x,y) is given in [13].
(b) Sinceϑ(x)=x2, by part (a) ϑ is (continuously) differentiable at x∈ℝn if and only if |x|∈int𝒦n, which is equivalent to requiring that x is invertible since |x|∈𝒦n always holds. When x is invertible, the formula of 𝒥ϑ(x) follows from part (a).For any givenx=(x1,x2),y=(y1,y2)∈ℝ×ℝn-1 with x2+y2∈bd+𝒦n, define
(56)θ1(g,h):=x1g1-x2Tg2+y1h1-y2Th2,θ2(g,h):=x1h2-h1x2+g1y2-y1g2
for any g=(g1,g2),h=(h1,h2)∈ℝ×ℝn-1, and let θ(g,h):=(θ1(g,h),θ2(g,h)). Then, comparing with (33), we can rewrite the function φ as
(57)φ(g,h)=∥θ(g,h)∥x12+y12,∀g,h∈ℝn.
Note that the Euclidean norm ∥·∥ is globally Lipschitz continuous and strongly semismooth everywhere in ℝn, and θ(·,·) is a linear function. Then, (57) implies that φ is globally Lipschitz continuous and strongly semismooth everywhere in ℝn×ℝn by [17, Theorem 19]. Also, the function φ is differentiable at (g,h) if and only if φ(g,h)>0. The following lemma characterizes the B-subdifferential of the function φ at the origin.Lemma 11.
For any given(x,y) with x2+y2∈bd+𝒦n, let φ be defined by (33). Then, the B-subdifferential of the function φ at (0,0) takes the following form:
(58)∂Bφ(0,0)={[(ξ2Ty2+ξ1x1x12+y12,-y1ξ2T-ξ1x2Tx12+y12),aaa(-ξ2Tx2+ξ1y1x12+y12,x1ξ2T-ξ1y2Tx12+y12)]:aa(ξ1,ξ2)∈ℝ×ℝn-1satisfiesξ12+∥ξ2∥2=1(ξ2Ty2+ξ1x1x12+y12,-y1ξ2T-ξ1x2Tx12+y12)}.Proof.
Let(uT,vT)∈∂Bφ(0,0). By the definition of the elements in ∂Bφ(0,0), there exists a sequence {(gk,hk)} in ℝn×ℝn converging to (0,0) with φ(gk,hk)>0 such that
(59)(uT,vT)=limk→∞𝒥φ(gk,hk).
By (57), a simple computation shows that such (uT,vT) belongs to the set on the right hand side of (58). Thus, ∂Bφ(0,0) is included in the set on the right hand side of (58). In fact, ξ1 and ξ2 in (58) are the limit points of {θ1(gk,hk)/∥θ(gk,hk)∥} and {θ2(gk,hk)/∥θ(gk,hk)∥}, respectively.
Conversely, let(uT,vT) be an arbitrary element of the set on the right hand side of (58). Then, there exists a (ξ1,ξ2)∈ℝ×ℝn-1 with ξ12+∥ξ2∥2=1 such that
(60)u=(ξ2Ty2+ξ1x1x12+y12,-y1ξ2-ξ1x2x12+y12),v=(-ξ2Tx2+ξ1y1x12+y12,x1ξ2-ξ1y2x12+y12).
Take the sequence {(gk,hk)}⊂ℝn×ℝn with gk=(x1ξ1/k,-y1ξ2/k) and hk=(y1ξ1/k,x1ξ2/k). Clearly, (gk,hk)→(0,0) as k→∞. Also, by Lemma 5, it is easy to verify that
(61)θ1(gk,hk)=1k(x12+y12)ξ1,θ2(gk,hk)=1k(x12+y12)ξ2.
This shows that φ(gk,hk)>0 and 𝒥φ(gk,hk)=(uT,vT). Hence, (uT,vT)∈∂Bφ(0,0). Thus, the set on the right hand side of (58) is included in ∂Bφ(0,0).Now we may prove the equivalence between theB-subdifferential of ϕFB at a general point (x,y) and that of its directional derivative function ϕFB′((x,y);(·,·)) at (0,0). This result corresponds to that of [18, Lemma 14] established for the NR SOC function ϕNR.Lemma 12.
For any given(x,y)∈ℝn×ℝn, let ψFB(·,·)≡ϕFB′((x,y);(·,·)). Then,
(62)∂BϕFB(x,y)=∂BψFB(0,0).Proof.
The result is direct by Proposition9(a)-(b) and Lemma A.1 in the Appendix.Using Lemma12, we may present an upper estimation for Clarke's Jacobian of ϕFB at the point (x,y) with x2+y2∈bd+𝒦n, which will be used in the next section.Proposition 13.
For any givenx=(x1,x2),y=(y1,y2) with x2+y2∈bd+𝒦n, one has
(63)∂ϕFB(x,y)⊆{[I-X-12(1-w~2)uTI-Y-12(1-w~2)vT](1-w~2)|foru=(u1,u2),v=(v1,v2)satisfyingtheinequalities|u1|≤∥u2∥≤1,|v1|≤∥v2∥≤1,(u1-v1)≤∥u2-v2∥,(u1+v1)≤∥u2+v2∥,(u1-v1)2+∥u2+v2∥2≤2,(u1+v1)2+∥u2-v2∥2≤2,(1,w~2T)u=0,(1,w~2T)v=0,(1,-w~2T)u=2u1,(1,-w~2T)v=2v1[I-X-12(1-w~2)uTI-Y-12(1-w~2)vT]|},
where X and Y are n×n real symmetric matrices defined as follows:
(64)X=12w1(x1x2Tx22x1I-w~2x2T),Y=12w1(y1y2Ty22y1I-w~2y2T).Proof.
We first make simplifications for the last two terms in (32) by X,Y. Note that
(65)x2Tg2+y2Th22x12+y12(0w~2)-12x12+y12×(xTg+yTh2x1g2+g1x2+2y1h2+h1y2)=12x12+y12(0w~2)(0x2T)g+12x12+y12(0w~2)(0y2T)h-12x12+y12(x1x2Tx22x1I)g-12x12+y12(y1y2Ty22y1I)h=-Xg-Yh,
where the last equality is using w1=2(x12+y12). Therefore, from (32), we have
(66)ϕFB′((x,y);(g,h))=(g+h)-φ(g,h)2(1-w~2)-Xg-Yh,∀g,h∈ℝn.
Now, applying Lemma 12, we immediately obtain that
(67)∂ϕFB(x,y)={[I-X-12(1-w~2)uTI-Y-12(1-w~2)vT](1-w~2)|aaaaforu=(u1,u2),v=(v1,v2)aaaawith(uT,vT)∈∂φ(0,0)[I-X-12(1-w~2)uTI-Y-12(1-w~2)vT]|},
where, by Lemma 11 and the definition of Clarke's Jacobian,
(68)∂φ(0,0)={[(ξ2Ty2+ξ1x1x12+y12,-y1ξ2T-ξ1x2Tx12+y12),aaa(-ξ2Tx2+ξ1y1x12+y12,x1ξ2T-ξ1y2Tx12+y12)]:(ξ1,ξ2)∈ℝ×ℝn-1satisfiesξ12+∥ξ2∥2≤1(ξ2Ty2+ξ1x1x12+y12,-y1ξ2T-ξ1x2Tx12+y12)}.
Let(uT,vT)∈∂φ(0,0) with u=(u1,u2),v=(v1,v2)∈ℝ×ℝn-1. Then, it suffices to prove that such u and v satisfy all inequalities and equalities in (63). By (68), there exists a vector (ξ1,ξ2)∈ℝ×ℝn-1 with ξ12+∥ξ2∥2≤1 such that
(69)u1=ξ2Ty2+ξ1x1x12+y12,u2=-y1ξ2-ξ1x2x12+y12,v1=-ξ2Tx2+ξ1y1x12+y12,v2=x1ξ2-ξ1y2x12+y12.
Using Lemma 5, it is immediate to obtain that
(70)|ξ2Ty2+ξ1x1|2=(ξ2Ty2)2+(ξ1x1)2+2ξ1x1ξ2Ty2≤∥ξ2∥2y12+ξ12x12+2ξ1y1ξ2Tx2=∥-y1ξ2-ξ1x2∥2≤∥ξ2∥2y12+ξ12x12+∥ξ2∥2x12+ξ12∥y2∥2=(∥ξ2∥2+ξ12)(x12+y12)≤x12+y12.
This means that |u1|≤∥u2∥≤1. Similarly, we also have |v1|≤∥v2∥≤1. We next prove that (u1-v1)2-∥u2-v2∥2≤0. By Lemma 5, it is easy to verify that
(71)(x2-y2)(x1+y1)=(x2+y2)(x1-y1),(x1-y1)2=∥x2-y2∥2.
Using the two equalities, it is not hard to calculate that
(72)(u1-v1)2-∥u2-v2∥2=(ξ2Ty2+ξ1x1+ξ2Tx2-ξ1y1)2x12+y12-∥-y1ξ2-ξ1x2-x1ξ2+ξ1y2∥2x12+y12=(ξ2Ty2+ξ2Tx2)2-∥ξ2∥2(y1+x1)2x12+y12≤0.
Similarly, we also have (u1+v1)2≤∥u2+v2∥2. In addition, we have that
(73)(u1-v1)2+∥u2+v2∥2=(ξ2Ty2+ξ1x1+ξ2Tx2-ξ1y1)2x12+y12+∥-y1ξ2-ξ1x2+x1ξ2-ξ1y2∥2x12+y12≤(ξ12+∥ξ2∥2)[(y1-x1)2+∥x2+y2∥2]x12+y12=2(ξ12+∥ξ2∥2)(x12+y12)x12+y12≤2.
A similar argument also yields (u1+v1)2+∥u2-v2∥2≤2. The last four equalities in (63) are direct by Lemma 5 and the expression of u1, u2, v1, and v2.To close this section, we establish a relation between theB-subdifferential of ϕFB at a complementarity point pair and that of ϕNR at the corresponding point pair.Lemma 14.
Let(x-,y-)∈ℝn×ℝn satisfy x-∈𝒦n, y-∈𝒦n and 〈x-,y-〉=0. Then,
(74)∂BϕNR(x-,y-)⊆∂BϕFB(x-,y-).Proof.
Since(x-,y-) satisfies x-∈𝒦n, y-∈𝒦n and 〈x-,y-〉=0, there exist spectral vectors u(1),u(2)∈ℝn and nonnegative real numbers λ1,λ2 and ν1,ν2 such that
(75)x-=λ1u(1)+λ2u(2),y-=ν1u(1)+ν2u(2).
Indeed, if x-=0 or y-=0, then the statement clearly holds. If x-≠0 and y-≠0, then the condition that x-∈𝒦n, y-∈𝒦n, and 〈x-,y-〉=0 implies x-,y-∈bd𝒦n. From Lemma 7, there exists α>0 such that x-2=-αy-2 and x-1=αy-1. Together with the spectral factorizations of x- and y-, the conclusion in (75) follows. Since 〈u(1),u(2)〉=0 and ∥u(1)∥=∥u(2)∥=1/2, using (75) and 〈x-,y-〉=0 yields that λ1ν1=λ2ν2=0. This, along with the nonnegativity of λ1,λ2 and ν1,ν2, implies
(76)x-=|x--y-|+(x--y-)2,y-=|x--y-|-(x--y-)2.
By the definition of ϕNR, we have ϕNR(x,y)=(x+y)-ψ(x,y) for x,y∈ℝn, where
(77)ψ(x,y):=12[(x+y)+|x-y|]∀x,y∈ℝn.
Comparing with the definition of ϕFB, we only need to prove the following inclusion:
(78)∂Bψ(x-,y-)⊆∂Bz(x-,y-).
For this purpose, let [UV]∈∂Bψ(x-,y-). By the definition of the elements in ∂Bψ(x-,y-) and Corollary 10(b), there exists a sequence {(xk,yk)}⊂ℝn×ℝn converging to (x-,y-) with ck≡xk-yk invertible such that
(79)[UV]=limk→∞𝒥ψ(xk,yk)=limk→∞[12(I+L|ck|-1Lck)12(I-L|ck|-1Lck)].
For each k, let x^k=(|ck|+ck)/2 and y^k=(|ck|-ck)/2. Then, using ck=xk-yk and (76), we have that x^k→x- and y^k→y- as k→∞. Also, z(x^k,y^k)=(ck)2=|ck|≻𝒦n0. By Corollary 10(a), the function z(·,·) is continuously differentiable at (x^k,y^k) with
(80)𝒥z(x^k,y^k)=[Lz(x^k,y^k)-1Lx^kLz(x^k,y^k)-1Ly^k]=[L|ck|-1L(|ck|+ck)/2L|ck|-1L(|ck|-ck)/2].
Together with (79), we have that [UV]=limk→∞𝒥z(x^k,y^k). This shows that [UV]∈∂Bz(x-,y-), and the inclusion in (78) follows. The proof is complete.


## 4. Nonsingularity Conditions

This section studies the nonsingularity of Clarke's Jacobian ofEFB at a KKT point. Let (ζ-,x-,μ-,s-,y-)∈ℝn×𝒦×ℝm×ℝn×𝒦 be a KKT point of the SOCP (4), that is,
(81)𝒥ζ,xL(ζ-,x-,μ-,s-,y-)=0,h(ζ-)=0,g(ζ-)-x-=0,-y-∈𝒩𝒦(x-).
Taking into account that -y-∈𝒩𝒦(x-) if and only if x- and y- satisfy
(82)x-j∈𝒦nj,y-j∈𝒦nj,〈x-j,y-j〉=0,j=1,2,…,r,
we introduce the following index sets associated with x- and y-:
(83)JI0:={j∣x-j∈int𝒦nj,y-j=0},J0I:={j∣x-j=0,y-j∈int𝒦nj},JBB:={j∣x-j,y-j∈bd+𝒦nj},JB0:={j∣x-j∈bd+𝒦nj,y-j=0},J0B:={j∣x-j=0,y-j∈bd+𝒦nj},J00:={j∣x-j=0,y-j=0}.
From [19], we learn that the above six index sets form a partition of {1,2,…,r}.First of all, let us take a careful look at the properties of the elements in∂ϕFB(x-j,y-j) for j∈JB0∪J0B, as stated in the following. The proof of Lemma 15 is given in the Appendix.Lemma 15.
For(x-,y-) satisfying (82), let [UjVj]∈∂ϕFB(x-j,y-j) for each j. Then,  (a)
whenj∈JB0, there exists an nj×nj orthogonal matrix Qj=[qjQ^jqj′] with
(84)qj=12(1x~j2),qj′=12(1-x~j2),x~j2=x-j2∥x-j2∥
such that Uj=QjDjQjT,Vj=QjΛjQjT, where Dj and Λj take one of the forms
(85)Dj=0,Λj=I,Qj=I;Dj=diag(0,0,…,0,1),Λj=diag(1,1,…,1,0);Dj=diag(0,0,…,0,1-uj1),Λj=(1000I00-12vjTQ^j1-vj1)
with uj=(uj1,uj2),vj=(vj1,vj2)∈ℝ×ℝnj-1 satisfying uj1,vj1<1,(b)
whenj∈J0B, there exists an nj×nj orthogonal matrix Qj=[qjQ^jqj′] with
(86)qj=12(1y~j2),qj′=12(1-y~j2),y~j2=y-j2∥y-j2∥
such that Uj=QjDjQjT,Vj=QjΛjQjT, where Dj and Λj take one of the forms
(87)Dj=I,Λj=0,Qj=I;Dj=diag(1,1,…,1,0),Λj=diag(0,0,…,0,1);(88)Dj=(1000I00-12ujTQ^j1-uj1),Λj=diag(0,0,…,0,1-vj1)
with uj=(uj1,uj2), vj=(vj1,vj2)∈ℝ×ℝnj-1 satisfying uj1,vj1<1.The following proposition plays a key role in achieving the main result of this section.Proposition 16.
For(x-,y-) satisfying (82), let [UjVj]∈∂ϕFB(x-j,y-j) for j=1,…,r. Then, for any (Δu)j,(Δv)j∈ℝnj, it holds that
(89)Uj(Δu)j+Vj(Δv)j=0⇒{(Δv)j=0,ifj∈JI0,(Δu)j=0,ifj∈J0I,〈(Δu)j,y-j〉=0,〈(Δv)j,x-j〉=0,ifj∈JBB,(Δu)j∈ℝ(y-j1,-y-j2),ifj∈J0B,(Δv)j∈ℝ(x-j1,-x-j2),ifj∈JB0.
Particularly, for each j∈JBB, the following implication also holds:
(90)Uj(Δu)j+Vj(Δv)j=0⇒{〈(Δu)j,(Δv)j〉=y-j1x-j1((Δu)j12-∥(Δu)j2∥2),〈(Δu)j,(Δv)j〉=x-j1y-j1((Δv)j12-∥(Δv)j2∥2).Proof.
Throughout the proof, letw-j=x-j2+y-j2 and z-j=w-j for j=1,2,…,r. We prove the conclusion by discussing five cases as shown in the following arguments.
Case
1
(
j
∈
J
I
0
). In this case z-j=x-j∈int𝒦nj. From Corollary 10(a), it follows that the function ϕFB is continuously differentiable at (x-j,y-j). Therefore,
(91)∂ϕFB(x-j,y-j)={𝒥ϕFB(x-j,y-j)}={[I-Lz-j-1Lx-jI-Lz-j-1Ly-j]}={[0I]}.
Then, Uj=0 and Vj=I. Together with Uj(Δu)j+Vj(Δv)j=0, we get (Δv)j=0.
Case
2
(
j
∈
J
0
I
). Using the same arguments as in Case 1 readily yields (Δu)j=0.
Case
3
(
j
∈
J
B
B
). Now x-j∈bd+𝒦nj and y-j∈bd+𝒦nj. By (82) and Lemma 7, there exists ρj>0 such that x-j1=ρjy-j1 and x-j2=-ρjy-j2, and consequently,
(92)w-j=(2(1+ρj2)y-j122(1-ρj2)y-j1y-j2)∈int𝒦nj,z-j=((1+ρj)y-j1(1-ρj)y-j2)=x-j+y-j.
From Corollary 10(a), ϕFB is continuously differentiable at (x-j,y-j), and hence
(93)Uj=I-Lz-j-1Lx-j=Lz-j-1Lz-j-x-j=Lz-j-1Ly-j,Vj=I-Lz-j-1Ly-j=Lz-j-1Lz-j-y-j=Lz-j-1Lx-j.
Thus, Uj(Δu)j+Vj(Δv)j=0 implies that Ly-j(Δu)j+Lx-j(Δv)j=0, and consequently,
(94)(x-j1(Δv)j1+x-j2T(Δv)j2)+(y-j1(Δu)j1+y-j2T(Δu)j2)=0,(95)(x-j2(Δv)j1+x-j1(Δv)j2)+(y-j2(Δu)j1+y-j1(Δu)j2)=0.
Making an inner product with y-j2/∥y-j2∥, we have from x-j,y-j∈bd+𝒦nj and Lemma 5 that
(96)-(x-j1(Δv)j1+x-j2T(Δv)j2)+(y-j1(Δu)j1+y-j2T(Δu)j2)=0.
Together with (94), we have 〈(Δu)j,y-j〉=0 and 〈(Δv)j,x-j〉=0.
We next prove the implication in (90). By the expressions of z-j,Uj, and Vj,
(97)Uj(Δu)j+Vj(Δv)j=0⟺[y-j1y-j2Ty-j2y-j1I](Δu)j+[x-j1x-j2Tx-j2x-j1I](Δv)j=0⟺[y-j1y-j2Ty-j2y-j1I](Δu)j+x-j1y-j1[y-j1-y-j2T-y-j2y-j1I](Δv)j=0⇒[y-j2y-j1I](Δu)j+x-j1y-j1[-y-j2y-j1I](Δv)j=0⟺[-y-j2y-j1I][x-j1y-j1((Δv)j1(Δv)j2)+(-(Δu)j1(Δu)j2)]=0,
where the second equivalence is due to x-j1=ρjy-j1 and x-j2=-ρjy-j2. Since the rank of [-y-j2y-j1I] is nj-1, the dimension of the solution space for the system [-y-j2y-j1I]ζ=0 equals 1. Note that y-j is a nonzero solution of this linear system. Therefore,
(98)x-j1y-j1((Δv)j1(Δv)j2)+(-(Δu)j1(Δu)j2)=cy-jfor somec∈ℝ.
Making an inner product with (Δu)j for the equality and using 〈(Δu)j,y-j〉=0, we get
(99)x-j1y-j1〈(Δu)j,(Δv)j〉=(Δu)j12-∥(Δu)j2∥2.
Using the similar arguments as above and noting that 〈(Δv)j,x-j〉=0, we may obtain
(100)y-j1x-j1〈(Δu)j,(Δv)j〉=(Δv)j12-∥(Δv)j2∥2.
The last two equalities show that the implication in (90) holds.
Case
4
(
j
∈
J
0
B
). By Lemma 15(b), there exists an nj×nj orthogonal matrix Qj=[qjQ^jqj′] such that Uj=QjDjQjT and Vj=QjΛjQjT, where qj and qj′ are given by (86), and Qj and Λj take one of the form in (87)-(88). Thus, we have
(101)Uj(Δu)j+Vj(Δv)j=0⟺DjQjT(Δu)j+ΛjQjT(Δv)j=0.
When Dj=I and Λj=0, we have QjT(Δu)j=0, and then (Δu)j=0. When Dj and Λj take the form in (87), we have [qjTQ^jT](Δu)j=0. Consequently,
(102)(Δu)j=QjQjT(Δu)j=[qjQ^jqj′][00(qj′)T(Δu)j]=(qj′)T(Δu)j2y-j1[y-j1-y-j2],
where the last equality is using the definition of qj′. When Dj and Λj take the form in (88), we also have [qjTQ^jT](Δu)j=0. Using the same arguments as above, we have that (Δu)j has the form of (102). Thus, we prove that (Δu)j∈ℝ(y-j1,-y-j2).
Case
5
(
j
∈
J
B
0
). Using Lemma 15(a) and following the same arguments as in Case 4, the result can be checked routinely. So, we omit the proof.The following lemma states an important property for the elements of Clarke's Jacobian ofϕFB at a general point, which will be used to prove Proposition 18.Lemma 17.
For any given(x,y)∈ℝn×ℝn, let [UV]∈∂ϕFB(x,y). Then,
(103)UΔu+VΔv=0⇒〈Δu,Δv〉≤0,∀Δu,Δv∈ℝn.Proof.
Since[UV]∈∂ϕFB(x,y), by Carathéodory's theorem, there exist a positive integer κ and [UiVi]∈∂BϕFB(x,y) for i=1,…,κ such that [UV]=∑i=1κ‍τi[UiVi] where τi≥0,i=1,…,κ, and ∑i=1κ‍τi=1. For each i∈{1,…,κ}, by Corollary 10(a) and the definition of the elements in ∂BϕFB(x,y), there exists a sequence {(xik,yik)} in ℝn×ℝn converging to (x,y) with zik=z(xik,yik)≻0 such that
(104)[UiVi]=limk→∞𝒥ϕFB(xik,yik)=limk→∞[I-Lzik-1LxikI-Lzik-1Lyik].
Consequently, for any Δu,Δv∈ℝn, we have that
(105)(I-U)Δu+(I-V)Δv=limk→∞∑i=1κ‍τi(Lzik-1LxikΔu+Lzik-1LyikΔv).
From the continuity and convexity of the Euclidean norm ∥·∥ and Lemma 4, we get
(106)∥(I-U)Δu+(I-V)Δv∥≤limk→∞∑i=1κ‍τi∥(Lzik-1LxikΔu+Lzik-1LyikΔv)∥≤∥Δu∥2+∥Δv∥2.
Now assume that UΔu+VΔv=0. Then, by the last inequality, we get the result.Proposition 18.
For(x-,y-) satisfying (82), let [UV]∈∂ϕFB(x-,y-). Then it holds that
(107)UΔu+VΔv=0⇒〈Δu,Δv〉≤∑j=1r‍Υx-j(y-j,(Δu)j)∀Δu,Δv∈ℝn,
where, for any given ϖ∈ℝn, Υϖj:ℝnj×ℝnj→ℝ is the linear-quadratic function:
(108)Υϖj(ξj,ηj):={ξj1ϖj1ηjT(100-I)ηj,ifϖj∈bd+𝒦nj,0,otherwise.Proof.
Fix anyΔu,Δv∈ℝn. Since U=diag(U1,…,Ur) and V=diag(V1,…,Vr) with [UjVj]∈∂ϕFB(x-j,y-j) for j=1,2,…,r, we may rewrite UΔu+VΔv=0 as
(109)Uj(Δu)j+Vj(Δv)j=0,j=1,2,…,r.
From Lemma 17 and (90) of Proposition 16, it then follows that
(110)〈Δu,Δv〉≤∑j∈JBB‍〈(Δu)j,(Δv)j〉=∑j∈JBB‍y-j1x-j1[(Δu)j12-∥(Δu)j2∥2].
In addition, by the definition of Υϖj, Υx-j(y-j,·)=0 for all j∈JI0∪J0I∪J0B∪J00 since x-j∉bd+𝒦nj, and Υx-j(y-j,·)=0 for j∈JB0 since y-j1=0. This means that
(111)∑j=1r‍Υx-j(y-j,(Δu)j)=∑j∈JBB‍Υx-j(y-j,(Δu)j)=∑j∈JBB‍y-j1x-j1[(Δu)j12-∥(Δu)j2∥2].
From the above two equations, we immediately obtain the desired result.Before stating the main result of this section, we also need to recall several concepts, including constraint nondegeneracy, Robinson's constraint qualification (CQ) (see [20]), and the strong second-order sufficient condition introduced in [7, Theorem 30]. To this end, let ω≡(ζ,x)∈ℝ2n and define f~:ℝ2n→ℝ,h~:ℝ2n→ℝn+m,g~:ℝ2n→ℝn by
(112)f~(ω):=f(ζ),h~(ω):=(h(ζ)g(ζ)-x),g~(ω):=x.
Then, we may rewrite the nonlinear SOCP (4) succinctly as follows:
(113)minω∈ℝ2nf~(ω)aas.t.h~(ω)=0,minω∈ℝ2ng~(ω)∈𝒦.Definition 19.
A feasible vectorω-=(ζ-,x-) of (4) is called constraint nondegenerate if
(114)(𝒥ωh~(ω-)𝒥ωg~(ω-))ℝ2n+({0}lin(𝒯𝒦(x-)))=(ℝm+nℝn),
where lin(𝒯𝒦(x-)) is the largest linear space of 𝒯𝒦(x-), that is, lin(𝒯𝒦(x-))=𝒯𝒦(x-)∩-𝒯𝒦(x-).Definition 20.
Robinson's CQ is said to hold at a feasible solutionω-=(ζ-,x-) to (4) if
(115)0∈int{(h~(ω-)g~(ω-))+(𝒥ωh~(ω-)𝒥ωg~(ω-))ℝ2n-({0}𝒦)},
which, since 𝒦 is a closed convex set in ℝn, can be equivalently written as
(116)(𝒥ωh~(ω-)𝒥ωg~(ω-))ℝ2n+({0}𝒯𝒦(x-))=(ℝm+nℝn).Clearly, the constraint nondegenerate condition (114) implies Robinson's CQ (116). If ω-=(ζ-,x-) is a locally optimal solution to (4) and Robinson's CQ holds at ω-, then there exists a Lagrange multiplier (μ-,s-,y-), together with ω-, satisfying the KKT conditions:
(117)𝒥ζ,xL(ζ-,x-,μ-,s-,y-)=0,h(ζ-)=0,g(ζ-)-x-=0,-y-∈𝒩𝒦(x-).
In the sequel, we let Λ(ω-) denote the set of Lagrange multipliers satisfying (117).Let(ζ-,x-,μ-,s-,y-)∈ℝn×𝒦×ℝm×ℝn×𝒦 be a KKT point of the SOCP (4). From [7, Lemma 25], it follows that the tangent cone of 𝒦 at x- takes the form of
(118)𝒯𝒦(x-)={djTd∈ℝn∣dj∈𝒦njforj∈J0I∪J0B∪J00;djT(x-j1,-x-j2)≥0forj∈JBB∪JB0},
which implies that the largest linear space in 𝒯𝒦(x-) has the following form:
(119)lin(𝒯𝒦(x-))={d∈ℝn∣dj=0forj∈J0I∪J0B∪J00;djT(x-j1,-x-j2)=0forj∈JBB∪JB0}.
We next recall the critical cone of problem (4) at a feasible ω0 which is defined as
(120)𝒞(ω0)≔{d∈ℝ2n∣𝒥ωh~(ω0)d=0,aaaa𝒥ωg~(ω0)d∈𝒯𝒦(g~(ω0)),aaaa𝒥ωf~(ω0)d≤0}.
The critical cone 𝒞(ω0) represents those directions for which the linearization of (4) does not provide any information about optimality of ω0 and is very important in studying second-order optimality conditions. Particularly, if the set of Lagrange multipliers Λ(ω0) at the point ω0 is nonempty, then 𝒞(ω0) can be rewritten as
(121)𝒞(ω0)={(g~(ω0))(y0)⊥d∈ℝ2n∣𝒥ωh~(ω0)d=0,aaaaaaa𝒥ωg~(ω0)d∈𝒯𝒦(g~(ω0))∩(y0)⊥},
where y0∈Λ(ω0) and (y0)⊥ means the orthogonal complementarity space of y0. Now let (μ-,s-,y-)∈Λ(ω-). Then, using g~(ω-)=x- and the expression of 𝒯𝒦(x-), we have that
(122)𝒞(ω-)={d∈ℝ2n∣𝒥ωg~j(ω-)d=0forj∈J0I,𝒥ωg~j(ω-)d∈ℝ+(y-j1,-y-j2)aaaaaaaaaaaaaaaaaforj∈J0B,〈𝒥ωg~j(ω-)d,y-j〉=0forj∈JBB,𝒥ωg~j(ω-)d∈𝒦njforj∈J00,(𝒥ωg~j(ω-)d)(x-j1,-x-j2)≥0aaaaaaaaaaaaaaaaaaforj∈JB0;𝒥ωh~(ω-)d=0}.Definition 21.
Letω-=(ζ-,x-) be a stationary point of the SOCP (4) such that Λ(ω-)={(μ-,s-,y-)}. We say that the strong second-order sufficient condition holds at ω- if
(123)〈d,𝒥ωω2L(ζ-,x-,μ-,s-,y-)d〉+〈d,H(ω-,y-)d〉>0,∀d∈aff(𝒞(ω-))∖{0},
where H(ω-,y-)=∑j=1r‍Hj(ω-,y-)∈ℝ2n×2n with Hj(ω-,y-)∈ℝ2n×2n defined by
(124)Hj(ω-,y-):={-y-j1x-j1𝒥ωg~j(ω-)T(100-I)𝒥ωg~j(ω-),ifj∈JBB∪JB0;0,otherwise,
and aff(𝒞(ω-)) denotes the affine hull of 𝒞(ω-) and is now equivalent to the span of 𝒞(ω-):
(125)aff(𝒞(ω-))={d∈ℝ2n∣𝒥ωh~(ω-)d=0;𝒥ωg~j(ω-)d=0forj∈J0I,〈𝒥ωg~j(ω-)d,y-j〉=0forj∈JBB,𝒥ωg~j(ω-)d∈ℝ(y-j1,-y-j2)forj∈J0B}.Now we are in a position to prove the nonsingularity of Clarke's Jacobian ofEFB under the strong second-order sufficient condition and constraint nondegeneracy.Proposition 22.
Let(ζ-,x-,μ-,s-,y-) be a KKT point of the nonlinear SOCP (4). Suppose that the strong second-order sufficient condition (123) holds at ω-=(ζ-,x-) and ω- is constraint nondegenerate, then any element in ∂EFB(ζ-,x-,μ-,s-,y-) is nonsingular.Proof.
Since the nondegeneracy condition (114) is assumed to hold at (ζ-,x-), from [21, Proposition 4.75], we know that Λ(ω-)={(μ-,s-,y-)}. Then, by the definition of L and g~, the strong second-order sufficient condition (123) takes the following form:
(126)〈ξ,𝒥ζζ2l(ζ-,μ-,s-)ξ〉-〈η,H^(x-,y-)η〉>0,∀(ξ,η)∈aff(𝒞(ω-))∖{(0,0)},
where l(ζ,μ,s):=f(ζ)+〈μ,h(ζ)〉+〈g(ζ),s〉 and H^(x-,y-)=∑j=1r‍H^j(x-,y-)∈ℝn×n with
(127)H^j(x-,y-):={-y-j1x-j1(100-I),ifj∈JBB∪JB0;0,otherwise.
Let W be an arbitrary element in ∂EFB(ζ-,x-,μ-,s-,y-). To prove that W is nonsingular, let (Δζ,Δx,Δμ,Δs,Δy)∈ℝn×ℝn×ℝm×ℝn×ℝn such that
(128)W(Δζ,Δx,Δμ,Δs,Δy)=0.
From the expression of EFB, we know that there exists a [UV]∈∂ϕFB(x-,y-) such that
(129)[𝒥ζζl(ζ-,μ-,s-)Δζ+𝒥ζh(ζ-)TΔμ+𝒥ζg(ζ-)TΔs-Δs-Δy𝒥ζh(ζ-)Δζ𝒥ζg(ζ-)Δζ-ΔxUΔx+VΔy]=0,
where U=diag(U1,…,Ur) and V=diag(V1,…,Vr) with [UjVj]∈∂ϕFB(x-j,y-j) for all j=1,2,…,r. The last system can be simplified as
(130)[𝒥ζζ2l(ζ-,μ-,s-)Δζ+𝒥ζh(ζ-)TΔμ-𝒥ζg(ζ-)TΔy𝒥ζh(ζ-)ΔζU𝒥ζg(ζ-)Δζ+VΔy]=0.
By the second and the third equations of (130) and (89), we get
(131)𝒥ζh(ζ-)Δζ=0,(𝒥ζg(ζ-)Δζ)j=ℝ(y-j1,-y-j2),forj∈J0B,(𝒥ζg(ζ-)Δζ)j=0,forj∈J0I,〈(𝒥ζg(ζ-)Δζ)j,y-j〉=0,forj∈JBB.
Comparing with the definition of aff(𝒞(ω-)) in Definition 21, it follows that
(132)(Δζ,𝒥ζg(ζ-)Δζ)∈aff(𝒞(ω-)).
From the first and the second equations of (130), it is not hard to verify
(133)0=〈Δζ,𝒥ζζ2l(ζ-,μ-,s-)Δζ+𝒥ζh(ζ-)TΔμ-𝒥ζg(ζ-)TΔy〉=〈Δζ,𝒥ζζ2l(ζ-,μ-,s-)Δζ〉-〈𝒥ζg(ζ-)Δζ,Δy〉,
which, together with the third equation of (130) and Proposition 18, implies that
(134)0≥〈Δζ,𝒥ζζ2l(ζ-,μ-,s-)Δζ〉-∑j=1r‍Υx-j(y-j,𝒥ζgj(ζ-)Δζ).
This, together with (132) and (126), yields that Δζ=0. Thus, (130) reduces to
(135)[𝒥ζh(ζ-)TΔμ-𝒥ζg(ζ-)TΔyVΔy]=0.
From the second equation of (135), we have Vj(Δy)j=0 for j∈JBB. In addition, by the arguments for Case 3 of Proposition 16, Vj=Lz-j-1Lx-j for j∈JBB, and so Lx-j(Δy)j=0 for j∈JBB. Since x-j∈bd+𝒦nj for j∈JBB, Lx-j has the two single eigenvalues 0 and 2x-j1 as well as the eigenvalues x-j1 with multiplicity nj-2, and (1,-x-j2/x-j1) is the eigenvector corresponding to eigenvalue 0. Thus, from Lx-j(Δy)j=0, we deduce
(136)(Δy)j∈ℝ(xj1,-x-j2),forj∈JBB.
By the second equation of (135), we use Proposition 16 with Δu=0, Δv=Δy to yield
(137)(Δy)j=0,forj∈JI0,(Δy)j∈ℝ(x-j1,-x-j2),forj∈JB0.
Using the constraint nondegeneracy condition (114), we know that there exist a vector (d1,d2)∈ℝn×ℝn and a vector υ∈lin(𝒯𝒦(x-)) such that
(138)𝒥ζh(ζ-)d1=Δμ,𝒥ζg(ζ-)d1-d2=-Δy,d2+υ=-Δy.
Since υ∈lin(𝒯𝒦(x-)), from (119), it follows that
(139)υj=0,forj∈J0I∪J0B∪J00,υjT(x-j1,-x-j2)=0,forj∈JBB∪JB0.
Combining the last four equations with the first equation of (135), we obtain
(140)〈Δμ,Δμ〉+2〈Δy,Δy〉=〈𝒥ζh(ζ-)d1,Δμ〉-〈𝒥ζg(ζ-)d1-d2,Δy〉-〈d2+υ,Δy〉=〈d1,𝒥ζh(ζ-)TΔμ-𝒥ζg(ζ-)TΔy〉-〈υ,Δy〉=-〈υ,Δy〉=0.
Thus, Δμ=0 and Δy=0. Along with Δζ=0, we show that W is nonsingular.Note that-y∈𝒩𝒦(x) if and only if -x∈𝒩𝒦(y). The KKT conditions in (7) can be equivalently written as the following generalized equation
(141)0∈[𝒥ζ,xL(ζ,x,μ,s,y)h(ζ)g(ζ)-xx]+[𝒩ℝn×ℝn(ζ,x)𝒩ℝm(μ)𝒩ℝn(s)𝒩𝒦(y)],
which is clear in the form of the generalized equation given by (29). Now using Proposition 22 and [9, Theorem 3.1], we may establish the main result of this paper, which states that Clarke's Jacobian of EFB at a KKT point is nonsingular if and only if the KKT point is a strongly regular solution to the generalized equation (141).Theorem 23.
Let(ζ-,x-) be a locally optimal solution to the nonlinear SOCP (4). Suppose that Robinson's CQ holds at this point. Let (μ-,s-,y-)∈ℝm×ℝn×𝒦 be such that (ζ-,x-,μ-,s-,y-) is a KKT point of (4). Then the following statements are equivalent.(a)
The strong second-order sufficient condition in Definition21 holds at (ζ-,x-) and (ζ-,x-) is constraint nondegenerate.(b)
Any element in∂EFB(ζ-,x-,μ-,s-,y-) is nonsingular.(c)
Any element in∂ENR(ζ-,x-,μ-,s-,y-) is nonsingular.(d)
(ζ-,x-,μ-,s-,y-) is a strongly regular solution of the generalized equation (141).Proof.
First, Lemma14 and the definition of EFB and ENR imply the following inclusion:
(142)∂ENR(ζ-,x-,μ-,s-,y-)⊆∂EFB(ζ-,x-,μ-,s-,y-).
Using this inclusion and Proposition 22, we have that (a) ⇒ (b) ⇒ (c). Since the SOCP (4) is obtained from (1) by introducing a slack variable, we know from [9, Theorem 3.1] that (a) ⇔ (c) ⇔ (d). Thus, we complete the proof of this theorem.


## 5. Conclusions

In this paper, for a locally optimal solution of the nonlinear SOCP, we established the equivalence between the nonsingularity of Clarke's Jacobian of the FB system and the strong regularity of the corresponding KKT point. This provides a new characterization for the strong regularity of the nonlinear SOCPs and extends the result of [22, Corollary 3.7] for the FB system of variational inequalities with the polyhedral cone ℝ+n constraints to the setting of SOCs. Also, this result implies that the semismooth Newton method [5, 6] applied to the FB system is locally quadratically convergent to a KKT point under the strong second-order sufficient condition and constraint nondegeneracy. We point it out that we have also established parallel (not exactly the same) results for SDP case in [11] recently. However, it seems hard to put them together in a unified framework under Euclidean Jordan algebra. The main reason causing this is due to that the analysis and techniques are totally different when dealing with the Clarke Jacobians associated with FB SOC complementarity function and FB SDP complementarity function.



---

*Source: 602735-2013-03-11.xml*