丁可偉, 馬會(huì)強(qiáng), 劉玲伶

(1. 西南民族大學(xué) 預(yù)科教育學(xué)院, 四川 成都 610041; 2. 西南民族大學(xué) 經(jīng)濟(jì)學(xué)院, 四川 成都 610041; 3. 西南石油大學(xué) 理學(xué)院, 四川 成都 610500)

混合離散分布信息下的全局分布魯棒問題

丁可偉1, 馬會(huì)強(qiáng)2, 劉玲伶3

(1. 西南民族大學(xué) 預(yù)科教育學(xué)院, 四川 成都 610041; 2. 西南民族大學(xué) 經(jīng)濟(jì)學(xué)院, 四川 成都 610041; 3. 西南石油大學(xué) 理學(xué)院, 四川 成都 610500)

針對分布魯棒問題的保守性,利用凸分析中的理論研究了一類混合離散分布信息下的全局分布魯棒問題的等價(jià)形式.當(dāng)只有概率分布是不確定變量時(shí),得到了相應(yīng)全局分布魯棒優(yōu)化問題的易計(jì)算的確定問題;當(dāng)樣本值與概率分布均不確定時(shí),得到其全局分布魯棒優(yōu)化問題的等價(jià)確定形式.

全局魯棒問題; 分布魯棒; 共軛函數(shù); 支撐函數(shù)

1 引言和主要結(jié)果

分布魯棒優(yōu)化是在分布信息不確定時(shí)做出決策的數(shù)學(xué)問題,是隨機(jī)優(yōu)化中的重要分支;其在金融市場,通訊工程及管理科學(xué)中有著廣泛的應(yīng)用.一類常見的分布魯棒優(yōu)化問題為

(1)

其中,X∈Rk是凸集,f(·):Rk→R是凸函數(shù),g(·,·):Rk×Rk→R分別關(guān)于x是凸的對任意的ξ以及關(guān)于ξ是凹的對任意的x,BP是模糊分布信息集合.一般情形下,上述問題是非凸的且不易求解.在一些特殊的分布信息下得到該問題的凸等價(jià)形式或者確定形式,是一種常見的思路.E. Delage等[1]考慮了一類橢球矩分布信息集下的分布魯棒問題,并得到了其等價(jià)的確定凸問題;K. Natarajan等[2]得到區(qū)間矩分布信息下的一類次線性函數(shù)的分布魯棒問題的凸等價(jià)形式;Zhu S.等[3]研究了一類混合分布信息集下的最壞情形下的CVaR模型,并給出了2種離散分布信息集下該模型的等價(jià)形式.用概率分布函數(shù)的散度距離來定義分布信息是另一種常見的思路.Hu Z.等[4]得到了KL散度約束下的分布魯棒問題的等價(jià)確定凸問題,同時(shí)得到了KL散度下的分布魯棒機(jī)會(huì)約束問題的確定機(jī)會(huì)約束形式;任詠紅等[5]基于Hellinger散度約束得到了分布魯棒問題的等價(jià)形式.

另一方面,針對魯棒問題的保守性,A. Ben-tal等[6-7]研究了全局魯棒優(yōu)化問題,對不等式約束的右端項(xiàng)進(jìn)行適當(dāng)?shù)姆糯?得到了更為有效的魯棒解.A. Ben-tal等[8]研究了軟分布魯棒問題,并指出該問題的計(jì)算復(fù)雜度等價(jià)于普通的魯棒問題.受上述研究啟發(fā),本文主要研究混合離散概率分布信息集下的全局分布魯棒優(yōu)化問題,在概率分布不確定及樣本值和概率分布均不確定的情況下分別得到其確定的等價(jià)形式.

定義如下記號(hào):當(dāng)凸函數(shù)f:Rk→(-∞,+∞],且dom(f)={x|f(x)<+∞}≠時(shí)，稱f(·)為正常凸函數(shù);當(dāng)凹函數(shù)g:Rk→[-∞,+∞),且dom(g)={x|g(x)>-∞}≠時(shí),稱g(·)為正常凹函數(shù).任意函數(shù)f(·)的凸共軛函數(shù)定義如下:

任意函數(shù)g(·)的凹共軛函數(shù)定義如下:

對二元函數(shù)f(·,·)而言，f*(·,·)和f*(·,·)表示對第一個(gè)變量求其對應(yīng)共軛函數(shù),f*(·;·)和f*(·;·)表示對所有變量求其對應(yīng)共軛函數(shù).

給定集合S∈Rk,記δ(x|S)為集合S的示性函數(shù)，表示如下:

引理 1(Fenchel對偶定理) 假設(shè)f(x)是Rk上的正常凸函數(shù),g(x)是Rk上的正常凹函數(shù),如果ri(dom(f)∩ri(dom(g)))≠,則有下式成立

2 主要結(jié)論

本文假設(shè)隨機(jī)變量ξ的概率分布函數(shù)屬于如下混合分布信息集

其中pj(·)是第j個(gè)可能的概率分布.文獻(xiàn)[9-10]等在魯棒優(yōu)化及金融問題中均使用到該信息集.由文獻(xiàn)[10]中的引理可知問題(1)在該混合分布信息集下等價(jià)于

