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

丁可偉, 馬會強, 劉玲伶

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

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

丁可偉1, 馬會強2, 劉玲伶3

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

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

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

1 引言和主要結果

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

(1)

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

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

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

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

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

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

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

2 主要結論

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

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

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

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

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

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

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

(2)

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

(3)

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

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

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

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

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

其拉格朗日對偶問題為

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

改寫上述3個最大子問題,可得:

由此可知

對第2個子問題有

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

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

命題得證.

例 1 討論文獻[10]中的問題min{cTx|(a+Bξ)Tx-β≤0}.假設ξ服從離散概率分布,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ù)φ*(·)的表達式見文獻[6]中表4,此處限于篇幅，不再闡述.

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

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

(4)

(6)

定理 2 全局魯棒優(yōu)化問題(6)可以等價的轉(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.

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

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

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

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

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

交換2個算子,得到如下等價形式

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

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

因此,第一個最大子問題可等價于如下問題:

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

同理可知,對于第2個子問題,可得

(-ψ)*(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)中的約束不等式可以等價的表述為

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)等價轉(zhuǎn)化為問題(7),命題得證.

例 2 繼續(xù)討論例1中的問題.假設此時樣本值亦是不確定的,且Ξ={Ξ∈Rn|‖Ξ-Ξ0‖2≤η1},其中同時令Ξ′={Ξ′∈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.

當l>1時,也就是說分布信息集有多個可能的離散概率分布時,其討論類似于定理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)化問題的一個等價形式[J]. 遼寧師范大學學報(自然科學版),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)和中央高?；究蒲袠I(yè)務費專項項目(2014NZYQN49)

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

O221

A

1001-8395(2017)03-0334-06

10.3969/j.issn.1001-8395.2017.03.011