# Jacobian Nonsingularity in Nonlinear Symmetric Conic Programming Problems and Its Application

Authors: Yun Wang; Dezhou Kong
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper considers the nonlinear symmetric conic programming (NSCP) problems. Firstly, a type of strong sufficient optimality condition for NSCP problems in terms of a linear-quadratic term is introduced. Then, a sufficient condition of the nonsingularity of Clarke’s generalized Jacobian of the Karush–Kuhn–Tucker (KKT) system is demonstrated. At last, as an application, this property is used to obtain the local convergence properties of a sequential quadratic programming- (SQP-) type method.


---

## Body

## 1. Introduction

In this paper, we consider the nonlinear symmetric conic programming (NSCP) as follows:(1)minx∈Xfx,s.t.hx=0,gx∈K,where X and Y are two finite dimensional real vector spaces; f:X⟶ℜ, h:X⟶ℜm, and g:X⟶Y are twice continuously differentiable functions; and K∈Y is a symmetric cone defined by Euclidean Jordan algebras. In the following part, unless otherwise specified, we denote X,Y, and Z to represent finite dimensional real vector spaces with a scalar product ⋅,⋅ and norm ⋅.It is well-known that the Karush–Kuhn–Tucker (KKT) conditions of optimization problem (1) are equivalent to the KKT system, which is a nonsmooth system with the metric projector over the symmetric cone. The nonsingularity of Clarke’s generalized Jacobian of the KKT system introduced by Pang and Qi [1] is not only one of the most important concepts in perturbation analysis of optimization problems but also plays a vital part in the design of the algorithms and the analysis of the convergence [2–4].WhenK in problem (1) is a polyhedral set, Robinson [5] has showed that the strong second-order sufficient condition and the LICQ imply the nonsingularity of Clarke’s generalized Jacobian of the KKT system. Interestingly, the converse is also true [2, 6, 7]. Bonnans and Ramírez [8] and Sun [9] demonstrate the equivalent conditions to the nonsingularity of the second-order cone programming problem (SOCP) and the semidefinite programming problem (SDP), respectively.WhenK is the class of C2-cone reducible sets ([3], Definition 3.135), there are lots of most important results about the Aubin property and the robust isolated calmness of the KKT solution mapping, which guarantee the nonsingularity of the KKT system (see [10–13] and the references therein).For symmetric cone programming problem, Kong, Tunçel, and Xiu [14–16] use a triangular representation of the Jacobian of Löwner operator to characterize the structure of Clarke’s generalized Jacobian of metric projection operator onto symmetric cone. They consider the linear symmetric cone programming problem as follows:(2)minc,x,s.t.Ax=b,x∈K,and present five equivalent conditions to the nonsingularity of Clarke’s generalized Jacobian of KKT system in [15].In this paper, we focus on the nonsingularity of Clarke’s generalized Jacobian of the KKT system in the setting of the nonlinear symmetric cone programming problem (1). In order to present the optimality conditions of NSCP, we need the variational analysis of symmetric cones and some important sets such as tangent cone. We found that, almost at the same time, we [17] and Kong et al. [15] independently obtained the same expressions of the tangent cone and so on by different approaches (see Proposition 2). Importantly, we introduce a linear-quadratic function to establish the second-order optimality conditions. Using the Euclidean Jordan Algebras and the Peirce decomposition of a finite-dimensional vector space, we obtain an upper bound of the linear-quadratic function. Under the constraint nondegeneracy condition, we demonstrate our main result that if a kind of strong second-order sufficient condition holds, any element in Clarke’s generalized Jacobian of the KKT system is nonsingular.In [18], the local convergence for an SQP-type method is ensured by the nonsingularity of Clarke’s generalized Jacobian. In this paper, as an application, we give an SQP-type method to solve NSCP (1). The analysis of the local convergence is presented by using the above properties of the nonsingularity, and our proof is a natural extension of the nonlinear programming problem.The paper is organized as follows. In Section2, it gives some preliminaries which are used in the paper, including the fundamental notations in Euclidean Jordan algebras. The properties of a linear-quadratic function are developed. In Section 3, we describe the KKT condition and a kind of second-order sufficient condition of NSCP (1) using the linear-quadratic function. Then, we discuss the nonsingularity of Clarke’s generalized Jacobian of the equation reformulation of the KKT system. Lastly, the local convergence of a SQP-type method is analyzed by using the nonsingularity in Section 4.


## 2. Preliminaries