s.t. EPi[g(x,ξ)]≤0, i=1,2,…,l.

假設(shè)混合分布信息集中的分布函數(shù)均是離散的,在后面的討論中先令l=1.

2.1 離散概率分布不確定下的全局魯棒優(yōu)化問題首先假定樣本ξ=(ξ1,ξ2,…,ξn)此時(shí)是確定的,其相應(yīng)的離散概率p=(p1,p2,…,pn)T屬于凸集P,是不確定的,得到如下問題:

s.t. pTg(x,ξ)≤0, p∈P,

其中g(shù)(x,ξ)=(g(x,ξ1),g(x,ξ2),…,g(x,ξn))T.對上式不等式條件右邊進(jìn)行放縮，考慮其全局問題

(2)

其中φ(p,p′)關(guān)于(p,p′)是非負(fù)的凸函數(shù),且φ(p,p)=0,P ′是P的凸子集.

(3)

定理 1 全局魯棒優(yōu)化問題(3)可以等價(jià)地轉(zhuǎn)化為如下確定問題

s.t. δ*(g(x,ξ)-θ|P)+φ*(θ;-θ)+δ*(θ|P ′)≤0.

證明 將問題(3)中約束不等式左側(cè)的函數(shù)改寫為

引入變量s、t,則等價(jià)于如下問題:

s.t. p=s, p′=t.

其拉格朗日對偶問題為

由于上述目標(biāo)函數(shù)關(guān)于(s,t,p,p′)是凹的,關(guān)于(λ,θ)是線性的,且P與P ′是凸集,根據(jù)強(qiáng)對偶定理可知,交換極大極小算子,可得如下等價(jià)問題

改寫上述3個(gè)最大子問題,可得:

由此可知

對第2個(gè)子問題有

因此λ=-θ.將θ視為整個(gè)問題的決策變量,可將問題(3)的不等式約束轉(zhuǎn)化為

δ*(g(x,ξ)-θ|P)+
φ*(θ;-θ)+δ*(θ|P ′)≤0.

命題得證.

例 1 討論文獻(xiàn)[10]中的問題min{cTx|(a+Bξ)Tx-β≤0}.假設(shè)ξ服從離散概率分布,P(ξi)=pi，且P={p∈Rn|p≥0,Cp≤d},其中Cp≤d包含不等式eTp≥1與eTp≤1.P ′={p∈Rn|p≥0,Cp≤d,Iφ(p,p0)≤τ},其中

將s、t、v1、v2亦視為決策變量,則該問題可表示為如下凸規(guī)劃問題

v1+v2=θ,s,t,u≥0,i=1,2,…,n,

其中共軛函數(shù)φ*(·)的表達(dá)式見文獻(xiàn)[6]中表4,此處限于篇幅，不再闡述.

s.t. δ*(w|P)+φ*(w+g(x,ξ),p0)≤0.

由于樣本點(diǎn)及概率分布均不確定,考慮如下全局問題:

(4)

(6)

定理 2 全局魯棒優(yōu)化問題(6)可以等價(jià)的轉(zhuǎn)化為如下確定問題:

(7)

s.t.δ*(w0|P)-

F*(w0+λ2;w1+γ1;w2+γ2;…;wn+γn,x)+

ψ*(-μ1;-μ2;…;-μn;μ1;μ2;…;μn)+

yi-γi=-μi,i=1,2,…,n,x∈X.

證明 改寫約束不等式中左側(cè)的函數(shù)

ψ(ξ1,…,ξn,τ1,…,τn))

s.t.s1=p,s2=p′,

引入拉格朗日乘子λ1、λ2、γi、μi,i=1,2,…,n，上述問題的對偶問題為

ψ(ξ1,…,ξn,τ1,…,τn)-

交換2個(gè)算子,得到如下等價(jià)形式

F(p,t1,…,tn,x)}=

F*(w0-λ1;w1+γ1;w2+γ2;…;wn+γn,x).

因此,第一個(gè)最大子問題可等價(jià)于如下問題:

F*(w0-λ1;w1+γ1;…;wn+γn,x).

同理可知,對于第2個(gè)子問題,可得

(-ψ)*(y1-γ1;…;yn-γn;μ1;…;μn)=

ψ*(-μ1;-μ2;…;-μn;μ1;μ2;…;μn)

s.t. yi-γi=-μi, i=1,2,…,n.

由前面的分析可知:

φ*(-λ1;-λ2),

且λ1=-λ2.由此可知,問題(6)中的約束不等式可以等價(jià)的表述為

F*(w0+λ2;w1+γ1;…;wn+γn,x)+

ψ*(-μ1;-μ2;…;-μn;μ1;μ2;…;μn)+

yi-γi=-μi, i=1,2,…,n.

將λ2、γi、μi、w0、wi、yi,i=1,2,…,n等所有中間變量視為問題(3)的決策變量,即可把問題(3)等價(jià)轉(zhuǎn)化為問題(7),命題得證.

