# Some Results about the Isolated Calmness of a Mixed Variational Inequality Problem

Authors: Yali Zhao; Hongying Li; Weiyi Qian; Xiaodong Fan
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

It is well known that optimization problem model has many applications arising from matrix completion, image processing, statistical learning, economics, engineering sciences, and so on. And convex programming problem is closely related to variational inequality problem. The so-called alternative direction of multiplier method (ADMM) is an importance class of numerical methods for solving convex programming problem. When analyzing the rate of convergence of various ADMMs, an error bound condition is usually required. The error bound can be obtained when the isolated calmness of the inverse of the KKT mapping of the related problem holds at the given KKT point. This paper is to study the isolated calmness of the inverse KKT mapping onto the mixed variational inequality problem with nonlinear term defined by norm function and indicator function of a convex polyhedral set, respectively. We also consider the isolated calmness of the inverse KKT mapping onto classical variational inequality problem with equality and inequality constrains under strict Mangasarian-Fromovitz constraint qualification condition. The results obtained here are new and very interesting.


---

## Body

## 1. Introduction

In this paper, let us consider the following mixed variational inequality problem: findx∈Rn such that (1)Fx,y-x+ϕy-ϕx≥0,∀y∈Rn,where F:Rn→Rn is a twice continuously differentiable mapping and ϕ:Rn→R∪+∞ is a proper convex lower semicontinuous functional. Problem (1) is denoted by MVIP(F,ϕ). Formulation of such problem was originally considered and studied by Brézis [1] in Hilbert space. It has been shown that a large class of obstacle, unilateral, contact, free, moving, and equilibrium problems arising in regional, physical, mathematical, engineering, and applied sciences can be studied in the unified and general framework of the mixed variational inequality problem. Some researchers considered and studied the existence of solutions and the numerical algorithms of the MVIP; for example, see [2] and the references therein.On the other hand, many important optimization problems can be reformulated as the mixed variational inequality problem (1) to study. For example, if F(x)=∇f(x), wheref:Rn→R is a continuously differentiable convex function, then (1) is related to the following convex optimization problem:(2)min⁡fx+ϕxs.t.Ax=b,gx≤0,where f:Rn→R- is a proper l.s.c. Convex function, g:Rn→Rp with g=(g1,…,gp) and each gi is a continuous convex function. Let us denote the feasible set of (2) by (3)K=x∈Rn:Ax=b,gx≤0.When there exists a vector x0∈Rn such that(4)Ax0=b,gx0<0,x0∈ridomϕ,then the optimality conditions for problem (2) coincide with the variational inequality (1). Indeed, problem (2) can be expressed as (5)minf^x=fx+ϕx+δKx,where δK is the indicator function of K. Obviously, f^ is a proper lower semicontinuous convex function and if x- is a solution to problem (2), then (6)0∈∂f^x-.Noting that (7)x0∈ridomf∩ridomϕ∩ridomδK,we have from [3] that (8)∂f^x-=∇fx-+∂ϕx-+NKx-.Noting that ∂[ϕ+δK](x-)=∂ϕ(x-)+NK(x-), we obtain from (6) and (8) that(9)-Fx-∈∂ϕ+δKx-,which implies from the definition of subdifferential that (10)0≤Fx-,y-x-+ϕy+δKy-ϕx-+δKx-,and this is an alternative expression for inequality (1) when x=x-.It is well known that optimization problem model (2) has many applications arising from matrix completion, image processing, and statistical learning. The so-called alternative direction of multiplier method (ADMM) is an importance class of numerical methods for solving problem (2). When analyzing the rate of convergence of various ADMMs, an error bound condition is usually required; see Han and Yuan (2013) [4], Hong and Luo (2017) [5], and Han et al. (2015) [6]. The error bound can be obtained when the isolated calmness of the inverse of the KKT mapping bolds at the given KKT point; see Han et al. [6] and this observation motivates us to study the stability of problem (1).The stability on variational inequalities is an important topic in optimization theory. For nonlinear programming, the strong regularity of the Karush-Kuhn-Tucker (KKT) system is completely characterized by Robinson (1980) [7] and Jongen et al. (1990) [8]. The equivalence of the strong regularity with the Aubin property for affine variational inequalities over convex polyhedral sets was established by Dontchev and Rockafellar (1996) [9]. Recently, results have been obtained for some matrix optimization problems. For instance, Y. Zhang and L. Zhang [10] proved the isolated calmness of the KKT mapping under the strict Robinson constraint qualification (SRCQ) and the second-order sufficient optimality condition for the nonlinear SDP problem. Han et al. [6] gave a characterization of isolated calmness of the KKT mapping for the convex composite quadratic semidefinite programming problems. Liu and Pan [11] extended the results in [6, 10] to the isolated calmness of the KKT mapping for the matrix optimization problem involving the epigraph cone of Ky Fan k-norm. Ding et al. [12] showed for a class of conic programming problems, under the Robinson constraint qualification, that the KKT solution mapping is robustly isolated calm if and only if both the strict Robinson constraint qualification and the second-order sufficient condition hold.Recently, Mordukhovich and Sarabi (2017) [13] established a set of conditions to characterize the robust isolated calmness of the KKT mapping for a type composite optimization problem; in particular, they adopted noncritical multiplier to characterize the isolated calmness. In our paper, the problem considered is a variational inequality, not a composite optimization problem; and we use second-order sufficient optimality conditions and the strict Robinson constraint qualification to ensure the isolated calmness of the solution mapping. In addition, we mainly discuss the isolated calmness of the inverse KKT mapping on problem (1) with nonlinear term ϕ defined by norm function and the indicator function of a convex polyhedral set, respectively. And we also consider the isolated calmness of the inverse KKT mapping on classical variational inequality problem with equality and inequality constrains under strict Mangasarian-Fromovitz constraint qualification condition.


