一类最小二乘的机会约束问题的凸逼近

丁可伟, 王 磊, 方诗虹

(1. 西南民族大学 预科教育学院, 四川 成都 610041; 2. 西南财经大学 经济数学学院, 四川 成都 610074;3. 西南民族大学 计算机科学与技术学院, 四川 成都 610041)

机会约束规划是由A. Charnes等[1]和L. Miller等[2]于20世纪60年代提出的，是在一定的概率意义下达到最优的理论.它是一种随机规划方法，针对约束条件中含有不确定系数，并且必须在观测到实际值的实现之前做出决策的问题.目前主要讨论如下机会约束问题：

i=1,2,…,m)≥1-,x∈χ.

当m=1时，称上述问题为单个机会约束问题，m>1时为联合机会约束问题.由于机会约束是非凸的，甚至不连通的，在大部分实际情况下，无法获得不确定系数的精确信息，无法获得上述问题的精确解.人们对单个机会约束问题在特定的条件下有了很多的研究成果.在假设模型的不确定系数服从正态分布、指数分布、均匀分布时，问题均可转化为确定性等价类形式，有得到相关的等价定理[3-4].然而在一般情况下，机会约束问题是不可行的，A. Nemirovski等[5]指出求解加权均匀分布的变量为非正仍然为NP-hard问题.

目前处理联合机会约束问题采用的是蒙特卡罗随机模拟方法，用样本点方法逼近机会约束已经有了非常多的理论结果[6-9].蒙特卡罗随机模拟方法有2个优点：一是不需要实际问题中很难获取的分布结构，二是该方法所形成的逼近问题是凸规划问题，易于计算.但蒙特卡罗随机模拟方法的计算规划很大，尤其是对计算精度要求很高时.针对这一问题，S. Zymler等[10]研究了精确矩信息下最坏情况下的机会约束问题，其解集可以由线性矩阵不等式(LMIs)表出，该问题的计算规模比蒙特卡罗方法有了大幅度的下降.

受上述研究启发，本文主要基于不确定系数的一阶二阶矩信息，讨论最坏情况下[11]的最小二乘的机会约束问题:

di(x),i=1,2,…,m)≥1-,x∈χ,

(1)

受上述文章启发，本文主要采用CVaR方法[12-13]对最坏情况下的最小二乘的单个机会约束问题进行逼近，而CVaR方法也是目前已知的该类问题的最紧的凸逼近[14].在得到其解集为LMIs后，再将其转化为一个半正定规划问题，从理论上得到了该问题的近似解.第二部分得到了最小二乘问题的联合机会约束问题的逼近问题.本文亦部分改进了文献[10]中的结果.

引理1[10]L(ζ):Rk→R是一个连续的损失函数且具有如下形式：

(i) 关于ζ是凹的;

(ii) 关于ζ是二次的；

那么有如下关系：

⟺

1 主要结论

1.1 单个机会约束 首先对机会约束中的不等式两边同时平方，那么该机会约束可以改写为

(ζT,1)T≤0.

从计算的角度出发，用下面两个条件来逼近该机会约束问题

∃U(x),u(x),u0(x);

infP(ζTU(x)ζ+2uT(x)ζ+u0(x)≤0)≥1-,

其中U(x),u(x)的每个元素都是关于x的仿射函数，u0(x)是x的仿射函数，这样由U(x),u(x),u0(x)形成的不等式是一个典型的关于x的线性矩阵.

由R. T. Rockafellar等[12]推广的CVaR方法是目前已知的对机会约束问题最紧的凸逼近，利用引理1，可以得到最小二乘的单个机会约束问题的如下逼近：

2uT(x)ζ+u0(x))≤0,

其中

现在来证明对于某些确定的x上述最坏情况下的CVaR值是可计算的.考虑上述最坏情况下的期望问题(等式中的sup问题)

根据随机变量的已知信息，可以得到如下模型：

2uT(x)ζ+u0(x)-β)μ(dζ),

s.t.y0∈R,y∈Rk,Y∈,

y0+yTζ+〈Y,ζζT〉≥0,

y0+yTζ+〈Y,ζζT〉≥

ζTU(x)ζ+2uT(x)ζ+u0(x)-β.

∀ζ∈Rk.

根据ζ∈Rk可得

s.t.M0.

由于上述模型中的约束条件为线性矩阵不等式(LMIs)，大部分实际情况下会形成有效的凸紧集，将inf改为min.那么将原问题转化为如下形式：