In this section, some preliminaries used in the paper are given firstly. Then, we introduce the decomposition results in Euclidean Jordan algebras, which are vital to this paper.For a locally Lipschitz continuous functionΞ:O⊆Y⟶Z, Clarke’s generalized Jacobian of Ξ at y is defined by(3)∂Ξy≔convV:V=limk⟶∞Ξ′yk,yk∈OΞ,yk⟶y,where OΞ is the set of F-differentiable points in O and “conv” denotes the convex hull.The next conclusion of the chain rule is given in [19], which is stronger than its first version in [9].Lemma 1.
Suppose thatΨ:X⟶Y is a continuously differentiable function and Ξ:O⊆Y⟶Z is a locally Lipschitz continuous function. Denote y∗≔Ψx∗∈O and let Ψ′x∗:X⟶Y be onto. Then, the composite function Φx≔ΞΨx is F-differentiable at x∈N^ if and only if Ξ is F-differentiable at Ψx, where N^ is an open neighborhood of x∗ and(4)∂BΦx∗=∂BΞy∗Ψ′x∗.The following conclusion of implicit functions can be obtained from [20] (Section 7.1) and [21] (Lemma 2) directly.Lemma 2.
LetΦ:X×Y⟶X be a locally Lipschitz continuous function and Φx¯,y¯=0. Suppose that any element in ΠX∂Φx¯,y¯ is nonsingular. Then, there exists a locally Lipschitz continuous function x⋅:OY⟶X satisfying xy¯=x¯ and(5)Φxy,y=0,where OY is an open neighborhood of y¯. Furthermore, if Φ is (strongly) semismooth, then x⋅ is (strongly) semismooth.In the last part of this section, we provide some properties about the metric projector over a convex setC in Banach space (see [22]).Lemma 3.
Suppose thatC is a convex set in a Banach space Z. Then, for any y∈Z and V∈∂ΠCy, V is self-adjoint. Furthermore, for any d∈Z, d,Vd≥0 and Vd,d−Vd≥0.


### 2.1. Euclidean Jordan Algebras

In this part, we show some useful notations and conclusions on Euclidean Jordan Algebras introduced in [23]. Suppose that F is the real field ℝ and V is a finite-dimensional vector space over F.For anyx∈V, denote(6)ℒxy≔x⋅yfor everyy∈V.The pairA≔V,⋅ defined over the real field ℝ is called a Euclidean Jordan algebra, if, for all x,y∈V:(i)
x⋅y=y⋅x(ii)
x⋅x2⋅y=x2⋅x⋅y, where x2≔x⋅x(iii)
x⋅y,zV=y,x⋅zVHere are some common concepts used in this paper.An elementc∈V is called to be the unit element of A if x⋅e=e⋅x=x for all x∈V. We always assume that there exists a unit element e∈V of A=V,⋅ in the following paper.If is called to be idempotent. If two idempotentsp and q satisfy p⋅q=0, they are called orthogonal. And k orthogonal idempotents c1,c2,…,ck are said to be a complete system if they satisfy(7)∑j=1kcj=e.If a nonzero idempotentq cannot be written as the sum of two other nonzero idempotents, we say q is primitive. And Jordan frame is a complete system of orthogonal primitive idempotents.The following theorem in [23] is very important to show the spectral decomposition.Theorem 1.
LetA=V,⋅ be a Euclidean Jordan algebra and RA=r. Then, for any x∈V,(8)x=∑j=1rλjxcj=λ1xc1+λ2xc2+⋯+λrxcr,where c1,c2,…,cr is a Jordan frame and λjx∈ℝ,j=1,…,r, satisfying λ1x≥λ2x≥⋯≥λrx.We say the numbersλ1x,λ2x,…,λrx to be eigenvalues of x. Then, x has the spectral decomposition (8) and(9)trx=∑j=1rλjx.Therefore, another associative inner product can be defined by usingtrx: x,y≔trx⋅y,x,y∈V. Let ⋅ be the norm on V induced by this inner product, then(10)x≔x,x=∑j=1rλj2x,x∈V.For a scalar-valued functionϕ:ℝ⟶ℝ, we define Löwner’s operator associated with A=V,⋅ from [24] as(11)ϕVx≔∑j=1rϕλjxcj=ϕλ1xc1+ϕλ2xc2+⋯+ϕλrxcr,where x=∑j=1rλjxcj∈V.The metric projection operator on(12)K≔y2:y∈Vcan be described by Löwner’s operator using ϕt=max0,t as follows:(13)ΠKx=x+=λ1x+c1+λ2x+c2+⋯+λrx+cr,which is very important in the following research.It is known from ([23], Theorem III.2.1) that the above cone K=y2:y∈V is a self-dual homogeneous closed convex cone, we call it a symmetric cone, which is the constraint set of problem (1)For a Jordan frame ofAc1,c2,…,cr, we denote Vij as follows:(14)Vij≔Vci,1,i=j,Vci,12∩Vcj,12,i≠j.Suppose thatCijx is the orthogonal projection onto Vij. Then, Cijx has the following expression:(15)Cjlx=∑i=1dvjli,⋅vjli,where vjlii=1d∈V denotes orthonormal vectors and d satisfies n=r+d/2rr−1.It follows from [25] that(16)h=∑j=1rCjjxh+∑1≤j<l≤rCjlxh=∑j=1rcj,hcj+∑1≤j<l≤r4cj⋅cl⋅h,∀h∈V.Actually, all the eigenvectors(17)c1,c2,…,cr,vjl1,vjl2,…,vjld,1≤j<l≤rform an orthonormal basis of V.Assume that there exist two integerss and s1 such that(18)λ1x≥⋯≥λsx>0=λs+1x=⋯=λs1x>λs1+1x≥⋯≥λrx.Let us introduce three index sets:(19)α≔1,…,s,β≔s+1,…,s1,andγ≔s1+1,…,r.For1≤j≤l, denote(20)hjj≔Cjjxh=cj,hcj,hjl≔Cjlxh=∑i=1dvjli,hvjli,hαα=∑j=1shjj+∑1≤j<l≤shjl,hαβ=∑j=1s∑l=s+1s1hjl,hαγ=∑j=1s∑l=s1+1rhjl,hββ=∑j=s+1s1hjj+∑s+1≤j<l≤s1hjl,hβγ=∑j=s+1s1∑l=s1+1rhjl,hγγ=∑j=s1+1rhjj+∑s1+1≤j<l≤rhjl.For the merit projectorΠK onto the symmetric cone, Sun and Sun [25] has proved that ΠK is strongly semismooth everywhere. Wang [17] gave a characterization pertaining the structure of the B-subdifferential of ΠK. Recently, Kong, Tunçel, and Xiu presented an exact expression for B-subdifferential and Clarke’s generalized Jacobian of ΠK [14, 15]. Here, we rewrite the conclusion obtained by Kong et al. [15] as follows.Proposition 1.
Letx=∑j=1rλjxcj and the indexsets α,β,γ be given by (19). Then, for any V∈∂ΠKx, there exists W∈∂ΠKβ0 such that(21)Vh=∑j=1shjj+∑j=1s∑l=j+1s1hjl+∑j=1s∑l=s1+1rλjxλjx−λlxhjl+Wh,where Kβ is the symmetric cone in subspace Vββ≔⊕i≤j,i∈β,j∈βVij.In order to describe the optimality conditions of NSCP (1), we need the expressions of some important sets, such as the tangent cone of K at x+TKx+, the linearity of TKx+linTKx+, critical cone Cx+, and the affine space of Cx+, denoted by affCx+. As Wang [17] and Kong et al. [15] have obtained the characterizations independently, we only show the topological results in the following proposition.Proposition 2.
Letx have eigenvalues as in (18). It holds that(22)TKx+=z:hββ+hβγ+hγγ≽0,(23)linTKx+=h:hββ=0,hβγ=0,hγγ=0,(24)Cx+=h:hββ≽0,hβγ=0,hγγ=0,(25)affCx+=h:hβγ=0,hγγ=0.


