Stability Analysis for Stochastic Optimization Problems

Journal of Shanghai Jiaotong University(Science) , Vol. E-12.No. 5,2007 ,684~ 687Article ID: 1007-1172(2007)05 0684-04Stability Analysis for Stochastic Optimization ProblemsLUO Jian-wen (骆建文)(School of Management，Shanghai Jiaotong Univ. , Shanghai 200052. China)Abstract: Stochastic optimization offers a means of considering the objectives and constrains with stochastic param-eters. However, it is generally difficult to solve the stochastic optimization problem by employing conventionalmethods for nonlinear programming when the number of random variables involved is very large. Neural networksmodels and algorithms were applied to solve the stochastic optimization problem on the basis of the stability theo-ry. Stability for stochastic programs was discussed. If random vector sequence converges to the random vector inthe original problem in distribution, the optimal value of the corresponding approximation problems converges tothe optimal value of the original stochastic optimization problem.Key words: stochastic optimization; stability; convergence in distributionCLC number: O 24Document code: Aweak convergence of probability measures on sta-Introductionbility analysis of stochastic programs. Romisch etStochastic optimization offers a means of con-al[2] showed that the stability analysis based on thesidering the objectives and constrains with stochas-L1-W asserstein distance and Holder continuity wastic parameters. Many real problems in uncertainobtained. In parallel to this development, muchenvironments may often be formulated as stochas-work was directed to the study of convergencetic optimization problem. However, it is generallyproperties of random approximations or statisticaldifficult to solve the stochastic optimization prob-estimation procedures in stochastic programming.lem by employing conventional methods for nonlin-Kummer[3] considered the quantitative stability ofear programming by reason of computational in-general convex programs based the Hausdorff dis-tractability if the number of random variables in-tance of subgradients. Wang[41] explored Lipschitzvolved is very large. Many investigators have beencontinuity of objective functiond in stochastic pro-longing for some flexible method for solving thegramming with fixed recourse.Shapiro-s] investi-stochastic optimization problem. Neural networkgated the expectation functions with smooth inte-models and algorithms have been recently appliedgrands in stochastic programs. King et ali6] foundfor solving the problem. In order to make sure thethat the relevant integrands were typically non-efficiency of the schemes, the stability theory forsmooth and uniqueness of optimal solutions wasdesigning or analyzing schemes should be givenrather exceptional such that the results forfirstly.stochastic programs with complete recourse.In the last twenty years, the approach methodShapirolJ used information contained in the defini-has been studied comprehensively on stochastic op-tion of the Hausdorff distance to derive quantita-timization. DupacovaCexamined the conditionstive stability properties.implying continuity properties of optimal valuesA general stochastic optimization problemand solution sets with respect to the topology 0with the objectives and constrains with stochasticparameters is considered in the paper. Stability forReceived date: 2005-09-20Foundation item: The National Natural Science Foundation ofstochas-and it is derived中国煤化工China(No. 70271039)that th? correspponding# E-mall: jwluo@xju. edu. cnapproxYHCNMHGtotheoptimalStability Analysis lor Stochastic Optimization Problems685value of the original problem if random vector se-is strictly quasi-convex function of x.quence converges to the random vector in the origi-Proot Clearly, Eg,(x,$(A,w)) is quasi-con-nal problem in distribution.vex function of x since g;(x,t) is quasi-convexThe considered problem isfunction of x for any given t. Next, it will bez(5(w)) = min {Ef(x,S(w))|proved that Eg,(r ,$(A,w)) is strictly quasi-convexEg,(x,$(w))≤0,j= 1,2...,p} (1)function.The corresponding approach problems can be for-Contradiction: suppose Eg,(x,S(A,w)) is notmulated asstrictly quasi-concave function ,then there exist a∈z(s'4)(w))=min{Ef(x ,5"*(w))|Eg;(x ,$"(如))≤0,(0,1), x1', x°'∈R* satisfyingEg,(r" ,$(X,w))≠Eg,(x<2) ,$(A,w))j= 1,2**,p},k= 1,2,..(2)where x is decision variable,X is compact set onEg,(ax["'+(1-a)x'2) ,$(A,u))=R", 5(w) is random vectors in probility spacemin (Eg(x") ,5(,u)),Eg,(x(2) ,s(),w))} (5)(R" ,β" ,P). E is the operator of $(w) with expecta-Without lose of generality , assume thattion value. s"(w) convergences to $(w) in distribu-Eg,(ax")+ (1一a)x(2),$(),w)) =tion.Eg,("' ,5(A,w))(6)By Kolmogrov' s existence theorem[8], ifTherefore5*)(w) convergences to $(w) in distribution, thenf8;(ax"" +(1-2>x*9.1)-there exists a random function $ (λ, w) satisfying8g,{("',I))dH(A,t) =5(0,w)=5(w) and $(w/k)= 5")(w).Eg(aI)+ (1一a)x(2) ,5(A,w))一Let H(A,t) is the K-distribution function ofEg;(x[) ,5(),w))= 0(7)5(A,w), and assume H(A,t) is continuous at λ∈A.On the other hand,For convenience, assume that H(A,t)≠0 is de-g,(a1'+ (1 - a)x<2,t)> g,(x'I',t)fined to be a function on compact set GCR" for anysince g,(x,t) is strictly quasi-convex function of xgiven.for any givent andIt should be noted that many concepts used inE,(x ,5(A,w))≠Eg,(x2) ,s(A,w))his paper come from Ref. [9] such as“set valueNote that g,(x,t) is continuous on R*+", thusmapping is closed at some point"," set to pointK = min{g,(ax") + (1一a)x(2),t) -mapping”，“upper semi-continuous"," lower se-g;{(x"',t)|t∈GCR"}> 0(8)mi-continuous”,“upper semi-continuous of func-obtaintion”, "lower semi- continuous of function", and soon.Ff:(ax"*+(. -a)x*", -五Continuous Properties of Optimatg,(x1). ,t))dH(A,t)>F unction_.KdH(.)=K≠0(9)Introducing the random function 5(A,w) intoObviously, Eq. (9) is contradicted with Eq. (7).Therefore Eg, (x,S(A,w)) is strictly quasi-convexEq. (2), yieldsz(5(),u))= min_ {Ef(x,S(A,w))|Lemma2 If g,(x,t)(j= 1,2...p) is contin-Eg;(x,$(A,w))≤0,j= 1,2,,p} (3)uous on R*+m and strictly quasi-convex function oFor convenience, let, for any given t, x∈XCR"，t∈GCR". IfM()= {x∈XC R"|Eg,(x,$(A,w))≤0，4)M°(h)≠e, then M(N)Sc1M(n).j= 1,2...,p}Lemma 1 If g;(x,t) is continuous on R*+m中国煤化工∈MO°un)={x∈and strictly quasi-convex functiqn of x for any giv-xCR=1,2...p).ent, x∈XCR",t∈G∈R". Then Eg,(x,$(A,w))a∈(0:TYTHCNMHG686 IUO Jian-uen(骆建文)(1) II Eg,(y,s(ao,w)) = Eg;(yo,5(x, w)),continuous on R"+m and strictly quasi-convex func-tion of x for any given t,x∈XCR",x∈GCR".thenEg,(yo,s(A,w))≤max{Eg;(y,s(2,w)),Assume that M°(A)≠0 ,thenEg,(Yo,5(A),w)}<0z(5(x,w))= min. {Ef(x,$(A,w)) |Eg;(x,(2) If Eg,(y,s(n,w))≠Eg,(yo,S(ho,w)), .$(A,w))≤0,j= 1,2,.p}then by Lemma 1,it is easy to getis upper semi-continuous at入。Eg,(y,s(n,w))≤max{Eg,(,s(h,w)),Proof Ef(x,$(A,w) )is upper semi-continu-Eg,(Yo,$(Ag,w))}≤0(10)ous on XX{a} since f(x,t) is upper semi contin-By (1) and (2), obtain y.∈M"(x). It is easyuous on R"+". By Lemma 4, M(a) is lower semi-to know that a-→0 implies that y→yYo, i.e, yo∈continuous at小. Therefore, by theorem 4. 2.2 inc1M°(A). Furthermore, M(A)EclM(x)).Ref.[9], z(5(A,w)) is upper semi-continuous atLemma 3 Assume that 8;(r,t) is continuouson R"+m ,where, x∈R",t∈R" ,then for any入→h,Proposition 2 Assume f(x,t) is upper semi-xn~ +λ●there iscontinuous on R"+", g;(x,t) is continuous on R"+"lim Eg,(x,S(n,w)) = Eg,(xo,S(x,w))and strictly quasi convex function of x for any giv-Proof Since g,(x,t) is continuous, there isent,x∈XC R”,x∈GCR". There exist some pointlim 8g,(xe,t) = 8,(工o,t)(11)xo such that Eg,(xo,S(Aa,w))<0 . Then z(S(n,Note that 5(Ay,w) convergences to 5(Ao,w) in dis-w)) is lower semi-continuous at A.tribution when入- +λ. Thus, by Eq. (11) and theo-Proof For any given 瓦→δ,let年∈M()rem 5. 5 in Re1. [10], obtainand x +xo. Lemma 3, implieslim g(x,S(x,w)二g,(xo,(,w)) (12)Eg,(2。,S(2o,w)) = lim Eg,(,,s(,w))≤0 (15)Hence,正o∈M(A). Thus M(X) is closed at心. AI-This yields thatlim Eg;(x,,s(An,w) = Eg;(xo,S(xo,w)) (13)so there exists a point工o such that Eg, (Io,$ (A，w))<0, which implies M° (2)≠e. Moreover,Lemma 4 Assume that g;(x,t)(j=,2,.,Ef(x,ζ(A,w)) is upper semi-continuous sincep) is continuous on R*+m and strictly quasi-convexf(x,t) is upper semi-continuous on R*+". Accord-function of x for any given t,x∈XCR° ,t∈GCR".ing to lemma 4. 2.1.1 in Ref. [9], z(5(),w)) isLet M°(A)≠B, then M(A) is lower semi-continu-lower semi-continuous at λ.ous at心.Proof By Lemma 3, Eg;(x,s(A,w)) is con-3 Approach Theoremtinuous at M(h) X {的}，particularly, upper semi-Here, assume that A=[- 1,1],X is compactcontinuous on M° (A)X {h}。Let 厂is identicaland XS =R".point-to-set mapping, i.e. ,Theorem Assume f(x,t) is upper semi-con-「(x) =I()= λVλ∈Atinuous on R+", g,(x,t) is continuous on R*+",Obviously, r is lower semi-continuous at心。Thenand strictly quasi-convex function of工for any giv-Lemma 2, yieldsent,x∈XCR" ,t∈GCR". Moreover, there exists(M∩r )(2) = M(h) C c1M°(Ax) =at least one point xo such that Eg,(xo,$(h,w))