## 2. Preliminaries

In this section, we first recall some related definitions and lemma, which are needed in the subsequent discussions.LetY be a finite dimensional real Euclidean space and S:Rn⇒Y be a set-valued mapping and (x-,y-)∈gphS.Definition 1.
The set-valued mappingS is said to be isolated calm at x- for y- if there exist a constant k>0 and neighborhoods U of x- and V of y- such that (11)Sx∩V⊂y-+kz-z-By∀x∈U,where By⊆Y is the unit ball in Y.The graphical derivative is a convenient tool for investigating the isolated calmness property.Definition 2 (see [14]).
The graphical derivative ofS at x- for y- is a set-valued mapping DSx-∣y-:Rn⇒Y defined by (12)DSx-∣y-u≔v∈Y∣u,v∈TgphSx-,y-.In the proof of the main theorem about the isolated calmness, we use the following basic characterization of the isolated calmness of the set-valued mappingS at x- for y-.Lemma 3 (King and Rockafellar [15], Levy [16]).
Let(x-,y-) ∈ gphS. Then S is isolated calm at x- for y- if and only if {0}=DSx-∣y-0.


## 3. The Isolated Calmness of MVIP

In this section, we consider MVIP(F,ϕ) (1), where F:Rn→Rn is a continuously differentiable mapping and ϕ:Rn→R- is a proper, lower semicontinuous and convex function. It is easy to know that MVIP(F,ϕ) (1) is equivalent to the following inclusion:(13)0∈Fx+∂ϕx.For an extended real-valued function f, the Moreau-Yosida regularization of f, denoted by eλf, is defined by (14)eλfx=infzfz+12λz-x2.It follows from [14] that, when f is a proper lower semicontinuous convex function, eλf is continuous differentiable and ∇eλf(x)=1/λx-pλfx, where pλf is the proximal mapping of f and defined by (15)pλfx=arg⁡minzfz+12λz-x2.The following lemma shows that (13) can be expressed as a nonsmooth equation. As it is an obvious result from the definition of the proximal mapping, we omit its proof.Lemma 4.
Equation (13) is equivalent to the following nonsmooth equation: (16)Fx+∇eλϕx-λFx=0or(17)x-pλϕx-λFx=0,for any λ>0.
Let(18)Gλx=x-pλϕx-λFx,which is named as KKT mapping for problem (1). Obviously, we have that the solution set for problem (1) is Gλ-1(0). Let x-∈Gλ-1(0). We discuss the isolated calmness of Gλ at (0,x-).From Lemma3, we can easily obtain the following result.Theorem 5.
Assume that the proximal mappingpλϕ is directionally differentiable. Then Gλ is isolated clam at (0,x-) if and only if (19)Gλ′x-;d=0⟹d=0.In the following, we consider two cases of MVIP: in the first caseϕ(z)=z1=∑i=1mzi, and in the second case ϕ(z)=δpz, where P is a convex polyhedral set. In particular, we consider the nonlinear complementarity problem, which corresponds to P=R+m in the second case.Case 1 (ϕ(z)=z1=∑i=1mzi).
We first introduce some notations. Letα={i:xi0>0}, β={i:xi0=0}, and γ={i:xi0<0} be three index sets such that β=βU∪βS∪βL, where (20)βU=i:xi0=0,Fix0=-1,βS=i:xi0=0,-1<Fix0<1,βL=i:xi0=0,Fix0=1.Let T={1,…,n}∖βS. Define the critical cone at x0 as follows:(21)Cx0=dT:0≤dβU⊥JxTFβUx0dT≥00≥dβL⊥JxTFβLx0dT≤0.We give a set of sufficient conditions for the isolated calmness of Gλ at a point (0,x0), where x0∈Gλ-1(0).Proposition 6.
LetF:Rn→Rn be a continuously differentiable mapping. Assume that x0∈Rn is a solution to problem (1) with ϕ(z)=z1 for z∈Rn. If for ∀dT∈C(x0)∖{0},(22)dT,JxTFTx0dT≠0,then Gλ is isolated calm at (0,x0).Proof.
Whenϕ(z)=z1, it is easy to obtain (23)v∈∂ϕx0⟺vi=1,xi0>0,∈-1,1,xi0=0,=-1,xi0<0.Therefore, we obtain the following equivalence:(24)-Fx0∈∂ϕx0⟺Fix0=-1,xi0>0,∈-1,1,xi0=0,=1,xi0<0.We consider the following equation in variable d:(25)d-pλϕ′x0-λFx0;d-λF′x0d=0.Nothing that pλϕ(y)=[y-λ]++[y+λ]-, we have that (25) can be equivalently expressed as(26)dβS=0,JxTFα∪γx0dT=0,0≤dβU⊥JxTFβUx0dT,0≥dβL⊥JxTFβLx0dT≤0.This implies that dT∈C(x0)∖{0}, dβS=0, and JxTFT(x0)dT=0. We have from condition (22) that dT=0. Thus, Gλ′(x-;d)=0 implies d=0 and from Theorem 5, Gλ is isolated calm at (0,x0). The proof is completed.Case 2 (ϕz=δP(z) where P is a convex polyhedral set).
For a convex coneK∈Rn, its dual, denoted by K∗, is defined by (27)K∗=w:v,w≥0,∀v∈K.For a point x0∈P, where P is a convex polyhedral set, the critical cone of the pair (P,F) at x0 is defined by(28)Cx0=TPx0∩Fx0⊥.Proposition 7.
LetF:Rn→Rn be a continuously differentiable mapping. Assume that x0∈Rn is a solution to problem (1) with ϕ(z)=δp(z) for z∈Rn. Then Gλ is isolated calm at (0,x0) if and only if (29)Cx0∋d⊥F′x0d∈Cx0∗⟹d=0.Proof.
In this case,(pλϕ)(y)=∏P(y), and ∂ϕ(y)=Np(y), so we have -λF(x0)∈Np(x0) for any λ>0. The equation Gλ′(x0;d)=0 is (30)d-pλϕ′x0-λfx0;d-λF′x0d=0,which is reduced to (31)d-∏′​P⁡x0-λFx0;d-λF′x0d=0.It follows from [17], for the directional derivative of the projection over a convex polyhedral set, that (31) is equivalent to(32)d-∏Cx0d-λF′x0d=0.As C(x0) is a convex polyhedral cone, (32) is actually the following cone complementarity: (33)Cx0∋d⊥F′x0d∈Cx0∗.Using condition (29), we obtain from Theorem 5, Gλ is isolated calm at (0,x0).Now we consider a special case whenP=R+n. Define(34)α=i:xi0=0,Fix0>0,β=i:xi0=0=Fix0,γ=i:x0>0,Fix0=0.Then we obtain the following result.Corollary 8.
The mappingGλ is isolated calm at (0,x0) if and only if (35)JβFβJγFβJβFγJγFγdβdγ∈R+β0⇓dβ=0,dγ=0.Proof.
Noting that, whenP=R+n, we have (36)Cx0=d:d∈TR+nx0,d⊥Fx0=d:dα=0,dβ≥0,Cx0∗=d:dβ≥0,dγ=0.We obtain the result from Proposition7.


