# Stochastic Methods Based onVU-Decomposition Methods for Stochastic Convex Minimax Problems

Authors: Yuan Lu; Wei Wang; Shuang Chen; Ming Huang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper applies sample average approximation (SAA) method based onVU-space decomposition theory to solve stochastic convex minimax problems. Under some moderate conditions, the SAA solution converges to its true counterpart with probability approaching one and convergence is exponentially fast with the increase of sample size. Based on the VU-theory, a superlinear convergent VU-algorithm frame is designed to solve the SAA problem.


---

## Body

## 1. Introduction

In this paper, the following stochastic convex minimax problem (SCMP) is considered:(1)min⁡x∈Rnfx,
where
(2)fx=max⁡Efix,ξ:i=0,…,m,
and the functions fix,ξ:Rn→R, i=0,…,m, are convex and C2, ξ:Ω→Ξ⊂Rn is a random vector defined on probability space (Ω,Υ,P); E denotes the mathematical expectation with respect to the distribution of ξ.SCMP is a natural extension of deterministic convex minimax problems (CMP for short). The CMP has a number of important applications in operations research, engineering problems, and economic problems. While many practical problems only involve deterministic data, there are some important instances where problems data contains some uncertainties and consequently SCMP models are proposed to reflect the uncertainties.A blanket assumption is made that, for everyx∈Rn, Efix,ξ, i=0,…,m, are well defined. Let ξ1,…,ξN be a sampling of ξ. A well-known approach based on the sampling is the so-called SAA method, that is, using sample average value of fi(x,ξ) to approximate its expected value because the classical law of large number for random functions ensures that the sample average value of fi(x,ξ) converges with probability 1 to E[fi(x,ξ)] when the sampling is independent and identically distributed (idd for short). Specifically, we can write down the SAA of our SCMP (1) as follows:
(3)min⁡x∈Rnf^Nx,
where
(4)f^Nx=max⁡f^iNx:i=0,…,m,f^iNx∶=1N∑j=1N‍fix,ξj.
The problem (3) is called the SAA problem and (1) the true problem.The SAA method has been a hot topic of research in stochastic optimization. Pagnoncelli et al. [1] present the SAA method for chance constrained programming. Shapiro et al. [2] consider the stochastic generalized equation by using the SAA method. Xu [3] raises the SAA method for a class of stochastic variational inequality problems. Liu et al. [4] give the penalized SAA methods for stochastic mathematical programs with complementarity constraints. Chen et al. [5] discuss the SAA methods based on Newton method to the stochastic variational inequality problem with constraint conditions. Since the objective functions of the SAA problems in the references talking above are smooth, then they can be solved by using Newton method.More recently, new conceptual schemes have been developed, which are based on theVU-theory introduced in [6]; see else [7–11]. The idea is to decompose Rn into two orthogonal subspaces V and U at a point x¯, where the nonsmoothness of f is concentrated essentially on V and the smoothness of f appears on the U subspace. More precisely, for a given g¯∈∂f(x¯), where ∂f(x¯) denotes the subdifferential of f at x¯ in the sense of convex analysis, then Rn can be decomposed into direct sum of two orthogonal subspaces, that is, Rn=U⊕V, where V=lin⁡(∂f(x¯)-g¯), and U=V⊥. As a result an algorithm frame can be designed for the SAA problem that makes a step in the V space, followed by a U-Newton step in order to obtain superlinear convergence. A VU-space decomposition method for solving a constrained nonsmooth convex program is presented in [12]. A decomposition algorithm based on proximal bundle-type method with inexact data is presented for minimizing an unconstrained nonsmooth convex function in [13].In this paper, the objective function in (1) is nonsmooth, but it has the structure which has the connection with VU-space decomposition. Based on the VU-theory, a superlinear convergent VU-algorithm frame is designed to solve the SAA problem. The rest of the paper is organized as follows. In the next section, the SCMP is transformed to the nonsmooth problem and the proof of the approximation solution set converges to the true solution set in the sense that Hausdorff distance is obtained. In Section 3, the VU-theory of the SAA problem is given. In the final section, the VU-decomposition algorithm frame of the SAA problem is designed.


## 2. Convergence Analysis of SAA Problem