### 2.2. A Linear-Quadratic Function

Inspired by the works by Bonnans and Shapiro [2] and Sun [9], we define a linear-quadratic function as follows, which is vital for establishing a kind of strong second-order sufficient condition.Definition 1.
For any givenv∈V, define a linear-quadratic function ϒv:V×V⟶ℜ by(26)ϒvz,h≔4z⋅h,v†⋅h,z,h∈V×V,where v† is the Moore–Penrose pseudoinverse of v.Here, the linear-quadratic function is different from Definition 3.2 in [15]. Even in the especial case, v∈K and v⋅z=0, the value of the linear-quadratic function (26) is twice the one in [15].For the linear-quadratic function (16), we have the following conclusions.Proposition 3.
Ifh∈affCx+, then(27)ϒx+x−x+,h=∑j=1s∑l=s1+1rλlλjhjl2.Proof.
Asx+=∑j=1sλjcj,x−x+=∑j=s1+1rλjcj, we have(28)x−x+⋅h=∑j=1s∑l=s1+1r∑i=1dλlvjli,hcl⋅vjli,n!r!n−r!,x+†⋅h=∑j=1sλj−1cj,hcj+∑j=1s∑l=s1+1r∑i=1dλj−1vjli,hcj⋅vjli,and (28) comes from the definition of ϒx+x−x+,h.Lemma 4.
Letb∈K and −r∈NKb. Then, for any v∈∂ΠKb−r,(29)Δb,Δr≥ϒbr,Δb,where Δb,Δr∈V satisfying Δb=vΔb+Δr.Proof.
Denotex≔b−r. Then,(30)b=ΠKb−r=ΠKxandb⋅r=r⋅b=0,b∈K,r∈K.
Thus, we assume thatx has the following spectral decomposition:(31)x=∑j=1sλjxcj+∑j=s1+1rλjxcjsatisfying (18), and b and r have the spectral decompositions as follows:(32)b=∑j=1sλjxcj,r=∑j=s1+1r−λjxcj.
From Proposition1, we have, for any V∈∂ΠKx, there exists W∈∂ΠKβ0 such that(33)Vh=∑j=1shjj+∑j=1s∑l=j+1s1hjl+∑j=1s∑l=s1+1rλjxλjx−λlxhjl+Wh.
Therefore, we have fromΔb=vΔb+Δr that(34)∑j=1sΔbjj+Δrjj+WΔb+Δr+∑j=1s∑l=j+1s1Δbjl+Δrjl+∑j=1s∑l=s1+1sλjxλjx−λlxΔbjl+Δrjl=∑j=1sΔbjj+∑j=s1rΔbjj+Δbββ+Δbαγ+Δbβγ+Δbγγ,which implies(35)∑j=1sΔrjj=0,∑j=s1+1rΔbjj=0,∑j=1s∑l=j+1s1Δrjl=0,∑l=s1+1r∑j=s+1l−1Δbjl=0,(36)∑j=1s∑l=s1+1rλjxλjx−λlxΔrjl+Δbjl=∑j=1s∑l=s1+1rΔbjl,(37)WΔb+Δr=Δbββ.
We can easily check that(38)WΔb+Δr=WΔbββ+Δrββ.
Then, by the properties of the projection of the metric projector in Lemma3,(39)Δbββ,Δrββ=WΔb+Δr,Δbββ+Δrββ−WΔb+Δr=Δbββ+Δrββ,W−W2Δbββ+Δrββ≥0.
Hence, by equations (35)–(37), we obtain from b†=∑j=1rλj−1xcj that(40)Δb,Δr=∑j=1sΔbjj+∑j=1s∑l=j+1rΔbjl+Δbββ,∑j=s1+1rΔrjj+∑l=s1+1r∑j=1l−1Δrjl+Δrββ≥∑j=1s∑l=s1+1rΔbjl,∑j=1s∑l=s1+1rΔrjl=−∑j=1s∑l=s1+1rλlxλjxΔbjl2=4r⋅Δb,b†⋅Δb=Υbr,Δb.
The proof is completed.


