# Stability Analysis of Stochastic Generalized Equation via Brouwer’s Fixed Point Theorem

Authors: Qiang Liu; Jie Zhang; Shuang Lin; Li-wei Zhang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The stochastic generalized equation provides a unifying methodology to study several important stochastic programming problems in engineering and economics. Under some metric regularity conditions, the quantitative stability analysis of solutions of a stochastic generalized equation with the variation of the probability measure is investigated via Brouwer’s fixed point theorem. In particular, the error bounds described by Hausdorff distance between the solution sets are established against the variation of the probability measure. The stability results obtained are finally applied to a stochastic conic programming.


---

## Body

## 1. Introduction

In this paper, we focus on the following stochastic generalized equation (SGE): findx∈Rn such that(1)0∈EPFx,ξω+Gx,where F:Rn×Ξ→Rm is a continuous function, ξ:Ω→Ξ is a random vector defined on a probability space (Ω,F,P) with support set Ξ⊆Rk, EP[·] denotes the expected value with respect to P, and G:Rn⇉Rm is an outer semicontinuous set-valued mapping. Throughout the paper, we assume that EP[F(x,ξ(ω))] is well defined for any x∈Rn. To ease notation, we will use ξ to denote either the random vector ξ(ω) or an element of Rk depending on the context.Model (1) a natural extension of deterministic parametric generalized equation [1] and the study of stochastic generalized equations can be traced down to King and Rockafellar’s early work [2]. In a particular case when G(·) is a normal cone operator NK(·) in which K is a closed convex cone in Rm, (1) reduces to a stochastic variational inequality problem (SVIP) which has been intensively studied over the past few years; see for instance [3–7] and the references therein. The research ranges from numerical schemes such as stochastic approximation method and Monte Carlo method to the fundamental theory and applications.In this paper, we concentrate our research on the stability of (1); namely, we look into the impact of variation of probability measure P on the solution of the SGE. Like similar existing research in deterministic generalized equation, this kind of stability analysis would address a number of fundamental theoretical issues including robustness, accuracy, and reliability of an optimal solution or an equilibrium against errors arising from the problem data or numerical schemes. Let Q denote a perturbation of the probability measure P. We consider the following perturbed stochastic generalized equations: find a vector x∈Rn such that(2)0∈EQFx,ξ+Gx.Let S(P) and S(Q) denote the solution set of (1) and (2), respectively. We investigate the relationship between S(Q) and S(P) as Q approximates P under some appropriate metric.Shapiro et al. [8] first discussed the sample average approximation (SAA) approach for (1). This method can be seen a special case of the perturbation of P (see Section 4 in this paper). They carried out comprehensive analysis including the existence and convergence of solutions. In our previous work [9], the consistency of Lipschitz-like property of solution map to (1) and its SAA counterpart have been studied. However, the above two studies only focus on the asymptotic analysis and are not related to the quantitative stability analysis. Recently, Liu et al. [7] have studied the qualitative stability of solutions of SGE (1) with F being a set-valued mapping as the underlying probability measure P varies. The results are applied to study the stability of stationary points of several stochastic optimization problems.In this paper, we follow Liu et al.’s approach to investigate the existence and quantitative stability analysis of solutions of problem (1) when P varies under some appropriate metric. We complement the results of Liu et al. on the issues essentially on twofold: (a) we use Brouwer’s fixed point theorem and metric regularity rather than Kummer’s results as in [7] to derive conditions for the existence of a solution to perturbation problem (2); (b) by Brouwer’s fixed point theorem, we establish the error bounds described by Hausdorff distance between solution sets, instead of the one described by distance from point to set as in [7], to show the quantitative stability of (1) when P varies. We also apply the results to analyze the convergence of SAA method for a class of stochastic conic programming and establish the corresponding error bounds.This paper is organized as follows: Section2 gives preliminaries needed throughout the paper. In Section 3, by Brouwer’s fixed point theorem, the existence of solution to perturbation problem (2) is investigated. Section 3 provides quantitative stability analysis of problem (1) when P varies under some appropriate metric. In particular, error bounds described by Hausdorff distance between S(P) and S(Q) are established. Finally, in Section 4, we apply the results obtained to obtaining quantitative convergence analysis of SAA method for a stochastic conic programming.


## 2. Preliminaries

### 2.1. Notation

Throughout this paper we use the following notations. Let· denote the Euclidean norm of a vector or the Frobenius norm of a matrix and d(x,D)≔infx′∈D⁡x-x′ denote the distance from point x to set D. For a multifunction Φ, gphΦ denotes its graph and for a set Ξ, intΞ denotes its interior. For an extended real-valued function φ:Rn→R∪±∞, ∇φ(x) denotes the gradient of φ at x. For a continuously differentiable mapping ϕ:Rn→Rm, Jϕ(x) denotes the Jacobian matrix of ϕ at x. We use Bn to denote the closed unite ball in Rn, B(x,δ) the closed ball around x of radius δ>0, and I the identity matrix. For two sets A,C⊂Rn, we denote by (3)DA,C≔inf⁡t≥0:A⊂C+tBnthe deviation of set A from the set C and(4)HA,C≔max⁡DA,C,DC,Athe Hausdorff distance between A and C. We use A+C to denote the Minkowski addition of two sets; that is, {a+c:a∈A,c∈C}. For the multifunction Φ:Rn⇉Rm, the set (5)lim⁡supx→x0⁡Φx≔y∈Rm:∃xk⟶x0,yk⟶ywithyk∈Φxk,∀kis called theouter limit of Φ as x→x0. If lim⁡supx→x0⁡Φ(x)⊂Φ(x0), then Φ isouter semicontinuous at x0 (see [10]). It follows from the definition that Φ is outer semicontinuous if and only if gphΦ is closed.


### 2.2. Some Basic Concepts and Results in Set-Valued and Variational Analysis

