王俊林，霍永亮

(1.重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶401331;2.重慶文理學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶永川402160)

機(jī)會(huì)約束規(guī)劃由查納斯(A.Charnes)和庫(kù)伯(W.W.Cooper)于1959年提出，作為隨機(jī)規(guī)劃的一個(gè)分支，當(dāng)問(wèn)題介入的隨機(jī)變量個(gè)數(shù)較多時(shí)，決定區(qū)域和期望中的多重積分求法比較難，使得非線性規(guī)劃的許多算法失效，于是常利用某種逼近方法來(lái)求解隨機(jī)規(guī)劃問(wèn)題［1］.由于概率的擾動(dòng)性，這就產(chǎn)生了最優(yōu)值與最優(yōu)解集在數(shù)量與性質(zhì)方面的穩(wěn)定性問(wèn)題.為了研究逼近解更好地接近初始問(wèn)題的解，近年來(lái)有許多學(xué)者以各種形式構(gòu)造機(jī)會(huì)約束規(guī)劃問(wèn)題的最優(yōu)解集、有效解集及弱有效解集的逼近方法.其中文獻(xiàn)［2］基于切平面的產(chǎn)生及算法研究了非線性機(jī)會(huì)約束規(guī)劃的最優(yōu)解;文獻(xiàn)［3］以概率測(cè)度的某種收斂性分析隨機(jī)規(guī)劃問(wèn)題逼近最優(yōu)解的穩(wěn)定性，得到了逼近解的一些相關(guān)結(jié)論;文獻(xiàn)［4，5］對(duì)隨機(jī)規(guī)劃逼近問(wèn)題作了一些穩(wěn)定性分析;文獻(xiàn)［6］提出概率約束規(guī)劃的概率目標(biāo)模型并以一種逼近算法求解，討論了其算法的有效性;文獻(xiàn)［8，9］研究了隨機(jī)規(guī)劃的上圖收斂及方法等.關(guān)于機(jī)會(huì)約束規(guī)劃問(wèn)題逼近的穩(wěn)定性方向，此處在文獻(xiàn)［3，7，12-14］的啟發(fā)下從單目標(biāo)機(jī)會(huì)約束規(guī)劃問(wèn)題最優(yōu)值函數(shù)著手，以分布收斂、K-收斂、上圖收斂、上半收斂等工具進(jìn)一步分析了問(wèn)題的逼近解及其穩(wěn)定性.

考慮如下單目標(biāo)機(jī)會(huì)約束規(guī)劃模型:

其中，x=(x1，x2，…，xN)T∈RN，ξ為定義在完備型概率空間(Ω，F(xiàn)，P)上的m維連續(xù)隨機(jī)向量，確定性約束集D?RN是緊致的，B(RN)表示RN中的Borel子集全體，P是定義在B(RN)上的概率測(cè)度全體，f:RN×Rm→R，g:RN×Rm→Rd，N為自然數(shù)全體.問(wèn)題(1)的可行集、最優(yōu)解集分別為S0和P0.

設(shè){ξn}為ξ的離散化隨機(jī)變量序列，且隨機(jī)變量序列按分布收斂于ξ0，記作，則問(wèn)題(1)的逼近模型為:

問(wèn)題(2)的可行集和最優(yōu)集分別記為Sn和Pn.

于是問(wèn)題(1)和(2)轉(zhuǎn)化成了與其等價(jià)的確定性機(jī)會(huì)約束規(guī)劃模型:

則問(wèn)題(3)的目標(biāo)函數(shù)、可行集及最優(yōu)解集記為Q(x，μ0)，S(μ0)及P(μ0);問(wèn)題(4)的目標(biāo)函數(shù)、可行集及最優(yōu)解集記為 Q(x，μn)，S(μn)及 P(μn).

于是由問(wèn)題(3)和(4)可以得到無(wú)約束的規(guī)劃型問(wèn)題(5)和(6)

主要以函數(shù)的上圖收斂、上半收斂等刻劃逼近問(wèn)題最優(yōu)解集的穩(wěn)定性，考慮到等價(jià)于μ，于是問(wèn)題(2)逼近(1)的最優(yōu)解就等價(jià)于問(wèn)題(6)逼近(5)的最優(yōu)解.

1 上圖收斂

引理1 設(shè){μ0;μn，n∈N}為B(RN)上的概率測(cè)度族，則下列條件等價(jià):

(2)對(duì)任意的{An，n∈N}?B(RN)，且(An)≤μ0(A0).

(3)對(duì)任意的{An，n∈N}?B(RN)，且(An)≥μ0(A0).

