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

王 煒, 曹新宇, 何 淼

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

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

王 煒, 曹新宇, 何 淼

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

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

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

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

1 預備知識

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

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

其中,p是關(guān)于A和b已知的分布.然而，在實踐中，沒有足夠的概率分布的信息來描述這個分布，一種可能的控制數(shù)據(jù)不確定性的方法是利用魯棒優(yōu)化將A和b控制在一個確定的范圍內(nè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)橐粋€分布魯棒隨機規(guī)劃：

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

(1)

其中，υ1，υ2是在具有Borel-σ代數(shù)的樣本空間Ωρ上定義的兩個給定測度，χρ是在(Ωρ，BΩρ)上的所有有限測度空間.μ，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)因為ΞN是有限集,協(xié)方差矩陣半正定，矩約束是凸的，所以PN是N中的凸緊集.

(3)

(4)

因為Χ和PN都是緊的，假設(shè)t→∞，(xt,Ρt)→(x*,Ρ*)，由式(3)和文獻[4]中的命題4.4，有

(5)

(6)

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

(7)

對式(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

國家自然科學基金資助項目(11671184)

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

1000-1735(2017)03-0293-04

10.11679/lsxblk2017030293