# Expected Residual Minimization Method for a Class of Stochastic Quasivariational Inequality Problems

Authors: Hui-Qiang Ma; Nan-Jing Huang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We consider the expected residual minimization method for a class of stochastic quasivariational inequality problems (SQVIP). The regularized gap function for quasivariational inequality problem (QVIP) is in general not differentiable. We first show that the regularized gap function is differentiable and convex for a class of QVIPs under some suitable conditions. Then, we reformulate SQVIP as a deterministic minimization problem that minimizes the expected residual of the regularized gap function and solve it by sample average approximation (SAA) method. Finally, we investigate the limiting behavior of the optimal solutions and stationary points.


---

## Body

## 1. Introduction

The quasivariational inequality problem is a very important and powerful tool for the study of generalized equilibrium problems. It has been used to study and formulate generalized Nash equilibrium problem in which a strategy set of each player depends on the other players’ strategies (see, for more details, [1–3]).QVIP is to find a vectorx*∈S(x*) such that
(1.1)〈F(x*),x-x*〉≥0,∀x∈S(x*),
where F:ℝn→ℝn is a mapping, the symbol 〈·,·〉 denotes the inner product in ℝn, and S:ℝn→2ℝn is a set-valued mapping of which S(x) is a closed convex set in ℝn for each x. In particular, if S is a closed convex set and S(x)≡S for each x, then QVIP (1.1) becomes the classical variational inequality problem (VIP): find a vector x*∈S such that
(1.2)〈F(x*),x-x*〉≥0,∀x∈S.In most important practical applications, the functionF always involves some random factors or uncertainties. Let (Ω,ℱ,P) be a probability space. Taking the randomness into account, we get stochastic quasivariational inequality problem (SQVIP): find an x*∈S(x*) such that
(1.3)P{ω∈Ω:〈F(x*,ω),x-x*〉≥0,∀x∈S(x*)}=1,
or equivalently,
(1.4)〈F(x*,ω),x-x*〉≥0,∀x∈S(x*),ω∈Ωa.s.,
where F:ℝn×Ω→ℝn is a mapping and a.s. is abbreviation for “almost surely” under the given probability measure P.Due to the introduction of randomness, SQVIP (1.4) becomes more practical and also evokes more and more attentions in the recent literature [4–16]. However, to our best knowledge, most publications in the existing literature discuss the stochastic complementarity problems and the stochastic variational inequality problems, which are two special cases of (1.4). It is well known that quasivariational inequalities are more complicated than variational inequalities and complementarity problems and that they have widely applications. Therefore, it is meaningful and interesting to study the general problem (1.4).Because of the existence of a random elementω, we cannot generally find a vector x*∈S(x*) such that (1.4) holds almost surely. That is, (1.4) is not well defined if we think of solving (1.4) before knowing the realization ω. Therefore, in order to get a reasonable resolution, an appropriate deterministic reformulation for SQVIP becomes an important issue in the study of the considered problem.Recently, one of the mainstreaming research methods on the stochastic variational inequality problem is expected residual minimization method (see [4, 5, 7, 11–13, 16] and the references therein). Chen and Fukushima [5] formulated the stochastic linear complementarity problem (SLCP) as a minimization problem which minimizes the expectation of gap function (also called residual function) for SLCP. They regarded the optimal solution of this minimization problem as a solution to SLCP. This method is the so-called expected residual minimization method (ERM). Following the ideas of Chen and Fukushima [5], Zhang and Chen [16] considered the stochastic nonlinear complementary problems. Luo and Lin [12, 13] generalized the expected residual minimization method to solve stochastic variational inequality problem.In this paper, we focus on ERM method for SQVIP. We first show that the regularized gap function for QVIP is differentiable and convex under some suitable conditions. Then, we formulate SQVIP (1.4) as an optimization problem and solve this problem by SAA method.The rest of this paper is organized as follows. In Section2, some preliminaries and the reformulation for SQVIP are given. In Section 3, we give some suitable conditions under which the regularized gap function for QVIP is differentiable and convex. In Section 4, we show that the objective function of the reformulation problem is convex and differentiable under some suitable conditions. Finally, the convergence results of optimal solutions and stationary points are given in Section 5.