## 2.1. Euclidean Jordan Algebras

In this part, we show some useful notations and conclusions on Euclidean Jordan Algebras introduced in [23]. Suppose that F is the real field ℝ and V is a finite-dimensional vector space over F.For anyx∈V, denote(6)ℒxy≔x⋅yfor everyy∈V.The pairA≔V,⋅ defined over the real field ℝ is called a Euclidean Jordan algebra, if, for all x,y∈V:(i)
x⋅y=y⋅x(ii)
x⋅x2⋅y=x2⋅x⋅y, where x2≔x⋅x(iii)
x⋅y,zV=y,x⋅zVHere are some common concepts used in this paper.An elementc∈V is called to be the unit element of A if x⋅e=e⋅x=x for all x∈V. We always assume that there exists a unit element e∈V of A=V,⋅ in the following paper.If is called to be idempotent. If two idempotentsp and q satisfy p⋅q=0, they are called orthogonal. And k orthogonal idempotents c1,c2,…,ck are said to be a complete system if they satisfy(7)∑j=1kcj=e.If a nonzero idempotentq cannot be written as the sum of two other nonzero idempotents, we say q is primitive. And Jordan frame is a complete system of orthogonal primitive idempotents.The following theorem in [23] is very important to show the spectral decomposition.Theorem 1.
LetA=V,⋅ be a Euclidean Jordan algebra and RA=r. Then, for any x∈V,(8)x=∑j=1rλjxcj=λ1xc1+λ2xc2+⋯+λrxcr,where c1,c2,…,cr is a Jordan frame and λjx∈ℝ,j=1,…,r, satisfying λ1x≥λ2x≥⋯≥λrx.We say the numbersλ1x,λ2x,…,λrx to be eigenvalues of x. Then, x has the spectral decomposition (8) and(9)trx=∑j=1rλjx.Therefore, another associative inner product can be defined by usingtrx: x,y≔trx⋅y,x,y∈V. Let ⋅ be the norm on V induced by this inner product, then(10)x≔x,x=∑j=1rλj2x,x∈V.For a scalar-valued functionϕ:ℝ⟶ℝ, we define Löwner’s operator associated with A=V,⋅ from [24] as(11)ϕVx≔∑j=1rϕλjxcj=ϕλ1xc1+ϕλ2xc2+⋯+ϕλrxcr,where x=∑j=1rλjxcj∈V.The metric projection operator on(12)K≔y2:y∈Vcan be described by Löwner’s operator using ϕt=max0,t as follows:(13)ΠKx=x+=λ1x+c1+λ2x+c2+⋯+λrx+cr,which is very important in the following research.It is known from ([23], Theorem III.2.1) that the above cone K=y2:y∈V is a self-dual homogeneous closed convex cone, we call it a symmetric cone, which is the constraint set of problem (1)For a Jordan frame ofAc1,c2,…,cr, we denote Vij as follows:(14)Vij≔Vci,1,i=j,Vci,12∩Vcj,12,i≠j.Suppose thatCijx is the orthogonal projection onto Vij. Then, Cijx has the following expression:(15)Cjlx=∑i=1dvjli,⋅vjli,where vjlii=1d∈V denotes orthonormal vectors and d satisfies n=r+d/2rr−1.It follows from [25] that(16)h=∑j=1rCjjxh+∑1≤j<l≤rCjlxh=∑j=1rcj,hcj+∑1≤j<l≤r4cj⋅cl⋅h,∀h∈V.Actually, all the eigenvectors(17)c1,c2,…,cr,vjl1,vjl2,…,vjld,1≤j<l≤rform an orthonormal basis of V.Assume that there exist two integerss and s1 such that(18)λ1x≥⋯≥λsx>0=λs+1x=⋯=λs1x>λs1+1x≥⋯≥λrx.Let us introduce three index sets:(19)α≔1,…,s,β≔s+1,…,s1,andγ≔s1+1,…,r.For1≤j≤l, denote(20)hjj≔Cjjxh=cj,hcj,hjl≔Cjlxh=∑i=1dvjli,hvjli,hαα=∑j=1shjj+∑1≤j<l≤shjl,hαβ=∑j=1s∑l=s+1s1hjl,hαγ=∑j=1s∑l=s1+1rhjl,hββ=∑j=s+1s1hjj+∑s+1≤j<l≤s1hjl,hβγ=∑j=s+1s1∑l=s1+1rhjl,hγγ=∑j=s1+1rhjj+∑s1+1≤j<l≤rhjl.For the merit projectorΠK onto the symmetric cone, Sun and Sun [25] has proved that ΠK is strongly semismooth everywhere. Wang [17] gave a characterization pertaining the structure of the B-subdifferential of ΠK. Recently, Kong, Tunçel, and Xiu presented an exact expression for B-subdifferential and Clarke’s generalized Jacobian of ΠK [14, 15]. Here, we rewrite the conclusion obtained by Kong et al. [15] as follows.Proposition 1.
Letx=∑j=1rλjxcj and the indexsets α,β,γ be given by (19). Then, for any V∈∂ΠKx, there exists W∈∂ΠKβ0 such that(21)Vh=∑j=1shjj+∑j=1s∑l=j+1s1hjl+∑j=1s∑l=s1+1rλjxλjx−λlxhjl+Wh,where Kβ is the symmetric cone in subspace Vββ≔⊕i≤j,i∈β,j∈βVij.In order to describe the optimality conditions of NSCP (1), we need the expressions of some important sets, such as the tangent cone of K at x+TKx+, the linearity of TKx+linTKx+, critical cone Cx+, and the affine space of Cx+, denoted by affCx+. As Wang [17] and Kong et al. [15] have obtained the characterizations independently, we only show the topological results in the following proposition.Proposition 2.
Letx have eigenvalues as in (18). It holds that(22)TKx+=z:hββ+hβγ+hγγ≽0,(23)linTKx+=h:hββ=0,hβγ=0,hγγ=0,(24)Cx+=h:hββ≽0,hβγ=0,hγγ=0,(25)affCx+=h:hβγ=0,hγγ=0.