Given a closed setC⊂Rn and a point x¯∈Ξ, the cone (6)N^Cx¯≔x∗∈Rnlim⁡supx→Ξx¯⁡x∗,x-x¯x-x¯≤0is called theFréchet normal cone to C at x¯. Then thelimiting normal cone (also known as Mordukhovich normal cone or basic normal cone) to C at x¯ is defined by (7)NCx¯≔lim⁡supx→Cx¯⁡N^Cx;see for instance [11]. It follows from the definition that the set-valued mapping NC:Rn→NC(x) is outer semicontinuous at x¯∈C and(8)N^Cx¯⊆NCx¯.If inclusion (8) becomes equality, we say that C isnormally regular at x¯ (or Clarke regular by [10]). According to [10, Theorem 6.9], each convex set is normally regular at all its points.IfC=C1×C2 for closed Ci∈Rni, i=1,2, then at any x¯=(x¯1,x¯2) with x¯i∈Ci, one has (9)NCx¯=NC1x¯1×NC2x¯2.For set-valued maps, the definition of coderivative was introduced by Mordukhovich in [12] based on the limiting normal cone.Definition 1.
Consider a mappingS:Rn⇉Rm and a point x¯∈domS. The coderivative of S at x¯ for any u¯∈S(x¯) is the mapping D∗S(x¯,u¯):Rm⇉Rn defined by (10)D∗Sx¯,u¯y=v:v,-y∈NgphSx¯,u¯.The notation D∗S(x¯,u¯) is simplified to D∗S(x¯) when S is single-valued at x¯, S(x¯)={u¯}.One of the tasks of variational analysis is to detect the stability of a nonlinear system when perturbations of the data occur. For this purpose, the following notations are related; see [11].Definition 2.
Consider the multifunctionF:Rm⇉Rn. (a)
(Metric regularity) we say thatF-1 is metrically regular at x¯ for y¯ with (x¯,y¯)∈gphF-1 if there are some τ>0 and some neighborhoods U of x¯ and V of y¯ such that (11)dx,Fy≤τdy,F-1x,∀x∈U,y∈V.(b)
(Lipschitz-like property) we say thatF is Lipschitz-like around (y¯,x¯)∈gphF, if there exist some κ>0 and some neighborhoods U of x¯ and V of y¯ such that (12)Fy′∩U⊂Fy+κy′-yBn∀y,y′∈V.(c)
(Calmness) we say thatF is calm at (y¯,x¯)∈gphF if there exist some k>0 and some neighborhoods U of x¯ and V of y¯ such that (13)dx,Fy¯≤ky-y¯,∀y∈V,x∈Fy∩U.We know from the definition that the calmness property is weaker than the Lipschitz-like property. As shown in [11], the metrical regularity of F-1 at x¯ for y¯ is equivalent to the Lipschitz-like of F around (y¯,x¯)∈gphF, which is equivalent to the coderivative condition(14)D∗Fy¯,x¯0=0.This condition is the famous Mordukhovich criterion.


### 2.3. Pseudometric

LetB denote the sigma algebra of all Borel subsets of Ξ and P be the set of all probability measures of the measurable space (Ξ,B) induced by ξ. To investigate the relationship between the solution sets of SGE (2) and (1) when the underlying probability metric P varies, we need to define a metric which is closely related to the involved random functions.LetX be a compact subset of Rn. We start by introducing a distance function for the set P, which is appropriate for our problem. Define the set of random functions:(15)G≔g·:gξ≔Fx,ξ,x∈X.The distance function for any probability measures P,Q∈P is defined by (16)DQ,P≔supg∈G⁡EPgξ-EQgξ.This type of distance was used by Römisch (see [13, Section 2.2]) for the stability analysis of stochastic programming and was called pseudometric in that it satisfies all properties of a metric except that D(Q,P)=0 does not necessarily imply P=Q unless the set of functions G is sufficiently large. It is well known that D is nonnegative and symmetric and satisfies the triangle inequality; see [13, Section 2.1].


## 2.1. Notation

Throughout this paper we use the following notations. Let· denote the Euclidean norm of a vector or the Frobenius norm of a matrix and d(x,D)≔infx′∈D⁡x-x′ denote the distance from point x to set D. For a multifunction Φ, gphΦ denotes its graph and for a set Ξ, intΞ denotes its interior. For an extended real-valued function φ:Rn→R∪±∞, ∇φ(x) denotes the gradient of φ at x. For a continuously differentiable mapping ϕ:Rn→Rm, Jϕ(x) denotes the Jacobian matrix of ϕ at x. We use Bn to denote the closed unite ball in Rn, B(x,δ) the closed ball around x of radius δ>0, and I the identity matrix. For two sets A,C⊂Rn, we denote by (3)DA,C≔inf⁡t≥0:A⊂C+tBnthe deviation of set A from the set C and(4)HA,C≔max⁡DA,C,DC,Athe Hausdorff distance between A and C. We use A+C to denote the Minkowski addition of two sets; that is, {a+c:a∈A,c∈C}. For the multifunction Φ:Rn⇉Rm, the set (5)lim⁡supx→x0⁡Φx≔y∈Rm:∃xk⟶x0,yk⟶ywithyk∈Φxk,∀kis called theouter limit of Φ as x→x0. If lim⁡supx→x0⁡Φ(x)⊂Φ(x0), then Φ isouter semicontinuous at x0 (see [10]). It follows from the definition that Φ is outer semicontinuous if and only if gphΦ is closed.


## 2.2. Some Basic Concepts and Results in Set-Valued and Variational Analysis