## 2. Preliminaries

Throughout this paper, we use the following notations.∥·∥ denotes the Euclidean norm of a vector. For an n×n symmetric positive-definite matrix G, ∥·∥G denotes the G-norm defined by ∥x∥G=〈x,Gx〉 for x∈ℝn and ProjS,G(x) denotes the projection of the point x onto the closed convex set S with respect to the norm ∥·∥G. For a mapping F:ℝn→ℝn, ∇xF(x) denotes the usual gradient of F(x) in x. It is easy to verify that
(2.1)λmin∥x∥≤∥x∥G≤λmax∥x∥,
where λmin and λmax are the smallest and largest eigenvalues of G, respectively.The regularized gap function for the QVIP (1.1) is given as follows:
(2.2)fα(x):=maxy∈S(x){-〈F(x),y-x〉-α2∥y-x∥G2},
where α is a positive parameter. Let X⊆ℝn be defined by X={x∈ℝn:x∈S(x)}. This is called a feasible set of QVIP (1.1). For the relationship between the regularized gap function (2.2) and QVIP (1.1), the following result has been shown in [17, 18].Lemma 2.1.
Letfα(x) be defined by (2.2). Then fα(x)≥0 for all x∈X. Furthermore, fα(x*)=0 and x*∈X if and only if x* is a solution to QVIP (1.1). Hence, problem (1.1) is equivalent to finding a global optimal solution to the problem:
(2.3)minx∈Xfα(x).Though the regularized gap functionfα(x) is directional differentiable under some suitable conditions (see, [17, 18]), it is in general nondifferentiable.The regularized gap function (or residual function) for SQVIP (1.4) is as follows:
(2.4)fα(x,ω):=maxy∈S(x){-〈F(x,ω),y-x〉-α2∥y-x∥G2},
and the deterministic reformulation for SQVIP is
(2.5)minx∈XΘ(x):=𝔼fα(x,ω),
where 𝔼 denotes the expectation operator.Note that the objective functionΘ(x) contains mathematical expectation. Throughout this paper, we assume that 𝔼fα(x,ω) cannot be calculated in a closed form so that we will have to approximate it through discretization. One of the most well-known discretization approaches is sample average approximation method. In general, for an integrable function ϕ:Ω→ℝ, we approximate the expected value 𝔼[ϕ(ω)] with sample average (1/Nk)∑ωi∈Ωk‍ϕ(ωi), where ω1,…,ωNk are independently and identically distributed random samples of ω and Ωk:={ω1,…,ωNk}. By the strong law of large numbers, we get the following lemma.Lemma 2.2.
Ifϕ(ω) is integrable, then
(2.6)limk→∞1Nk∑ωi∈Ωk‍ϕ(ωi)=𝔼[ϕ(ω)]
holds with probability one.Let(2.7)Θk(x):=1Nk∑ωi∈Ωk‍fα(x,ωi).
Applying the above techniques, we can get the following approximation of (2.5):
(2.8)minx∈XΘk(x).


## 3. Convexity and Differentiability offα(x)

