分布魯棒最小二乘問題的割平面算法

王 煒, 曹新宇, 何 淼

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院， 遼寧 大連 116029)

分布魯棒最小二乘問題的割平面算法

王 煒, 曹新宇, 何 淼

(遼寧師范大學(xué) 數(shù)學(xué)學(xué)院， 遼寧 大連 116029)

實(shí)際應(yīng)用中很多重要問題可以轉(zhuǎn)化為最小二乘問題.提出一種在一般最小二乘問題中用數(shù)據(jù)的概率不確定性描述的魯棒框架，它的不確定分布集是通過測(cè)度有界的矩約束給出的.此時(shí)，它為一個(gè)凸優(yōu)化問題.當(dāng)樣本空間具有有限支撐時(shí)，可以用割平面算法在有限步求解，而算法可以通過線性規(guī)劃和線性錐規(guī)劃相關(guān)的求解器來(lái)實(shí)現(xiàn).

最小二乘問題；分布魯棒優(yōu)化；矩約束；割平面算法

隨著社會(huì)的進(jìn)步和各種交叉學(xué)科的發(fā)展，優(yōu)化問題在各個(gè)領(lǐng)域中發(fā)揮著重要作用，一般最小二乘問題就是諸多應(yīng)用中的一個(gè)基本問題.而在實(shí)際問題中，參數(shù)的獲取并不是精確的，也會(huì)因?yàn)楦鞣N原因產(chǎn)生隨機(jī)的誤差.引入一個(gè)隨機(jī)變量來(lái)刻畫這種誤差，這個(gè)變量一般服從確定的分布，而這個(gè)分布通常是未知的，一般情況下，只知道它的部分信息.魯棒優(yōu)化[1]就是一類考慮不確定因素的數(shù)學(xué)規(guī)劃問題，是一種能有效地處理含有不確定因素的優(yōu)化方法.考慮不確定性服從某一范圍分布的分布魯棒優(yōu)化問題.這個(gè)不確定分布集合的定義方式有多種，比如橢球不確定集和范數(shù)不確定集，筆者主要研究的分布集合由測(cè)度有界的矩魯棒[2]確定.當(dāng)樣本具有有限支撐時(shí)，可以通過某一種割平面算法[3]在有限步得到問題的解.這個(gè)算法將一般不可解的問題變?yōu)槊坎蕉伎山獾淖訂栴}，這在現(xiàn)實(shí)生活中有重要的意義.

1 預(yù)備知識(shí)

最小二乘問題的一般形式為

其中，X是n中的緊集，A∈m×n和b∈m是已知的.然而，在許多實(shí)際情況中，參數(shù)A和b會(huì)產(chǎn)生隨機(jī)的誤差.例如，當(dāng)數(shù)據(jù)來(lái)源于物理實(shí)驗(yàn)時(shí)，相同的試驗(yàn)中輸出的結(jié)果可能不一樣，另外，由于一些實(shí)際問題如噪聲污染和證券組合等.于是，考慮如下的隨機(jī)最小二乘問題：

其中,p是關(guān)于A和b已知的分布.然而，在實(shí)踐中，沒有足夠的概率分布的信息來(lái)描述這個(gè)分布，一種可能的控制數(shù)據(jù)不確定性的方法是利用魯棒優(yōu)化將A和b控制在一個(gè)確定的范圍內(nèi)來(lái)保證最壞的可能.令Ωρ：=ξA,ξb：‖ξA,ξb‖F(xiàn)≤ρ，于是有了如下極大極小化問題：

令ξ=[vec(ξA);ξb]，則ξ∈m(n+1).由于(P1)沒有考慮Ωρ的概率結(jié)構(gòu)，并且出現(xiàn)最壞情況的可能性很小，內(nèi)部問題過于悲觀，所以用不確定集Ωρ上ξ分布的部分信息定義不確定集，將(P1)變?yōu)橐粋€(gè)分布魯棒隨機(jī)規(guī)劃：

它將保證Ωρ上的最壞情況變?yōu)楸ＷC上的最壞情況，這里不確定集的定義方式有很多種，我們考慮測(cè)度有界的矩魯棒:

(1)

其中，υ1，υ2是在具有Borel-σ代數(shù)的樣本空間Ωρ上定義的兩個(gè)給定測(cè)度，χρ是在(Ωρ，BΩρ)上的所有有限測(cè)度空間.μ，Q分別為ξ的均值和協(xié)方差矩陣.

(2)

則問題(P2)變?yōu)?/p>

2 具體算法

給出求解問題(P0)的方法：

算法

Step 1 解決外極小化問題：

令xt，σt分別為最優(yōu)解和最優(yōu)值.

Step 2 解決內(nèi)極大化問題:

令pt，νt分別為最優(yōu)解和最優(yōu)值.

若νt≤σt，停止.

Step 3 令Pt+1=Pt∪{pt}，t=t+1，返回第一步.

3 收斂性證明

定理令{xt,Pt}是算法產(chǎn)生的序列，則xt收斂到(P0)的最優(yōu)解.

證證明分如下幾步：

(1)因?yàn)棣甆是有限集,協(xié)方差矩陣半正定，矩約束是凸的，所以PN是N中的凸緊集.

(3)

(4)

因?yàn)棣逗蚉N都是緊的，假設(shè)t→∞，(xt,Ρt)→(x*,Ρ*)，由式(3)和文獻(xiàn)[4]中的命題4.4，有

(5)

(6)

由文獻(xiàn)[5]中參數(shù)規(guī)劃的經(jīng)典穩(wěn)定性結(jié)果，有

(7)

對(duì)式(4)取極限，結(jié)合式(5)，式(7)有

(8)

結(jié)合上述等式與式(8)，有

[1] FABOZZI F J, KOLM P N, PACHAMA D, et al. Robust portfolio optimization and management[M].S.l.:John Wiley,2007:291-292.

[2] MEHROTRA S,ZHANG H.Model and algorithms for distributionally robust least squares problems[J].Math Program, Ser A，2014,146(1):123-141.

[3] XU H F,LIU Y C,SUN H L.Distributionally robust optimization with matrix moment constraints:Lagrange duality and cutting plane methods[J].Mathematical Programming,2017:1-41.

[4] BONNANS J F,SHAPIRO A.Perturbation analysis of optimization problems[M].New York:Springer,2000:260-270.

[5] KLATTE D.A note on quantitative stability results in nonlinear optimization[C]∥LOMMATZSCH K.Proceedings 19.Jahrestagung Mathematische Optimierung.Berlin:Humboldt-Universit?t Berlin,Sektion Mathematik,Seminarbericht Nr.90,1987:77-86.

Cuttingplanemethodfordistributionallyrobustleastsquaresproblems

WANGWei,CAOXinyu,HEMiao

(School of Mathematics, Liaoning Normal University, Dalian 116029, China)

Many important problems in the practical application can be converted to the least squares problem.We present the robust framework using probabilitic ambiguity descriptions of the date in least squares problems, the ambiguity distribution set is given by bounds on the probability measure with moments constraints.At this time, it is a convex optimization problem.It can be solved using the cutting plane methodin finite steps when the sample space has finite support.This method can be achieved by the solver which is related to linear programming and linear cone programming.

least squares problem;distributionlly robust optimization;moments constraints;cutting plane method

O224

:A

2017-04-25

國(guó)家自然科學(xué)基金資助項(xiàng)目(11671184)

王煒(1960- )，女，遼寧本溪人，遼寧師范大學(xué)教授，博士.

1000-1735(2017)03-0293-04

10.11679/lsxblk2017030293