Given a closed setC⊂Rn and a point x¯∈Ξ, the cone (6)N^Cx¯≔x∗∈Rnlim⁡supx→Ξx¯⁡x∗,x-x¯x-x¯≤0is called theFréchet normal cone to C at x¯. Then thelimiting normal cone (also known as Mordukhovich normal cone or basic normal cone) to C at x¯ is defined by (7)NCx¯≔lim⁡supx→Cx¯⁡N^Cx;see for instance [11]. It follows from the definition that the set-valued mapping NC:Rn→NC(x) is outer semicontinuous at x¯∈C and(8)N^Cx¯⊆NCx¯.If inclusion (8) becomes equality, we say that C isnormally regular at x¯ (or Clarke regular by [10]). According to [10, Theorem 6.9], each convex set is normally regular at all its points.IfC=C1×C2 for closed Ci∈Rni, i=1,2, then at any x¯=(x¯1,x¯2) with x¯i∈Ci, one has (9)NCx¯=NC1x¯1×NC2x¯2.For set-valued maps, the definition of coderivative was introduced by Mordukhovich in [12] based on the limiting normal cone.Definition 1.
Consider a mappingS:Rn⇉Rm and a point x¯∈domS. The coderivative of S at x¯ for any u¯∈S(x¯) is the mapping D∗S(x¯,u¯):Rm⇉Rn defined by (10)D∗Sx¯,u¯y=v:v,-y∈NgphSx¯,u¯.The notation D∗S(x¯,u¯) is simplified to D∗S(x¯) when S is single-valued at x¯, S(x¯)={u¯}.One of the tasks of variational analysis is to detect the stability of a nonlinear system when perturbations of the data occur. For this purpose, the following notations are related; see [11].Definition 2.
Consider the multifunctionF:Rm⇉Rn. (a)
(Metric regularity) we say thatF-1 is metrically regular at x¯ for y¯ with (x¯,y¯)∈gphF-1 if there are some τ>0 and some neighborhoods U of x¯ and V of y¯ such that (11)dx,Fy≤τdy,F-1x,∀x∈U,y∈V.(b)
(Lipschitz-like property) we say thatF is Lipschitz-like around (y¯,x¯)∈gphF, if there exist some κ>0 and some neighborhoods U of x¯ and V of y¯ such that (12)Fy′∩U⊂Fy+κy′-yBn∀y,y′∈V.(c)
(Calmness) we say thatF is calm at (y¯,x¯)∈gphF if there exist some k>0 and some neighborhoods U of x¯ and V of y¯ such that (13)dx,Fy¯≤ky-y¯,∀y∈V,x∈Fy∩U.We know from the definition that the calmness property is weaker than the Lipschitz-like property. As shown in [11], the metrical regularity of F-1 at x¯ for y¯ is equivalent to the Lipschitz-like of F around (y¯,x¯)∈gphF, which is equivalent to the coderivative condition(14)D∗Fy¯,x¯0=0.This condition is the famous Mordukhovich criterion.


## 2.3. Pseudometric

LetB denote the sigma algebra of all Borel subsets of Ξ and P be the set of all probability measures of the measurable space (Ξ,B) induced by ξ. To investigate the relationship between the solution sets of SGE (2) and (1) when the underlying probability metric P varies, we need to define a metric which is closely related to the involved random functions.LetX be a compact subset of Rn. We start by introducing a distance function for the set P, which is appropriate for our problem. Define the set of random functions:(15)G≔g·:gξ≔Fx,ξ,x∈X.The distance function for any probability measures P,Q∈P is defined by (16)DQ,P≔supg∈G⁡EPgξ-EQgξ.This type of distance was used by Römisch (see [13, Section 2.2]) for the stability analysis of stochastic programming and was called pseudometric in that it satisfies all properties of a metric except that D(Q,P)=0 does not necessarily imply P=Q unless the set of functions G is sufficiently large. It is well known that D is nonnegative and symmetric and satisfies the triangle inequality; see [13, Section 2.1].


## 3. Main Results

In this section, we discuss existence and quantitative stability analysis of solutions to the perturbed SGE (2). To this end, we assume that X⊂Rn is a compact and convex set throughout the section and make the following assumptions.Assumption 3.
LetP^⊂P be a set of probability measures such that P,Q∈P^. The following hold: (a)
F(x,ξ) is continuous at x∈Rn for each ξ∈Ξ and there exists κ(ξ) satisfying supP∈P^⁡EP[κ(ξ)]<∞ such that F(x,ξ)<κ(ξ) for each x∈Rn and ξ∈Ξ.(b)
F(x,ξ) is continuously differentiable at x∈Rn for each ξ∈Ξ and there exists τ(ξ) satisfying supP∈P^⁡EP[τ(ξ)]<∞ such that JxF(x,ξ)<τ(ξ) for each x∈Rn and ξ∈Ξ.We know from [8, Theorem 7.43, 7.44] that condition (a) in Assumption 3 means that for Q∈P^, EQFx,ξ is well defined and continuous at each x∈Rn and under condition (b) in Assumption 3, EQ[F(x,ξ)] is continuously differentiable and JEQ[F(x,ξ)]=EQ[JxF(x,ξ)].


### 3.1. Existence of a Solution to the Perturbed SGE

