# A Nonlinear Lagrange Algorithm for Stochastic Minimax Problems Based on Sample Average Approximation Method

Authors: Suxiang He; Yunyun Nie; Xiaopeng Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

An implementable nonlinear Lagrange algorithm for stochastic minimax problems is presented based on sample average approximation method in this paper, in which the second step minimizes a nonlinear Lagrange function with sample average approximation functions of original functions and the sample average approximation of the Lagrange multiplier is adopted. Under a set of mild assumptions, it is proven that the sequences of solution and multiplier obtained by the proposed algorithm converge to the Kuhn-Tucker pair of the original problem with probability one as the sample size increases. At last, the numerical experiments for five test examples are performed and the numerical results indicate that the algorithm is promising.


---

## Body

## 1. Introduction

Consider the stochastic minimax problems of the form(1)min-x∈ℜnmax⁡i∈I𝔼[fi(x,ω)],
where I={1,…,m}, ω is a random vector supported on the probability space (Ω,ℱ,𝒫), fi:ℜn×Ω→ℜ(i∈I), 𝔼 denotes expectation with respect to the distribution of ω∈Ω, and 𝔼[fi(x,ω)](i∈I) is well defined. Problem (1) has drawn much attention in recent years, which arises in various situations such as inventory theory, robust optimization, and engineering filed; for example, see [1–5].A nonlinear Lagrange function for problem (1) can be established based on Zhang and Tang [6]; that is,
(2)G(x,u,t)=tln⁡(∑i∈I‍uie(1/t)𝔼[fi(x,ω)]),
where u is Lagrange multiplier and u∈Γ(u)={u∈ℜm∣∑i∈I‍ui=1,ui≥0}, and t>0 is a controlling parameter. The good properties of function (2) were investigated in [6] and the convergence analysis of the corresponding nonlinear Lagrange algorithm was presented in [7]. Although function (2) overcomes the nondifferentiability of the objective function F(x)=max⁡i∈I𝔼[fi(x,ω)] in problem (1), the exact numerical evaluation of the expected value 𝔼[fi(x,ω)](i∈I) in (2) is very difficult because either distribution of random vector ω is unknown or it is too complex to compute the multidimensional integral.The sample average approximation (in short, SAA) method [8–15] is a well-behaved approach for bypassing this difficulty. The idea of SAA method is to generate a random sample ω1,…,ωN of the random variable ω∈Ω with sample size N and approximate the involved expected value function 𝔼[fi(x,ω)](i∈I) by the corresponding sample average function (1/N)∑j=1N‍fi(x,ωj)(i∈I). Inspired by the SAA method, we present the SAA function of G(x,u,t) as follows:
(3)G^N(x,u,t)=tln⁡(∑i∈I‍uie(1/t)g^N,i(x)),
where g^N,i(x)=(1/N)∑j=1N‍fi(x,ωj). Furthermore, we will propose an implementable nonlinear Lagrange algorithm based on SAA function (3), in which function (3) is minimized and the Lagrange multiplier is updated by its SAA form. Under some mild assumptions on problem (1), we will show that the sequences of solution and multiplier generated by the SAA method-based nonlinear Lagrange algorithm converge to the Kuhn-Tucker pair of the original problem with probability one as the sample size N increases.The remainder of this paper is organized as follows. Preliminaries are given in Section2. The SAA method-based nonlinear Lagrange algorithm and convergence analysis are established in Section 3. Section 4 reports the numerical results by using the proposed algorithm to solve five test examples. Finally, conclusions are drawn in Section 5.


## 2. Preliminaries

