兩階段隨機線性優化問題的等價形式

王 煒，李忠偉，王丹丹

（遼寧師范大學 數學學院，遼寧 大連 116029）

隨機規劃是一類含有隨機因素的數學規劃問題。在數學規劃問題的模型中引入隨機變量，能夠使模型更加符合實際情況，從而使決策更加合理。極小極大隨機線性優化問題是由?á?ková[1]率先提出的。求解極小極大隨機優化問題的算法包括樣本均值近似法[2]、基于梯度法[3]、切平面算法[4]和橢球算法[5]等。本研究在概率分布集合由一階矩和二階矩刻畫時，將兩階段極小極大隨機線性優化問題轉化為為半定優化問題。

面對各項系數都含有隨機變量的規劃問題時，往往需要在觀察到隨機變量的實現之前作出決策，會導致某些決策不滿足約束條件。此時，通常需要建立和引入二階段有補償的問題模型，既可以使決策滿足約束條件，又可以使損失懲罰達到最小。本研究擬引入帶有固定補償的極小極大兩階段隨機線性優化問題模型[6]解決含有隨機變量的數學規劃問題，如式（1）所示。

其中，

x為一階段決策變量，二階段決策變量w取自集合X(x) ={x ∈Rn:Ww= h - Tx,w ≥0}，W為補償矩陣，T為影響隨機變量ξ的一個參數矩陣，h為常量。P為隨機參數ξ的概率分布，在實際應用中一般不能精確地求得，所以通常用概率分布集合P上第二階段期望成本的最大值來處理概率分布的不確定性。

為了使模型更接近實際，從而得到更加可靠的數值解，通常將風險考慮到模型中。風險建模的方法是在二階段成本中采用一個效用函數U(·)，如式（2）所示。

其中，效用函數U(Q(x,ξ))為置信水平為ε的最壞情況下的條件風險值

因此，式（2）即為本文要研究的兩階段隨機線性優化問題的目標函數。

設μ ∈Rk是均值，Σ ∈Sk是協方差矩陣（Sk為k 維對稱矩陣的集合），為了保證二階期望成本EP[U(Q(x,ξ))]有定義，假設μ,Σ是有限的，且Σ ?0，則由一階矩和二階矩描述的所有概率分布構成的集合可表示為

A ?0 表示A 是正定矩陣，A-?0 表示A 是半正定的。同理，A ?0 表示A 是負定矩陣，A-?0 表示A 是負半定的。

1 目標函數的內部極大化

考慮式（2）的內部極大化問題

假設該優化問題的概率分布P對應的測度為F，則式（3）就等價為

引入Lagrange乘子ζ ∈R,η ∈Rk,G ∈Sk，則式（4）的Lagrange函數為

其中，矩陣A,B的內積定義為A,B = tr(ATB)，tr(· )表示矩陣的跡。由強對偶定理[7]可知

因此，式（4）的對偶問題為

2 效用函數的等價形式

由條件風險值的定義

可得

引入Lagrange乘子y0∈R,y ∈Rk,Y ∈Sk，則式（7）中的極大值函數

可得式（8）的對偶問題為

式（10）中的約束可以寫成兩個等價的約束

3 結論

將式（14）代入式（6）的約束[ξT1]H[ξT1]T≥U(Q(x,ξ))中，可得

即

上式又等價為

即

因此

綜上所述，問題（2）最終可以轉化為

把Ω、H、M帶入問題（15）中得半定規劃問題