二层随机规划逼近最优解集的上半收敛性

周婉娜, 霍永亮, 吴凡

(1.重庆师范大学数学学院,重庆 401331;2.重庆文理学院数学与财经学院数学研究所,重庆 402160; 3.重庆文理学院数学党群部,重庆 402160)

二层随机规划逼近最优解集的上半收敛性

周婉娜1, 霍永亮2, 吴凡3

(1.重庆师范大学数学学院,重庆 401331;2.重庆文理学院数学与财经学院数学研究所,重庆 402160; 3.重庆文理学院数学党群部,重庆 402160)

下层随机规划以上层决策变量作为参数,而上层随机规划是以下层随机规划的唯一最优解作为响应的一类二层随机规划问题,首先在下层随机规划的原问题有唯一最优解的假设下,讨论了下层随机规划的任意一个逼近最优解序列都收敛于原问题的唯一最优解,然后将下层随机规划的唯一最优解反馈到上层,得到了上层随机规划逼近最优解集序列的上半收敛性.

二层随机规划,最优解集,上半收敛

1 引言

近几十年来,国内外许多学者对随机规划的逼近理论有了较深入的研究,随机规划稳定性理论的内容也得到了极大的丰富.文献[1]分别对随机规划的期望模型、机会约束模型以及二阶段固定补偿模型作了全面的探讨,得到了一些好的结果.文献[2]研究了当离散化随机变量序列依分布收敛时,随机规划逼近解的收敛性.文献[3]将随机函数引入随机规划问题中,研究了最优函数逼近问题的收敛性.文献[4-5]讨论了在Fourtet-Mourier度量上随机规划问题的稳定性.文献[6]研究了逼近随机规划可行集序列的收敛性条件,得到了随机规划逼近最优解集的上半收敛性.文献[7]利用Kuratowski收敛,研究了二层规划问题的逼近法的有关上图收敛性问题.文献[8]研究了以下层最优值作为响应反馈到上层的一类二层规划的逼近问题的收敛性.目前对二层随机规划稳定性的研究相对较少,作者利用上图收敛性,分别研究了下层随机规划最优解集序列的收敛性和假设原下层随机规划有唯一最优解时,上层随机规划最优解集序列的收敛性.本文研究的内容与文献[7-8]的区别在于:

(1)研究了二层随机规划最优解集的上半收敛性,而文献[7-8]只研究了一般二层规划目标函数的上图收敛性;

(2)研究的是以下层随机规划的唯一最优解作为响应反馈到上层的一类二层随机规划,而文献[7-8]研究的是以下层规划的最优值作为响应反馈到上层的一类二层规划.

本文考虑如下的二层随机规划问题:

的解.其中,本文始终假设X和Y分别是Rn和Rm上的紧集,F,f,g是定义在Rn×Rm×Rp上的函数,µ0=P◦ξ−1,µn=,ξ为定义在概率空间(Ω,F,P)上的m维随机向量,ξn为ξ的离散化逼近随机变量序列.

2 下层随机规划最优解的收敛性

为讨论上层随机规划问题最优解集的收敛性,首先讨论下层随机规划问题最优解的收敛性.当x0∈Rn固定时,下层随机规划问题的原问题变为

问题(3)和问题(4)的可行集分别记为S0(x0)和Sn(xn),即

下层随机规划问题(3)和问题(4)又可转化为与其等价的无约束规划问题(5)和问题(6):

其中

问题(5)和问题(6)的最优解集分别记为M0(x0)和Mn(xn).

引理 2.1(1)若xn→x0且f(x,y,u)在 X×Y×Rp上连续有界,µnw→µ0,则对任意的y0∈Rm,且yn→y0,有

(2)若xn→x0且f(x,y,u)在 X×Y×Rp上连续有界,则对每个固定的n0,

均在Rm上连续.