In the remainder of this paper, we restrict ourself to a special case, whereS(x)=S+m(x). Here, S is a closed convex set in ℝn and m(x):ℝn→ℝn is a mapping. In this case, we can show that fα(x) is continuously differentiable whenever so are the functions F(x) and m(x). In order to get this result, we need the following lemma (see [19, Chapter 4, Theorem  1.7]).Lemma 3.1.
LetS∈ℝn be a nonempty closed set and U∈ℝm be an open set. Assume that f:ℝn×U→ℝ be continuous and the gradient ∇uf(·,·) is also continuous. If the problem minx∈Sf(x,u) is uniquely attained at x(u) for any fixed u∈U, then the function ϕ(u):=minx∈Sf(x,u) is continuously differentiable and ∇uϕ(u) is given by ∇uϕ(u)=∇uf(x(u),u).For anyy∈S(x)=S+m(x), we can find a vector z∈S such that y=z+m(x). Thus, we can rewrite (2.2) as follows:
(3.1)fα(x)=maxz∈S{-〈F(x),z+m(x)-x〉-α2∥z-(x-m(x))∥G2}=-minz∈S{〈F(x),z-(x-m(x))〉+α2∥z-(x-m(x))∥G2}.
The minimization problem in (3.1) is essentially equivalent to the following problem:
(3.2)minz∈S∥z-[x-m(x)-α-1G-1F(x)]∥G2.It is easy to know that problem (3.2) has a unique optimal solution ProjS,G(x-m(x)-α-1G-1F(x)). Thus, ProjS,G(x-m(x)-α-1G-1F(x)) is also a unique solution of problem (3.1). The following result is a natural extension of [20, Theorem  3.2].Theorem 3.2.
IfS is a closed convex set in ℝn and m(x) and F(x) are continuously differentiable, then the regularized gap function fα(x) given by (2.2) is also continuously differentiable and its gradient is given by
(3.3)∇fα(x)=[I-∇m(x)]F(x)-[∇F(x)-α(I-∇m(x))G][zα(x)-(x-m(x))],
where zα(x)=ProjS,G(x-m(x)-α-1G-1F(x)) and I denotes the n×n identity matrix.Proof.
Let us define the functionh:ℝn×S→ℝ by
(3.4)h(x,z)=〈F(x),z-(x-m(x))〉+α2∥z-(x-m(x))∥G2.
It is obviously that if F(x) and m(x) are continuous, then h(x,z) is continuous in (x,z). If F(x) and m(x) are continuously differentiable, then
(3.5)∇xh(x,z)=-[I-∇m(x)]F(x)+[∇F(x)-α(I-∇m(x))G][z-(x-m(x))]
is continuous in (x,z). By (3.1), we have
(3.6)fα(x)=-minz∈Sh(x,z).
Since the minimum on the right-hand side of (3.6) is uniquely attained at z=zα(x), it follows from Lemma 3.1 that fα(x) is differentiable and its gradient is given by
(3.7)∇fα(x)=-∇xh(x,zα(x))=[I-∇m(x)]F(x)-[∇F(x)-α(I-∇m(x))G][zα(x)-(x-m(x))].
This completes the proof.Remark 3.3.
Whenm(x)≡0, we have S(x)≡S and so QVIP (1.1) reduces to VIP (1.2). In this case
(3.8)∇fα(x)=F(x)-[∇F(x)-αG][zα(x)-x],
where
(3.9)zα(x)=ProjS,G(x-α-1G-1F(x)).
Moreover, when α=1, we have
(3.10)∇fα(x)=F(x)-[∇F(x)-G][zα(x)-x],zα(x)=ProjS,G(x-G-1F(x)),
which is the same as [20, Theorem  3.2].Now we investigate the conditions under whichfα(x) is convex.Theorem 3.4.
Suppose thatF(x)=Mx+q and m(x)=Nx, where M and N are n×n matrices and q∈ℝn is a vector. Denote βmin and μmax by the smallest and largest eigenvalues of MT(I-N)+(I-N)TM and (N-I)TG(N-I), respectively. We have the following statements.(i)
Ifμmax>0, βmin≥0 and α≤(βmin/μmax), then the function fα(x) is convex. Moreover, if there exists a constant β>0 such that α≤(βmin/μmax(1+β)), then fα(x) is strongly convex with modulus αβμmax.(ii)
Ifμmax=0 and βmin≥0, then the function fα(x) is convex. Moreover, if βmin>0, then fα(x) is strongly convex with modulus βmin.Proof.
SubstitutingF(x)=Mx+q and m(x)=Nx into (3.1), we have
(3.11)fα(x)=maxz∈S{-〈Mx+q,z+(N-I)x〉-α2∥z-(I-N)x∥G2}.
Define
(3.12)H(x,z)=-〈Mx+q,z+(N-I)x〉-α2∥z-(I-N)x∥G2.
Noting that
(3.13)∇x2H(x,z)=MT(I-N)+(I-N)TM-α(N-I)TG(N-I),
we have, for any y∈ℝn,
(3.14)yT∇x2H(x,z)y=yT[MT(I-N)+(I-N)TM]y-αyT(N-I)TG(N-I)y≥(βmin-αμmax)∥y∥2.
Ifμmax>0, βmin≥0 and α≤(βmin/μmax), we have
(3.15)yT∇x2H(x,z)y≥(βmin-αμmax)∥y∥2≥0.
This implies that the Hessen matrix ∇x2H(x,z) is positive semidefinite and hence H(x,z) is convex in x for any z∈S. In consequence, by (3.11), the regularized gap function fα(x) is convex. Moreover, if α≤(βmin/μmax(1+β)), then
(3.16)yT∇x2H(x,z)y≥(βmin-αμmax)∥y∥2≥αβμmax∥y∥2,
which means that H(x,z) is strongly convex with modulus αβμmax in x for any z∈S. From (3.11), we know that the regularized gap function fα(x) is strongly convex.
Ifμmax=0 and βmin≥0, we have
(3.17)yT∇x2H(x,z)y≥βmin∥y∥2≥0.
Thus, the regularized gap function fα(x) is convex. Moreover, if βmin>0, then the regularized gap function fα(x) is strongly convex with modulus βmin. This completes the proof.Remark 3.5.
WhenN=0, QVIP (1.1) reduces to VIP (1.2). Denote β¯min and μ¯max by the smallest and largest eigenvalues of MT+M and G, respectively. In this case, the function
(3.18)f¯α(x)=maxz∈S{-〈F(x),z-x〉-α2∥z-x∥G2}
is convex when μ¯max>0, β¯min≥0 and α≤(β¯min/μ¯max).Remark 3.6.
WhenN=0 and G=I, we have that μ¯max=1. In this case, the function
(3.19)f^α(x)=maxz∈S{-〈F(x),z-x〉-α2∥z-x∥2}
is convex when β¯min≥0 and α≤β¯min. This is consistent with [4, Theorem  2.1].