This section serves as a preparation for the convergence analysis of the proposed SAA method-based nonlinear Lagrange algorithm. The assumptions on problem (1) are provided firstly. Furthermore, some results that are essential to our discussion are listed. At last, we recall the nonlinear Lagrange algorithm in [7].Let(x*,u*) denote the Kuhn-Tucker pair of problem (1). Let δ>0 be small enough and define S(x*,δ)={x∈ℜn∣∥x*-x∥≤δ}. The Lagrange function for problem (1) is defined by L(x,u)=∑i∈I‍ui𝔼[fi(x,ω)]. Set B(x*)={i∣𝔼[fi(x*,ω)]=F(x*),i∈I} and f(x,ω)=(f1(x,ω),…,fm(x,ω))T. We list the following assumptions on problem (1), which will be used in the subsequent theoretical analysis.(A1)
𝔼[f(x,ω)] is twice continuously differentiable on ℜn.(A2)
There exists a nonnegative measurable functionϕ(ω) such that 𝔼[ϕ(ω)] is finite and for every x∈S(x*,δ) the inequality
(4)∥f(x,ω)∥<ϕ(ω)
holds with probability one.(A3)
The random sampleω1,…,ωN is independent and identically distributed.(A4)
(x*,u*) satisfies the K-T condition. That is,
(5)∇xL(x*,u*)=0,u*∈Γ(u),ui*(F(x*)-𝔼[fi(x,ω)])=0,i∈I.(A5)
Strict complementary condition holds; that is,ui*>0 for i∈B(x*).(A6)
Linear independent constraint qualification holds. That is,(6){(1∇𝔼[fi(x*,ω)])∣i∈B(x*)}
is a set of linear independent vectors.(A7)
For ally∈ℜn satisfying ∇𝔼[fi(x*,ω)]Ty=0, i∈B(x*)(y≠0), it holds that
(7)yT∇x2L(x*,u*)y≥λ∥y∥2,where λ>0 is a constant.Definition 1 (see [11]).
For nonempty setsA and B in ℜn, one denotes by dist⁡(x,A)=inf⁡x∈A∥x-x′∥ the distance from x∈ℜn to A and by 𝔻(A,B)=sup⁡x∈Adist⁡(x,B) the deviation of the set A from the set B.Lemma 2 (Heine-Cantor theorem; see [16]).
Ifh(x):M→N is continuous function and M is compact, then h(x) is uniformly continuous, where M and N are two metric spaces.Note. An important special case is that every continuous function from a closed interval to the real numbers is uniformly continuous.Lemma 3.
DefineWNj(x),Wj(x):ℜn→ℜ for j=1,…,p. Suppose that WNj(x) converges to Wj(x) with probability one uniformly on ℜn for j=1,…,p. Then ∑j=1p‍WNj(x) converges to ∑j=1p‍Wj(x) with probability one uniformly on ℜn.Proof.
From the given condition, forj=1,…,p, one has that, for any ϵ>0, there exists Nj∈N+ such that when N>Nj, |WNj(x)-Wj(x)|<ϵ/p holds with probability one for any x∈ℜn.
LetN0=max⁡1≤j≤p{Nj}. Thus we have that, for any ϵ>0, when N>N0, for any x∈ℜn, the following holds with probability one:
(8)|∑j=1p‍WNj(x)-∑j=1p‍Wj(x)|≤∑j=1p‍|WNj(x)-Wj(x)|<p·ϵp=ϵ,
which means that Lemma 3 is true.Algorithm4 is from [7].Algorithm 4.
We have the following.
Step1. Choose t∈(0,t^), where t^∈(0,1), u(0)∈Γ(u), and ϵ∈(0,1) small enough and set k=0.
Step2. Solve
(9)min⁡x∈ℜnG(x,u(k),t)
and obtain the optimal solution x(k).
Step3. If |∑i∈I‍ui(k)(𝔼[fi(x(k),ω)]-F(x(k)))|<ϵ, then stop. Otherwise go to Step 4.
Step4. Update the Lagrange multiplier u(k) by
(10)ui(k+1)=ui(k)e(1/t)𝔼[fi(x(k)]∑j∈I‍uj(k)e(1/t)𝔼[fj(x(k)],i=1,…,m.Step5. Set k=k+1 and return to Step 2.


## 3. The SAA Method-Based Nonlinear Lagrange Algorithm and Its Convergence

In view of the numerical computation difficulty in Algorithm4 and motivated by the SAA method, we provide the following implementable nonlinear Lagrange algorithm based on the SAA method firstly. Furthermore we establish the convergence analysis of the SAA method-based algorithm under assumptions (A1)–(A7) in this section.Implementable SAA method-based Algorithm5 is presented as follows.Algorithm 5.
We have the following.
Step1. Choose t∈(0,t^), where t^∈(0,1), ϵ∈(0,1) small enough, u^N(0)∈Γ(u), and N is large enough. Set k=0.Step2. Solve
(11)min⁡x∈ℜnG^N(x,u^N(k),t)and obtain the optimal solutionx^N(k).Step3. If |∑i∈I‍u^N,i(k)(g^N,i(x^N(k))-F(x^N(k)))|<ϵ, then stop. Otherwise go to Step 4.Step4. Update the Lagrange multiplier u^N(k) by
(12)u^N,i(k+1)=u^N,i(k)e(1/t)g^N,i(x^N(k))∑j∈I‍u^N,j(k)e(1/t)g^N,j(x^N(k)),i=1,…,m.Step5. Set k=k+1 and return to Step 2.Taking into account the local convergence analysis of Algorithm4 given in [7], next we will study the convergence of the sequence pair (x^N(k),u^N(k)) obtained by Algorithm 5 on S(x*,δ)×S(u*,δ). Let v(k) and S(k) denote the optimal value and the set of optimal solutions of min⁡x∈S(x*,δ)G(x,u(k),t) and v^N(k) and S^N(k) denote the optimal value and the set of optimal solutions of min⁡x∈S(x*,δ)G^N(x,u^N(k),t), respectively. Set gi(x)=𝔼[fi(x,ω)].Theorem 6.
If assumptions (A1)–(A3) hold andu^N,i(k) converges to ui(k)(i=1,…,m) with probability one for some k, then the following statements hold: (i)
G^N(x,u^N(k),t) converges to G(x,u(k),t) with probability one uniformly on S(x*,δ);(ii)
v^N(k) converges to v(k) and 𝔻(S^N(k),S(k)) tends to 0 with probability one as N→∞.Proof.
(i) Letφ(a,b)=bea/t, where a,b∈ℜ. Then one has
(13)G^N(x,u^N(k),t)=tln⁡∑i∈I‍φ(g^N,i(x),u^N,i(k)).
Now we prove that φ(g^N,i(x),u^N,i(k)) converges to φ(gi(x),ui(k)) with probability one uniformly on S(x*,δ). Considering the definition of φ(a,b), we have
(14)|φ(g^N,i(x),u^N,i(k))-φ(gi(x),ui(k))|≤|φ(g^N,i(x),u^N,i(k))-φ(g^N,i(x),ui(k))|+|φ(g^N,i(x),ui(k))-φ(gi(x),ui(k))|=|u^N,i(k)e(1/t)g^N,i(x)-ui(k)e(1/t)g^N,i(x)|+|ui(k)e(1/t)g^N,i(x)-ui(k)e(1/t)gi(x)|=e(1/t)g^N,i(x)|u^N,i(k)-ui(k)|+ui(k)|e(1/t)g^N,i(x)-e(1/t)gi(x)|.
It follows from assumption (A1) and Theorem  7.48 in [11] that both g^N,i(x) and gi(x)(i=1,…,m) are continuous at x on S(x*,δ). Consequently, for any x∈S(x*,δ), there exist constants a1 and a2 such that g^N,i(x)∈[a1,a2] and gi(x)∈[a1,a2] for i=1,…,m. Since φ(a,1) is continuous at a on ℜ and from Lemma 2, we have that φ(a,1) is uniformly continuous on [a1,a2]; that is, for any ϵ>0 and x,y∈[a1,a2], there exists δ^>0 such that, for |x-y|<δ^, it holds that
(15)|φ(x,1)-φ(y,1)|<ϵ.
Furthermore, from Theorem  7.48 in [11] we know that g^N,i(x) converges to gi(x) with probability one uniformly on S(x*,δ), which means that, for the above given δ^, there exists N0∈N+ such that when N>N0, the inequality
(16)|g^N,i(x)-gi(x)|<δ^
holds with probability one for any x∈S(x*,δ). In view of formula (15) and formula (16), one draws the conclusion that, for any ϵ>0, there exists N0∈N+ such that when N>N0, it holds that
(17)|φ(g^N,i(x),1)-φ(gi(x),1)|<ϵ
with probability one for any x∈S(x*,δ). That is, e(1/t)g^N,i(x) converges to e(1/t)gi(x) with probability one uniformly on S(x*,δ).
In view ofu^N,i(k) converging to ui(k) with probability one, e(1/t)g^N,i(x) being bounded on S(x*,δ) with probability one, ui(k)∈Γ(u), and formula (14), we obtain that φ(g^N,i(x),u^N,i(k)) converges to φ(gi(x),ui(k)) with probability one uniformly on S(x*,δ) as N→∞. Moreover, one gets that ∑i∈I‍φ(g^N,i(x),u^N,i(k)) converges to ∑i∈I‍φ(gi(x),ui(k)) with probability one uniformly on S(x*,δ) as N→∞ from Lemma 3.
Next we prove thatG^N(x,u^N(k),t) converges to G(x,u(k),t) with probability one uniformly on S(x*,δ). Let ΦN(x)=∑i∈I‍φ(g^N,i(x),u^N,i(k)) and Φ(x)=∑i∈I‍φ(gi(x),ui(k)). Hence, one has
(18)|G^N(x,u^N(k),t)-G(x,u(k),t)|=t|ln⁡ΦN(x)-ln⁡Φ(x)|.
From the above discussion, we know that ΦN(x), Φ(x)∈[ea1/t,ea2/t] for any x∈S(x*,δ). Since ϕ(y)=ln⁡y is continuous at y on ℜ++ and by Lemma 2, we obtain that ϕ(y) is uniformly continuous on the interval [ea1/t,ea2/t]. That is, for any ϵ0>0 and x′,y′∈[ea1/t,ea2/t], there exists δ¯>0 such that, for |x′-y′|<δ¯, it holds that
(19)|ln⁡x′-ln⁡y′|<ϵ0.
Moreover, for the given δ¯, there exists N0∈N+ such that, for N>N0, it holds that
(20)|ΦN(x)-Φ(x)|<δ¯
with probability one for any x∈S(x*,δ). From formulas (19) and (20), it follows that, for any ϵ0>0, there exists N0∈N+ such that, for N>N0, the following inequality holds:
(21)|ln⁡ΦN(x)-ln⁡Φ(x)|<ϵ0
with probability one for any x∈S(x*,δ). Combined with formula (18), statement (i) is true.(ii)
From statement (i) and Theorem  5.3 in [11], statement (ii) is obtained. The proof of Theorem 6 is completed.Theorem 7.
If assumptions (A1)–(A3) hold, lettingu^N,i(0)=ui(0), i=1,…,m, then, for any k≥1, the following statements hold:(i)
u^N,i(k) converges to ui(k) with probability one for i=1,…,m;(ii)
G^N(x,u^N(k),t) converges to G(x,u(k),t) with probability one uniformly on S(x*,δ);(iii)
v^N(k) tends to v^(k), and 𝔻(S^N(k),S(k)) tends to 0 with probability one as N→∞.Proof.
(i) We use the mathematical induction method to show that statement (i) is true below.(a)
Letk=1; then for i=1,…,m we have
(22)u^N,i(1)=u^N,i(0)e(1/t)g^N,i(x^N(0))∑j∈I‍u^N,j(0)e(1/t)g^N,j(x^N(0)),ui(1)=ui(0)e(1/t)gi(x(0))∑j∈I‍uj(0)e(1/t)gj(x(0)).
Consideringu^N,i(0)=ui(0), we have that x^N(0) converges to x(0) with probability one from Theorem 6. For j=1,…,m, it holds that
(23)|g^N,j(x^N(0))-gj(x(0))|≤|g^N,j(x^N(0))-gj(x^N(0))|+|gj(x^N(0))-gj(x(0))|.
Noting that the first term in the right-hand side of formula (23) converges to 0 with probability one by Theorem  7.48 in [11] and the second term converges to 0 with probability one for gj(x) being continuous, we obtain that g^N,j(x^N(0)) converges to gj(x(0)) with probability one. Moreover, since m(y)=ey/t is continuous at y on ℜ, one gets that e(1/t)g^N,j(x^N(0)) converges to e(1/t)gj(x(0)) with probability one. Then it follows from the properties of convergent sequence that u^N,i(1) converges to ui(1) with probability one for i=1,…,m.(b)
Whenk=p, we assume that u^N,i(p) converges to ui(p) with probability one for i=1,…,m. Then, when k=p+1, next we prove that u^N,i(p+1) converges to ui(p+1) with probability one for i=1,…,m.
Letk=p+1; then for i=1,…,m one has
(24)u^N,i(p+1)=ui(p)e(1/t)g^N,i(x^N(p))∑j∈I‍uj(p)e(1/t)g^N,j(x^N(p)),ui(p+1)=ui(p)e(1/t)gi(x(p))∑j∈I‍uj(p)e(1/t)gj(x(p)).
From Theorem6, we know that x^N(p) converges to x(p) with probability one as N→∞. By a similar proof process to that in (a), we have that e(1/t)g^N,j(x^N(p)) converges to e(1/t)gj(x(p)) with probability one for j=1,…,m. For j=1,…,m, one has that
(25)|u^N,j(p)e(1/t)g^N,j(x^N(p))-uj(p)e(1/t)gj(x(p))|≤|u^N,j(p)e(1/t)g^N,j(x^N(p))-uj(p)e(1/t)g^N,j(x^N(p))|+|uj(p)e(1/t)g^N,j(x^N(p))-uj(p)e(1/t)gj(x(p))|=e(1/t)g^N,j(x^N(p))|u^N,j(p)-uj(p)|+uj(p)|e(1/t)g^N,j(x^N(p))-e(1/t)gj(x(p))|.
Noting that the first term of (25) tends to 0 with probability one as N→∞ for u^N,j(p) converging to uj(p) with probability one and e(1/t)g^N,j(x^N(p)) being bounded on S(x*,δ) with probability one and the second term tends to 0 with probability one as N→∞ for uj(p)∈(0,1), we obtain that u^N,j(p)e(1/t)g^N,j(x^N(p)) converges to uj(p)e(1/t)gj(x(p)) with probability one. Then it follows from properties of convergent sequence that u^N,i(p+1) converges to ui(p) with probability one for i=1,…,m.
According to (a) and (b), we have that statement (i) holds.(ii)
From statement (i) and Theorem6, we obtain that statement (ii) is true.(iii)
From statement (ii) and Theorem  5.3 in [11], one has that statement (iii) holds.The above theorem shows that the sample average approximation Lagrange multiplieru^N(k) converges to its counterpart u(k) with probability one, and the optimal value and optimal solutions of the subproblem min⁡x∈S(x*,δ)G^N(x,u^N(k),t) converge to their counterparts of the subproblem min⁡x∈S(x*,δ)G(x,u(k),t) with probability one under some mild conditions. Next we will analyze the convergence of Algorithm 5 under some mild conditions.Theorem 8.
If assumptions (A1)–(A7) hold, lettingu^N,i(0)=ui(0)(i=1,…,m), then there exist δ>0 and t^∈(0,1) such that, for any (u(0),t)∈S(u*,δ)×(0,t^), it holds that the sequence pair (x^N(k),u^N(k)) converge to the K-T pair (x*,u*) with probability one.Proof.
Under assumptions (A1) and (A4)–(A7), from Theorem  3.1 in [7], we have that there exist δ>0 and t^∈(0,1) such that, for any k≥1 and (u(0),t)∈S(u*,δ)×(0,t^), the following inequality holds:
(26)max⁡{∥x(k)-x*∥,∥u(k)-u*∥}≤cktk∥u(0)-u*∥,
where c>0 is a constant, which implies that the pair (x(k),u(k)) tend to the K-T pair (x*,u*) of the original problem (1) as k→∞.
Since assumptions (A1)–(A3) hold andu^N,i(0)=ui(0)(i=1,…,m), it follows by Theorem 7 that the pair (x^N(k),u^N(k)) converge to the pair (x(k),u(k)) with probability one as N→∞.
Furthermore, since(27)∥x^N(k)-x*∥≤∥x^N(k)-x(k)∥+∥x(k)-x*∥,∥u^N(k)-u*∥≤∥u^N(k)-u(k)∥+∥u(k)-u*∥,
the conclusion is obtained.Remark 9.
Theorem8 shows that, under some mild assumptions, the sequence pair (x^N(k),u^N(k)) generated by Algorithm 5 locally tend to the K-T pair (x*,u*) of the original problem (1) with probability one as N→∞ and k→∞ when the controlling parameter t is less than the threshold t^.


## 4. Numerical Results

The numerical results for five test examples by using Algorithm5 are presented in this section, where the five test problems are compiled based on the deterministic optimization problems in the literature [17, 18]. The numerical experiments are implemented in Matlab 7.1 runtime environment on the same computer, whose basic parameters are Intel CORE i3-2310 M@2.10 GHz and memory 2 Gb.In the experiments, the sampleω1,…,ωN with sample size N is generated by unifrnd in Matlab 7.1. For each problem, we choose N=102, N=103, N=104, N=105, N=106, and N=107, respectively, to make comparison. The initial value uN(0)=(1/m,…,1/m)T for each example. Unconstrained minimization problem in Step 2 of Algorithm 5 is solved by BFGS quasi-Newton method combined with Wolf nonexact linear search rule, and the control precision is 10-6 in this step. The stopping criterion in Step 3 is
(28)|∑i∈I‍u^N,i(k)(g^N,i(x^N(k))-F(x^N(k)))|≤ɛ,
where ɛ=10-8.The obtained numerical results are reported in Tables1–5, in which N, 1/t, iter., ∥x*-x^N(k)∥, and ∥v^N(k)-v*∥ represent the sample size, the value of controlling parameter, the number of iterations, the error between the solution sequence x^N(k) by Algorithm 5 and the optimal solution x* of problem (1), and the error between the optimal value v^N(k) by Algorithm 5 and the optimal value v* of problem (1), respectively.Table 1
The numerical results for Example1.
N
1
/
t
Iter.
∥
x
*
-
x
^
N
(
k
)
∥
∥
v
^
N
(
k
)
-
v
*
∥
1
0
2
10
3
1.904585
e
-
001
1.929105
e
-
001
1
0
3
10
2
5.976346
e
-
002
2.127908
e
-
002
1
0
4
10
1
3.668249
e
-
002
8.282325
e
-
002
1
0
5
10
1
5.525511
e
-
003
3.098093
e
-
003
1
0
6
10
1
1.319634
e
-
003
1.279392
e
-
003
1
0
7
10
1
5.493409
e
-
004
9.275895
e
-
004Table 2
The numerical results for Example2.
N
1
/
t
Iter.
∥
x
*
-
x
^
N
(
k
)
∥
∥
v
^
N
(
k
)
-
v
*
∥
1
0
2
5
2
4.503171
e
-
001
1.050617
e
-
001
1
0
3
5
2
1.604489
e
-
001
1.028518
e
-
001
1
0
4
5
2
4.014238
e
-
002
1.801205
e
-
002
1
0
5
5
2
6.732682
e
-
003
4.511915
e
-
003
1
0
6
5
4
4.870377
e
-
003
1.690755
e
-
003
1
0
7
5
4
3.176635
e
-
004
1.530397
e
-
004Table 3
The numerical results for Example3.
N
1
/
t
Iter.
∥
x
*
-
x
^
N
(
k
)
∥
∥
v
^
N
(
k
)
-
v
*
∥
1
0
2
11
4
8.816640
e
-
002
2.888003
e
-
001
1
0
3
11
4
2.816097
e
-
002
1.355825
e
-
001
1
0
4
11
4
2.859081
e
-
003
1.536729
e
-
003
1
0
5
11
3
4.731965
e
-
003
1.960690
e
-
003
1
0
6
11
4
4.279962
e
-
004
8.171314
e
-
004
1
0
7
11
4
2.830422
e
-
004
1.131960
e
-
004Table 4
The numerical results for Example4.
N
1
/
t
Iter.
∥
x
*
-
x
^
N
(
k
)
∥
∥
v
^
N
(
k
)
-
v
*
∥
1
0
2
3.63
2
8.258801
e
-
002
3.835420
e
+
000
1
0
3
3.63
2
5.495890
e
-
002
2.518867
e
+
000
1
0
4
3.63
2
3.114568
e
-
002
1.552539
e
+
000
1
0
5
3.63
2
7.241573
e
-
003
4.854735
e
-
002
1
0
6
3.63
3
6.411032
e
-
005
6.869434
e
-
004
1
0
7
3.63
3
4.752318
e
-
005
1.734132
e
-
004Table 5
The numerical results for Example5.
N
1
/
t
Iter.
∥
x
*
-
x
^
N
(
k
)
∥
∥
v
^
N
(
k
)
-
v
*
∥
1
0
2
1.26
5
2.210460
e
-
001
3.206412
e
+
000
1
0
3
1.26
5
1.040470
e
-
002
1.698143
e
-
001
1
0
4
1.26
6
3.016663
e
-
003
2.977730
e
-
002
1
0
5
1.26
6
2.854231
e
-
003
2.331369
e
-
002
1
0
6
1.26
6
6.241527
e
-
004
5.987215
e
-
003
1
0
7
1.26
6
1.796381
e
-
004
1.225449
e
-
003Example 1 (Hald-Madson [17]).
Consider the unconstrained min-max stochastic problem (1), in which ω is uniformly distributed on Ω=[0,1] and fi:ℜ2×Ω→ℜ(i=1,…,4) are given by
(29)f1(x,ω)=10(2ωx2-3ω2x12),f2(x,ω)=-f1(x,ω),f3(x,ω)=4ω3-2ωx1,f4(x,ω)=-f3(x,ω).
This problem has the optimal solution x*=(1,1)T and the optimal value v*=0. The numerical results for this example obtained by Algorithm 5 are shown in Table 1.Example 2 (Beale [18]).
Consider the unconstrained min-max stochastic problem (1), in which ω is uniformly distributed on Ω=[0,1] and fi:ℜ3×Ω→ℜ(i=1,…,5) are given by
(30)f1(x,ω)=4ωx12+2x22+x32+6ω2x1x2+2x1x3-8x1-18ω2x2-8ωx3+9,f2(x,ω)=f1(x,ω)+10(x1+3ω2x2+2x3-6ω),f3(x,ω)=f1(x,ω)-10x1,f4(x,ω)=f1(x,ω)-30ω2x2,f5(x,ω)=f1(x,ω)-20ωx3.
This problem has the optimal solution x*=(4/3,7/9,4/9)T and the optimal value v*=1/9. The numerical results for this example obtained by Algorithm 5 are shown in Table 2.Example 3 (Rosen Suzuki [18]).
Consider the unconstrained min-max stochastic problem (1), in which ω is uniformly distributed on Ω=[0,1] and fi:ℜ4×Ω→ℜ(i=1,…,4) are given by
(31)f1(x,ω)=3ω2x12+x22+6ω2x32+2ωx42-5x1-20ω3x2-23x3+7x4,f2(x,ω)=11x12+22ωx22+12x32+44ω3x42+5x1-15x2-11x3-3x4-160ω,f3(x,ω)=11x12+21x22+36ω2x32+21x42-15x1-10ωx2-21x3-9ω2x4-100,f4(x,ω)=11x12+11x22+12x32+3ω2x42+15x1-15x2-21x3-3x4-150ω2.
This problem has the optimal solution x*=(0,1,2,-1)T and the optimal value v*=-44. The numerical results for this example obtained by Algorithm 5 are shown in Table 3.Example 4 (Wong 1 [17]).
Consider the unconstrained min-max stochastic problem (1), in which ω is uniformly distributed on Ω=[0,1] and fi:ℜ7×Ω→ℜ(i=1,…,5) are given by
(32)f(x,ω)=(x1-10)2+5(x2-12)2+2ωx34+3(x4-11)2+10x56+7x62+3ω2x74-4x6x7-10x6-8x7.f1(x,ω)=f(x,ω),f2(x,ω)=f(x,ω)-10(-2x12-9ω2x24-x3-4x42-5x5+120+21ω2),f3(x,ω)=f(x,ω)-10(-7x1-6ωx2-10x32-2ωx4+x5+282),f4(x,ω)=f(x,ω)-10(-23x1-3ω2x22-6x62+8x7+196),f5(x,ω)=f(x,ω)-10(-4x12-2ωx22+3x1x2-6ω2x32-5x6+11x7),
This problem has the optimal solution x*=(2.3305,1.9514,-0.47754,4.3657,-0.62449,1.0381,1.5942)T and the optimal value v*=680.6301. The numerical results for this example obtained by Algorithm 5 are shown in Table 4.Example 5 (Wong 2 [18]).
Consider the unconstrained min-max stochastic problem (1), in which ω is uniformly distributed on Ω=[0,1] and fi:ℜ10×Ω→ℜ(i=1,…,9) are given by
(33)f(x,ω)=x12+2ωx22+x1x2-14x1-48ω2x2+(x3-10)2+4(x4-5)2+(x5-3)2+4ω(x6-1)2+5x72+7(x8-11)2+2(x9-10)2+(x10-7)2+45,f1(x,ω)=f(x,ω),f2(x,ω)=f(x,ω)-10(-6ω(x1-2)2-4(x2-3)2-2x32+7x4+120),f3(x,ω)=f(x,ω)-10(-15ω2x12-8x2-(x3-6)2+4ωx4+40),f4(x,ω)=f(x,ω)-10(-2ω3(x1-8)2-2(x2-2)2-3x52+2ωx6+30),f5(x,ω)=f(x,ω)-10(-x12-2(x2-2)2+2x1x2-14x5+6x6),f6(x,ω)=f(x,ω)-10(-4x1-10ωx2+3x7-9x8+105),f7(x,ω)=f(x,ω)-10(-10x1+8x2+17x7-6ω2x8),f8(x,ω)=f(x,ω)-10(3x1-12ωx2-12(x9-8)2+7x10),f9(x,ω)=f(x,ω)-10(8x1-2x2-5x9+2x10+24ω).
This problem has the optimal solution
(34)x*=(2.171996,2.363683,8.773926,5.095985,0.990655,1.430574,1.321644,9.828726,8.280092,8.375927)T
and the optimal value v*=24.306209. The numerical results for this example obtained by Algorithm 5 are shown in Table 5.
From the above numerical results, the following remarks are proposed.Remark 10.
The preliminary numerical results show that Algorithm5 is feasible and promising.Remark 11.
Compared with the numerical results for the same test example with the different sample sizeN, the above numerical results show that, with the sample size being chosen larger, the precision of the optimal solution and the optimal value by Algorithm 5 become higher, which coincides with the theoretical analysis in Section 3.


## 5. Conclusions

This paper investigates a nonlinear Lagrange algorithm for solving stochastic minimax problems based on the sample average approximation method. And the convergence theory of the proposed algorithm is established under some assumptions. Furthermore, the preliminary numerical results are reported to demonstrate the feasibility and effectiveness of the algorithm. The future works on improving the numerical experiments to obtain the solutions with higher precision and performing the numerical experiments for large-scale test examples deserve our further attention. And applying this proposed algorithm to some practical problems is also interesting.



---

*Source: 497262-2014-04-03.xml*