# An Implementable SAA Nonlinear Lagrange Algorithm for Constrained Minimax Stochastic Optimization Problems

Authors: Chuanmei Wang; Suxiang He; Haiying Wu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper proposes an implementable SAA (sample average approximation) nonlinear Lagrange algorithm for the constrained minimax stochastic optimization problem based on the sample average approximation method. A computable nonlinear Lagrange function with sample average approximation functions of original functions is minimized and the Lagrange multiplier is updated based on the sample average approximation functions of original functions in the algorithm. And it is shown that the solution sequences obtained by the novel algorithm for solving subproblem converge to their true counterparts with probability one as the sample size approximates infinity under some moderate assumptions. Finally, numerical experiments are carried out for solving some typical test problems and the obtained numerical results preliminarily demonstrate that the proposed algorithm is promising.


---

## Body

## 1. Introduction

Minimax stochastic optimization is a kind of important problem in stochastic optimization. Minimax stochastic optimization has drawn much attention in recent years, which has been widely applied in subjects such as inventory theory, finance optimization, control science, and engineering field (see [1–7]).This paper considers the constrained minimax stochastic optimization problems as follows:(1)minTxs.t.Egjx,ξ≤0,j=1,…,p,Ehlx,ξ=0,l=1,…,q,where T(x)=maxi∈{1,2,…,m}Efix,ξ, ξ:Ω→Ξ⊆Rk is a random vector that is defined on the probability space (Ω,F,P), E denotes mathematical expectation with respect to the distribution of ξ∈Ξ, and fi:Rn×Ξ→R(i=1,…,m), gj:Rn×Ξ→R(j=1,…,p) and hl:Rn×Ξ→R(l=1,…,q) are well-defined. Since the objective function T(x) is not differentiable, the efficient smooth optimization methods cannot be used to solve the problem (1) directly. Moreover, either distribution of random vector ξ is unknown or it is too complex to compute the multidimensional integral, so the exact numerical evaluation of the expected value functions in problem (1) is very difficult, which results in that problem (1) cannot be solved directly by the traditional deterministic optimization methods even though problem (1) is smooth.On the one hand, as one of the famous smoothing techniques aiming to overcome the nonsmoothness ofT(x) (see [1, 8–16]), the nonlinear Lagrange method has many interesting merits, such as no restrictions on the feasibility of variables x, improvement on the convergence rate and the numerical robustness compared with penalty method by introducing the Lagrangian multipliers as the main driving force. On the other hand, the sample average approximation method is one of the well-behaved approaches for solving stochastic programming problems, the basic idea of which is to generate an independent and identically distributed (i.i.d.) sample ξ1,⋯,ξN of the random variable ξ∈Ξ with sample size N by Monte Carlo sampling method and approximate the involved expected value functions in problem (1) by their corresponding sample average functions. The SAA method has drawn much attention from many authors, see the comprehensive work by Shapiro [17] and the other works in [18–30].Motivated by the effectiveness of the nonlinear Lagrange method, this paper presents a nonlinear Lagrange function for problem (1) based on the work in [13] as follows:(2)L¯x,u,v,y,z,t=tln∑i∈MuieFix-z/t+∑j∈PvjeGjx/t-1+1t∑l∈Qyl+12tHlxHlx,where Fi(x)=E[fi(x,ξ)], Gj(x)=E[gj(x,ξ)], Hl(x)=E[hl(x,ξ)], u=(u1,…,um)T∈U(m)(U(m)≔{u∈Rm∣∑i=1mui=1,ui≥0, i∈M={1,…,m}}), v=(v1,…,vp)T∈R+p(R+p≔{v∈Rp∣vj≥0, j∈P={1,…,p}}, y=(y1,…,yq)T∈Rq, (u,v,y) is Lagrange multiplier, Q={1,…,q}, t>0 is a penalty parameter, and z∈R is an estimate of the objective function T(x). L¯(x,u,v,y,z,t) has good properties and the corresponding nonlinear Lagrangian algorithm is recalled below (see [13]).Algorithm 1.
​​
Step 1. Choose t∈(0,t^), where t^∈(0,1), u(0)∈U(m), v(0)∈R++p(R++p≔{v∈Rp|vj>0,j∈P}), y(0)∈Rq, z(0)∈R++(R++≔{z∈R|z>0}), and ε∈(0,1) being small enough and set k=0.
Step 2. Solve(3)minx∈RnL¯x,uk,vk,yk,zk,tand obtain the optimal solution x(k).
​
Step 3. If ∑i∈Mui(k)(Fi(x(k))-T(x(k)))+∑j∈Pvj(k)Gj(x(k))+Hl(x(k))≤ε, then stop; otherwise go to Step 4.
​
Step 4. Update the Lagrange multiplier ui(k),vj(k),yl(k), and z(k) by (4)uik+1=uikeFixk/t∑i=1muikeFixk/t,i∈M,vjk+1=vjkeGjxk/t,j∈P,ylk+1=ylk+1tHlxk,l∈Q,zk+1=tln∑i=1muikeFixk/t.
Step 5. Set k=k+1 and return to Step 2.In view of the difficulty in the numerical computation of the expected value function in Algorithm1 and the inspiration from the SAA method, this paper will propose an implementable SAA nonlinear Lagrange algorithm in Section 3. And under some suitable assumptions, the convergence of the proposed algorithm will be analyzed in Section 3. In Section 2, some useful preliminaries will be presented. Furthermore, the numerical results for some typical test problems are reported to verify the feasibility and effectiveness of the proposed algorithm in Section 4. In the last section, the conclusion is drawn.


## 2. Preliminaries

This section serves as a preparation for the theoretical analysis in the subsequent section. Firstly, this section provides some assumptions on problem (1), and then recalls some related definitions and conclusions.The Lagrange function for problem (1) is defined by L(x,u,v,y)=∑i∈MuiFi(x)+∑j∈PvjGj(x)+∑l∈QylHl(x). Let (x∗,u∗,v∗,y∗) denote the Karush-Kuhn-Tucker (KKT) solution of problem (1) and z∗=T(x∗) (see [13]). Let δ>0 be small enough. Define S(x∗,δ)={x∈Rn∣x-x∗≤δ}, S(u∗,δ)={u∈Rm∣u-u∗≤δ}, S(v∗,δ)={v∈Rp∣v-v∗≤δ}, S(y∗,δ)={y∈Rq∣y-y∗≤δ}, and S(z∗,δ)={z∈R∣z-z∗≤δ}. Define Bδ(x∗,u∗,v∗,y∗,z∗)={(x,u,v,y,z)∈Rn×Rm×Rp×Rq×R∣x∈S(x∗,δ),u∈S(u∗,δ),v∈S(v∗,δ),y∈S(y∗,δ),z∈S(z∗,δ)}. Some assumptions on problem (1) are made as follows:(a)
For anyξ∈Ξ, f(x,ξ), g(x,ξ), h(x,ξ) are twice continuously differentiable with respect to x on S(x∗,δ), and the function values are finite, where f(x,ξ)=(f1(x,ξ),⋯,fm(x,ξ))T, g(x,ξ)=(g1(x,ξ),⋯,gp(x,ξ))T, and h(x,ξ)=(h1(x,ξ),⋯,hq(x,ξ))T.(b)
There exist nonnegative measurable functionspi(ξ)(i=1,2,3) such that E[pi(ξ)](i=1,2,3) being finite and for every x∈S(x∗,δ) the following inequalities are true with probability one: (5)supx∈Sx∗,δfx,ξ<p1ξ,supx∈Sx∗,δgx,ξ<p2ξ,supx∈Sx∗,δhx,ξ<p3ξ.(c)
The random sampleξ1,…,ξN is independent and identically distributed, and obeys the law of large numbers.(d)
For ease of presentation, assume(6)I1x∗=i∣Fix∗=Tix∗,i∈M=1,…,r1,I2x∗=j∣Gjx∗=0,j∈P=1,…,r2.(e)
KKT condition holds. That is,(7)∇xLx∗,u∗,v∗,y∗=0,u∗∈Um,v∗∈R+p,y∗∈Rq,ui∗Tx∗-Fix∗=0,i∈M,vj∗Gjx∗=0,Gjx∗≤0,j∈P,Hlx∗=0,l∈Q.(f)
Strict complementarity condition holds, i.e.,vj∗>0 for i∈I1(x∗) and ui∗>0 for j∈I2(x∗).(g)
The vectors of{∇Fi(x∗)∣i∈I1(x∗)}∪{∇Gj(x∗)∣i∈I2(x∗)}∪{∇Hl(x∗)∣l∈Q} are linearly independent.(h)
There exists a constantλ>0 such that, for all y¯ in Rn satisfying ∇Fi(x∗)Ty¯=0, i∈I1(x∗), ∇Gj(x∗)Ty¯=0, j∈I2(x∗), and ∇Hl(x∗)Ty¯=0, l∈Q, it holds that (8)y¯T∇x2Lx∗,u∗,v∗,y∗y¯≥λy¯2.The following definition (see [17]) is recalled.Definition 2.
For nonempty setsA and B in Rn, we denote by dist(x,A)=infx′∈Ax-x′ the distance from x∈Rn to A, and by D(A,B)=supx∈Adist(x,B) the deviation of the set A from the set B.To present the basic lemma, we now consider the following stochastic optimization problem:(9)minx∈Cdx≔EDx,ξ,where C is a nonempty and compact subset on Rn, ξ is a random vector on Ξ, D:C×Ξ→R. For any ξ∈Ξ, D(x,ξ) is finite and continuous for all x∈C. The sample average approximation problem of (9) can be expressed as(10)minx∈Cd^Nx≔1N∑j=1NDx,ξj,where ξ1,…, and ξN are N independent sample observations and obey the law of large numbers. Let υ∗ and S denote the optimal value and the optimal solution set of problem (9), υ^N and S^N indicate the optimal value and the optimal solution set of problem (10). Then the resulted essential conclusion is obtained in Lemma 3.Lemma 3 (see [17]).
Suppose that there exists a nonnegative measurable functionp¯(ξ) independent of x for Dx,ξ such that supx∈CDx,ξ≤p¯ξ with probability one. Then the following conclusions are true: (i)
d(x) is continuous and finite on C;(ii)
d^N(x) converges to d(x) with probability one uniformly on C as N→∞;(iii)
υ^N converges to υ∗ with probability one as N→∞;(iv)
D(S^N,S) converges to 0 with probability one as N→∞.


## 3. The SAA Nonlinear Lagrange Algorithm and Its Convergence

This section presents an implementable SAA nonlinear Lagrange algorithm based on the SAA nonlinear Lagrange function of nonlinear Lagrange function (2) and then analyzes its convergence by means of the preliminaries in Section 2.Firstly, we construct a SAA nonlinear Lagrange function of nonlinear Lagrange function (2) below:(11)L¯N.=tln∑i∈MuieF^N,ix-z/t+∑j∈PvjeG^N,jx/t-1+1t∑l∈Qyl+12tH^N,lxH^N,lx,where (.) denotes (x,u,v,y,z,t), F^N,i(x)=(1/N)∑k=1Nfi(x,ξk), G^N,j(x)=(1/N)∑k=1Ngj(x,ξk), H^N,l(x)=(1/N)∑k=1Nhl(x,ξk), and ξ1,…,ξN is a random sample.Based on the SAA nonlinear Lagrange function (11) and Algorithm 1, an implementable SAA nonlinear Lagrange algorithm is presented as follows.Algorithm 4.
​​
Step 1. Choose t∈(0,t^), where t^∈(0,1), ϵ∈(0,1) being small enough, u^N(0)∈U(m), v^N(0)∈R++p, y^N(0)∈Rq, z^N(0)∈R++, and N is large enough. Set k=0.
Step 2. Solve(12)minx∈RnL¯Nx,u^Nk,v^Nk,y^Nk,z^Nk,tand obtain the optimal solution x^N(k).Step 3. If ∑i∈Mu^N,i(k)(F^N,i(x^N(k))-T(x^N(k)))+∑j∈Pv^N,j(k)G^N,j(x^N(k))+H^N(x^N(k))≤ε, then stop; otherwise go to.Step 4. Update the Lagrange multiplier u^N,i(k),v^N,j(k),y^N,l(k), and z^N(k) by (13)u^N,ik+1=u^N,ikeF^N,ix^Nk/t∑i=1mu^N,ikeF^N,ix^Nk/t,i∈M,v^N,jk+1=v^N,jkeG^N,jx^Nk/t,j∈P,y^N,lk+1=y^N,lk+1tH^N,lx^Nk,l∈Q,z^Nk+1=tln∑i=1mu^N,ikeF^N,ix^Nk/t.Step 5. Set k=k+1 and return to Step 2.Next, we study the convergence of Algorithm4 on Bδx∗,u∗,v∗,y∗,z∗ based on the assumptions (a)-(h) and Lemma 3 in Section 2. Let υN(k) and S^N(k) denote the optimal value and optimal solution set of problem (12), υ(k) and S(k) denote the optimal value and optimal solution set of problem (3).Theorem 5.
If assumptions (a)-(c) hold and fork(k=0,1,…), u^N,i(k) converges to ui(k)(i=1,…,m) with probability one, v^N,j(k) converges to vj(k)(j=1,…,p) with probability one, y^N,l(k) converges to yl(k)(l=1,…,q) with probability one, and z^N(k) converges to z(k) with probability one as N→∞, then the following statements are true. (i)
L¯N(x,u^N(k),v^N(k),y^N(k),z^N(k),t) converges to L¯(x,u(k),v(k),y(k),z(k),t) with probability one uniformly as N→∞ on S(x∗,δ);(ii)
υN(k) converges to υ(k) with probability one and D(S^N(k),S(k)) converges to 0 with probability one as N→∞.Proof.
(i) Defineφ(1)(a,b,z,t)=ae(b-z)/t, φ(2)(c,d,t)=d(ec/t-1), and φ3(e,f,t)=(1/t)(e+(1/2t)f)f, where a,b,z,c,d,e,f∈R and t is defined as in (2). And set(14)ϕx,t=∑i∈Mφ1uik,Fix,zk,t+∑j∈Pφ2vjk,Gjx,t+∑l∈Qφ3ylk,Hlx,t,ϕNx,t=∑i∈Mφ1u^N,ik,F^N,ix,z^Nk,t+∑j∈Pφ2v^N,jk,G^N,jx,t+∑l∈Qφ3y^N,lk,H^N,lx,t.
At first, we are to prove thatϕN(x) converges to ϕ(x) with probability one uniformly as N→∞, for which we need to prove that as N→∞, φ(1)(uN,i(k), F^N,i(x),z^N(k),t) converges to φ(1)(ui(k),Fi(x),z(k),t)(i=1,…,m) with probability one uniformly, φ(2)(vN,j(k),G^N,j(x),t) converges to φ(2)(vj(k),Gj(x),t)(j=1,…,p) with probability one uniformly, and φ(3)(yN,l(k),H^N,l(x),t) converges to φ(3)(yl(k),Hl(x),t)(l=1,…,q) with probability one uniformly on S(x∗,δ), respectively. The proof for it is divided into the following three parts.
(A) First we shall prove that asN→∞, φ(1)(uN,i(k),F^N,i(x),zN(k)) converges to φ1(uik,Fix,zk)i=1,…,m with probability one uniformly on S(x∗,δ).
According to the definition ofφ(1)(a,b,z), we have(15)φ1u^N,ik,F^N,ix,z^Nk,t-φ1uik,Fix,zk,t=u^N,ikeF^N,ix-z^Nk/t-uikeF^N,ix-z^Nk/t+uikeF^N,ix-z^Nk/t-uikeFix-zk/t≤u^N,ik-uikeF^N,ix-z^Nk/t+uikeF^N,ix-z^Nk/t-eFix-zk/t.
One has thatF^N,i(x) and Fi(x)(i=1,…,m) are continuous on S(x∗,δ) with respect to x from the assumption (a) and Lemma 3, so there exists a closed interval [c1,d1](c1,d1∈R) such that F^N,i(x)∈c1,d1, and Fi(x)∈c1,d1 for x∈S(x∗,δ). Since z^N(k) and z(k) are bounded, there exist c1′, d1′∈R, such that F^N,i(x)-zN(k)∈[c1′,d1′] and Fi(x)-z(k)∈[c1′,d1′]. Thus, we have that e(F^N,i(x)-zNk)/t is bounded on S(x∗,δ) with respect to x. Let P(y)=ey/t(y∈R). Then P(y) is continuous in [c1′,d1′] with respect to y. It follows that P(y) is continuous uniformly in [c1′,d1′] from the property of continuous function. That is, for any ε>0, there exists δ^1, for x,y∈[c1′,d1′]; if x-y<δ^1, it holds that(16)ex/t-ey/t<ε.
Note thatF^N,i(x) converges to Fi(x)(i=1,…,m) with probability one uniformly on S(x∗,δ) from Lemma 3 and z^N(k) converges to z(k) with probability one; hence for δ^1>0, there exists N1, when N>N1, for any x∈S(x∗,δ), we have(17)F^N,ix-z^Nk-Fix-zk<F^N,ix-Fix+z^Nk-zk<δ^12+δ^12=δ^1.
It follows from (16) and (17) that for any ε>0, there exists N1, when N>N1; for any x∈Sx∗,δ, it holds that(18)eF^N,ix-zNk/t-eFix-zk/t<ε.
Thus, in view of (15), ui(k)∈S(u∗,δ), and the condition that u^N,i(k) converges to ui(k)(N→∞) with probability one, we obtain that φ(1)(uN,i(k),F^N,i(x),z^N(k),t) converges to φ(1)(ui(k),Fi(x),z^(k),t) with probability one uniformly on S(x∗,δ) as N→∞.
(B) Next, we prove thatφ(2)(vN,j(k),G^N,j(x),t) converges to φ(2)(vj(k),Gj(x),t)(j=1,…,p) with probability one uniformly on S(x∗,δ) as N→∞.
From the definition ofφ(2)(c,d,t), we have(19)φ2v^N,jk,G^N,jx,t-φ2vjk,Gjx,t=v^N,jkeG^N,jx/t-1-vjkeG^N,jx/t-1+vjkeG^N,jx/t-1-vjkeGjx/t-1≤v^N,jk-vjkeG^N,jx/t-1+vjkeG^N,jx/t-eGjx/t.
SinceG^N,j(x) and Gj(x)(j=1,…,p) are continuous on S(x∗,δ) with respect to x from the assumption (a) and Lemma 3, there exits a closed interval [c2,d2](c2,d2∈R) such that G^N,j(x)∈c2,d2 and Gi(x)∈c2,d2 for x∈S(x∗,δ), which means that eG^N,j(x)/t is bounded on S(x∗,δ) with respect to x. From the proof process of (A), we get that, for any ε>0, there exists a positive integer N2, when N>N2, for x∈S(x∗,δ), it holds that (20)eG^N,jx/t-eGjx/t<ε.
Therefore, combined with (19), it follows from v^N,j(k) converging to vj(k) with probability one as N→∞ and vj(k)∈S(v∗,δ) that φ(2)(v^N,j(k),G^N,j(x),t) converges to φ(2)(vj(k),Gj(x),t)(j=1,…,p) uniformly with probability one on S(x∗,δ) as N→∞.
(C) Now we prove thatφ(3)(yN,l(k),H^N,l(x),t) converges to φ(3)(yl(k),Hl(x),t) with probability one uniformly on S(x∗,δ) as N→∞.
From the definition ofφ(3)(e,f,t), we have(21)φ3y^N,lk,H^N,lx,t-φ3ylk,Hlx,t=1ty^N,lk+12tH^N,lxH^N,lx-1tylk+12tH^N,lxH^N,lx+1tylk+12tH^N,lxH^N,lx-1tylk+12tHlxHlx≤1ty^N,lk-ylkH^N,lx+1tylk+12tH^N,lx+HlxH^N,lx-Hlx.
SinceH^N,l(x) and Hl(x)(l=1,…,q) are continuous on S(x∗,δ) with respect to x according to the assumption (a) and Lemma 3, there exists a closed interval c3,d3c3,d3∈R such that H^N,l(x)∈c3,d3 and Hl(x)∈c3,d3 for x∈S(x∗,δ); i.e., H^N,l(x)+Hl(x) is bounded. Then from yl(k)∈S(y∗,δ) it follows that [ylk+(1/2t)(H^N,l(x)+Hl(x))] is bounded on S(x∗,δ). From Lemma 3, it is true that H^N,l(x) converges to Hl(x)(l=1,…,q) with probability one uniformly on S(x∗,δ). That is, for any ε>0, there exists a positive integer N3, when N>N3, for x∈S(x∗,δ), the following inequality holds with probability one: (22)H^N,lx-Hlx<ε.
Moreover, considering (21) and the fact that y^N,l(k) converges to yl(k) with probability one as N→∞, we have that φ(3)(y^N,l(k),H^N,l(x),t) converges to φ(3)(yl(k),Hl(x),t) with probability one uniformly on S(x∗,δ) as N→∞.
Thus, from the above analyses of (A), (B) and (C), we draw the conclusion thatϕN(x) converges to ϕ(x) with probability one uniformly on S(x∗,δ) as N→∞. Furthermore, in view of the fact that ln⁡x is continuous with respect to x on R, it can be proven that tln⁡ϕN(x,t) converges to tln⁡ϕ(x) uniformly with probability one as N→∞ for t>0, which implies that the conclusion (i) is true.
(ii) From the conclusion (i) and Lemma3, we can prove that the conclusion (ii) is true.Theorem 6.
If assumptions (a)-(c) hold and lettingu^N,i(0)=ui(0)(i=1,…,m), v^N,j(0)=vj(0)(j=1,…,p), y^N,l(0)=yl(0)(l=1,…,q), and z^N(0)=z(0), then for any k≥0, the following statements hold: (i)
AsN→∞, u^N,i(k) converges to ui(k) with probability one for i=1,⋯,m, v^N,j(k) converges to vj(k) with probability one for j=1,⋯,p, y^N,l(k) converges to yl(k) with probability one for l=1,⋯,q, and z^N(k) converges to z(k) with probability one;(ii)
L¯N(x,u^N(k),v^N(k),y^N(k),z^N(k),t) converges to L¯(x,u(k),v(k),y(k),z(k),t) with probability one uniformly on S(x∗,δ) as N→∞;(iii)
υ^N(k) converges to υ(k) with probability one, and D(S^N(k),S(k)) converges to 0 with probability one as N→∞.Proof.
(i) We use the mathematical induction method to show that the statement (i) is true below. Fork=0, we know that u^N,i(0)=ui(0)(i=1,…,m), v^N,j(0)=vj(0)(j=1,…,p), y^N,l(0)=yl(0)(l=1,…,q) and z^N(0)=z(0), which means that the conclusion (i) is true for k=0. Next we prove that the conclusion (i) is true for k≥1.
Fork=1, from u^N,i(0)=ui(0), one has that (23)u^N,i1=ui0eF^N,ix^N0/t∑j=1muj0eF^N,jx^N0/t,ui1=ui0eFix0/t∑j=1muj0eFjx0/t,i=1,…,m.
For anyi(i=1,…,m), we have(24)F^N,ix^N0-Fix0≤F^N,ix^N0-Fix^N0+Fix^N0-Fix0.From Lemma 3, we know that F^N,i(x^N(0)) converges to Fi(x^N(0)) with probability one as N→∞, which implies that the first term on the right side of (24) converges to 0 as N→∞. And we know that Fi(x) is continuous and bounded on S(x∗,δ) from Lemma 3, and x^N(0) converges to x(0) with probability one as N→∞ from Theorem 5, so the second part on the right side of (24) converges to 0 as N→∞. That is, F^N,i(x^N(0)) converges to Fi(x(0)) with probability one as N→∞. And we know ex/t is continuous with respect to x on R, hence eF^N,i(x^N(0))/t converges to eFi(x(0))/t with probability one as N→∞. Furthermore, we can prove that u^N,i(1) converges to ui(1) with probability one as N→∞ for i=1,…,m.
Fork=1, we have (25)v^N,j1=v^N,j0eG^N,jx^N0/t,vj1=vj0eG^jx0/t,j=1,…,p. For any j(j=1,…,p), v^N,j(0)=vj(0), so we have (26)v^N,j1-vj1=vj0eG^N,jx^N0/t-eGjx0/t. Similarly, we can prove that v^N,j(1) converges to vj(1) with probability one as N→∞ for j=1,…,p from Lemma 3 and Theorem 5.
Fork=1, since y^N,l(0)=y^l(0)(l=1,…,q), it holds that (27)y^N,l1=yl0+1tH^N,lx^N0,yl1=yl0+1tHlx0,l=1,…,q. Hence for any l(l=1,…,q), we have (28)y^N,l1-yl1=1tH^N,lx^N0-Hlx0≤1tH^N,lx^N0-Hlx^N0+1tHlx^N0-Hlx0.We can also prove that y^N,l(1) converges to yl(1)(l=1,…,q) with probability one as N→∞ for l=1,…,q from Lemma 3 and Theorem 5.
Fork=1, it holds that (29)z^N1=tln∑i=1mu^N,i0eF^N,ix^N0/t,z1=tln∑i=1mui0eFix^0/t.Similar to the above proof process, we can draw the conclusion that z^N(1) converges to z(1) with probability one as N→∞.
That is, we have proven that the conclusion (i) is true fork=1. Now suppose that the conclusion (i) is true for k=r, where r is an integer (r≥2). Next, we prove that the conclusion (i) is true for k=r+1.
Since the conclusion (i) is true fork=r, we have that x^N(r) converges to x(r) with probability one as N→∞ from Theorem 5. For k=r+1, we have (30)u^N,ir+1=u^N,ireF^N,ix^Nr/t∑j=1mu^N,jreF^N,jx^Nr/t,uir+1=uireFixr/t∑j=1mujreFjxr/t,i=1,…,m.For any i(i=1,…,m), one has(31)u^N,ireF^N,ix^Nr/t-uireFixr/t≤u^N,ireF^N,ix^Nr/t-uireF^N,ix^Nr/t+uireF^N,ix^Nr/t-uireFixr/t=u^N,ir-uireF^N,ix^Nr/t+uireF^N,ix^Nr/t-eFixr/t.In view of the proof process in Theorem 5, it follows that u^N,i(r)eF^N,i(x^N(r))/t converges to ui(r)eFi(x(r))/t with probability one as N→∞. Moreover, note that the special forms of u^N,i(r+1) and ui(r+1), we can verify that u^N,i(r+1) converges to ui(r+1) with probability one as N→∞ for i=1,⋯,m.
Similarly, we can prove thatv^N,j(r+1) converges to vj(r+1) with probability one as N→∞ for j=1,⋯,p, y^N,l(r+1) converges to yl(r+1) with probability one as N→∞ for l=1,⋯,q, and z^N(r+1) converges to z(r+1) with probability one as N→∞ from Lemma 3 and Theorem 5. That is, the conclusion (i) is true for k=r+1. By mathematical induction method, hence we know that conclusion (i) is true for any k≥0.
(ii) Considering conclusion (i) and Theorem5, we know that conclusion (ii) is true.
(iv) In view of conclusion (ii) and Lemma3, we have that conclusion (iii) is true.
Thus, the proof of Theorem6 is completed.Up until now, we have established the relationship between the optimal solution of problem (3) and the optimal solution of problem (12), and the convergence of the SAA Lagrange multiplier sequence in Algorithm 4 with probability one as N→∞. Next we are to prove that the optimal solution sequence and the SAA Lagrange multiplier sequence obtained by Algorithm 4 converge to the optimal solution and the corresponding Lagrange multiplier of problem (1) with probability one as N→∞ under the assumptions (a)-(h).Theorem 7.
If assumptions (a)-(h) hold, and letu^N,i(0)=ui(0)(i=1,…,m), v^N,j(0)=vj(0)(j=1,…,p), y^N,l(0)=yl(0)(l=1,…,q), zN(0)=z(0), then there exist δ¯>0 and t^∈(0,1) such that for any (u(0),v(0),y(0),z(0),t)∈Bδ¯(u∗,v∗,y∗,z∗)×(0,t^), x^N(k) converges to x∗ with probability one, u^N(k) converges to u∗ with probability one, v^N(k) converges to v∗ with probability one, and y^N(k) converges to y∗ with probability one, respectively, when N→∞ and k→∞.Proof.
Based on the property of norm, one has(32)x^Nk-x∗≤x^Nk-xk+xk-x∗,(33)u^Nk-u∗≤u^Nk-uk+uk-u∗,(34)v^Nk-v∗≤v^Nk-vk+vk-v∗,(35)y^Nk-y∗≤y^Nk-yk+yk-y∗,(36)z^Nk-z∗≤z^Nk-zk+zk-z∗.
If assumptions (d)-(h) are satisfied, then it follows from Theorem 3.1 of [13] that there exist δ¯>0(δ¯<δ) and t^∈(0,1) such that as k→∞, x(k)→x∗, u(k)→u∗, v(k)→v∗, y(k)→y∗, and z(k)→z∗ for any u(0),v(0),y(0),z(0),t∈Bδ¯u∗,v∗,y∗,z∗×0,t^.
If assumptions (a)-(c) are satisfied, andu^N,i(0)=ui(0)(i=1,…,m), v^N,j(0)=vj(0)(j=1,…,p), y^N,l(0)=yl(0)(l=1,…,q) and z^N(0)=z(0), it follows from Theorem 6 that u^N(k) converges to u(k) with probability one, v^N(k) converges to v(k) with probability one, y^N(k) converges to y(k) with probability one, z^N(k) converges to z(k) with probability one, and x^N(k) converges to x(k) with probability one as N→∞.
Thus, combined with (32)-(35) and the above analysis, it has been proven that Theorem 7 is true under assumptions (a)-(h).Remark 8.
Theorem7 shows that Algorithm 4 is locally convergent under assumptions (a)-(h). That is, when the initial multiplier (u^N(0),v^N(0),y^N(0)) are close to the optimal multiplier (u∗,v∗,y∗), z(0) is close to z∗, and t is less than a threshold, the solution sequence x^N(k) obtained by Algorithm 4 locally converges to the optimal solution x∗ of original problem (1) with probability one as N→∞, (u^N(k),v^N(k),y^N(k)) converges to (u∗,v∗,y∗) with probability one as N→∞, and z^N(k)) converges to z∗ with probability one as N→∞ under assumptions (a)-(h).


