混合离散分布信息下的全局分布鲁棒问题

丁可伟, 马会强, 刘玲伶

(1. 西南民族大学 预科教育学院, 四川 成都 610041; 2. 西南民族大学 经济学院, 四川 成都 610041; 3. 西南石油大学 理学院, 四川 成都 610500)

混合离散分布信息下的全局分布鲁棒问题

丁可伟1, 马会强2, 刘玲伶3

(1. 西南民族大学 预科教育学院, 四川 成都 610041; 2. 西南民族大学 经济学院, 四川 成都 610041; 3. 西南石油大学 理学院, 四川 成都 610500)

针对分布鲁棒问题的保守性,利用凸分析中的理论研究了一类混合离散分布信息下的全局分布鲁棒问题的等价形式.当只有概率分布是不确定变量时,得到了相应全局分布鲁棒优化问题的易计算的确定问题;当样本值与概率分布均不确定时,得到其全局分布鲁棒优化问题的等价确定形式.

全局鲁棒问题; 分布鲁棒; 共轭函数; 支撑函数

1 引言和主要结果

分布鲁棒优化是在分布信息不确定时做出决策的数学问题,是随机优化中的重要分支;其在金融市场,通讯工程及管理科学中有着广泛的应用.一类常见的分布鲁棒优化问题为

(1)

其中,X∈Rk是凸集,f(·):Rk→R是凸函数,g(·,·):Rk×Rk→R分别关于x是凸的对任意的ξ以及关于ξ是凹的对任意的x,BP是模糊分布信息集合.一般情形下,上述问题是非凸的且不易求解.在一些特殊的分布信息下得到该问题的凸等价形式或者确定形式,是一种常见的思路.E. Delage等[1]考虑了一类椭球矩分布信息集下的分布鲁棒问题,并得到了其等价的确定凸问题;K. Natarajan等[2]得到区间矩分布信息下的一类次线性函数的分布鲁棒问题的凸等价形式;Zhu S.等[3]研究了一类混合分布信息集下的最坏情形下的CVaR模型,并给出了2种离散分布信息集下该模型的等价形式.用概率分布函数的散度距离来定义分布信息是另一种常见的思路.Hu Z.等[4]得到了KL散度约束下的分布鲁棒问题的等价确定凸问题,同时得到了KL散度下的分布鲁棒机会约束问题的确定机会约束形式;任咏红等[5]基于Hellinger散度约束得到了分布鲁棒问题的等价形式.

另一方面,针对鲁棒问题的保守性,A. Ben-tal等[6-7]研究了全局鲁棒优化问题,对不等式约束的右端项进行适当的放大,得到了更为有效的鲁棒解.A. Ben-tal等[8]研究了软分布鲁棒问题,并指出该问题的计算复杂度等价于普通的鲁棒问题.受上述研究启发,本文主要研究混合离散概率分布信息集下的全局分布鲁棒优化问题,在概率分布不确定及样本值和概率分布均不确定的情况下分别得到其确定的等价形式.

定义如下记号:当凸函数f:Rk→(-∞,+∞],且dom(f)={x|f(x)<+∞}≠时，称f(·)为正常凸函数;当凹函数g:Rk→[-∞,+∞),且dom(g)={x|g(x)>-∞}≠时,称g(·)为正常凹函数.任意函数f(·)的凸共轭函数定义如下:

任意函数g(·)的凹共轭函数定义如下:

对二元函数f(·,·)而言，f*(·,·)和f*(·,·)表示对第一个变量求其对应共轭函数,f*(·;·)和f*(·;·)表示对所有变量求其对应共轭函数.

给定集合S∈Rk,记δ(x|S)为集合S的示性函数，表示如下:

引理 1(Fenchel对偶定理) 假设f(x)是Rk上的正常凸函数,g(x)是Rk上的正常凹函数,如果ri(dom(f)∩ri(dom(g)))≠,则有下式成立

2 主要结论

本文假设随机变量ξ的概率分布函数属于如下混合分布信息集

其中pj(·)是第j个可能的概率分布.文献[9-10]等在鲁棒优化及金融问题中均使用到该信息集.由文献[10]中的引理可知问题(1)在该混合分布信息集下等价于

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

假设混合分布信息集中的分布函数均是离散的,在后面的讨论中先令l=1.

2.1 离散概率分布不确定下的全局鲁棒优化问题首先假定样本ξ=(ξ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′)是非负的凸函数,且φ(p,p)=0,P ′是P的凸子集.

(3)

定理 1 全局鲁棒优化问题(3)可以等价地转化为如下确定问题

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

证明 将问题(3)中约束不等式左侧的函数改写为

引入变量s、t,则等价于如下问题:

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

其拉格朗日对偶问题为

由于上述目标函数关于(s,t,p,p′)是凹的,关于(λ,θ)是线性的,且P与P ′是凸集,根据强对偶定理可知,交换极大极小算子,可得如下等价问题

改写上述3个最大子问题,可得:

由此可知

对第2个子问题有

因此λ=-θ.将θ视为整个问题的决策变量,可将问题(3)的不等式约束转化为

δ*(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亦视为决策变量,则该问题可表示为如下凸规划问题

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

其中共轭函数φ*(·)的表达式见文献[6]中表4,此处限于篇幅，不再阐述.

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

由于样本点及概率分布均不确定,考虑如下全局问题:

(4)

(6)

定理 2 全局鲁棒优化问题(6)可以等价的转化为如下确定问题:

(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.

证明 改写约束不等式中左侧的函数

ψ(ξ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)等价转化为问题(7),命题得证.

例 2 继续讨论例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函数的极小极大分布鲁棒优化问题的一个等价形式[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)和中央高校基本科研业务费专项项目(2014NZYQN49)

丁可伟(1986—),男,讲师,主要从事随机优化的研究,E-mail:bluedkw@163.com

O221

A

1001-8395(2017)03-0334-06

10.3969/j.issn.1001-8395.2017.03.011