一类概率约束规划的近似方法及其收敛性_古福文
1997年8月第34卷第4期四川大学学报(自然科学版)
Jo urnal of Sichuan U niver sity (N atur al Suience Editio n) Aug. 1997Vo l. 34 N o. 4
一类概率约束规划的近似方法及其收敛性
古福文
(应用数学系)
r
摘要 对概率约束规划min{cx +E
∑q [F -i
i
i =1
A i x ]+ûP (A x ≥F ) ≥p , Bx ≥b }, 讨论了
F 是无界随机向量时的近似方法, 并证明了这种近似方法的收敛性.
关键词 随机规划, 概率约束规划, 机会约束规划, 近似方法, 收敛性中图法分类号 O 221. 5
1 引言
讨论具有如下形式的概率约束规划:
r
min{cx +
∑q E [F -i
i
i =1
A i x ]+}, s . t . P (Ax ≥F ) ≥p , B x ≥b ,
(1. 1)
其中F 是r 维随机向量; A 、B 分别是r ×n 和m ×n 维非随机矩阵; b 、c 分别是m 维和n 维
非随机向量; x 是n 维决策向量; q 1, …, q r 是非负常数, p 是一可靠性水平, 0
+
的第i 行, [F i -A i x ]的数学期望.
+
[F i -A i x ]=
F i -A i x ,
F i -A i x
当F 是仅取有限个可能值的离散随机向量, 且A i x 是{x ûBx ≥b }上的有界函数(i =1, …r ) 时, (1. 1) 可转化成有限多个线性规划. 因此, A. Preko pa 在文[1]中提出了一个求解(1. 1) 的对偶算法.
当F 是有界连续型随机向量时, 本文作者在文[2]中讨论了求(1. 1) 近似解的方法, 并证明了这种方法的收敛性.
F i -A i x ≥0,
2 主要结论
在下面的讨论中, 设F , {F }都定义在同一概率空间(8, F , P ) 上, F 是连续型随机向量,
(l ) (1) (2) (l )
E F 存在, F 是仅取有限个可能值的离散型随机向量, F ≤F ≤…≤F , F 依分布收敛于F .
我们用下面的规划(2. 1) 作为(1. 1) 的近似.
(l )
400四川大学学报(自然科学版) 第34卷
r
min{cx +
∑q E [F
i
i =1
(l )
i
-A i x ]}, s . t P (Ax ≥F ≥P , Bx ≥b
+(l )
(2. 1)
近似规划(2. 1) 的求解是容易的, 在文[2]中, 我们讨论了它的求解方法. 下面我们将证明近似值及近似解的收敛性.
-=c -qA , q =(q 1, …, q r ) , 则有cx +令c
r
-i -A i x ]=c x +∑q i E [F
+
i =1
r
∑q ∫F (z ) d
i
r
A x
i
i =1
-∞
i z
+
∑q E F .
i
i
i =1
因此规划(1. 1) 、(2. 1) 分别等价于规划(2. 2) 、(2. 3) .
-min{c x +min{-c x +
∑q ∫F (z ) dz }, s . t P (Ax ≥F )
i
r
A x
i
i =1
-∞
i
≥p , B x ≥b , (2. 2) (2. 3)
r i =1
∑q i
r i =1
∫
i i
A x
F i (z ) d z }, s . t P (A x ≥F (l ) ) ≥p , Bx ≥b -∞
A x
(l )
(l )
其中F i , F (i l ) 分别为F i , F i 的分布函数. 为了讨论方便, 我们引入过渡性规则(2. 4).
min{-c x +
∑q i
∫
(l )
F i (z ) d z }, s . t P (A x ≥F ≥P , Bx ≥b . -∞
(l )
(l )
(2. 4)
令X ={x ûP (A x ≥F ) ≥p , Bx ≥b }, X ={x ûP (A x ≥F ≥p , Bx ≥b }, V ={(u ,
-v ) ≥0ûuA +vB =C }, X (y ) ={x ûAx ≥y , B x ≥b }, W (l ) ={x (l ) ûx (l ) 为(2. 3) 的最优
***(l ) -(l )
解}, W ={x ûx 是(2. 2) 的最优解}, z 、z 、z 分别是规划(2. 2) 、(2. 3) 、(2. 4) 的最优值, D (p , F ) ={y ∈R r ûP (F ≤y ) ≥p , 且若存在-y ∈R r 使得P (F ≤-y ) ≥p , 则有-y K y }. -R =RU {+∞}, I ={i ûinf{z ∈-R ûF i (z ) =1}0, A x ≥0, Bx ≥0,
-c x =0}=§}.
引理1[2] 任给l , 存在正整数N (l ) 和R r 中的N (l ) 个点y (1l ) , …, y (N l ) (l ) , 使得:
(l )
D (p , F ) ={y (1l ) , …, y (N l ) (l ) },
{x ûP (A x ≥F ) ≥p }=j ∪{x ûA x ≥y (i l ) }.=1
证明 注意到D (p , F ) y 1≤y 2时{x ûAx ≥y 1}B {x ûA x ≥y 2}即得.
x j x j
+
(l )
(l )
N (l )
x x
L (y j =1
+
x x
L (y )
+
j
+
引理2 设X (y ) ≠§, x -j ) 为{x -≥0û(D , -D , -I ) x -=d }的一切基本可
I
I
I
行解, (j =1, …, L (y ) ) , 令E (y ) ={∑C j (x
-x ) ûM j ≥0,
+
-
-j
∑C =
j
j =1
1}, 则有:
X (y ) ={x ûDx ≥0}+E (y ) , D (x j -x j ) ≥d (j =1, …, L (y ) ) ,
且存在一个正数M 使得任给x ∈a ≤∪E (y ) 有‖x ‖≤M . y ≤-a 其中D =
A
[2]
B b
引理3 设X (y ) ≠§, V ≠§, 则对任一随机向量G =(G 1, …, G r ) T , 存在-x ∈E (y )
-{r i , d =
y
-∈R r . , I 是r +m 阶的单位矩阵, a , a
使得
(û() i
A x
G
第4期古福文:一类概率约束规划的近似方法及其收敛性
--=c x +
401
∑q ∫F
i
i =1
-∞(l )
r
A i x
G
i
(z ) d z ,
r
i 的分布函数. 其中F G i 为G
令D (p , F , z
(l )
(l )
(l ) (l )
) ={y
(l )
(l )
∈D (p , F ) û-z (e ) =min{-c x +
(l )
∑q i
i =1
r i =1
X (y ) }}, D (p , F , z ) ={y
(l )
∈D (p , F ) ûz
(l ) (l )
-x +=m in{c
∫
∑q ∫F (z ) dz ûx
i
A x
(l ) F i (z ) d z ûx ∈-∞A x
i
i
-∞
i
∈
x (y ) }}.
引理4 设x ≠§, V ≠§, 则有:
(1) (2) (l ) *(l ) (l ) *-----(a) -∞
(b ) D (p , F , z ≠§, D (p , F , z (l ) ) =§.
证明 (a) 的证明见[文2, P51, 引理4], 因此仅需证明(b). 任给l , 由引理1有X
(l )
(l )
=∪X (y j ) , 所以j =1
r i =1
N (l )
(l ) -z =min{-c x +
∑q i
∫
i
A x
F i (z ) d z ûx ∈X -∞
r i =1
(l )
}
(l )
-=1≤min min{c x +j ≤N (l ) =min{-c x +
r i =1
∑q i
A x
i
∫
i
A x
F i (x ) dz ûx ∈X (y j ) }-∞
∑q i
∫
-∞
F i (z ) d z ûx ∈X (y (j l 0) ) }.
(l ) -(l ) (l ) -(l ) (l )
因此, y (j 0l ) ∈D (p , F , z ) , 故D (p , F , z ) ≠§. 同理可证D (p , F , z (l ) ) ≠§.
引理5 设X ≠§, V ≠§, I ={1, …, r }且存在x 0∈R r 使得A x 0>0, B x 0≥0, 则
r (l ) (l ) (l ) (l )
存在两个向量a , -a ∈R 使得任给l 及y ∈D (p , F , -z ) 有a ≤-y ≤-a .
证明 令I *={i ûinf{z ∈-R ûF i (z ) =1}=+∞}, I **={i ûinf{z ∈-R ûF i (z ) =1}
I VI ={1, 2, …, r }=I .
(1)
因F 是仅取有限多个点的随机向量, 所以存在一个下界向量a =(a 1, …, a r ) T , 使得P (F >a ) =1. 注意到F ≥F , 所以对任意的l 有
i i P (F >a ) ≥P (F >a ) =1]P (F >a i ) =1 (i ∈I ) ]P (F ≤a i ) =0 (i ∈I ) .
(l )
任给y (l ) ∈D (p , F ) 下证y (l ) >a .
(l )
若y (l ) >a 不成立, 即有y (l ) 的某个分量y (i 0l ) 使得y (i 0l ) ≤a i 0. 则由(*) 有0=P (F i ≤a i ) 00(l )
(1)
(l )
(l )
(1)
(l )
(1) *
**
≥P (F i ≤y i 0) ≥0, 即P (F i ≤y i ) =0. 但另一方面又有P (F i ≤y i 0) ≥P (F ≤y ) 0000≥p >0. 矛盾. 所以任给l 及y ∈D (p , F ) 有y >a .
(l ) -(l ) (l ) (l ) -(l )
注意到D (p , F , z ) A D (p , F ) , 故任给l 及y (l ) ∈D (p , F , z ) 有y (l ) >a . 因此找到了所需的下界向量a , 下面我们来找上界向量-a .
对于任意给定的i ∈I *, 令D i =A i x 0, T i ={x ∈R n ûB x ≥0, A i x ≥D i , A j x ≥0, j =1, …, i -1, i +1, …, r }.
由x 0∈{x ∈R ûA x >0, B x ≥0}可得x 0∈T i 且D i >0. 构造线性规划
min -c x , s . t x ∈T i , n
(l )
(l )
(l )
(l ) (l ) (l ) (l ) (l ) (l ) (l ) (l )
(2. 5)
402四川大学学报(自然科学版) max D i u i , s . t (u , v ) ∈V
第34卷(2. 6)
因T i ≠§, V ≠§, 由[文4, P212, 定理1. 1]知(2. 5) 、(2. 6) 都存在最优解, 且最优值相等.
设-x (i ) 、(-u (i ) , -v (i ) ) 分别是(2. 5) 、(2. 6) 的最优解, 则有-c -x (i ) =D i -u (i i ) ≥0. 而当i ∈I *=I *
(i ) (i ) (i ) ---∩I 时, 有{x ûA i x >0, Ax ≥0, Bx ≥0, c x =0}=§, 因此必有c x =D i -u i >0]-u i >0.
(l ) (l ) (l ) (l ) *(l )
对于任给的l 及y ∈D (p , F , -z ) , 显然有X (y ) ≠§. 根据引理3知存在x ∈E (y ) A X (y ) 使得-z (l ) =m in{-c x +
(l )
-*
∑q j -∞F j (z ) dz ûx ∈X (y ) }=c x +
j =1
r
∫
j
A x
(l )
∑q ∫
j
r
A x
*
j
-x *≥m in{c -由q j ≥0, F j (z ) ≥0(j =1, …, r ) 有-z (l ) ≥c x ûx ∈X (y (l ) ) }=m ax {uy (l ) ≠
(i ) (l ) (i ) (l ) -(i ) b =-vb û(u , v ) ∈V }≥-u y +v u i y i +
(i ) (l ) (i ) (i ) (l ) u j y j +-v b ≥-u i y i +∑-j ≠i
j =1
-∞
F j (z ) dz .
u ∑-j ≠i
(i )
j
(i )
a j +-v b .
即任给l 有-u (i i ) y (i l ) +
u ∑-j ≠i
(i ) j
-(i ) ) 与a j +-v (i ) b ≤-z (l ) ≤z *(引理4(a ) ) . 注意此处的(-u (i ) , v
(l ) -(l )
l , y (l ) 无关, 所以任给l 及y (l ) ∈D (p , F , z ) 有:
y
max {(z 0, -h =
*
(l )
i
≤(z
*
--v (i ) b -(i ) j
u ∑-j ≠i
(i ) j
a j ) /-u (i i ) .
i *≠§, *
I =§, I **≠§, **
I =§.
令h =
(i )
--v b -
u ∑-j ≠i
(i ) *
a j ) /-u i ûi ∈I },
max {inf{z ∈-R ûF j (z ) =1}ûj ∈I **}, 0,
任给l 及y (l )
-h =m ax {h , -h }, -a =(~h , …, ~h ) T .
(l ) -(l ) -就是所需的上界向量. ∈D (p , F , z ) , 从上面的讨论易知有y (l ) ≤-a . 故a
引理6 设引理5的假设成立, 则有:
(l ) (l ) (l )
(a) lim z 存在且lim z =lim -z ;
(l )
(b) 存在一个上界向量-a ∈R r 使得任给l 及y (l ) ∈D (p , F , z (l ) ) 有a ≤y (l ) ≤~a .
(l ) (l ) (l ) (l )
证明 由{X ûF i (X ) ≤z }B {X ûF i (X ) ≤z }有F i (z ) ≥F i (z ) , 从而z ≥-z .
l →∞
l →∞
l →∞
由引理4知存在y
(l )
(l ) (l )
∈D (p , F , -z ) 使得
--z (l ) =min{c x +
再由引理3知存在x
(l ) (l ) --z =[c x +
r (l )
(l )
∑q ∫F (z ) dz ûx ∈X (y
i
i =1
-∞
i
r
i
i =1
r
r
A i x
(l )
) },
(l )
-(l ) =-∈E (y ) 使得z c x (l ) +
∑q ∫
A i x
-∞
F i (z ) dz , 所以
(l )
r i =1
∑q i
∫
i i
A x (l ) -∞
F (z ) d z ]+
(l )
(l )
i
∑q i
i =1
∫
i
A x (l ) -∞
[F i (z ) -F i (z ) ]dz
≥z
(l )
+
∑q i
i =1
∫
A x (l ) -∞
[F i (z ) -F i (z ) ]dz .
根据引理5有a ≤y (l ) ≤-a ]‖x (l ) ‖≤M (引理2) ]{A i x (l ) }是一有界序列(1≤i ≤
-=max {M 1, …, M r }.因而任给i ∈{1, …, r }和l 有A i x (l ) ≤M -综上r ). 设其界为M i , 令M
第4期古福文:一类概率约束规划的近似方法及其收敛性
(l ) (l )
0≤-z -z ≤∑q i
i =1r i =1-M r
403
∫[F
i
A x (l ) -∞-M
(l )
i
(z ) -F i (z ) ]dz
≤∑q i
由[文5, P105, 定理1]有lim q i
l →∞∑
i =1
r
∫[F
-∞(l ) i
(l ) i
(z ) -F i (z ) ]dz .
∫
[F (z ) -F i (z ) ]dz =-∞
∑q ∫lim [F
i
i =1
-∞l →∞
r
-M
(l )
i
(z ) -
F i (z ) ]dz =0.
因此lim (z l →∞
(l )
(l )
(l ) (l ) -(l ) ) =0. 由引理4知lim z -(l ) 存在, 故lim z (l ) =lim [(z (l ) ----z z +z ]=l →∞l →∞l →∞
-lim z , 即(a ) 成立. l →∞
由y a .
(l )
>a 及D (p , F , z ) A D (p , F ) 可得, 任给l 及y
(l ) (l ) (l ) (l )
∈D (p , F , z ) 有y
(l ) (l ) (l )
>
*(i ) (i ) (i ) 对于任意给定的i ∈I , 从引理5的证明知存在-x , (-u , -v ) 分别是(2. 5) 、(2. 6) 的最
优解且-U (i i ) >0.
对于任给的l 及y ≤z
(l )
(l )
∈D (p , F , z
(l ) (l )
) , 类似于引理5的证明有-u (i ) y (i l ) +
∑U
j ≠i
(i ) j
a j +-v (i ) b
.
(l ) (l ) (l )
因为lim z 存在, 所以{z }是一有界序列, 设其界为K . 则对任给的l 及y ∈D (p , l →∞
(l )
F , z (l ) ) , 有
-u (i ) y (i l ) +
即
(l )
∑u
j ≠i
(i )
j
-(i ) b ≤z (l ) ≤K , a j +v
y i ≤(K --v (i ) b -(i )
max {(K --v b -
∑u
j ≠i
-(j i ) a j ) /-u i (i ) . I *≠§, *
I =§
令f =
u ∑-j ≠i
(i ) j
(i ) *
a j ) /-u i ûi ∈I },
0,
f -=m ax{f , -h }, T
~a =(-f , …, -f ) .
则对任给的l 及y
(l )
∈D (p , F , z
(l ) (l )
) 有a ≤y
(l )
≤~a , 即(b ) 成立.
n
有了上述引理, 我们可以给出这种近似方法的收敛性定理.
定理1 设X ≠§, V ≠§, I ={1, 2, …, r }且存在x 0∈R 使得A x 0>0, Bx 0≥0, 则有:
(a) 任给l , W (l ) ≠§;
(b) (limsup W ) ≠§, 其中limsup W (c) (lim sup W
(l ) (l )
(l )
={x ûx
(l )
k
→x , x
(l )
k
≤W
(l )
k
};
) A W ;
(l )
(l )
(l )
(l )
(l )
(l )
(d) lim z (l ) =z *. l →∞
证明 任给l , 由引理4(b ) 知D (p , F , z c r i ) ≠§. 设y ∈D (p , F , z ) , 则有z =
i
i
A x
û(-(l ) (l )
404
再由引理3知存在x
(l )
四川大学学报(自然科学版) ∈E (y ) (A X (y ) A x ) 使得z
(l )
(l )
(l )
(l )
第34卷
-x (l ) +=c
r i =1
∑q i
∫F
i
A x (l ) -∞
(l )
i
(z ) dz .
所以x (l ) ∈W (l ) , 即(a) 成立.
(l ) (l )
由引理6(b) 知a ≤y ≤-a . 因此上述所得的最优解序列{x }是一有界序列(引理2) , 所以存在收敛的子序列{x k }.
(l ) k 设lim x l k →∞=-x , 则-x ∈(limsup W (l ) ) ](b ) 成立.
又设x
*
*
(l )
∈(limsup W ) ]存在x
(l ) (l )
k
∈W
(l )
k
使得x
*
=lim x k →∞
(l )
k
]li l m F →∞
k
(l )
k
(A x
(l )
k
) =
F (A x ) ([文6, P83, (7) ]) .
因P (A x P (Ax
*
(l )
k
≥F ≥p , 所以p ≤l lim P (Ax →∞
k
k
(l )
(l )
k
≥F =l lim F (l k ) (A x (l k ) ) =F (A x *) =→∞
k
k
(l ) r
≥F ). 显然有Bx
(l ) (k i
*
-≥b , 因此x ∈X ]c x *+
*
(l )
k
∑q ∫F (z ) dz ≥z
i
i =1
-∞
i
(l ) -(z ) dz ≥c x k +
r
i
i =1
Ax
*
*
.
i
由F 所以
z ) ≥F i (z ) 有z
-x (l k ) +=c
∑q ∫
i
r
A x (l k ) -∞
i
i =1
F
(l )
k i
∑q ∫
A x (l k ) -∞
F i (z ) dz ,
lim z l →∞
(l )
=l lim z →∞
k
(l )
k
(l ) -k
≥l lim [c x +→∞
k
∑∫
i
r
A x (l k ) -∞*
i =1
F i (z ) dz ]
=-c x +
*
∑q ∫
i
r
A x *-∞
i
i =1
F i (z ) dz ≥z .
*
结合(1) 、(4) 、(8) 有lim z l →∞
(l )
=lim z l →∞
(l )
=z 且z
*
=-c x *+
∑q ∫F (z ) dz ]
i
r
A x
*
i
i =1
-∞
i
x *∈
W ](c) 、(d) 成立.
定理1中的(a ) 表明了近似规划解的存在性, (d ) 说明了近似值收敛到原规划的最优值, (b ) 、(c ) 表明了存在一个收敛到原规划最优解的近似解子序列.
参 考 文 献
b 1 P reko pa A . ZO R zeitschr ift fu r O per atio ns R esea rch , 1990, 34(6) :441～4612 古福文. 运筹学杂志, 1993, 12(2) :47～55
3 W an Chung ping , Huang Y ang x in. A M ax imum Entr o py A ppr ox imatio n M etho d for Stochastic Par a-me-95, V ol . 2, W or ld Scientif ic ter Pr o gr amming , O pt imization T echniques and A pplicatio ns , ICOT A ’P ress, Sing apor e, 1995, 979～985
4 刘光中. 凸分析与极值问题. 北京:高等教育出版社, 1991
5 夏道行. 突变函数论与泛函分析概要(第二版). 上海:上海科学技术出版社, 19636 W ang J. Jo ur nal o f O ptimizatio n T heor y and A pplicatio ns, 1989, 63(1) :79～897 王金德. 随机规划. 南京:南京大学出版社, 19908 古福文. 成都科技大学学报, 1994, 31:98～102
9 高勇, 陈志平. 带随机过程的随机规划问题的稳定性分析. 中国工业与应用数学学会第三次大会文集.
北京:清华大学出版社, 1994, 222～225
第4期古福文:一类概率约束规划的近似方法及其收敛性 405
THE APPROXIMATION METHOD AND CONVERGENCE FOR
ONE KIND OF PROBABILISTIC CONSTRAINED PROGRAMS
Gu Fuw en
(Departm ent of A pplied M athematics)
Abstract It w as discussed that the approx im ation m ethod of the pro babilistic con-r
strained pr ogram s m in{cx +
∑q E [F -i
i
i =1
A i x ]+ûP (A x ≥F ) ≥p , Bx ≥b }, and the conver-
gence of the approx imation metho d was proved .
Key words stochastic progr am s , probabilistic prog rams , chance constrained pro -gram s, appro ximation method, convergence
(1991MSC90C30)