一類最小二乘的機會約束問題的凸逼近

丁可偉, 王 磊, 方詩虹

(1. 西南民族大學 預科教育學院, 四川 成都 610041; 2. 西南財經大學 經濟數學學院, 四川 成都 610074;3. 西南民族大學 計算機科學與技術學院, 四川 成都 610041)

機會約束規劃是由A. Charnes等[1]和L. Miller等[2]于20世紀60年代提出的，是在一定的概率意義下達到最優的理論.它是一種隨機規劃方法，針對約束條件中含有不確定系數，并且必須在觀測到實際值的實現之前做出決策的問題.目前主要討論如下機會約束問題：

i=1,2,…,m)≥1-,x∈χ.

當m=1時，稱上述問題為單個機會約束問題，m>1時為聯合機會約束問題.由于機會約束是非凸的，甚至不連通的，在大部分實際情況下，無法獲得不確定系數的精確信息，無法獲得上述問題的精確解.人們對單個機會約束問題在特定的條件下有了很多的研究成果.在假設模型的不確定系數服從正態分布、指數分布、均勻分布時，問題均可轉化為確定性等價類形式，有得到相關的等價定理[3-4].然而在一般情況下，機會約束問題是不可行的，A. Nemirovski等[5]指出求解加權均勻分布的變量為非正仍然為NP-hard問題.

目前處理聯合機會約束問題采用的是蒙特卡羅隨機模擬方法，用樣本點方法逼近機會約束已經有了非常多的理論結果[6-9].蒙特卡羅隨機模擬方法有2個優點：一是不需要實際問題中很難獲取的分布結構，二是該方法所形成的逼近問題是凸規劃問題，易于計算.但蒙特卡羅隨機模擬方法的計算規劃很大，尤其是對計算精度要求很高時.針對這一問題，S. Zymler等[10]研究了精確矩信息下最壞情況下的機會約束問題，其解集可以由線性矩陣不等式(LMIs)表出，該問題的計算規模比蒙特卡羅方法有了大幅度的下降.

受上述研究啟發，本文主要基于不確定系數的一階二階矩信息，討論最壞情況下[11]的最小二乘的機會約束問題:

di(x),i=1,2,…,m)≥1-,x∈χ,

(1)

受上述文章啟發，本文主要采用CVaR方法[12-13]對最壞情況下的最小二乘的單個機會約束問題進行逼近，而CVaR方法也是目前已知的該類問題的最緊的凸逼近[14].在得到其解集為LMIs后，再將其轉化為一個半正定規劃問題，從理論上得到了該問題的近似解.第二部分得到了最小二乘問題的聯合機會約束問題的逼近問題.本文亦部分改進了文獻[10]中的結果.

引理1[10]L(ζ):Rk→R是一個連續的損失函數且具有如下形式：

(i) 關于ζ是凹的;

(ii) 關于ζ是二次的；

那么有如下關系：

?

1 主要結論

1.1 單個機會約束 首先對機會約束中的不等式兩邊同時平方，那么該機會約束可以改寫為

(ζT,1)T≤0.

從計算的角度出發，用下面兩個條件來逼近該機會約束問題

?U(x),u(x),u0(x);

infP(ζTU(x)ζ+2uT(x)ζ+u0(x)≤0)≥1-,

其中U(x),u(x)的每個元素都是關于x的仿射函數，u0(x)是x的仿射函數，這樣由U(x),u(x),u0(x)形成的不等式是一個典型的關于x的線性矩陣.

由R. T. Rockafellar等[12]推廣的CVaR方法是目前已知的對機會約束問題最緊的凸逼近，利用引理1，可以得到最小二乘的單個機會約束問題的如下逼近：

2uT(x)ζ+u0(x))≤0,

其中

現在來證明對于某些確定的x上述最壞情況下的CVaR值是可計算的.考慮上述最壞情況下的期望問題(等式中的sup問題)

根據隨機變量的已知信息，可以得到如下模型：

2uT(x)ζ+u0(x)-β)μ(dζ),

s.t.y0∈R,y∈Rk,Y∈,

y0+yTζ+〈Y,ζζT〉≥0,

y0+yTζ+〈Y,ζζT〉≥

ζTU(x)ζ+2uT(x)ζ+u0(x)-β.

?ζ∈Rk.

根據ζ∈Rk可得

s.t.M0.

由于上述模型中的約束條件為線性矩陣不等式(LMIs)，大部分實際情況下會形成有效的凸緊集，將inf改為min.那么將原問題轉化為如下形式：