## 4. Numerical Results

In this section, the numerical results for eight test examples by using Algorithm4 are presented. These test examples are compiled based on the deterministic optimization problems in [13] by considering random variable ξ. The numerical experiments are implemented in Matlab2014 on the same computer whose CPU basic parameters are Intel CORE(TM) i5-3337U@1.80GHZ and memory 8GB.In the experiments, the random variableξ is set to be uniformly distributed on Ξ=[0,1] and the random sample {ξ1,ξ2,…,ξN} with sample size N is generated by random number generator unifrnd in Matlab2014. We choose N=102, N=103, N=104, N=105, and N=106 to make comparison for each test example. The initial values of uN(0), vN(0), yN(0) and zN(0) are set as uN(0)=(1/m,…,1/m)T, vN(0)=(1,⋯,1)T, yN(0)=(1,⋯,1)T and zN(0)=1 for each example, and t(0) is chosen small enough and determined by the scale of test problem; Unconstrained minimization problem in Step 2 of Algorithm 4 is solved by BFGS quasi-Newton method combined with Wolf nonexact linear search rule. The stopping precision in Step 3 is ε=10-5, and the termination condition is(37)∑i∈Mu^N,ikF^N,ix^Nk-Tx^Nk+∑j∈Pv^N,jkG^N,jx^Nk+H^Nx^Nk≤ε.The obtained numerical results are reported in Tables1-8, in which N represents sample size; 1/t represents the value of 1/t; it represents the number of iterations, i.e., the numbers of the Lagrange multipliers being updated; x^N(k)-x∗ represents the gap between the solution sequence x^N(k) obtained by Algorithm 4 and the optimal solution x∗ of the corresponding test problem; and zN(k)-z∗ represents the gap between the approximate value zN(k) of objective function T(x) obtained by Algorithm 4 and the optimal value z∗ of the corresponding test problem, respectively.Table 1
The numerical results for Example1.
N 1t i t x ^ N ( k ) - x ∗ z^N(k)-z∗ 1 0 2 3 30 0.053618 2.714061e-02 1 0 3 3 30 0.013345 5.746432e-02 1 0 4 3 30 0.002998 1.567222e-03 1 0 5 3 34 0.001830 6.904709e-03 1 0 6 3 34 0.000273 2.444700e-04Example 1.
In problem (1), fi(x,ξ)(i=1,2,3) and hl(x,ξ)(l=1,2) are defined as follows: (38)f1x,ξ=3ξ2x12+x22,f2x,ξ=2-x12+2ξ2-x22,f3x,ξ=4ξexpx2-x1,h1x,ξ=x1+2ξx2-4ξ,h2x,ξ=-x12-x22+6.75ξ2,where the optimal solution and the optimal value (see [13]) are (39)x∗=1.35355,0.64645T,z∗=2.25. The numerical results for this example obtained by Algorithm 4 are shown in Table 1.Example 2.
In problem (1), fi(x,ξ)(i=1,2,3), gj(x,ξ)(j=1), and hl(x,ξ)(l=1) are defined as follows: (40)f1x,ξ=3ξ2x14+x22,f2x,ξ=2-x12+2ξ2-x22,f3x,ξ=4ξexpx2-x1,g1x,ξ=-4ξx13-3ξ2x22,h1x,ξ=x12-2ξx22,where the optimal solution and the optimal value (see [13]) are (41)x∗=1,1T,z∗=2. The numerical results for this example obtained by Algorithm 4 are shown in Table 2.Table 2
The numerical results for Example2.
N 1 t i t x ^ N ( k ) - x ∗ z^N(k)-z∗ 1 0 2 0.2 48 0.040829 1.723749e-02 1 0 3 0.2 73 0.004546 1.666095e-03 1 0 4 0.2 89 0.001116 3.148451e-03 1 0 5 0.2 104 0.000239 8.722890e-04 1 0 6 0.2 107 0.000188 4.128465e-04Example 3.
In problem (1), fi(x,ξ)(i=1,2) and hl(x,ξ)(l=1,2) are defined as follows: (42)f1x,ξ=2ξexpx121000+x2-12,f2x,ξ=3ξ2expx121000+x2+12,h1x,ξ=x121000+2ξx22+3ξ2x1x2,h2x,ξ=-2ξx1+x22,where the optimal solution and the optimal value (see [13]) are (43)x∗=0,0T,z∗=2.71828. The numerical results for this example obtained by Algorithm 4 are shown in Table 3.Table 3
The numerical results for Example3.
N 1 t i t x ^ N ( k ) - x ∗ z^N(k)-z∗ 1 0 2 0.1 23 0.000755 4.628155e-04 1 0 3 0.1 26 0.000408 1.361478e-04 1 0 4 0.1 26 0.000363 5.530880e-04 1 0 5 0.1 26 0.000191 2.105646e-04 1 0 6 0.1 26 0.000051 1.955180e-05Example 4.
In problem (1), fi(x,ξ)(i=1,2,3) and hl(x,ξ)(l=1,2) are defined as follows: (44)f1x,ξ=0.52ξx1+10x1x1+0.1+4ξx22,f2x,ξ=0.5-2ξx1+10x1x1+0.1+4ξx22,f3x,ξ=0.52ξx1-10x1x1+0.1-4ξx22,h1x,ξ=2ξx12+2ξx22+x1x2,h2x,ξ=-2ξx1+x22,where the optimal solution and the optimal value (see [13]) are (45)x∗=0,0T,z∗=2.71828. The numerical results for this example obtained by Algorithm 4 are shown in Table 4.Table 4
The numerical results for Example4.
N 1t i t x ^ N ( k ) - x ∗ z^N(k)-z∗ 1 0 2 0.5 4 0.000000 4.061068e-07 1 0 3 0.5 4 0.000000 4.053219e-07 1 0 4 0.5 4 0.000000 4.050488e-07 1 0 5 0.5 4 0.000000 4.050740e-07 1 0 6 0.5 4 0.000000 4.050678e-07Example 5.
In problem (1), fi(x,ξ)(i=1,…,5), gj(x,ξ)(j=1,2,3), and hl(x,ξ)(l=1) are defined as follows: (46)f1x,ξ=2x12+4ξx22+2ξx32+2x1x2+4ξx1x3-24ξ2x1-6x2-8ξx3+9,f2x,ξ=f1x,ξ+10h1x,ξ,f3x,ξ=f1x,ξ+10g1x,ξ,f4x,ξ=f1x,ξ+10g2x,ξ,f5x,ξ=f1x,ξ+10g3x,ξ,g1x,ξ=-2ξx1,g2x,ξ=-3ξ2x2,g3x,ξ=-2ξx3,h1x,ξ=x1+x2+8ξ3x3-3,where the optimal solution and the optimal value (see [13]) are (47)x∗=43,79,49T,z∗=19. The numerical results for this example obtained by Algorithm 4 are shown in Table 5.Table 5
The numerical results for Example5.
N 1 t i t x ^ N ( k ) - x ∗ z ^ N ( k ) - z ∗ 1 0 2 0.8 18 0.350233 7.913036e-01 1 0 3 0.8 18 0.199523 4.201455e-01 1 0 4 0.8 17 0.032177 5.933858e-02 1 0 5 0.8 17 0.006590 1.221448e-03 1 0 6 0.8 17 0.000542 8.848920e-04Example 6.
In problem (1), fi(x,ξ)(i=1,…,9), gj(x,ξ)(j=1,2) and hl(x,ξ)(l=1,…,6) are defined as follows: (48)f1x,ξ=x12+x22+2ξx1x2-28ξx1-16x2+x3-102+12ξ2x4-52+2ξx5-32+2x6-12+20ξ3x72+7x8-112+4ξx9-102+x10-72+90ξ,f2x,ξ=f1x,ξ+20h1x,ξ,f3x,ξ=f1x,ξ+20h2x,ξ,f4x,ξ=f1x,ξ+20g1x,ξ,f5x,ξ=f1x,ξ+20h3x,ξ,f6x,ξ=f1x,ξ+20h4x,ξ,f7x,ξ=f1x,ξ+20h5x,ξ,f8x,ξ=f1x,ξ+20g2x,ξ,f9x,ξ=f1x,ξ+20h6x,ξ,g1x,ξ=--12x1-82-4ξx2-22-9ξ2x52+2ξx6+30,g2x,ξ=-3x1-12ξx2-12x9-82+7x10,h1x,ξ=--3x1-22-8ξx2-32-6ξ2x32+7x4+240ξ,h2x,ξ=--5x12-16ξx2-x3-62+4ξx4+120ξ2,h3x,ξ=--x12-4ξx2-22+6ξ2x1x2-14x5+6x6,h4x,ξ=--4x1-10ξx2+9ξ2x7-9x8+105,h3x,ξ=--x12-4ξx2-22+6ξ2x1x2-14x5+6x6,h4x,ξ=--4x1-10ξx2+9ξ2x7-9x8+105,h6x,ξ=-8x1-2x2-10ξx9+6ξ2x10+12,where the optimal solution and the optimal value (see [13]) are (49)x∗=2.171996,2.363683,8.773926,5.095985,0.990655,1.430574,1.321644,9.828726,8.280092,8.375927T,z∗=24.306209.The numerical results for this example obtained by Algorithm 4 are shown in Table 6.Table 6
The numerical results for Example6.
N 1 t i t x ^ N ( k ) - x ∗ z ^ N ( k ) - z ∗ 1 0 2 0.8 21 0.175122 2.486983e-01 1 0 3 0.8 21 0.017835 1.832466e-02 1 0 4 0.8 21 0.014858 5.719731e-02 1 0 5 0.8 21 0.004011 5.719731e-03 1 0 6 0.8 21 0.000949 4.484174e-04Example 7.
In problem (1), fi(x,ξ)(i=1,…,5), gj(x,ξ)(j=1,2), and hl(x,ξ)(l=1,2) are defined as follows: (50)f1x,ξ=x1-102+10ξx2-122+5ξ4x34+3x4-112+20ξx56+7x62+3ξ2x74-4x6x7-20ξx6-8x7,f2x,ξ=f1x,ξ+10h1x,ξ,f3x,ξ=f1x,ξ+10g1x,ξ,f4x,ξ=f1x,ξ+10g2x,ξ,f5x,ξ=f1x,ξ+10h2x,ξ,g1x,ξ=--7x1-6ξx2-10x32-2ξx4+3ξ2x5+282,g2x,ξ=--23x1-x22-18ξ2x62+16ξx7+196,h1x,ξ=--2x12-6ξx24-x3-8ξx42-5x5+127,h2x,ξ=--4x12-x22+3x1x2-6ξ2x32-10ξx6+11x7,where the optimal solution and the optimal value (see [13]) are(51)x∗=2.33050,1.95137,-0.47754,4.36573,-0.62449,1.03813,1.59423T,z∗=680.63006.The numerical results for this example obtained by Algorithm 4 are shown in Table 7.Table 7
The numerical results for Example7.
N 1t i t x ^ N ( k ) - x ∗ z^N(k)-z∗ 1 0 2 1 17 0.105795 2.061338e-01 1 0 3 1 17 0.015291 2.527593e-02 1 0 4 1 17 0.002059 4.118053e-03 1 0 5 1 13 0.001702 1.004443e-03 1 0 6 1 21 0.000676 9.903274e-04Table 8
The numerical results for Example8.
N 1t i t x ^ N ( k ) - x ∗ z^N(k)-z∗ 1 0 2 0.5 30 0.236371 2.061338e-01 1 0 3 0.5 30 0.107028 2.527593e-01 1 0 4 0.5 30 0.031119 4.118053e-02 1 0 5 0.5 30 0.003603 5.506888e-03 1 0 6 0.5 30 0.001569 2.177321e-03Example 8.
In problem (1), fi(x,ξ)(i=1,…,18), gj(x,ξ)(j=1,…,5), and hl(x,ξ)(l=1,…,12) are defined as follows: (52)f1x,ξ=x12+x22+2ξx1x2-28ξx1-16x2+x3-102+12ξ2x4-52+2ξx5-32+2x6-12+20ξ3x72+7x8-112+4ξx9-102+x10-72+2ξx11-92+10x12-12+10ξx13-72+4x14-142+27x15-12+5ξ4x164+2ξx17-22+13x18-22+x19-22+2ξx202+95,f2x,ξ=f1x,ξ+20h1x,ξ,f3x,ξ=f1x,ξ+20h2x,ξ,f4x,ξ=f1x,ξ+20g1x,ξ,f5x,ξ=f1x,ξ+20h3x,ξ,f6x,ξ=f1x,ξ+20h4x,ξ,f7x,ξ=f1x,ξ+20h5x,ξ,f8x,ξ=f1x,ξ+20g2x,ξ,f9x,ξ=f1x,ξ+20h6x,ξ,f10x,ξ=f1x,ξ+20g3x,ξ,f11x,ξ=f1x,ξ+20h7x,ξ,f12x,ξ=f1x,ξ+20h8x,ξ,f13x,ξ=f1x,ξ+20g4x,ξ,f14x,ξ=f1x,ξ+20g5x,ξ,f15x,ξ=f1x,ξ+20h9x,ξ,f16x,ξ=f1x,ξ+20h10x,ξ,f17x,ξ=f1x,ξ+20h11x,ξ,f18x,ξ=f1x,ξ+20h12x,ξ,g1x,ξ=--12x1-82-4ξx2-22-9ξ2x52+2ξx6+30,g2x,ξ=-3x1-12ξx2-12x9-82+7x10,g3x,ξ=--2ξx1-x2-8ξx11+21x12,g4x,ξ=--3x1-12ξ2x2-6ξx13-62+14x14+10,g5x,ξ=--14x12-70ξx15+79x16+92,h1x,ξ=--3x1-22-8ξx2-32-6ξ2x32+7x4+240ξ,h2x,ξ=--5x12-16ξx2-x3-62+4ξx4+120ξ2,h3x,ξ=--x12-4ξx2-22+6ξ2x1x2-14x5+6x6,h4x,ξ=--4x1-10ξx2+9ξ2x7-9x8+105,h5x,ξ=--10x1+16ξx2+17x7-4ξx8,h6x,ξ=-8x1-2x2-10ξx9+6ξ2x10+12,h7x,ξ=--x12-15x11+16ξx12+28,h8x,ξ=--4x1-18ξx2-10ξx132+27ξ2x14+87,h9x,ξ=--15x22-22ξx15+183ξ2x16+54,h10x,ξ=--5x12-2x2-9x174+4ξ3x18+68,h11x,ξ=--x12+x2-38ξx19+40ξx20-19,h12x,ξ=--7x12-5x22-2ξx192+30x20,where the optimal solution and the optimal value (see [13]) are (53)x∗=2.175216,2.352850,8.766448,5.066932,0.988667,1.431000,1.329483,9.835926,8.287277,8.370178,2.275828,1.358623,6.077186,14.170830,0.9962345,0.655691,1.466590,2.000361,1.046588,2.063194T,z∗=133.7283.The numerical results for this example obtained by Algorithm 4 are shown in Table 8.From the numerical results in Tables1-8, the following remarks are made.Remark 9.
The preliminary numerical results show that Algorithm4 is feasible and promising.Remark 10.
Compared with the numerical results for the same test example with the different sample sizeN, the numerical results in Tables 1-8 show that the precisions of the optimal solution and the optimal value by Algorithm 4 become higher as the sample size is chosen larger, which coincides with the convergence result of Algorithm 4 in Section 3.


## 5. Conclusions

An implementable SAA nonlinear Lagrange algorithm for solving constrained minimax stochastic optimization problems is presented by this paper. And the convergence theory of the proposed algorithm is established under some assumptions, in which the KKT solution sequence obtained by the algorithm is demonstrated to converge to the optimal KKT solution of the original problem with probability one as the sample size approaches to infinity. Furthermore, numerical experiments are implemented by using the proposed SAA nonlinear Lagrange algorithm for solving eight typical test examples, and the results of numerical experiment verify the convergence theory and indicate that the new algorithm is promising. Moreover, the numerical experiments for obtaining the solutions with higher precision and solving large scale problems deserve our future attention. And applying this proposed algorithm to solve some practical problems is also interesting.



---

*Source: 5498760-2018-12-09.xml*