In this section, we discuss the convergence of (3) to (1) as N increases. Specifically, we investigate the fact that the solution of the SAA problem (3) converges to its true counterpart as N→∞. Firstly, we make the basic assumptions for SAA method. In the following, we give the basic assumptions for SAA method.Assumption 1.
(a) LettingX be a set, for i=1,…,n, the limits
(5)MFit∶=lim⁡N→∞MFiNt
exist for every x∈X.
(b) For everys∈X, the moment-generating function Ms(t) is finite-valued for all t in a neighborhood of zero.
(c) There exists a measurable functionκ:Ω→R+ such that
(6)gs′,ξ-gs,ξ≤κξs′-s
for all ξ∈Ω and all s′,s∈X.
(d) The moment-generating functionMκ(t)=E[etκ(ξ)] of κ(ξ) is finite-valued for all t in a neighborhood of zero, where Ms(t)=E[et(g(s,ξ)-G(s))] is the moment-generating function of the random variable g(s,ξ)-G(s).Theorem 2.
LetS* and SN denote the solution sets of (1) and (3). Assuming that both S* and SN are nonempty, then, for any ɛ>0, one has D(SN,S*)<ɛ, where D(SN,S*)=sup⁡x∈SNd(x,S*).Proof.
For any pointsx~∈SN and x∈Rn, we have
(7)f^Nx~=max⁡f^iNx~,i=0,…,m=max⁡1N∑j=1N‍fix~,ξj,i=0,…,m≤max⁡1N∑j=1N‍fix,ξj,i=0,…,m.
From Assumption 1, we know that, for any ɛ>0, there exist M; if N>M, i=0,…,m, then
(8)1N∑j=1N‍fix,ξj-Efix,ξj<ɛ.
By letting N>M, we obtain
(9)f^Nx~≤max⁡1N∑j=1N‍fix,ξj,i=0,…,m≤max⁡Efix,ξj+ɛ,i=0,…,m=fx+ɛ.
This shows that d(x~N,S*)<ɛ, which implies D(x~N,s*)<ɛ.We now move on to discuss the exponential rate of convergence of SAA problem (3) to the true problem (1) as sample increases.Theorem 3.
LetxN be a solution to the SAA problem (3) and S* is the solution set of the true problem (1). Suppose Assumption 1 holds. Then, for every ɛ>0, there exist positive constants c(ɛ) and d(ɛ), such that
(10)ProbdxN,S*≥ɛ≤cɛexp⁡-Nd(ɛ)
for N sufficiently large.Proof.
Letɛ>0 be any small positive number. By Theorem 2 and
(11)1N∑j=1N‍fix,ξj-Efix,ξj<ɛ,
we have d(xN,S)<ɛ. Therefore, by Assumption 1, we have
(12)ProbdxN,S*≥ɛ≤Prob1N∑j=1N‍fix,ξj-Efix,ξj≥δ≤cɛexp⁡-Ndɛ.
The proof is complete.


## 3. TheVU-Theory of the SAA Problem

In the following sections, we give theVU-theory, VU-decomposition algorithm frame, and convergence analysis of the SAA problem.The subdifferential off^N at a point x∈Rn can be computed in terms of the gradients of the function that are active at x. More precisely,
(13)∂f^Nx=Convg∈Rn∣g=∑i∈I(x)αiN∑j=1N∇fix,ξj:α=αii∈I(x)∈ΔIxg∈Rn∣g=∑i∈IxαiN∑j=1N∇fix,ξj,
where
(14)Ix=i∈I∣f^Nx=f^iNx
is the set of active indices at x, and
(15)Δs=α∈Rs∣αi≥0,∑i=1s‍αi=1.
Let x¯∈Rn be a solution of (3). By continuity of the structure functions, there exists a ball Bɛ(x¯)⊆Rn such that
(16)∀x∈Bɛx¯,Ix⊆Ix¯.
For convenience, we assume that the cardinality of I(x¯) is m1+1(m1≤m) and reorder the structure functions, so that I(x¯)={0,…,m1}. From now on, we consider that
(17)∀x∈Bɛx¯,f^Nx=f^iNx,i∈Ix¯.
The following assumption will be used in the rest of this paper.Assumption 4.
The set(18)∇f^iNx-∇f^0Nx0≠i∈I(x¯)
is linearly independent.Theorem 5.
Suppose Assumption4 holds. Then Rn can be decomposition at x¯:Rn=U⊕V, where
(19)V=lin⁡∇f^iNx-∇f^0Nx0≠i∈I(x¯),U=d∈Rn∣d,∇f^iNx-∇f^0Nx0≠i∈I(x¯)=0.Proof.
The proof can be directly obtained by using Assumption4 and the definition of the spaces V and U.
Given a subgradientg¯∈∂f^N with V-component g¯v=V¯Tg¯, the U-Lagrangian of f^N, depending on g¯v, is defined by
(20)Rdim⁡U∋u⟼Luu;g¯v∶=min⁡v∈Rdim⁡Vf^Nx¯+U¯u+V¯v-g¯v,vv.
The associated set of V-space minimizers is defined by
(21)Wu;g¯v∶=v:Luu;g¯v=f^Nx¯+U¯u+V¯v-g¯v,vv.Theorem 6.
Suppose Assumption4 holds. Let χ(u)=x¯+u⊕v(u) be a trajectory leading to x¯ and let H¯:=∇2Lu(0,0). Then for all u sufficiently small the following hold: (i)
the nonlinear system, with variablev and the parameter u,
(22)f^iNx¯+U¯u+V¯v-f^0Nx¯+U¯u+V¯v=0,0≠i∈Ix¯
has a unique solution v=v(u) and v:Rdim⁡U→Rdim⁡V is a C2 function;(ii)
χ(u) is a C2-function with Jχ(u)=U¯+V¯Jv(u);(iii)
Lu(u;0)=f^iN(x¯+u⊕v(u))=f^N(x¯+u⊕v(u))=f^iN(x¯)+(1/2)uTH¯u+o(|u|2);(iv)
∇Lu(u;0)=H¯u+o(|u|);(v)
f^N(χ(u))=f^iN(χ(u)), i∈I(x¯).Proof.
Item (i) follows from the assumption thatfi are C2 and applying a Second-Order Implicit Function Theorem (see [14], Theorem 2.1). Since v(u) is C2, χ(u) is C2 and the Jacobians Jv(u) exist and are continuous. Differentiating the primal track with respect to u, we obtain the expression of Jχ(u) and item (ii) follows.
(iii) By the definition ofLu(u;g¯v) and W(u;g¯v), we have
(23)Luu;0=f^iNx¯+u⊕vu=f^Nx¯+u⊕vu.
According to the second-order expansion ofLu, we obtain
(24)Luu;0=Lu0;0+∇Lu0;0,u+12uT∇2Lu0;0u+ou.
SinceLu(0;0)=f^iN(x¯), i∈I(x¯), ∇Lu(0;0)=0, and H¯=∇2Lu(0;0),
(25)Luu;0=f^iNx¯+12uTH¯u+ou2.
Similar to (iii), we get (iv):(26)∇Luu;0=∇Lu0;0+uT∇2Lu0;0,u+ou2=H¯+ou.
The conclusion of (v) can be obtained in terms of (i) and the definition of χ(u).