证明(1)设 xn→ x0,且 yn→ y0,令 gn(u)=f(xn,yn,u),g0(u)=f(x0,y0,u),由于f(x,y,u)在 X×Y×Rp上连续,所以gn(u)和g0(u)在Rp上连续,且gn(u)连续收敛于g0(u),由于f(x,y,u)有界,则函数族{g0;gn,n∈N}等度有界,由于µnµ0,则有

即

(2)在(1)中分别令

引理 2.2若xn→x0,令

那么:

(1)若gj(x,y,u),j=1,2,···,d,在X×Y×Rp上下半连续且下有界,µn→wµ0,则(y)下半收敛于(y).

(2)若gj(x,y,u),j=1,2,···,d,在X×Y×Rp上下半连续且下有界,对每个固定的n0,则(y)和(y)在Rm上下半连续.

(3)若gj(x,y,u),j=1,2,···,d,在X×Y×Rp上下半连续且下有界,对每个固定的y, gj(x,y,u)关于(x,u)上半连续,且,则

证明设xn→x0,且yn→y0,令tn(u)=gj(xn,yn,u),t0(u)=gj(x0,y0,u),由gj(x,y,u)

在 X×Y×Rp上下半连续,则对任意 u0∈Rp,且 un→ u0,有而gj(x,y,u),j=1,2,···,d,在X×Y×Rp上下有界,则函数族{t0;tn,n∈N}等度下有界,而且则

(2)类似于(1)的证明,分别令

(3)在引理2.1中令f(x,y,u)=gj(x,y0,u),j=1,2,···,d.

定义 2.1[6]称可行集 S0(x0)是正则的,即满足 S0(x0)=clS0(x0)°,并且 S0(x0)°∅,其中{∫}

定义 2.2[7]如果xn→x0,集合序列满足:

则称集合序列{Sn(xn)}收敛于S0(x0),记为,意即

(1)如果对任意yn→y0,且yn∈Sn(xn),则y0∈S0(x0);

(2)对任意y0∈S0(x0),则存在yn→y0,那么对充分大的n,有yn∈Sn(xn).

引理 2.3若xn→x0,设gj(x,y,u),j=1,2,···,d,在X×Y×Rp上下半连续且下有界,对每个固定的y,gj(x,y,u)关于(x,u)上半连续,可行集S0(x0)正则,且则

(1)存在n0,当n≥n0时,Sn(xn)为非空紧集;(2)

证明(1)由于S0(x0)正则,则S0(x0)°/∅,设y0∈S0(x0)°,即

并且,y0∈Y,令

则ε>0,由引理2.2的(3)可知,对每个固定的y0,存在nj,当n≥nj,有

令n0=,当n≥n0,有

因此,当 n≥n0时,有 y0∈Sn(xn),即 Sn(xn)/∅,由引理 2.2的 (2)知,Sn(xn)为闭集,而Sn(xn)⊂Y及Y的紧致性,所以Sn(xn)为非空紧集.

yn→y0,由引理2.2的(1)可得,对每个j,均有

而yn∈Y及由Y的紧致性,则y0∈Y,于是

再证明S0(x0)⊂设y0∈S0(x0),由于S0(x0)正则,则S0(x0)=clS0(x0)°,即存在{zn}⊂S0(x0)°,使得zn→y0.由(1)的证明可知,对每个zn,存在Nn,当n≥Nn时有zn∈Sn(xn),构造下列序列yn,

由yn的构造可知,对所有n>N1,有yn∈Sn(xn),另一方面,由zn→y0,则有yn→y0,所以综上,

定义 2.3如果,称上图收敛于记为,是指

(1)对任意yn→y0,有

(2)存在某个yn→y0,使得

引理 2.4若xn→x0,且f(x,y,u)在X×Y×Rp上连续有界,gj(x,y,u),j=1,2,···,d,在 X×Y×Rp上下半连续且有界,对每个固定的 y,gj(x,y,u)关于(x,u)上半连续,可行集S0(x0)正则,且则有

证明首先,证明对任意y0∈Rm,且yn→y0,(7)式成立.

对y0∈Rm分两种情况讨论.