M0,

受R. T. Rockafellar等[13]的结论所启发，得到如下结论.

定理1问题2可写成如下等价形式:

M0,

证明验证两个模型有相同的最优解和最优解集即可.假设(x*,β*,M*)与(x0,β0,M0)分别是问题(P)与问题(FP)的一组最优解.由于

两个模型剩下约束都是一样，发现(x*，β*,M*)是问题(FP)的一组可行解.

另一方面，

(x0,β0,M0)是问题(P)的一组可行解.

观察到双方的最优解互为对方的可行解.假设cTx*cTx0与(x*,β*,M*)是问题(P)的一组最优解相矛盾.因此，得到cTx*=cTx0.定理证毕.

问题(FP)的形式有利于在计算方面的实现，当χ是凸紧集且U(x),u(x)与u0(x)已知时，问题(FP)是凸规划问题，就可以求到了最小二乘的机会约束问题的一个逼近解.相对于线性规划问题的机会约束问题，上述问题明显的一个关键问题就是如何得到U(x),u(x)与u0(x)，而且U(x),u(x)与u0(x)的“好坏”直接影响到逼近解.

例1考虑如下最小二乘的机会约束：

其中χ={(x1,x2)|0≤x1,x2≤1}将上述机会约束改写为文章的标准形式:

1.2 联合机会约束问题 处理联合机会约束问题一种较为常见的方法是Bonferroni逼近方法，对于任意的安全因子向量i,i≥0，用如下m个单个机会约束去逼近联合机会约束:

这种方法过于保守，逼近程度不是非常理想.实际上，可以采用上节的方法用m个线性矩阵对该m个约束进行逼近，

i=1,2,…,m)≥1-,

由于方法的特殊性，上面第一个约束有如下逼近：

这样联合机会约束问题可以用一个单个机会约束来逼近，采用上节类似的分析，可以用最坏情况下的CVaR方法去逼近联合机会约束问题，并转化为凸规划问题，从而得到它的近似解.

定理2当m>1时，问题1可用如下凸规划来逼近:

M0,

x∈χ,i=1,2,…,m.

[1] Charnes A, Cooper W, Symonds G. Cost horizons and certainty equivalents: an approach to stochastic progrmming of heating oil[J]. Managements Sci,1958,4(3):235-263.

[2] Miller L, Wagnet H. Chance-constrained programming with joint constraints[J]. Oper Res,1965,13(6):930-945.

[3] Alizadeh F, Goldfarb D. Second-order cone programming[J]. Math Program,2003,A95(1):3-51.

[4] Calafiore G, Ghaoui L. Distributionally robust chance-constrained linear programms with applications[J]. J Optim Theory Appl,2006,130(1):1-22.

[5] Nemirovski A, Shapiro A. Convex approximation of chance constrained programms[J]. SIAM J Optim,2006,17(4):969-996.

[6] Calafiore G, Campi M C. Uncertain convex programming: randomized solutions and confidence levels[J]. Math Program,2005,A102(1):25-46.

[7] Calafiore G, Campi M C. The scenario approach to robust control design[J]. IEEE Trans Automatic Control,2006,51(5):742-753.

[8] Ergodan G, Iyengar G. Ambiguous chance constrained problems and robust optimization[J]. Math Program,2006,B107(1):37-64.

[9] Luedtke J, Ahmed S. A sampling approximation approach for optimization with probabilistic constraints[J]. SIAM J Optim,2008,19(2):674-699.

[10] Zymler S, Kuhn D, Rustem B. Distributionally robust joint chance constraints with second-order moment information[J]. Math Progam,2013,A137:167-198.

[11] Bertsimas D, Brown D B, Caramanis C. Theory and application of robust optimization[J]. SIAM Rev,2011,53(3):464-501.

[12] Rockafellar R T, Uryasev S. Optimization of conditional value-at-risk[J]. J Risk,2000,2:21-41.

[13] Rockafellar R T, Uryasev S. Conditional value-at-risk for general loss distributions[J]. J Banking Finance,2002,26:1443-1471.

[14] Chen W, Sim M, Sun J, et al. From CVaR to uncertainy set: Implicaions in joint chance constrained optimization[J]. Oper Res,2010,55(6):470-485.

[15] Shapiro A, Kleywegt A J. Minimax analysis of stochastic problems[J]. Optim Methods Software,2002,17:523-542.