例 2 繼續(xù)討論例1中的問題.假設(shè)此時(shí)樣本值亦是不確定的,且Ξ={Ξ∈Rn|‖Ξ-Ξ0‖2≤η1},其中同時(shí)令Ξ′={Ξ′∈Rn|‖Ξ′-Ξ0‖∞≤η2,‖Ξ′-Ξ0‖2≤η3}，且‖可以知道

s.t.w0-CTs≤0,s≥0,

F*(w0+λ2;w1+γ1;w2+γ2;…;wn+γn,x)=

利用拉格朗日對偶可得

F*(w0+λ2;w1+γ1;w2+γ2;…;wn+γn,x)=

s.t.wi+γi=θiBx,i=1,2,…,n.

ψ*(-μ1;-μ2;…;-μn;μ1;μ2;…;μn)=

將θ、s、t、u、v1、v2、λ2、γi、μi、w0、wi、yi亦視為決策變量,其中i=1,2,…,n,再引入中間變量χ1、χ2、χ3,則該問題可表示為如下問題

χ1+χ2+χ3≤0,w0-CTs≤0,v1-CTt≤0,

yi-γi=-μi,s,t,u≥0,i=1,2,…,n.

當(dāng)l>1時(shí),也就是說分布信息集有多個(gè)可能的離散概率分布時(shí),其討論類似于定理1與定理2的討論,限于篇幅此處不再闡述.

[1] DELAGE E, YE Y.Distributionally robust optimization under moment uncertainty with application to data-driven problems[J].Operations Research,2010,58(3):595-612.

[2] NATARAJAN K, SIM M, UICHANCO J. Tractable robust expected utility and risk models for portofolio optimization[J]. Mathematical Finance,2010,20(4):695-731.

[3] ZHU S, FUKUSHIMA M. Worst-case conditional value-at-risk with application to robust portfolio management[J]. Operations Research,2009,57(5):1155-1168.

[4] HU Z, HONG L. Kullback-Leibler divergence constrained distributionally robust optimization[OL]. http://www.optimization-online.org/DB_FILE/2012/11/3677.pdf.

[5] 任詠紅,趙娣,顧鈺,等. 基于Helinger函數(shù)的極小極大分布魯棒優(yōu)化問題的一個(gè)等價(jià)形式[J]. 遼寧師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,39(1):11-14.

[6] BEN-TAL A, BOYD S, NEMIROVSKI A. Extending scope of robust optimization:comprehensive robust counterparts of uncertain problems[J]. Mathematical Programming,2006,B107(1):63-89.

[7] BEN-TAL A, BREKELMANS R, HERTOG D, et al. Globalized robust optimization for nonlinear uncertain inequalities[J]. Center Discussion Paper,2015,2015:031.

[8] BEN-TAL A, BERTSIMAS D, BROWN D. A soft robust model for optimization under ambiguity[J]. Operations Research,2010,58(4):1220-1234.

[9] PEEL D, MCLACHLAN G. Robust mixture modelling using the t distribution[J]. Statistics Computing,2000,10:339-348.

[10] BEN-TAL A, HERTOG D, WAEGENAERE A, et al. Robust solutions of optimization problems affected by uncertain probabilities[J]. Management Science,2013,59(2):341-357.

[11] BERTSIMAS D, BROWN B, CARAMANIS C. Theory and application of robust optimization[J]. SIAM Review,2011,53:464-501.

[12] SHAPIRO A, DENTCHEVA D, RUSZCZYNSKI A. Lecture on Stochastic Programming:Modeling and Theory[M]. Philadelphia: SIAM,2009.

[13] BEN-TAL A, GHAOUI L, NEMIROVSKI A. Robust Optimization[M]. New Jersey:Princeton University Press,2009.

[14] WIESEMANN W, KUHN D, SIM M. Distributionally robust convex optimization[J]. Operations Research,2014,62:1358-1376.

2010 MSC: 49M37; 90C15; 90C26

(編輯 周 俊)

Globalized Distributionally Robust Optimizaiton Problem with Mixture Discrete Distribution Information

DING Kewei1, MA Huiqiang2, LIU Lingling3

(1.DepartmentofFoundationEducation,SouthwestUniversityforNationalities,Chengdu610041,Sichuan; 2.SchoolofEconomics,SouthwestUniversityforNationalities,Chengdu610041,Sichuan; 3.SchoolofSciences,SouthwestPetroleumUniversity,Chengdu610500,Sichuan)

For the conservation of the solution of robust optimization problem, we consider a class of globalized distributionally robust optimization problem under mixture discrete distribution information by the convex analysis. When probability vector is uncertain, we get the explicit and computationally tractable problem for globalized distributionally robust optimization problem. When samples and their probabilities are both uncertain, we present an explicit problem for globalized distributionally robust optimization problem.

globalized robust problem; distributionally robust; conjugate functions; support functions

2017-01-22

四川省教育廳科研基金(16ZB0080)和中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)項(xiàng)目(2014NZYQN49)

丁可偉(1986—),男,講師,主要從事隨機(jī)優(yōu)化的研究,E-mail:bluedkw@163.com

O221

A

1001-8395(2017)03-0334-06

10.3969/j.issn.1001-8395.2017.03.011