證明 參見(jiàn)文獻(xiàn)［3］的定理1.1.

定義 1［3］令:

定義2［10］稱集合 S(μ)是正則的，指 S(μ)=cl S(μ)°，且 S(μ)°≠?，其中 cl表示閉包，S(μ)°=00000{x∈D?RN:μ0(h(x))-α ＞0}.

證明 要證Q(xn，μn)在D×Rm上連續(xù)，即要證其在D×Rm內(nèi)上半連續(xù)且下半連續(xù).

情形1 當(dāng)f(x，ξ)在D×Rm上下半連續(xù)時(shí)，設(shè)x0∈D且xn→x0，令 ξ0H(xn)，其中

(2)對(duì)每個(gè)給定的 x∈RN，μ0(N(x))=0.其中 N(x)={μ∈Rm:gi(x，μ)=0，i=1，2，…，d}.

(3)S(μ0)=cl S(μ0)°，且 S(μ0)°≠?.

則 i)存在N0，當(dāng)n≥N0時(shí)，S(μn)是非空緊集.

證明 i)由定理1的(3)可知 S(μ0)°≠?.令任意 x0∈S(μ0)°，x0∈D 且 μ0(h(x0))-α ＞0，設(shè) β=μ0(h(x0))-α，即 β ＞0，由定理1 的(2)知對(duì)每個(gè)固定的 x0∈RN，有 μ0(N(x0))=0，又由文獻(xiàn)［3］，定理5.6可知，對(duì)任意給定ε＞0，使得0＜ε＜β時(shí)，存在N0，當(dāng)n≥N0時(shí)，有

于是當(dāng) n≥N0時(shí)，有 x0∈S(μn)，即 S(μ0)°?S(μn)?D，由 D 的緊性知，Sn是非空緊集.

ii)由gi(x，μ)(i=1，2，…，d)在RN×Rm上連續(xù)及S(μn)?S(μ0).下證:S(μ0)).不妨設(shè) x0∈S(μ0)，由可行集 S(μ0)為正則的，則必存在{zn}?S(μ0)°，使得 zn→x0，由 i)的證明過(guò)程可知，對(duì)?zn，?Nn時(shí)，有zn∈S(μn)，于是可以構(gòu)造如下數(shù)列:

從序列的構(gòu)造可得，對(duì)所有的 n≥N1，有 xn∈S(μn).又由 zn→x0，故 x0，于是由定義 1 可知

定義 3［9，10］設(shè)函數(shù)序列{f:RN×Rm→∈N}和函數(shù) f:RN×，若有

i)對(duì)?x0∈RN，xn→x0，有)≥f(x0).

ii)對(duì)?x0∈RN，?xn→x0，有)≤f(x0).

則稱函數(shù)序列{fn:RN×Rm→R，n∈N}上圖收斂于f:RN×Rm→R，記

定理2 設(shè)對(duì)任意 i∈{1，2，…，d}，gi(x，μ)在 D × Rm上下半連續(xù)，對(duì)給定的 x，gi(x，ξ)，關(guān)于 μ 上半連續(xù)，且滿足:

(2)對(duì)每個(gè)給定的 x∈RN，μ0(N(x))=0.其中 N(x)={μ∈Rm:gi(x，μ)=0，i=1，2，…，d}.

(3)S(μ0)=clS(μ0)°，且 S(μ0)°≠?.

不妨設(shè)x0∈RN，由D的緊致性知，必存在xn→x0，接著對(duì)x0∈RN以下兩種情形討論:

① 若 x0∈S(μ0)，并且 xn→x0，由 δS(x)的定義有:

② 若 x0?S(μ0)，并且 xn→x0，則必存在 N，當(dāng) n≥N 時(shí)，有 xn?S(μn).否則，存在{nk}，使得 xnk∈S(μnk)，且xnk→x0.由，則x0∈S(μ0)，這與x0?S(μ0)矛盾.于是由δS(x)的定義知:

根據(jù)(8)(9)兩式知定義3(i)成立.

同理，設(shè)x0∈RN，面對(duì)其亦分兩種情形討論:

由(10)(11)兩式知定義3(ii)成立，綜合式(8)(11)，結(jié)論成立，證畢.

2 最優(yōu)解集的上半收斂性

定義 4［14］如果)=0，則稱集合序列{S}上半收斂于 S.其中上半距離 e(A，B)=n0.集合 A?RN，B?RN，RN為 N 維歐氏空間.