(i)如果y0∈S0(x0),且yn→y0,由引理2.1的(1),有

(ii)如果 y0S0(x0),且 yn→ y0,则存在 n0,当 n≥n0时,有 yn/∈Sn(xn),否则存在 {ynk}使得 ynk∈Snk(xnk),又由于 {yn}为收敛序列,则 ynk→ y0,又由引理 2.3的 (2)有,所以y0∈S0(x0),矛盾.于是有

由(8)式和(9)式知(7)式成立.

其次,证明对任意y0∈Rm,存在某个yn→y0,使得(10)式成立.

对y0∈Rm分两种情况讨论.

(i)如果 y0∈S0(x0),由引理 2.3的 (2),有则存在某 yn→ y0,使yn∈Sn(xn).由引理2.1的(1),有

(ii)如果y0/∈S0(x0),对任意yn→y0,有

由(11)式和(12)式知(10)式成立.综上可知结论成立.

集合A⊂Rn到集合B⊂Rn的上半距离定义为其中

定义 2.4[9]若xn→x0,称集合序列{Mn(xn)}上半收敛于M0(x0),是指

定理 2.1若xn→x0,且f(x,y,u)在X×Y×Rp上连续有界,gj(x,y,u),j=1,2,···,d,在 X×Y×Rp上下半连续且有界,对每个固定的 y,gj(x,y,u)关于 (x,u)上半连续,可行集S0(x0)正则,且则问题(6)的最优解集序列Mn(xn)上半收敛于问题(5)的最优解集M0(x0).

证明由于S0(x0)正则,由引理2.1的(2)和引理2.3的(1)知,存在n0,当n≥n0时,

Mn(xn)∅且M0(x0)/∅.为了证明,即需证明:∀ε>0,∃N0,当n≥N0时,有e(Mn(xn),M0(x0))<ε,也即需证明:∀ε>0,∃N0,当n≥N0时,有

现证对任意包含M0(x0)的开集V,存在n0,当n≥n0时,有Mn(xn)⊂V.假设不成立,即存在nk,使得ynk∈Mnk(xnk)但ynk/∈V,而由于Mnk(xnk)⊂Y及Y的紧致性,则{ynk}必存在聚点y0,而V为开集,则y0/∈V.而另一方面,由引理2.4可得,y0∈M0(x0),即y0/∈V与M0(x0)⊂V矛盾,特别取V=M0(x0)+Bε(0),从而有

推论 2.1若xn→x0,且f(x,y,u)在X×Y×Rp上连续有界,gj(x,y,u),j=1,2,···,d,在 X×Y×Rp上下半连续且有界,对每个固定的 y,gj(x,y,u)关于 (x,u)上半连续,可行集S0(x0)正则,且如果下层随机规划问题(5)有唯一最优解,则问题(6)的任意一个最优解yn(xn)∈Mn(xn)连续收敛于问题(5)的唯一最优解y0(x0).

证明由定理2.1可知,问题(6)的最优解集序列{Mn(xn)}上半收敛于问题(5)的最优解集M0(x0).即∀ε>0,∃N0,当n≥N0时,有

其中 Bε(0)={y∈Rm|∥y−0∥<ε}.由于下层随机规划问题 (5)有唯一最优解 y0(x0),即 M0(x0)={y0(x0)},且对任意的 yn(xn)∈Mn(xn),则由 (13)式可得,∀ε>0,∃N0,当n≥N0时,有

3 上层随机规划最优解集的收敛性

设y0(x)是下层随机规划原问题(1b)的唯一最优解,yn(x)是下层随机规划逼近问题(2b)最优解集中的任意一个最优解.则上层随机规划的原问题改写为:

相应的逼近问题改写为:

问题(14)和问题(15)的最优解集分别为M0和Mn.

定理 3.1若xn→x0,且 F(x,y,u),f(x,y,u)在X×Y×Rp上连续有界,gj(x,y,u), j=1,2,···,d,在X×Y×Rp上下半连续且有界,对每个固定的y,gj(x,y,u)关于(x,u)上半连续,可行集S0(x0)正则,且如果下层随机规划原问题(1b)有唯一最优解,则