## 4. VIP with Equality and Inequality Constraints

In this section, we consider the following variational inequality problem (for short, denoted by VIP): findx∈K such that(37)Fx,y-x≥0,∀y∈K,where(38)K=x∈Rn:hx=0,gx≤0,with h:Rn→Rp and g:Rn→Rp being twice continuously differentiable.Letx- be a solution to VIP (37). We need the following assumption.Assumption 9.
The constraint setK satisfies Mangasarian-Fromovitz constraint qualification at x-, namely,
(i)∇h1(x-),…,∇hq(x-) are linearly independent;
(ii) there exists a vectord0∈Rn such that (39)∇hjx-Td0=0,j=1,…,q,∇gix-Td0<0,i∈Ix-,where I(x-)={i:gi(x-)=0,i=1,…,p}.
Under Assumption9, the normal cone of K at x- coincides with the regular normal cone, which is given by (40)NKx-=N^Kx-=RangeJhx-T+Jgx-Tλ:0≤λ⊥gx-.From the definition of regular normal cone, if x- is a solution to VIP (37), then we have(41)0∈Fx-+N^Kx-.Therefore, we obtain from (40) that there exists (μ-,λ-)∈Rq×Rp such that (42)0=Fx-+Jhx-Tμ-+Jgx-Tλ-,hx-=0,0≤λ-⊥gx-≤0.System (42) is named as the KKT conditions for VIP (37). The set of all points (x-,μ-,λ-) satisfying (42) is denoted by Ω-.
Define(43)Gx,μ,λ=Fx+JhxTμ+JgxTλhx=0gx-∏R-pgx+λ.Obviously, we have G-1(0)=Ω-. We discuss the isolated calmness of G-1 at a point (0,(x-,μ-,λ-)). In order to obtain our main results, we need the following lemmas.Lemma 10.
Leta∈R-p, b∈NR-P(a), Δa, and Δb∈Rp satisfy(44)Δa-∏R-pa+b,Δa+Δb=0.Then (i)
Δa∈TR-p(a)∩b⊥;(ii)
〈Δa,Δb〉=0;(iii)
Δb∈[TR-p(a)∩b-1]o.Proof.
From Facchinei and Pang (2003), we have(45)∏R-pa+b,Δa+Δb=∏TR-pa∩b⊥Δa+Δb.Thus, we obtain from (44) that (46)Δa=∏TRPa∩b⊥Δa+Δb,which implies(47)TR-pa∩b⊥∋Δa⊥Δb∈TR-pa∩b⊥o.Thus, we get the properties (i), (ii), and (iii).Lemma 11.
LetA1∈Rq×n, A2∈Rp×n, a∈R-P, and b∈NR-P(a) satisfy(48)ARn+TR-pa∩b⊥=Rq+p,where A=[A1,A2], and then (49)A1TΔa+A2TΔb=0,∏′​R-P⁡a+b,Δb=0⇓Δa=0,Δb=0.Proof.
For(Δa,Δb)∈[ARn+TR-p(a)∩b⊥]o, one has(50)AΤΔa,Δb=0,Δb∈TR-pa∩b⊥o,A1ΤΔa+A2ΤΔb=0,∏R-P∩b⊥Δb=0⟺∏R-Pa+b,Δb=0.Thus, the conclusion comes from the polar of the left-side of (48) being a zero cone. The proof is completed.Theorem 12.
Assume thatF is continuously differentiable. Let (x-,μ-,λ-)∈Rn×Rq×Rp. Consider the following conditions:
(i)x-,μ-,λ-∈G-10≠ϕ.
(ii) For anyd∈Cx-∖0.(51)JLx-,μ-,λ-d,d>0;
(iii) Strict Mangasarian-Fromovitz constraint qualification holds:(52)Rq+p=Jhx-Jgx-gx-∏R-pgx+λRn+T0q×R-p0,gx-∩μ-λ-⊥.If conditions (i), (ii), and (iii) are satisfied, then G-1 is isolated calm at 0,x-,μ-,λ-.Proof.
We only check the following implication:(53)G′x-,μ-,λ-;d⟹d=0,where d=(dx,dμ,dλ)∈Rn×Rq×Rp. By direct calculation, we obtain from (53) that(54)Lx-,μ-,λ-dx+Jhx-Τdμ+Jgx-Τdλ=0,Jhx-dx=0,Jgx-dx-∏′​R-p⁡gx-+λ-,Jgx-dx+dλ=0.It follows from Lemma 10 that(55)Jgx-dx∈TR-pgx-∩λ-⊥,dλ-∈TR-pgx-∩λ-⊥o,Jgx-d,dλ=0.From KKT conditions for VIP (37), we have(56)Fx-Τdx=-Jhx-Τμ--Jgx-Τλ-Τdx=-μ-,Jhx-dx-λ-,Jgx-dx=0.Combining the above properties about d, we have that dx∈C(x-). Then, by premultiplying dxΤ to the first line of (55), we get(57)dx,JxLx-,μ-,λ-dx=0,implying dx=0 from (ii).
Noticingdx=0, we have from (55) that(58)Jhx-Τdu+Jgx-Τdλ=0,∏′​R-p⁡gx-+λ,dλ=0.We simplify (iii) as(59)Jhx-Jgx-Rn+0TR-pgx-∩λ-⊥=Rq+p.We obtain from Lemma 11 and (58) that dμ=0, dλ=0, which completed the proof.Remark 13.
An interesting question is whether (i), (ii), and (iii) are necessary for the isolated calmness ofG-1 at (0,(x-,μ-,λ-)). In the near future, we will pay attention to the study of this question.



---

*Source: 2728967-2018-04-08.xml*