We now turn to discuss existence of a solution to the perturbed SGE (2). This issue has been investigated in [7] based on the results of deterministic generalized equations in Kummer [14] under the assumption of convexity of EP[F(x,ξ)]+G(x). Without this assumption, we derive the existence results based on the metric regularity.Theorem 4.
Suppose thatS(P)≠∅ and there exist x¯∈S(P) such that x¯∈intX. If condition (a) in Assumption 3 holds and (a) ΨP(x)=EP[F(x,ξ)]+G(x) is metrically regular at x¯ for 0 and (b) ΨP-1(·) is a convex-valued multifunction, then S(Q)≠∅ for all Q close to P.Proof.
We know from metric regularity ofΨP(x)=EP[F(x,ξ)]+G(x) at x¯ for 0 that there exist positive constants γ, ε, and δ such that (17)dx,ΨP-1q≤γdq,ΨPxfor x∈B(x¯,δ)∩X and q∈B(0,ε). Since ΨP-1 is a convex-valued multifunction, by [15, Theorem 2.2], we can define a continuous function x^(·):B(0,ε)↦B(x¯,δ)∩X such that x^(q)∈ΨP-1(q) for q∈B(0,ε) and(18)x¯-x^q≤γdq,ΨPx¯≤γq.For each Q, let ΥQ(x)=EP[F(x,ξ)]-EQ[F(x,ξ)] and δ′=min⁡{ε,1/2γ-1δ}. Since under condition (a) in Assumption 3,(19)supx∈X⁡ΥQx=DQ,P⟶0as Q is close to P, there exists δ1>0 such that (20)supQ∈UP,δ1,x∈X⁡ΥQx≤δ′.This implies that ΥQ(x)∈B(0,ε) for Q∈U(P,δ1) and x∈X. Therefore, by (18), we can define a function(21)H^Q:Bx¯,δ∩X⟶Bx¯,δ∩Xx⟼x^∘ΥQxfor Q∈U(P,δ1). This is a continuous mapping from the compact convex set B(x¯,δ)∩X to itself. By Brouwer’s fixed point theorem, H^Q has a fixed point in B(x¯,δ). We assume that it is xQ; then (22)xQ=H^QxQ∈ΨP-1q^QxQ,which means that (23)EPFxQ,ξ-EQFxQ,ξ∈EPFxQ,ξ+Gx.Therefore, (24)0∈EQFxQ,ξ+Gxand hence S(Q)≠∅ for all Q close to P.Remark 5.
In the case whenG(x)≡K in (1) with K being a closed convex set, we may have more simple results; that is, if 0∈int{EP[F(X,ξ)]+K}, then S(P)≠∅ and S(Q)≠∅ for Q close to P.Corollary 6.
Suppose thatG(x)≡NK(x) in (1) with K being a closed convex set and NK being a normal cone operator and S(P)≠∅. Suppose that there exist x¯∈S(P) such that x¯∈intX and Assumption 3 holds. If EP[F(·,ξ)] is monotone on K and condition(25)0∈D∗NKx¯,-EPFx¯,ξy∗+JEPFx¯,ξTy∗⟹y∗=0holds, then S(Q)≠∅ for Q close to P.Proof.
We only need to verify the conditions in Theorem4. We know from [16, Theorem 3.2] that if condition (b) in Assumption 3 holds, then under condition (25), ΨP(x)=EP[F(x,ξ)]+NK(x) is metrically regular at x¯ for 0. This verifies condition (a) in Theorem 4. Since EP[F(·,ξ)] is monotone on K, we have (26)EPFx,ξ-q-EPFy,ξ-qTx-y≥0for x,y∈K, which means that EP[F(·,ξ)]-q is monotone on K for any q∈Rn. Then EP[F(·,ξ)]-q is monotone on K, which, by [17, Theorem 2.3.5] and condition (a) in Assumption 3, means that ΨP-1(q)=x:q∈EPFx,ξ+NKx is a convex-valued mapping; this verifies condition (b) in Theorem 4.Remark 7.
We make some comments on the conditions in Corollary6. (i) The condition that there exists x¯∈S(P) such that x¯∈intX is reasonable in that, by [17, Proposition 2.28] and its proof, S(P) is nonempty if and only if there exists a closed set X with intX≠∅ such that 0∈EP[F(x,ξ)]+NK∩X(x) has a solution in intX. In particular, X can be taken to a closed Euclidean ball with the fact that a solution x¯ of S(P) is the center. In this case, we know that x¯ is also a solution of 0∈EP[F(x,ξ)]+NK(x). (ii) In [16, Theorem 3.2], under a calmness condition, condition (25) implies the metrical regularity of ΨP(x) at x¯ for 0. In fact, in our case, by Definition 1, such calmness condition holds naturally by the Mordukhovich’s criterion.


### 3.2. Stability of SGE