M0,

受R. T. Rockafellar等[13]的結論所啟發，得到如下結論.

定理1問題2可寫成如下等價形式:

M0,

證明驗證兩個模型有相同的最優解和最優解集即可.假設(x*,β*,M*)與(x0,β0,M0)分別是問題(P)與問題(FP)的一組最優解.由于

兩個模型剩下約束都是一樣，發現(x*，β*,M*)是問題(FP)的一組可行解.

另一方面，

(x0,β0,M0)是問題(P)的一組可行解.

觀察到雙方的最優解互為對方的可行解.假設cTx*cTx0與(x*,β*,M*)是問題(P)的一組最優解相矛盾.因此，得到cTx*=cTx0.定理證畢.

問題(FP)的形式有利于在計算方面的實現，當χ是凸緊集且U(x),u(x)與u0(x)已知時，問題(FP)是凸規劃問題，就可以求到了最小二乘的機會約束問題的一個逼近解.相對于線性規劃問題的機會約束問題，上述問題明顯的一個關鍵問題就是如何得到U(x),u(x)與u0(x)，而且U(x),u(x)與u0(x)的“好壞”直接影響到逼近解.

例1考慮如下最小二乘的機會約束：

其中χ={(x1,x2)|0≤x1,x2≤1}將上述機會約束改寫為文章的標準形式:

1.2 聯合機會約束問題 處理聯合機會約束問題一種較為常見的方法是Bonferroni逼近方法，對于任意的安全因子向量i,i≥0，用如下m個單個機會約束去逼近聯合機會約束:

這種方法過于保守，逼近程度不是非常理想.實際上，可以采用上節的方法用m個線性矩陣對該m個約束進行逼近，

i=1,2,…,m)≥1-,

由于方法的特殊性，上面第一個約束有如下逼近：

這樣聯合機會約束問題可以用一個單個機會約束來逼近，采用上節類似的分析，可以用最壞情況下的CVaR方法去逼近聯合機會約束問題，并轉化為凸規劃問題，從而得到它的近似解.

定理2當m>1時，問題1可用如下凸規劃來逼近:

M0,

x∈χ,i=1,2,…,m.

[1] Charnes A, Cooper W, Symonds G. Cost horizons and certainty equivalents: an approach to stochastic progrmming of heating oil[J]. Managements Sci,1958,4(3):235-263.

[2] Miller L, Wagnet H. Chance-constrained programming with joint constraints[J]. Oper Res,1965,13(6):930-945.

[3] Alizadeh F, Goldfarb D. Second-order cone programming[J]. Math Program,2003,A95(1):3-51.

[4] Calafiore G, Ghaoui L. Distributionally robust chance-constrained linear programms with applications[J]. J Optim Theory Appl,2006,130(1):1-22.

[5] Nemirovski A, Shapiro A. Convex approximation of chance constrained programms[J]. SIAM J Optim,2006,17(4):969-996.

[6] Calafiore G, Campi M C. Uncertain convex programming: randomized solutions and confidence levels[J]. Math Program,2005,A102(1):25-46.

[7] Calafiore G, Campi M C. The scenario approach to robust control design[J]. IEEE Trans Automatic Control,2006,51(5):742-753.

[8] Ergodan G, Iyengar G. Ambiguous chance constrained problems and robust optimization[J]. Math Program,2006,B107(1):37-64.

[9] Luedtke J, Ahmed S. A sampling approximation approach for optimization with probabilistic constraints[J]. SIAM J Optim,2008,19(2):674-699.

[10] Zymler S, Kuhn D, Rustem B. Distributionally robust joint chance constraints with second-order moment information[J]. Math Progam,2013,A137:167-198.

[11] Bertsimas D, Brown D B, Caramanis C. Theory and application of robust optimization[J]. SIAM Rev,2011,53(3):464-501.

[12] Rockafellar R T, Uryasev S. Optimization of conditional value-at-risk[J]. J Risk,2000,2:21-41.

[13] Rockafellar R T, Uryasev S. Conditional value-at-risk for general loss distributions[J]. J Banking Finance,2002,26:1443-1471.

[14] Chen W, Sim M, Sun J, et al. From CVaR to uncertainy set: Implicaions in joint chance constrained optimization[J]. Oper Res,2010,55(6):470-485.

[15] Shapiro A, Kleywegt A J. Minimax analysis of stochastic problems[J]. Optim Methods Software,2002,17:523-542.