## 4. Properties of FunctionΘ

In this section, we consider the properties of the objective functionΘ(x) of problem (2.5). In what follows we show that Θ(x) is differentiable under some suitable conditions.Theorem 4.1.
Suppose thatF(x,ω):=M(ω)x+Q(ω), where M:Ω→ℝn×n and Q:Ω→ℝn with
(4.1)𝔼[∥M(ω)∥2+∥Q(ω)∥2]<+∞.
Let S(x)=S+Nx. Then the function Θ(x) is differentiable and
(4.2)∇xΘ(x)=𝔼∇xfα(x,ω).Proof.
SinceS(x)=S+Nx, it is easy to know that
(4.3)fα(x,ω)=-〈F(x,ω),yα(x,ω)-(x-Nx)〉-α2∥yα(x,ω)-(x-Nx)∥G2,
where
(4.4)yα(x,ω)=ProjS,G(x-Nx-α-1G-1F(x,ω)).
It follows from Lemma 2.1 that fα(x,ω)≥0 and so
(4.5)α2∥yα(x,ω)-x+Nx∥G2≤-〈F(x,ω),yα(x,ω)-x+Nx〉≤∥F(x,ω)∥∥yα(x,ω)-x+Nx∥≤1λmin∥F(x,ω)∥∥yα(x,ω)-x+Nx∥G.
Thus,
(4.6)∥yα(x,ω)-x+Nx∥G≤2αλmin∥F(x,ω)∥,∥yα(x,ω)-x+Nx∥≤1λmin∥yα(x,ω)-x+Nx∥G≤2αλmin∥F(x,ω)∥.
In a similar way to Theorem3.2, we can show that fα(x,ω) is differentiable with respect to x and
(4.7)∇xfα(x,ω)=(I-N)F(x,ω)-[M(ω)-α(I-N)G][yα(x,ω)-(I-N)x].
It follows that
(4.8)∥∇xfα(x,ω)∥≤∥I-N∥∥F(x,ω)∥-∥M(ω)-α(I-N)G∥∥yα(x,ω)-(I-N)x∥≤{∥I-N∥+2αλmin∥M(ω)-α(I-N)G∥}∥F(x,ω)∥≤(1+2∥G∥λmin)∥I-N∥∥F(x,ω)∥+2αλmin∥M(ω)∥∥F(x,ω)∥≤(1+2∥G∥λmin)∥I-N∥(1+∥x∥)(∥M(ω)∥+∥Q(ω)∥)+2αλmin(1+∥x∥)(∥M(ω)∥+∥Q(ω)∥)2≤(1+2∥G∥λmin)∥I-N∥(1+∥x∥)(∥M(ω)∥+∥Q(ω)∥)+4αλmin(1+∥x∥)(∥M(ω)∥2+∥Q(ω)∥2).
By [21, Theorem  16.8], the function Θ is differentiable and ∇xΘ(x)=𝔼∇xfα(x,ω). This completes the proof.The following theorem gives some conditions under whichΘ(x) is convex.Theorem 4.2.
Suppose that the assumption of Theorem4.1 holds. Let
(4.9)β0≔infω∈Ω∖Ω0λmin(M(ω)T(I-N)+(I-N)TM(ω)),
where Ω0 is a null subset of Ω and λmin(G) denotes the smallest eigenvalue of G. We have the following statements. (i)
Ifμmax>0, β0>0 and α≤(β0/μmax), then the function Θ(x) is convex. Moreover, if α≤(β0/μmax(1+β)) with β>0, then Θ(x) is strongly convex with modulus αβμmax.(ii)
Ifμmax=0 and β0≥0, then the function Θ(x) is convex. Moreover, if β0>0, then Θα(x) is strongly convex with modulus β0.Proof.
Define(4.10)H(x,z,ω)=-〈M(ω)x+Q(ω),z+(N-I)x〉-α2∥z-(I-N)x∥G2.
Noting that
(4.11)∇x2H(x,z,ω)=M(ω)T(I-N)+(I-N)TM(ω)-α(N-I)TG(N-I),
we have, for any y∈ℝn,
(4.12)yT∇x2H(x,z,ω)y=yT[M(ω)T(I-N)+(I-N)TM(ω)]y-αyT(N-I)TG(N-I)y≥(β0-αμmax)∥y∥2,
where the inequality holds almost surely.
Ifμmax>0, β0>0 and α≤(β0/μmax), then
(4.13)yT∇x2H(x,z,ω)y≥0.
This implies that the Hessen matrix ∇x2H(x,z,ω) is positive semidefinite and hence H(x,z,ω) is convex in x for any z∈S. Since
(4.14)fα(x,ω)=maxy∈S(x){-〈F(x,ω),y-x〉-α2∥y-x∥G2}=maxz∈SH(x,z,ω),
the regularized gap function fα(x,ω) is convex and so is Θ(x). Moreover, if α≤(β0/μmax(1+β)), then
(4.15)yT∇x2H(x,z,ω)y≥αβμmax∥y∥2,
which means that H(x,z,ω) is strongly convex in x for any z∈S. From the definitions of H(x,z,ω) and fα(x,ω), we know that fα(x,ω) is strongly convex with modulus αβμmax and so is Θ(x).
Ifμmax=0 and β0≥0, then
(4.16)yT∇x2H(x,z,ω)y≥β0∥y∥2≥0,
which implies that the regularized gap function fα(x,ω) is convex and so is Θ(x). Moreover, if β0>0, then Θ(x) is strongly convex with modulus β0. This completes the proof.It is easy to verify thatX={x∈ℝn:x∈S(x)} is a convex subset when S(x)=S+Nx. Thus, Theorem 4.2 indicates that problem (2.5) is a convex program. From the proof details of Theorem 4.2, we can also get that problem (2.8) is a convex program. Hence we can obtain a global optimal solution using existing solution methods.