In this section, we undertake stability analysis of SGE (1), namely, investigating the relationship between the set of solutions to the perturbed SGE (2) and SGE (1) when probability measure Q is close to P under the pseudometric defined in the preceding section.Theorem 8.
Suppose thatS(P)≠∅, S(Q)≠∅ for Q close to P, and condition (a) in Assumption 3 holds. If X⊂Rn is a convex compact set such that S(P)⊆X and S(Q)⊆X for Q close to P, then the following assertions hold:(i)
For any small positive numberε>0, there exists δ>0 such that (27)SQ⊆SP+εBn.for anyQ∈U(P,δ), where U(P,δ)=Q∈P:DQ,P<δ.(ii)
IfΨP(x)=EP[F(x,ξ)]-G(x) is metrically regular at any x∗∈S(P) for 0, then there exists L^>0 such that(28)DSQ,SP≤L^DQ,Pfor anyQ∈U(P,δ).(iii)
IfΨP(x)=EP[F(x,ξ)]-G(x) is metrically regular at any x∗∈S(P) for 0 and ΨP-1(·) is a convex-valued multifunction, then there exists L^>0 such that(29)HSQ,SP≤L^DQ,Pfor anyQ∈U(P,δ).Proof.
(i) Notice thatS(Q) is bounded for Q close to P. The proof is directly from Theorem 3.1(ii) in [7].
Part (ii): sinceΨP is metrically regular at x^ for 0, there exist positive constants δx^, εx^, and γx^ depending on x^ such that(30)dx,SP≤γx^d0,ΨPxfor all x∈S(Q)∩B(x^,δx^). Since x∈S(Q) means (31)0∈EQFx,ξ+Gxthere exists t>0 such that for x∈S(Q), (32)d0,ΨPx≤DEQFx,ξ+Gx∩tB,EPFx,ξ+Gx∩tB≤EQFx,ξ-EPFx,ξ≤DQ,P,which, by (30), yields(33)dx,SP≤γx^DQ,Pfor x∈S(Q)∩B(x^,δx^). Since x^ is any choice in S(P), this means that set S(P) may be covered by the union of a collection of δ-balls; that is, (34)SP⊆⋃x^∈SQintBx^,δx^.Notice that S(P) is a compact set, by the finite covering theorem. There exist a finite set of points x1,x2,…,xk∈S(P) and a positive number δ^>0 such that (35)SP+δ^Bn⊆⋃i=1kintBxi,δxi.In other words, the δ^-neighborhood of S(P) may be covered by a finite δ-net of balls. Let γ^=max⁡γx1,…,γxk. We have from (33) that(36)dx,SP≤γ^DQ,Pfor all x∈S(P)+δ^Bn. Through conclusion (i), we arrive at the fact that (36) holds for all x∈S(Q) when Q is close to P, which means the conclusion of (ii).
(iii) We only need to show that there existsL>0 such that (37)DSP,SQ≤LDQ,Pfor Q close to P.
Step 1. Let x^∈S(P). We know from metric regularity of ΨP at x^ for 0 that there exist positive constants δx^, εx^, and γx^ depending on x^ such that(38)dx,ΨP-1q≤γx^dq,ΨPxfor all x∈B(x^,δx^) and q∈B(0,εx^). Since S(P) can be covered by Bx^,δx^:x^∈SP, similarly to the proof in (i), there exist γ>0, δ>0 and ε>0 such that(39)dx,ΨP-1q≤γdq,ΨPxfor any x∈S(P)+δBn and q∈B(0,ε).
Step 2. In particular, for fixed x¯∈S(P), (39) holds for any x∈B(x¯,δ) and q∈B(0,ε). Since ΨP-1 is a convex-valued multifunction, by [15, Theorem 2.2], we can define a continuous function x~(·):B(0,ε)→B(x¯,δ) such that x~(q)∈ΨP-1(q) for q∈B(0,ε) and(40)x¯-x~q≤γq.For each Q, let q^Q(x)=EP[F(x,ξ)]-EQ[F(x,ξ)] and δ′=min⁡{δ,1/2γ-1ε}. Under condition (a) in Assumption 3, there exists δ1>0 such that (41)supQ∈UP,δ1,x∈X⁡q^Qx<δ′,which means that q^Q(x)∈B(0,δ) for Q close to P. Let hQ(x)=x~∘q^Q(x). We know from (40) that hQ(x) is a continuous function which maps B(x¯,δ) to itself uniformly for Q close to P. By Brouwer’s fixed point theorem, for each Q, there exist x(Q)∈B(x¯,δ) such that x(Q)∈ΨP-1q^QxQ; that is, x(Q)∈S(Q) and by (40), (42)xQ-x¯=xQ-x~∘q^QxQ≤γq^QxQ≤γsupQ∈UP,δ1,x∈X⁡q^Qx≤γDQ,Pfor Q close to P, which means that(43)dx¯,SQ≤xQ-x¯≤γDQ,P.Notice that x¯ is an arbitrary choice in S(P) and by (39), γ is independent of x¯; then we know from (43) that(44)DSP,SQ≤γDQ,Pfor Q close to P. Combining (28) and (44), we complete the proof of (iii).Remark 9.
In [7], the error bounds described by distance from point to set are obtained to show the qualitative stability analysis of SGE (1). In Theorem 8, we establish the error bounds described by Hausdorff distance between solution sets, which extends the results of [7, Theorem 3.1].In the case when SGE (1) has a unique solution, we need the concept of strong regularity.Definition 10.
Suppose that condition (b) in Assumption3 holds. We say that a solution x¯∈S(P)∩intX is strongly regular if there exist neighborhoods V and W of 0∈Rn and x¯, respectively, such that for every δ∈V, the stochastic generalized equation(45)δ∈EPFx¯,ξ+JEPFx¯,ξx-x¯+Gxhas a unique solution in W and denoted x~=x~(δ), and x~(·) is Lipschitz continuous on V.In [18], consistency analysis of strong regular solution of SAA generalized equation is established. For completeness, we present a measure analogue of [18, Theorem 5.14].Theorem 11.
Suppose that condition (b) in Assumption3 holds. If there exists x¯P∈intX such that S(P)={x¯P} and x¯P is strongly regular, then(i)
there existsε>0 such that for every Q∈U(P,ε), S(Q) contains a unique solution, denoted by xQ;(ii)
there exist constantsε>0 and L>0 such that (46)DSQ,SP=xQ-xP≤L^DQ,Pfor allQ∈U(P,ε).Proof.
LetV be a convex compact neighborhood of x¯P and C1(V,Rn) be a space of continuously differentiable mappings ϕ:V→Rn equipped with the norm (47)ϕ1,V≔supx∈V⁡ϕx+supx∈V⁡Jϕx.Since x¯P is a strongly regular solution of the stochastic generalized equation, there exists ϵ>0 such that for any u∈C1(V,Rn) satisfying u-EP[F(·,ξ)]1,V≤ϵ, 0∈u(x)+G(x) has a unique solution x^=x^(u)∈V such that x^(·) is Lipschitz continuous with a Lipschitz modular, denoted by L with respect to the norms ·1,V and(48)x^u-x^P≤Lu1,V.Since(49)EPF·,ξ-EQF·,ξ1,V⟶0as Q is close to P, then there exists δ>0 such that S(Q) has a unique solution in V as Q∈U(P,δ). This proves (i). The conclusion of (ii) is directly from (48).


## 3.1. Existence of a Solution to the Perturbed SGE

We now turn to discuss existence of a solution to the perturbed SGE (2). This issue has been investigated in [7] based on the results of deterministic generalized equations in Kummer [14] under the assumption of convexity of EP[F(x,ξ)]+G(x). Without this assumption, we derive the existence results based on the metric regularity.Theorem 4.
Suppose thatS(P)≠∅ and there exist x¯∈S(P) such that x¯∈intX. If condition (a) in Assumption 3 holds and (a) ΨP(x)=EP[F(x,ξ)]+G(x) is metrically regular at x¯ for 0 and (b) ΨP-1(·) is a convex-valued multifunction, then S(Q)≠∅ for all Q close to P.Proof.
We know from metric regularity ofΨP(x)=EP[F(x,ξ)]+G(x) at x¯ for 0 that there exist positive constants γ, ε, and δ such that (17)dx,ΨP-1q≤γdq,ΨPxfor x∈B(x¯,δ)∩X and q∈B(0,ε). Since ΨP-1 is a convex-valued multifunction, by [15, Theorem 2.2], we can define a continuous function x^(·):B(0,ε)↦B(x¯,δ)∩X such that x^(q)∈ΨP-1(q) for q∈B(0,ε) and(18)x¯-x^q≤γdq,ΨPx¯≤γq.For each Q, let ΥQ(x)=EP[F(x,ξ)]-EQ[F(x,ξ)] and δ′=min⁡{ε,1/2γ-1δ}. Since under condition (a) in Assumption 3,(19)supx∈X⁡ΥQx=DQ,P⟶0as Q is close to P, there exists δ1>0 such that (20)supQ∈UP,δ1,x∈X⁡ΥQx≤δ′.This implies that ΥQ(x)∈B(0,ε) for Q∈U(P,δ1) and x∈X. Therefore, by (18), we can define a function(21)H^Q:Bx¯,δ∩X⟶Bx¯,δ∩Xx⟼x^∘ΥQxfor Q∈U(P,δ1). This is a continuous mapping from the compact convex set B(x¯,δ)∩X to itself. By Brouwer’s fixed point theorem, H^Q has a fixed point in B(x¯,δ). We assume that it is xQ; then (22)xQ=H^QxQ∈ΨP-1q^QxQ,which means that (23)EPFxQ,ξ-EQFxQ,ξ∈EPFxQ,ξ+Gx.Therefore, (24)0∈EQFxQ,ξ+Gxand hence S(Q)≠∅ for all Q close to P.Remark 5.
In the case whenG(x)≡K in (1) with K being a closed convex set, we may have more simple results; that is, if 0∈int{EP[F(X,ξ)]+K}, then S(P)≠∅ and S(Q)≠∅ for Q close to P.Corollary 6.
Suppose thatG(x)≡NK(x) in (1) with K being a closed convex set and NK being a normal cone operator and S(P)≠∅. Suppose that there exist x¯∈S(P) such that x¯∈intX and Assumption 3 holds. If EP[F(·,ξ)] is monotone on K and condition(25)0∈D∗NKx¯,-EPFx¯,ξy∗+JEPFx¯,ξTy∗⟹y∗=0holds, then S(Q)≠∅ for Q close to P.Proof.
We only need to verify the conditions in Theorem4. We know from [16, Theorem 3.2] that if condition (b) in Assumption 3 holds, then under condition (25), ΨP(x)=EP[F(x,ξ)]+NK(x) is metrically regular at x¯ for 0. This verifies condition (a) in Theorem 4. Since EP[F(·,ξ)] is monotone on K, we have (26)EPFx,ξ-q-EPFy,ξ-qTx-y≥0for x,y∈K, which means that EP[F(·,ξ)]-q is monotone on K for any q∈Rn. Then EP[F(·,ξ)]-q is monotone on K, which, by [17, Theorem 2.3.5] and condition (a) in Assumption 3, means that ΨP-1(q)=x:q∈EPFx,ξ+NKx is a convex-valued mapping; this verifies condition (b) in Theorem 4.Remark 7.
We make some comments on the conditions in Corollary6. (i) The condition that there exists x¯∈S(P) such that x¯∈intX is reasonable in that, by [17, Proposition 2.28] and its proof, S(P) is nonempty if and only if there exists a closed set X with intX≠∅ such that 0∈EP[F(x,ξ)]+NK∩X(x) has a solution in intX. In particular, X can be taken to a closed Euclidean ball with the fact that a solution x¯ of S(P) is the center. In this case, we know that x¯ is also a solution of 0∈EP[F(x,ξ)]+NK(x). (ii) In [16, Theorem 3.2], under a calmness condition, condition (25) implies the metrical regularity of ΨP(x) at x¯ for 0. In fact, in our case, by Definition 1, such calmness condition holds naturally by the Mordukhovich’s criterion.