## 4. Algorithm and Convergence Analysis

Supposing0∈∂f^N(x¯), we give an algorithm frame which can solve (3). This algorithm makes a step in the V-subspace, followed by a U-Newton step in order to obtain superlinear convergence rate.Algorithm 7 (algorithm frame).
Step
0. Initialization: given ɛ>0, choose a starting point x(0) close to x¯ enough and a subgradient g~(0)∈∂f^N(x(0)) and set k=0.Step
1. Stop if
(27)g~(k)≤ɛ.Step
2. Find the active index set I(x¯).Step
3. Construct VU-decomposition at x¯; that is, Rn=V⊕U. Compute
(28)∇2Lu0;0=U¯TM0U¯,
where
(29)M0=∑i∈I(x¯)‍α¯i∇2f^iNx¯.Step
4. Perform V-step. Compute δV(k) which denotes v(u) in (22) and set x(k)=x(k)+0⊕δV(k).Step
5. Perform U-step. Compute δU(k) from the system
(30)U¯TM0U¯δU+U¯Tg~(k)=0,
where
(31)∑i∈I(x¯)αiu∇f^iNix(k)=g~(k)∈∂f^Nx(k)
is such that V¯Tg~(k)=0. Compute x(k+1)=x~(k)+δU(k)⊕0=x(k)+δU(k)⊕δV(k).Step
6. Update: set k=k+1 and return to Step 1.Theorem 8.
Suppose the starting pointx(0) is close to x¯ enough and 0∈ri∂f^(x¯), ∇2Lu(0;0)≻0. Then the iteration points {x(k)}k=1∞ generated by Algorithm 7 converge and satisfy
(32)x(k+1)-x¯=ox(k)-x¯.Proof.
Letu(k)=(x(k)-x¯)U and v(k)=(x(k)-x¯)V+δV(k). It follows from Theorem 6(i) that
(33)x(k+1)-x¯V=x(k)-x¯Vx(k+1)-x¯Vl=ox(k)-x¯U=ox(k)-x¯.
Since ∇2Lu(0;0) exists and ∇Lu(0;0)=0, we have from the definition of U-Hessian matrix that
(34)∇Luu(k);0=U¯Tg~(k)=0+∇2Lu0;0u(k)+ou(k)U.
By virtue of (30), we have ∇2Lu(0;0)(u(k)+δU(k))=o(∥u(k)∥U). It follows from the hypothesis ∇2Lu(0;0)≻0 that ∇2Lu(0;0) is invertible and hence ∥u(k)+δU(k)∥=o(∥u(k)∥U). In consequence, one has
(35)xk+1-x¯U=xk+1-xkU+xk-xkU+xk-x¯U=u(k)+δU(k)=ou(k)U=ox(k)-x¯.
The proof is completed by combining (33) and (35).



---

*Source: 894248-2014-12-04.xml*