## 5. Convergence of Solutions and Stationary Points

In this section, we will investigate the limiting behavior of the optimal solutions and stationary points of (2.8).Note that if the conditions of Theorem4.1 are satisfied, then the set X is closed, and
(5.1)𝔼∥M(ω)∥<∞,𝔼[∥M(ω)∥+∥Q(ω)∥+c]2<∞,
where c is a constant.Theorem 5.1.
Suppose that the conditions of Theorem4.1 are satisfied. Let xk be an optimal solution of problem (2.8) for each k. If x* is an accumulation point of {xk}, then it is an optimal solution of problem (2.5).Proof.
Without loss of generality, we assume thatxk itself converges to x* as k tends to infinity. It is obvious that x*∈X.
We first show that(5.2)limk→∞|Θk(xk)-Θk(x*)|=0.
It follows from mean-value theorem that
(5.3)|Θk(xk)-Θk(x*)|=|1Nk∑ωi∈Ωk‍[fα(xk,ωi)-fα(x*,ωi)]|≤1Nk∑ωi∈Ωk‍|fα(xk,ωi)-fα(x*,ωi)|≤1Nk∑ωi∈Ωk‍∥∇xfα(yik,ωi)∥∥xk-x*∥,
where yik=γikxk+(1-γik)x* and γik∈[0,1]. From the proof details of Theorem 4.1, we have
(5.4)∥∇xfα(yik,ωi)∥≤(1+2∥G∥λmin)(1+∥yik∥)(∥M(ωi)∥+∥Q(ωi)∥)∥I-N∥+2αλmin(1+∥yik∥)(∥M(ωi)∥+∥Q(ωi)∥)2.
Since limk→+∞xk=x*, there exists a constant C such that ∥xk∥≤C for each k. By the definition of yik, we know that ∥yik∥≤C. Hence,
(5.5)∥∇xfα(yik,ωi)∥≤(1+2∥G∥λmin)(1+C)(∥M(ωi)∥+∥Q(ωi)∥)∥I-N∥+2αλmin(1+C)(∥M(ωi)∥+∥Q(ωi)∥)2≤C'(∥M(ωi)∥+∥Q(ωi)∥+1)2,
where
(5.6)C'=max{(1+2∥G∥λmin)(1+C)∥I-N∥,2αλmin(1+C)}.
It follows that
(5.7)|Θk(xk)-Θk(x*)|≤C'1Nk∑ωi∈Ωk‍(∥M(ωi)∥+∥Q(ωi)∥+1)2∥xk-x*∥→0,
which means that (5.2) holds.
Now, we show thatx* is an optimal solution of problem (2.5). It follows from (5.2) and
(5.8)|Θk(xk)-Θ(x*)|≤|Θk(xk)-Θk(x*)|+|Θk(x*)-Θ(x*)|,
that limk→+∞Θk(xk)=Θ(x*). Since xk is an optimal solution of problem (2.8) for each k, we have that, for any x∈X,
(5.9)Θk(xk)≤Θk(x).
Letting k→∞ above, we get from (5.2) and Lemma 2.2 that
(5.10)Θ(x*)≤Θ(x),
which means x* is an optimal solution of problem (2.5). This completes the proof.In general, it is difficult to obtain a global optimal solution of problem (2.8), whereas computation of stationary points is relatively easy. Therefore, it is important to study the limiting behavior of stationary points of problem (2.8).Definition 5.2.
x
k is said to be stationary to problem (2.8) if
(5.11)〈∇xΘk(xk),y-xk〉≥0,∀y∈X,
and x* is said to be stationary to problem (2.5) if
(5.12)〈∇xΘ(x*),y-x*〉≥0,∀y∈X.Theorem 5.3.
Letxk be stationary to problem (2.8) for each k. If the conditions of Theorem 4.1 are satisfied, then any accumulation point x* of {xk} is a stationary point of problem (2.5).Proof.
Without loss of generality, we assume that{xk} itself converges to x*.
At first, we show that(5.13)limk→∞∥∇xΘk(xk)-∇xΘk(x*)∥=0.
It follows from (2.1) and the nonexpansivity of the projection operator that
(5.14)∥yα(xk,ω)-yα(x*,ω)∥≤1λmin∥yα(xk,ω)-yα(x*,ω)∥G=1λmin∥ProjS,G(xk-Nxk-α-1G-1F(xk,ω))=1λmin-ProjS,G(x*-Nx*-α-1G-1F(x*,ω))∥G≤1λmin∥xk-Nxk-α-1G-1F(xk,ω)-[x*-Nx*-α-1G-1F(x*,ω)]∥G≤λmaxλmin∥xk-Nxk-α-1G-1F(xk,ω)-[x*-Nx*-α-1G-1F(x*,ω)]∥≤λmaxλmin(∥I-N∥+α-1∥G-1∥∥M(ω)∥)∥xk-x*∥.
Thus,
(5.15)∥∇xΘk(xk)-∇xΘk(x*)∥≤1Nk∑ωi∈Ωk∥∇xfα(xk,ωi)-∇xfα(x*,ωi)∥=1Nk∑ωi∈Ωk∥(I-N)[M(ωi)xk+Q(ωi)]-[M(ωi)-α(I-N)G]1Nk∑×[yα(xk,ωi)-(I-N)xk]1Nk∑-{(I-N)[M(ωi)x*+Q(ωi)]-[M(ωi)-α(I-N)G]1Nk∑×[yα(x*,ωi)-(I-N)x*]}[M(ωi)xk+Q(ωi)]∥≤2∥xk-x*∥∥I-N∥1Nk∑ωi∈Ωk∥M(ωi)∥‍+α∥I-N∥2∥G∥∥xk-x*∥+1Nk∑ωi∈Ωk∥M(ωi)-α(I-N)G∥∥yα(xk,ωi)-yα(x*,ωi)∥≤2∥xk-x*∥∥I-N∥1Nk∑ωi∈Ωk∥M(ωi)∥‍+α∥I-N∥2∥G∥∥xk-x*∥+λmaxλmin1Nk∑ωi∈Ωk∥M(ωi)-α(I-N)G∥‍[∥I-N∥+α-1∥G-1∥∥M(ωi)∥]∥xk-x*∥≤[2+λmaxλmin(∥G∥∥G-1∥+1)]∥I-N∥1Nk∑ωi∈Ωk∥M(ωi)∥∥xk-x*∥+(1+λmaxλmin)α∥I-N∥2∥G∥∥xk-x*∥+α-1∥G-1∥λmaxλmin1Nk∑ωi∈Ωk∥M(ωi)∥2∥xk-x*∥→0,
which means that (5.13) is true.
Next, we show that(5.16)limk→∞∇xΘk(xk)=∇xΘ(x*).
It follows from Lemma 2.2 and Theorem 4.1 that
(5.17)limk→∞∇xΘk(x*)=limk→∞1Nk∑ωi∈Ωk‍∇xfα(x*,ωi)=𝔼∇xfα(x*,ω)=∇xΘ(x*).
By (5.13), we have
(5.18)∥∇xΘk(xk)-∇xΘ(x*)∥≤∥∇xΘk(xk)-∇xΘk(x*)∥+∥∇xΘk(x*)-∇xΘ(x*)∥→0,
which implies that (5.16) is true.
Now we show thatx* is a stationary point of problem (2.5). Since xk is stationary to problem (2.8), that is, for any y∈X,
(5.19)〈∇xΘk(xk),y-xk〉≥0.
Letting k→∞ above, we get from (5.16) that
(5.20)〈∇xΘ(x*),y-x*〉≥0.
Thus, x* is a stationary point of problem (2.5). This completes the proof.



---

*Source: 816528-2012-11-10.xml*