## 2.2. A Linear-Quadratic Function

Inspired by the works by Bonnans and Shapiro [2] and Sun [9], we define a linear-quadratic function as follows, which is vital for establishing a kind of strong second-order sufficient condition.Definition 1.
For any givenv∈V, define a linear-quadratic function ϒv:V×V⟶ℜ by(26)ϒvz,h≔4z⋅h,v†⋅h,z,h∈V×V,where v† is the Moore–Penrose pseudoinverse of v.Here, the linear-quadratic function is different from Definition 3.2 in [15]. Even in the especial case, v∈K and v⋅z=0, the value of the linear-quadratic function (26) is twice the one in [15].For the linear-quadratic function (16), we have the following conclusions.Proposition 3.
Ifh∈affCx+, then(27)ϒx+x−x+,h=∑j=1s∑l=s1+1rλlλjhjl2.Proof.
Asx+=∑j=1sλjcj,x−x+=∑j=s1+1rλjcj, we have(28)x−x+⋅h=∑j=1s∑l=s1+1r∑i=1dλlvjli,hcl⋅vjli,n!r!n−r!,x+†⋅h=∑j=1sλj−1cj,hcj+∑j=1s∑l=s1+1r∑i=1dλj−1vjli,hcj⋅vjli,and (28) comes from the definition of ϒx+x−x+,h.Lemma 4.
Letb∈K and −r∈NKb. Then, for any v∈∂ΠKb−r,(29)Δb,Δr≥ϒbr,Δb,where Δb,Δr∈V satisfying Δb=vΔb+Δr.Proof.
Denotex≔b−r. Then,(30)b=ΠKb−r=ΠKxandb⋅r=r⋅b=0,b∈K,r∈K.
Thus, we assume thatx has the following spectral decomposition:(31)x=∑j=1sλjxcj+∑j=s1+1rλjxcjsatisfying (18), and b and r have the spectral decompositions as follows:(32)b=∑j=1sλjxcj,r=∑j=s1+1r−λjxcj.
From Proposition1, we have, for any V∈∂ΠKx, there exists W∈∂ΠKβ0 such that(33)Vh=∑j=1shjj+∑j=1s∑l=j+1s1hjl+∑j=1s∑l=s1+1rλjxλjx−λlxhjl+Wh.
Therefore, we have fromΔb=vΔb+Δr that(34)∑j=1sΔbjj+Δrjj+WΔb+Δr+∑j=1s∑l=j+1s1Δbjl+Δrjl+∑j=1s∑l=s1+1sλjxλjx−λlxΔbjl+Δrjl=∑j=1sΔbjj+∑j=s1rΔbjj+Δbββ+Δbαγ+Δbβγ+Δbγγ,which implies(35)∑j=1sΔrjj=0,∑j=s1+1rΔbjj=0,∑j=1s∑l=j+1s1Δrjl=0,∑l=s1+1r∑j=s+1l−1Δbjl=0,(36)∑j=1s∑l=s1+1rλjxλjx−λlxΔrjl+Δbjl=∑j=1s∑l=s1+1rΔbjl,(37)WΔb+Δr=Δbββ.
We can easily check that(38)WΔb+Δr=WΔbββ+Δrββ.
Then, by the properties of the projection of the metric projector in Lemma3,(39)Δbββ,Δrββ=WΔb+Δr,Δbββ+Δrββ−WΔb+Δr=Δbββ+Δrββ,W−W2Δbββ+Δrββ≥0.
Hence, by equations (35)–(37), we obtain from b†=∑j=1rλj−1xcj that(40)Δb,Δr=∑j=1sΔbjj+∑j=1s∑l=j+1rΔbjl+Δbββ,∑j=s1+1rΔrjj+∑l=s1+1r∑j=1l−1Δrjl+Δrββ≥∑j=1s∑l=s1+1rΔbjl,∑j=1s∑l=s1+1rΔrjl=−∑j=1s∑l=s1+1rλlxλjxΔbjl2=4r⋅Δb,b†⋅Δb=Υbr,Δb.
The proof is completed.