## 3.2. Stability of SGE

In this section, we undertake stability analysis of SGE (1), namely, investigating the relationship between the set of solutions to the perturbed SGE (2) and SGE (1) when probability measure Q is close to P under the pseudometric defined in the preceding section.Theorem 8.
Suppose thatS(P)≠∅, S(Q)≠∅ for Q close to P, and condition (a) in Assumption 3 holds. If X⊂Rn is a convex compact set such that S(P)⊆X and S(Q)⊆X for Q close to P, then the following assertions hold:(i)
For any small positive numberε>0, there exists δ>0 such that (27)SQ⊆SP+εBn.for anyQ∈U(P,δ), where U(P,δ)=Q∈P:DQ,P<δ.(ii)
IfΨP(x)=EP[F(x,ξ)]-G(x) is metrically regular at any x∗∈S(P) for 0, then there exists L^>0 such that(28)DSQ,SP≤L^DQ,Pfor anyQ∈U(P,δ).(iii)
IfΨP(x)=EP[F(x,ξ)]-G(x) is metrically regular at any x∗∈S(P) for 0 and ΨP-1(·) is a convex-valued multifunction, then there exists L^>0 such that(29)HSQ,SP≤L^DQ,Pfor anyQ∈U(P,δ).Proof.
(i) Notice thatS(Q) is bounded for Q close to P. The proof is directly from Theorem 3.1(ii) in [7].
Part (ii): sinceΨP is metrically regular at x^ for 0, there exist positive constants δx^, εx^, and γx^ depending on x^ such that(30)dx,SP≤γx^d0,ΨPxfor all x∈S(Q)∩B(x^,δx^). Since x∈S(Q) means (31)0∈EQFx,ξ+Gxthere exists t>0 such that for x∈S(Q), (32)d0,ΨPx≤DEQFx,ξ+Gx∩tB,EPFx,ξ+Gx∩tB≤EQFx,ξ-EPFx,ξ≤DQ,P,which, by (30), yields(33)dx,SP≤γx^DQ,Pfor x∈S(Q)∩B(x^,δx^). Since x^ is any choice in S(P), this means that set S(P) may be covered by the union of a collection of δ-balls; that is, (34)SP⊆⋃x^∈SQintBx^,δx^.Notice that S(P) is a compact set, by the finite covering theorem. There exist a finite set of points x1,x2,…,xk∈S(P) and a positive number δ^>0 such that (35)SP+δ^Bn⊆⋃i=1kintBxi,δxi.In other words, the δ^-neighborhood of S(P) may be covered by a finite δ-net of balls. Let γ^=max⁡γx1,…,γxk. We have from (33) that(36)dx,SP≤γ^DQ,Pfor all x∈S(P)+δ^Bn. Through conclusion (i), we arrive at the fact that (36) holds for all x∈S(Q) when Q is close to P, which means the conclusion of (ii).
(iii) We only need to show that there existsL>0 such that (37)DSP,SQ≤LDQ,Pfor Q close to P.
Step 1. Let x^∈S(P). We know from metric regularity of ΨP at x^ for 0 that there exist positive constants δx^, εx^, and γx^ depending on x^ such that(38)dx,ΨP-1q≤γx^dq,ΨPxfor all x∈B(x^,δx^) and q∈B(0,εx^). Since S(P) can be covered by Bx^,δx^:x^∈SP, similarly to the proof in (i), there exist γ>0, δ>0 and ε>0 such that(39)dx,ΨP-1q≤γdq,ΨPxfor any x∈S(P)+δBn and q∈B(0,ε).
Step 2. In particular, for fixed x¯∈S(P), (39) holds for any x∈B(x¯,δ) and q∈B(0,ε). Since ΨP-1 is a convex-valued multifunction, by [15, Theorem 2.2], we can define a continuous function x~(·):B(0,ε)→B(x¯,δ) such that x~(q)∈ΨP-1(q) for q∈B(0,ε) and(40)x¯-x~q≤γq.For each Q, let q^Q(x)=EP[F(x,ξ)]-EQ[F(x,ξ)] and δ′=min⁡{δ,1/2γ-1ε}. Under condition (a) in Assumption 3, there exists δ1>0 such that (41)supQ∈UP,δ1,x∈X⁡q^Qx<δ′,which means that q^Q(x)∈B(0,δ) for Q close to P. Let hQ(x)=x~∘q^Q(x). We know from (40) that hQ(x) is a continuous function which maps B(x¯,δ) to itself uniformly for Q close to P. By Brouwer’s fixed point theorem, for each Q, there exist x(Q)∈B(x¯,δ) such that x(Q)∈ΨP-1q^QxQ; that is, x(Q)∈S(Q) and by (40), (42)xQ-x¯=xQ-x~∘q^QxQ≤γq^QxQ≤γsupQ∈UP,δ1,x∈X⁡q^Qx≤γDQ,Pfor Q close to P, which means that(43)dx¯,SQ≤xQ-x¯≤γDQ,P.Notice that x¯ is an arbitrary choice in S(P) and by (39), γ is independent of x¯; then we know from (43) that(44)DSP,SQ≤γDQ,Pfor Q close to P. Combining (28) and (44), we complete the proof of (iii).Remark 9.
In [7], the error bounds described by distance from point to set are obtained to show the qualitative stability analysis of SGE (1). In Theorem 8, we establish the error bounds described by Hausdorff distance between solution sets, which extends the results of [7, Theorem 3.1].In the case when SGE (1) has a unique solution, we need the concept of strong regularity.Definition 10.
Suppose that condition (b) in Assumption3 holds. We say that a solution x¯∈S(P)∩intX is strongly regular if there exist neighborhoods V and W of 0∈Rn and x¯, respectively, such that for every δ∈V, the stochastic generalized equation(45)δ∈EPFx¯,ξ+JEPFx¯,ξx-x¯+Gxhas a unique solution in W and denoted x~=x~(δ), and x~(·) is Lipschitz continuous on V.In [18], consistency analysis of strong regular solution of SAA generalized equation is established. For completeness, we present a measure analogue of [18, Theorem 5.14].Theorem 11.
Suppose that condition (b) in Assumption3 holds. If there exists x¯P∈intX such that S(P)={x¯P} and x¯P is strongly regular, then(i)
there existsε>0 such that for every Q∈U(P,ε), S(Q) contains a unique solution, denoted by xQ;(ii)
there exist constantsε>0 and L>0 such that (46)DSQ,SP=xQ-xP≤L^DQ,Pfor allQ∈U(P,ε).Proof.
LetV be a convex compact neighborhood of x¯P and C1(V,Rn) be a space of continuously differentiable mappings ϕ:V→Rn equipped with the norm (47)ϕ1,V≔supx∈V⁡ϕx+supx∈V⁡Jϕx.Since x¯P is a strongly regular solution of the stochastic generalized equation, there exists ϵ>0 such that for any u∈C1(V,Rn) satisfying u-EP[F(·,ξ)]1,V≤ϵ, 0∈u(x)+G(x) has a unique solution x^=x^(u)∈V such that x^(·) is Lipschitz continuous with a Lipschitz modular, denoted by L with respect to the norms ·1,V and(48)x^u-x^P≤Lu1,V.Since(49)EPF·,ξ-EQF·,ξ1,V⟶0as Q is close to P, then there exists δ>0 such that S(Q) has a unique solution in V as Q∈U(P,δ). This proves (i). The conclusion of (ii) is directly from (48).