定理3 設(shè)f(x，ξ)在 D ×Rm上連續(xù);對(duì)任意 i∈{1，2，…，d}，gi(x，μ)在 D ×Rm上下半連續(xù);對(duì)給定的x，gi(x，μ)關(guān)于 μ 上半連續(xù)，滿足:

則問(wèn)題(6)的最優(yōu)解集序列{~P(μn)}上半收斂于式(5)的最優(yōu)解~P(μ0).

因S(μ0)是正則，故存在n0，當(dāng)n＞n0時(shí)，P~(μn)≠?，利用文獻(xiàn)［9］，定理7及式(12)可知，要證明最優(yōu)解集{P~(μn)}上半收斂于 P~(μ0)，即)，P~(μ0))=0，需證:?ε ＞0，?N0，當(dāng) n≥N0時(shí)，有 P~(μn)?P~(μ0)+Bε(0)，其中 Bε(0)={x∈RN:x-0 ＜ε}.下證:對(duì)任意的開(kāi)集 V 且 P~(μ0)?V，?N0，當(dāng) n≥N0時(shí)，有P~(μn)?V，假設(shè)此結(jié)論不成立，則必存在序列{xn}，使得xn∈P~(μn)且xn?V，因 P~(μn)?D和D的緊kkkkk性，序列{xnk}必存在聚點(diǎn)x0，又由V是開(kāi)集，故x0?V，另外由文獻(xiàn)［10］的定理4及文獻(xiàn)［11］命題3.3知，x0∈P~(μ0)，這與 P~(μ0)?V 矛盾.特別地，取 V=P~(μ0)+Bε(0).證畢.

推論1 設(shè)f(x，ξ)在 D ×Rm上有界連續(xù)，且對(duì)任意 i∈{1，2，…，d}，gi(x，μ)在 D ×Rm上有界下半連續(xù);對(duì)給定的x，gi(x，μ)有界且關(guān)于μ上半連續(xù)，滿足:

則問(wèn)題(4)的最優(yōu)解集序列{P(μn)}上半收斂于(3)的最優(yōu)解P(μ0).

證明 考慮到條件中f(x，ξn)在D×Rm上的有界性及等價(jià)于應(yīng)用定理3知，對(duì)任意 i∈{1，2，…，d}，問(wèn)題(4)的最優(yōu)解集序列{P(μn)}上半收斂于式(3)的最優(yōu)解 P(μ0).

［1］駱建文，魯世杰.概率約束規(guī)劃的穩(wěn)定性分析［J］.高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，2001，16(1):119-124

［2］WEINTRAUB A.A cuting plane approach for chance constrained linear programs［J］.operations research，1991，39(5):776-785

［3］霍永亮.隨機(jī)規(guī)劃穩(wěn)定性理論［M］.成都:西南交通大學(xué)出版社，2010

［4］駱建文，魯世杰.隨機(jī)規(guī)劃逼近解的收斂性［J］.浙江大學(xué)學(xué)報(bào)，2000，16(4):15-20

［6］張克邦，黃炳章.概率約束規(guī)劃的概率目標(biāo)模型及其解法［J］.上海交通大學(xué)學(xué)報(bào)，1992，26(1):90-95

［5］DENTCHEVA D，HENRION R，RUSZCZYNSKI A.Stability and sensitivity of optimi-zation problems with first order stochastic dominance constraints［J］.Society for industrial and applied Mathmatics，2007，18(1):322-337

［7］R?MISCH W，SCHULTZ R.STABILITY ANALYSISFOR STOCHASTIC PROGRAMS［J］.Annals of Operations Research，1992(30):241-266

［8］ ZERVOS M.ON THE EPICONVERGENCE OF STOCHASTIC OPTIMIZATION PROBLEMS［J］.Mathematics of Operations Research，1999(2):495-508

［9］ PENNANEN T，KOIVN M.Epi-covergent discretizations of stochastic programs via integration quadratures［J］.Numerische Mathematic，2005，100(1):141-163

［10］霍永亮，劉三陽(yáng).隨機(jī)規(guī)劃逼近最優(yōu)解集的上半收斂性［J］.西安電子科技大學(xué)學(xué)報(bào)，2005，36(6):953-957

［11］DUPACOVA J，WETSR J B.Asymptotic Behavior of Statistical Estimators of Optimal Solutions of Optimiation Problems［J］.the Annals of statistics，1998，16(1):1517-1549

［12］SALINETTI G.Approximations for chance constrained programming problems［J］.Stochastic，1983(10):157-179

［13］KUCHLER C.On stability of multistage stochastic programs［J］.Society for industrial and applied Mathmatics，2008，19(2):952-968