## 3. Optimality Conditions and Nonsingularity

We consider nonlinear conic problem (1). Let x belong to the feasible set of problem (1). If(41)0∈inthxgx+h′xg′xX−0K,we say that Robinson’s constraint qualification holds at x. Then, there exists a Lagrange multiplier y,z∈ℜm×Y satisfying the following KKT conditions:(42)∇xLx,y,z=0,hx=0,−z∈NKgx,where(43)Lx,y,z=fx+y,hx−z,gxis the Lagrangian function of (1). Let Λx⊂ℜm×Y be the set of all the Lagrangian multipliers.It is easy to verify the KKT conditions (42) which can be equivalently expressed as(44)Fx,y,z=∇xLx,y,zhxgx−ΠKgx−z=∇xLx,y,zhxz−ΠKz−gx=0.For a general constraintGx∈K′,x∈X, where G:X⟶Y′ is a continuously differentiable function and K′⊆Y′ is a closed convex set, if for a feasible point x,(45)G′xX+linTK′Gx=Y′,then the constraint nondegeneracy condition holds at x. So, for conic optimization problem (1), the constraint nondegeneracy condition at x∗ has the following form:(46)h′x∗g′x∗X+0linTKgx∗=ℜmY.It follows from [2] that, if a locally optimal solution x∗ satisfies (46), then Λx∗ is a singleton.For a KKT pointx∗,y∗,z∗∈X×ℜm×Y of problem (1), suppose that u∗≔gx∗−z∗ has the spectral decomposition:(47)u∗=λ1c1+⋯+λrcr,satisfying(48)λ1≥⋯≥λs>0=λs+1=⋯=λs1>λs1+1≥⋯≥λr.Then,(49)gx∗=∑j=1sλjcj,z∗=−∑j=s1+1rλjcj.According to (23) and (25), we have(50)linTKgx∗=w∈Y:wββ=0,wβγ=0,wγγ=0.Although the critical coneCx∗ of problem (1) has an explicit formula(51)Cx∗=d∈X:f′x∗d≤0,h′x∗d=0,g′x∗d∈TKgx∗,affCx∗ is not easy to describe. Instead, we define the following outer approximation set to affCx∗ with respect to y∗,z∗:(52)appy∗,z∗=d∈X:h′x∗d=0,g′x∗dβγ=0,g′x∗dγγ=0.It is easy to get that, for anyy∗,z∗∈Λx∗,(53)affCx∗⊆appy∗,z∗.We now introduce a kind of strong second-order sufficient condition for problem (1), which is coincided with the strong second-order sufficient condition in [8, 9] when K is a SDP cone and a second-order cone.Definition 2.
Letx∗ be a feasible point of (1) such that constraint nondegeneracy condition (46) holds at x∗. We say that the strong second-order sufficient condition holds at x∗ if(54)d,∇xx2Lx∗,y∗,z∗d+Υgx∗z∗,g′x∗d>0,∀d∈appy∗,z∗∖0,where y∗,z∗=Λx∗⊂ℜm×Y and appy∗,z∗ is defined by (52).The following theorem establishes the relationship between the strong second-order sufficient condition and the nonsingularity of Clarke’s Jacobian of the mappingF defined by (44).Theorem 2.
Letx∗ is a local minimizer of (1). Assume that x∗,y∗,z∗∈X×ℜm×Y is a KKT point to (1). If the constraint nondegeneracy condition and the second-order sufficient condition (53) hold at x∗, then any element in ∂Fx∗,y∗,z∗ is nonsingular.Proof.
Firstly, we assume that the strong second-order sufficient condition (53) holds at x∗ with the constraint nondegeneracy condition (46). We shall prove that any W∈∂Fx∗,y∗,z∗ is nonsingular. Let Δx,Δy,Δz∈X×ℜm×Y satisfying the condition(55)WΔx,Δy,Δz=0.
Suppose thatu=gx∗−z∗ has the spectral decomposition (47) satisfying (48), then we can write gx∗ and z∗ in the form of (49). From Lemma 1, there exists V∈∂ΠKgx∗ such that(56)WΔx,Δy,Δz=∇xx2Lx∗,y∗,z∗Δx+∇hx∗Δy−∇gx∗Δz,−h′x∗Δx,−g′x∗Δx+Vg′x∗Δx−Δz=0.
From the third equality in (56), namely,(57)g′x∗Δx=Vg′x∗Δx−Δz,it has(58)∑j=s1+1rcj,g′x∗Δxcj=0,∑l=s1+1r∑j=s+1l−1∑i=1dvjli,g′x∗Δxvjli=0.
Then, it implies from (52) and (56) that(59)Δx∈appy∗,z∗,0=Δx,∇xx2Lx∗,y∗,z∗Δx+∇hx∗Δy−∇gx∗Δz=Δx,∇xx2Lx∗,y∗,z∗Δx+−Δz,g′x∗Δx.
Combining with the last equation of (36) and Lemma 4, we obtain(60)Δx,∇xx2Lx∗,y∗,z∗Δx+Υgx∗z∗,g′x∗Δx≤0.
Comparing with the strong second-order sufficient condition in the strong form (53), we get Δx=0. Thus, (36) can be expressed in the following form:(61)∇hx∗Δy−∇gx∗ΔzVΔz=0.
FromVΔz=0, we have(62)Δzαα=0,Δzαβ=0,Δzαγ=0.
Then, it follows from the nondegeneracy (46) that there exists a vector d∈X and w∈linTKgx∗ satisfying(63)h′x∗d=Δy,g′x∗d+w=−Δz.
Therefore, we have(64)Δy,Δy+Δz,Δz=Δy,h′x∗d−Δz,g′x∗d+w=−w,Δz=0,where the last equation can be obtained by (50) and (62). Thus, Δy=0,Δz=0. Together with Δx=0, we get that W is nonsingular. The proof is completed.