## 4. Application to Stochastic Conic Programming

Consider the following stochastic optimization problem:(50)minx∈RnEPfx,ξωs.t.EPGx,ξω∈Kx∈X,where X is a compact and convex subset of Rn, K is a closed convex cone in Rm, f:Rn×Rk→R and G:Rn×Rk→Rm are continuous functions, ξ:Ω→Ξ is vector of random variables defined on probability space (Ω,F,P) with support set Ξ⊂Rk, and EP[·] denotes mathematical expectation with respect to probability measure. Model (50) can be found in [2] and the linear-quadratic tracking problem is a special case of this model.In this section, we focus on a special case when the probability measureP is approximated by a sequence of empirical measures PN defined as (51)PN≔1N∑i=1N1ξkω,where ξ1,…,ξN is an independent and identically distributed sampling of ξ and (52)1ξkω=1,ifξω=ξkω,0,ifξω≠ξkω.In this case,(53)EPNfx,ξω=1N∑i=1Nfx,ξi,EPNGx,ξω=1N∑i=1NGx,ξi.By classical law of large numbers in statistics, EPN[f(x,ξ(ω))] and EPN[G(x,ξ(ω))] converge to EP[f(x,ξ(ω))] and EP[G(x,ξ(ω))], respectively, as N tends to infinity. This kind of approximation is known in stochastic programming under various names such as sample average approximation (SAA), Monte Carlo method, and sample path optimization; see [4, 8] and the references therein. Consequently, by the SAA method, problem (50) can be approximated by the following problem:(54)minx∈Rnf^Nx≔1N∑i=1Nfx,ξis.t.G^Nx≔1N∑i=1NGx,ξi∈Kx∈X.Problem (54) is called the SAA problem and (50) the true problem.If condition (b) in Assumption3 holds for mappings f(·,ξ) and G(·,ξ), respectively, G(·,ξ) is convex with respect to -K for each ξ, that is, the multifunction x↦G(x,ξ)-K is convex for each ξ, and the constraint qualification(55)0∈intEPGX,ξω-Kholds, then by [19, Proposition 2.104, Theorem 3.9], for any locally optimal solution of x∗, there exists λ∗∈NK(EP[G(x∗,ξ)]) such that (x∗,λ∗) satisfies the following stationary condition:(56)0∈∇EPfx∗,ξ+JEPGx∗,ξTλ∗+NXx∗,which can be rewritten as a stochastic generalized equation (57)0∈EPFx∗,λ∗,ξ+NΘx∗,λ∗,where F(x,ξ)=L(x,λ,ξ)G(x,ξ) with L(x,λ,ξ)≔∇f(x,ξ)+JxG(x,ξ)Tλ and Θ≔X×K-, where K- is the polar cone of K. Similarly, for fixed N, if x^N is the locally optimal solution of problem (54), then under corresponding constraint qualification, there exists multiplier λ^N such that (x^N,λ^N) satisfies the following stationary condition: (58)0∈F^Nx^N,λ^N+NΘx^N,λ^N,where F^N(x,ξ)=L^N(x,λ)G^N(x) with L^N(x,λ)≔∇f^N(x)+JG^N(x)Tλ and Θ≔X×K-.LetΛ0=λ∈Rm:∃x∈Xs.t.0∈EPFx,λ,ξ+NΘx,λ and ΛN=λ∈Rm:∃x∈Xs.t.0∈F^Nx,λ+NΘx,λ. Next we show that all the two sets are bounded.Lemma 12.
If condition (b) in Assumption3 holds for mappings f(·,ξ) and G(·,ξ), respectively, G(·,ξ) is convex with respect to -K for each ξ, and condition (55) holds, then there exist a compact set Λ and a number N¯∈N such that Λ0∪(∪N≥N¯ΛN)⊆Λ almost surely.Proof.
We at first show that there exists a numberN¯∈N such that ∪N≥N¯ΛN is bounded almost surely. Assume by contradiction that there exists a sequence λN satisfying λN∈ΛN and λN→+∞ with probability one (w.p.1) as N→+∞. Then there exist a sequence xN⊆X and a number sequence αN↘0 such that(59)0∈∇f^NxN+JG^NxNTλN+NXxNwith λN∈NK(G^N(xN)) and αNλN→λ¯≠0 w.p.1 as N→+∞. Under condition (b) in Assumption 3, we have by the law of large numbers that ∇f^N(x), JG^N(x), and G^N(x) converge to ∇EP[f(x,ξ)], JEP[G(x,ξ)], and EP[G(x,ξ)] w.p.1, respectively. Since X is a compact set, without loss of generality, we may assume that xN→x¯ w.p.1 as N tends to infinity. Then by the outer semicontinuity of normal cone, it holds that (60)lim⁡supN→∞⁡NXxN⊆NXx∗w.p.1,lim⁡supN→∞⁡NKG^NxN⊆NKEPGx∗,ξw.p.1.Multiplying αN by the two sides of (59) and letting N tend to infinity, we obtain(61)0∈JEPGx∗,ξTλ¯+NXx∗with λ¯∈NK(EP[G(x∗,ξ)]). Since condition (55) holds, we have from [19, Proposition 2.104] that (62)0∈intEPGx∗,ξ+JEPGx∗,ξX-x∗-Kholds, which, by [20, Proposition 2.2], is equivalent to (63)0∈JEPGx∗,ξTλ+NXx∗λ∈NKEPGx∗,ξ⇓λ=0.This, by (61), means that λ¯=0, which is a contradiction. Therefore there exists a number N¯∈N such that ∪N≥N¯ΛN is bounded almost surely. In the similar way, we can demonstrate that Λ0 is bounded.LetS=x,λ∈Rn×Rm:0∈EPFx,λ,ξ+NΘx,λ and S^N=x,λ∈Rn×Rm:0∈F^Nx,λ+NΘx,λ. We want to demonstrate the quantitative stability of S when it is approximated by S^N.Theorem 13.
If condition (b) in Assumption3 holds for mappings f(·,ξ),G(·,ξ),∇xf(·,ξ),JxG(·,ξ), respectively, G(·,ξ) is convex with respect to -K for each ξ and condition (55) holds. If condition(64)0∈D∗NXx,-EPLx,λ,ξu+JxEPLx,λ,ξu+JEPGx,ξTv0∈D∗NKλ,-EPGx,ξv+JEPGx,ξu⇓u,v=0holds for any (x,λ)∈S, then the following hold:(i)
There existsL^>0 such that (65)DS^N,S≤L^supϕ∈Φ⁡supx∈X⁡1N∑i=1Nϕx,ξi-EPϕx,ξforN is large enough, where Φ=G·,ξ,∇xf·,ξ,JxG·,ξ.(ii)
If, in addition, the matrix(66)JxEPLx,λ,ξJxEPGx,ξTJxEPGx,ξ0is semidefinite for any(x,λ)∈S, then there exists L^>0 such thatH ( S ^ N , S ) ≤ L ^  sup ϕ ∈ Φ ⁡ sup x ∈ X ⁡ 1 N ∑ i = 1 N ϕ ( x , ξ i ) - E P ϕ x , ξ forN large enough.Proof.
It suffices to verify the conditions in Theorem8. By Lemma 12, there exist a compact set Λ and a number N¯∈N such that Λ0∪(∪N≥N¯ΛN)⊆Λ almost surely, which means that S∪(∪N≥N¯S^N) contains in a compact set X×Λ almost surely. We know from [16, Theorem 3.2] that if(67)0∈D∗NΘx,λ,-EPFx,λ,ξy∗+Jx,λEPFx,λ,ξy∗⟹y∗=0,for any (x,λ)∈S, then conclusion (i) in Theorem 8 holds. Notice that by Definition 1, (68)D∗NΘx,λ,-EPFx,λ,ξy1∗,y2∗=D∗NXx,-EPLx,λ,ξy1∗×D∗NK-λ,-EPGx,ξy2∗and Jx,λEP[F(x,λ,ξ)] is matrix (66), which implies that (67) is equivalent to condition (64). Therefore by Theorem 8, conclusion (i) holds.
We know from [17, Proposition 2.3.2] that if matrix (66) is semidefinite, then EP[F(x,λ,ξ)] is monotone, which, by the proof of Corollary 6, means that Σ(q)=x,λ:q∈EPFx,λ,ξ+NΘx,λ is a convex-valued mapping; this verifies condition in (ii) of Theorem 8. Conclusion (ii) follows from Theorem 8.


## 5. Conclusion

The existence results and quantitative stability analysis described by Hausdorff distance are established in this paper for SGE (1) when P varies under some appropriate metric, which extends the results in [7]. The obtained results are then applied to a stochastic conic programming. In fact, Hausdorff distance type quantitative stability analysis obtained may be applied to more stochastic models such as stochastic mathematical program with equilibrium constraints (SMPEC) and stochastic semi-infinite programming. We let this be our further research topic.



---

*Source: 8680540-2018-03-26.xml*