证明由推论2.1可知,当xn→x0时,yn(xn)连续收敛于y0(x0).此外,由于F(x,y,u)在X×Y×Rp上连续有界,所以对每个固定的u,有

故由文献[9]的定理5.1,有

定理 3.2若F(x,y,u),f(x,y,u)在X×Y×Rp上连续有界,gj(x,y,u),j=1,2,···,d,在X×Y×Rp上下半连续且有界,对每个固定的y,gj(x,y,u)关于(x,u)上半连续,对任意的x0∈Rn,可行集S0(x0)正则及X为紧集,且如果下层随机规划原问题(1b)有唯一最优解,则问题(15)的最优解集序列Mn上半收敛于问题(14)的最优解集M0.

证明令Hn(x)=F(x,yn(x),u)µn(du).H0(x)=F(x,y0(x),u)µ0(du),应用定理3.1可知,当xn→x0时,有

其余类似于文献[9]的定理5.4证明.

[1]Wets R J B.Stochastic Programming[A].Handbook of Operations Research and Management Science[C]. Amsterdam:Elsevier Science Publisher,1989.

[2]骆建文,鲁世杰.随机规划逼近解的收敛性[J].浙江大学学报,2000,27(5):493-497.

[3]Luo Jianwen.Stability analysis for stochastic optimization problems[J].Journal of Shanghai Jiaotong University,2007,12(5):684-687.

[4]Romish W,Schultz R.Stability analysis for stochastic programs[J].Annals of Operations Research, 1991,30(1):241-266.

[5]Dupatcova J,Growe-Kuska N,Romish W.Scenario reduction in stochastic programming:An approach using probability metric[J].Mathematical Programming,2003,95(3):493-511.

[6]霍永亮,刘三阳.随机规划逼近最优解集的上半收敛性[J].西安电子科技大学学报,2005,32(6):953-957.

[7]万仲平,吴国民,陈开周.一类二层规划的上图收敛性[J].运筹学学报,1998,2(24):48-53.

[8]万仲平.关于二层规划的逼近问题[J].系统科学与数学,2000,20(3):289-294.

[9]霍永亮.随机规划稳定性理论[M].成都:西南交通大学出版社,2010.

The upper semi-convergence of the optimal solution set of approximation for bi-level stochastic programming

Zhou Wanna1,Huo Yongliang2,Wu Fan3
(1.College of Mathematics,Chongqing Normal University,Chongqing 401331,China; 2.College of Mathematics and Finance,Institute of Mathematics,Chongqing University of Arts and Sciences, Chongqing 402160,China; 3.Party Member and Concourse Department,Chongqing University of Arts and Sciences, Chongqing 402160,China)

A bi-level stochastic programming problem where the upper level stochastic programming is an optimization problem including a parametric unique optimal solution of the lower level stochastic programming, and the lower level stochastic programming is a parametric nonlinear programming including the decision variables of the upper level stochastic programming as parameters.This paper f i rst discusses the assumption that the lower level stochastic programming has unique optimal solution of the original problem,any approximation optimal solution sequence of the lower level stochastic programming converges to the unique optimal solution of the original problem.And then feedbacks the unique optimal solution of lower level stochastic programming to the upper level,obtains the upper semi-convergence of the upper level stochastic programming approximation optimal solution sequence.

Bi-level stochastic programming,optimal solution set,upper semi-convergence

O221.5

A

1008-5513(2014)02-0207-09

10.3969/j.issn.1008-5513.2014.02.013

2013-07-01.

重庆市教委科研基金(KJ091211);重庆高校创新团队建设计划项目(KJ301321).

周婉娜(1987-),硕士生,研究方向:随机规划稳定性理论.

霍永亮(1965-),教授,研究方向:随机规划稳定性理论.

2010 MSC:90C30