## 4. Application

In this section, as an application of the nonsingularity in Theorem2, we will study the sequential quadratic programming- (SQP-) type method to solving problem (1). Let xk,yk,zk be the current iteration point. The new iteration points xk+1,yk+1,zk+1 will be generated by solving the following quadratic problem:(Subk)(65)minΔx∇fxkTΔx+12ΔxTMkΔx,s.t.hxk+h′xkΔx=0,gxk+g′xkΔx∈K,where Mk≔Mxk,yk,zk and M:X×ℜm×Y⟶X×X is a matrix function satisfying Mx∗,y∗,z∗=∇xx2Lx∗,y∗,z∗. This model introduced in [18] to solve the classical nonlinear programming problems is used to solve the nonlinear SDP problems [26, 27] and nonlinear second-order cone programming problems [28, 29], where they may choose the different forms of M⋅,⋅,⋅.Theorem 3.
Suppose thatx∗,y∗,z∗∈X×ℜm×Y is a KKT point to (1) and the second-order sufficient condition (53) with constraint nondegeneracy condition holds at x∗x∗. Let the matrix function M:X×ℜm×Y⟶X×X satisfying Mx∗,y∗,z∗=∇xx2Lx∗,y∗,z∗ be semismooth at x∗,y∗,z∗. Then, for any xk,yk,zk∈U, a neighborhood of x∗,y∗,z∗, (39) has a KKT solution Δxk,yQPk,zQPk satisfying(66)Δxk+yQPk−y∗+zQPk−z∗=Oxk,yk,zk−x∗,y∗,z∗.Proof.
LetΔx,yQP,zQP be a KKT point of (Subk). Then,(67)∇fxk+zkΔx+∇hxkyQP−∇gxkzQP=0,hxk+h′xkΔx=0,gxk+g′xkΔx=ΠKgxk+g′xkΔx−zQP,namely,(68)F^Δx,yQP,zQP,xk,yk,zk=0,where(69)F^ζ,η,ξ,x,y,z≔∇fx+Mx,y,zζ+∇hxη−∇gxξ,hx+h′xζ,gx+g′xζ−ΠKgx+g′xζ−ξ.is a function with the variable ζ,η,ξ,x,λ,μ∈X×ℜm×Y×X×ℜm×Y. Let τ≔ζ,η,ξ∈X×ℜm×Y and ν≔x,λ,μ∈X×ℜm×Y. Let τ∗=0,y∗,z∗ and ν∗=x∗,y∗,z∗. We can easily have the following equation:(70)F^0,y∗,z∗,x∗,y∗,z∗=F^τ∗,ν∗=0.
By replacingxk,Mk in (65) with , we obtain a new problem expressed as (Sub∗), and 0,y∗,z∗ is an KKT point of (Sub∗).
Therefore, the strong second-order sufficient condition of (Sub∗) at 0,y∗,z∗ under the constraint nondegeneracy condition (46) has the same expression as condition (53). It is concluded from Theorem 2 that any element W∈ΠX×ℜm×Y∂F^τ∗,z∗ is nonsingular. Then, there exists a strong semismooth function τ⋅:U⟶X×ℜm×Y satisfying(71)τν∗=τ∗,F^τν,ν=0,∀ν∈U,where U is a neighborhood of ν∗. Denote Δxk,yQPk,zQPk≔τνk. Then, Δxk,yQPk,zQPk is a KKT point of (Subk) if νk∈U. By the strong semismoothness of τ⋅,(72)τνk−τ∗=Oνk−ν∗.
The proof is completed.
Now we present a local SQP method based on solving SQP-type model (Subk) in each iteration to solve (1).Next, the primal-dual quadratic convergence of Algorithm1 is demonstrated by using the semismoothness of M and Theorem 2.Algorithm 1: Local SQP method.
Step 0: for a given initial pointx1,y1,z1, calculate the value of hx1,gx1,∇fx1,h′x1 and g′x1. Set k≔1.Step 1: if∇xLxk,yk,zk=0,hxk=0,gxk∈Q, stop.Step 2: calculateMk=Mxk,yk,zk and find a KKT point Δxk,yQPk,zQPk of (Subk) by solving the KKT system (67).Step 3: setxk+1≔xk+Δxk,yk+1≔yQPk,zk+1≔zQPk.Step 4: calculatehxk+1,gxk+1,∇fxk+1,h′xk+1andg′xk+1. Set k≔k+1. Go to step 1.Theorem 4.
Suppose that all the hypotheses of Theorem3 still hold for Algorithm 1. Then, there exists a neighborhood U of x∗,y∗,z∗ such that, for any x1,y1,z1∈U, the sequence xk,yk,zk generated by Algorithm 1 converges to x∗,y∗,z∗ quadratically.Proof.
According to Theorem3, it is easy to verify that the algorithm is well-defined. Denote(73)δk≔xk,yk,zk−x∗,y∗,z∗.
We obtain(74)Δxk=Oδk,yk+1−y∗=Oδk,zk+1−z∗=Oδk,where Δxk is a solution to (65), and yk+1=yQPk,zk+1=zQPk is the associated multiplier.
AsMx∗,y∗,z∗=∇xx2Lx∗,y∗,z∗ and M is semismooth at x∗,y∗,z∗,(75)Mk−∇xx2Lx∗,y∗,z∗=Oxk,yk,zk−x∗,y∗,z∗.
It follows from the Taylor expansion to (67) at x∗,y∗,z∗, ∇xLx∗,y∗,z∗=0,xk+1=xk+Δxk, (74), and (75) that(76)∇xx2Lx∗,y∗,z∗xk+1−x∗+∇hx∗yk+1−y∗−∇gx∗zk+1−z∗=Oδk2,(77)h′x∗xk+1−x∗=Oδk2.
Because of the strongly semismoothness of the projection operatorΠK⋅, we get V∈∂ΠKgx∗−z∗ satisfying(78)ΠKgx∗−z∗=ΠKgxk+g′xkΔxk−zQPk+Vgx∗−z∗−gxk−g′xkΔxk+zQPk+Ogx∗−z∗−gxk−g′xkΔxk+zQPk2.
Since(79)gx∗−z∗−gxk−g′xkΔxk+zQPk=gx∗−gx∗−g′x∗xk−x∗+Oxk−x∗2−g′x∗Δxk+Oxk−x∗Δxk−z∗+zk+1g′x∗x∗−xk+1−z∗+zk+1+Oδk2,it is known that(80)ΠKgxk+g′xkΔxk−zQPk=ΠKgx∗−z∗−Vg′x∗x∗−xk+1−z∗+zk+1+Oδk2,which, together with ΠKgx∗−z∗=gx∗ and ΠKgxk+g′xkΔxk−zQPk=gxk+g′xkΔxk, implies(81)V−Ig′x∗xk+1−x∗−Vzk+1−z∗=Oδk2.
Following from (76), (77), with (81), we obtain(82)∇xx2Lx∗,y∗,z∗∇hx∗−∇gx∗h′x∗00−g′x∗+Vg′x∗0−Vxk+1−x∗yk+1−y∗zk+1−z∗=Oδk2.
Combining (46) and (54) with Theorem 2, we show that(83)xk+1−x∗yk+1−y∗zk+1−z∗=Oδk2,which means the quadratic convergence of the sequence xk,yk,zk. Then, we complete the proof.


## 5. Conclusion

In this paper, we discuss the nonlinear symmetric conic programming problems. We show that a kind of strong second-order sufficient condition, together with constraint nondegeneracy condition, implies the nonsingularity of Clarke’s generalized Jacobian of the mappingF at the KKT point. In the special cases of NLP, SCOP, and SDP, the converses are also true. Then, we demonstrate the local quadratic convergence of the SQP-type method for solving the nonlinear symmetric conic programming problems.



---

*Source: 8824126-2020-12-31.xml*