半无限凸规划的割面算法 矩鲁棒优化的应用

因此，将这些方法的收敛速度与可行方法的收敛速度进行比较，在每次迭代中更新最佳可行解决方案，5将中心切割曲面算法应用于momentrobust优化本节的目的是证明，只要集合x是凸有界的，P是由（3）定义的，算法1与随机列生成法结合，通过P的某些（不一定是多项式的）Momentsr@fi(ζ）P(dζ）上的下界(`i,ui),可用于求解在x(foreurer∑∑)中凸的每一个目标h的(DRO)。Boundscan被施加在任意阶矩上，而不仅仅是施加在第一阶矩和第二阶矩上。Therandomized列生成方法，第5.2节提出，是作者早期随机规划情景生成算法（Mehrotra和Papp,我们也可以考虑具有鲁棒随机约束的优化问题，即具有凸函数G的formep[g(x)]≤0±p∈P的约束。本节给出的算法完全适用于这类问题，但为了保持表示简单，我们只考虑更简单的形式(DRO)。然而，我们给出了我们的方法应用于鲁棒随机约束的一个数值例子示例4。在不丧失一般性的情况下，我们将假定f1是常数函数，`=u=1。我们还将使用向量值函数(f，)的简称f。我们的观察是，在（2）中寻找ε-最优P时，必须考虑有充分支持的分布。定理9。当ε>0时，优化问题（2）的ε-最优分布支持点不超过N+2点。对于每一个z∈R，setlz=(v,w)∈Rn×RP:v=zf(ζ）P(dζ）,w=zh(x,ζ）P(dζ）,`≤v≤u,w≥z是包含在{(f(ζ,....,fN(ζ,h,x,ζ）tζ,}的凸壳中的(N+1)维凸集。因此，根据Carath\'Eodory定理，只要存在一个(v,w)∈Lz,也存在N+2个点ζ。..,ζn+2in.和非负权w,。..,wn+2satisfyingv=N+2xk=1wkf(ζk）和w=N+2xk=1wkh(x,ζk）。（Mehrotra and Papp,2013）的一个结果是，当分布集合P满足（3）时，使用随机抽样列的列生成算法可以用来定义最多支持在N个点上的分布P∈P。换句话说，使用随机列生成算法可以找到（2）的可行解。在第5.2节中，我们推广了这一结果，表明（2）也可以用随机列生成法在规定的ε>0精度内解到最优值。算法2给出了完整算法的形式化描述。在本节的其余部分，我们给出了一个简短的非形式化描述和正确性的证明。如果我们的优化问题（2）是一个线性规划，它的决策变量是分布P赋予每个点ζi∈⑵的权值。类似地，(2)在一般情况下，可以写成一个以权函数w:7→r+为变量的半线性规划问题。对于（2）的解，相应的列生成算法如下：我们从一个支持一个可行解的候选场景集{ζ,...,ζk}开始，这样的点可以用（Mehrotra and Papp,2013）中的算法1得到。在每次迭代时，我们取当前的候选场景集并求解辅助线性编程maxw∈rk(kxk=1wkh(x,ζk)`≤kxk=1wkf(ζk)≤u,w≥0)(12)及其对偶问题min(p+,p-)∈r2npt+u-pt-`(p+-p-)Tf(ζk)≥h(x,ζk)(k=)1,...,k）；p+≥0，p-≥0。

（13）注意，通过构造初始节点集，原问题总是可行的，并且由于原问题也是有界的，所以原最优解和对偶最优解都是存在的，设W和(p+，p-)是得到的原最优解和对偶最优解；apointζ的约化代价为π(ζ）def=h(x,ζ）-(P+-P-)Tf(ζ）。（14）对于每一个（或半）线性规划，如果每一个ζ存在π(ζ）≤0，则当前的原对偶是最优的，即对应于点ζ和权值wks的离散概率分布是（2）的最优解。此外，对于问题(2)，我们有以下更强的事实：定理10。让ζ。如上，设ε≥0。如果π(ζ）≤ε，则由支持点ζ构成的分布。..,ζKand加权w，.WKI是问题（2）的ε-最优可行解。证明。根据辅助线性程序（12）的认识，只需要证明ε-最优性。如果不等式π(ζ）≤ε对于每一个ζ存在，则通过积分，我们对于每一个概率分布P也得到了z(P+-p-)Tf(ζ）P(dζ≥z(h(x,ζ）-ε)P(dζ=zh(x,ζ）P(dζ-ε(15)。特别地，考虑了一个最优解P*to(2),其中M*def=rζ∈f(ζ）P*(dζ。自然地，`≤m＇≤u，因此我们得到了Kxk=1wkh(x,ζk)=pt+u-pt-`≥(p+-p-)tm＇==z(p+-p-)Tf(ζ）p＇(dζ)≥zh(x,ζ）p＇(dζ-ε，在第一步使用强对偶对(12)-(13),在第二步使用强对偶对，`≤m＇≤u和对偶变量的符号约束，在最后一步使用不等式（15）。5.1用多项式优化法生成列如果我们可以用正的降低代价来构造一个ζ，我们可以把它作为ζk+1加到候选支持集上，然后递归。不幸的是，即使在参数为[0,1]d,常数为零，且最多为二次的单项式的情况下，求最大约化代价的ζ点，甚至判定是否存在正约化代价的ζ是NP困难的；这是由单位立方体上的二次优化的nphropertial得到的，唯一的非平凡特例是多项式时间可解的，其中π是二次多项式，μ是椭球。然后，将maxζ∈ππ(ζ）等价于非线性规划的信赖域子问题。在其他情况下，原则上可以使用多项式优化的平方和逼近，这导致了可处理的半有限规划松弛(Parrilo，2003)。（Mehrotra and Papp，2013,Secs.4-5）在矩匹配场景生成的上下文中总结了GloptiPoly（Henrion and Lasserre，2003)和SparsePOP（Wakiet al.，2006)两个现有实现的经验，其中类似于本文提出的列生成方法导致定价问题，这些问题是在解决时获得的问题(DRO)的特殊情况。在这些问题中，用半有限元规划方法可以得到的最大问题是涉及矩达5阶的三维问题。为了在多项式时间内找出π(ζ）>0的点ζ（或证明这类点不存在），不需要求π的全局极大值；有一个具有正逼近比的多项式时间逼近算法是非常必要的。然而，在这个方向上已知的唯一适用的肯定的结果是，当μ是单纯形时，对于每一次都存在一个多项式时间逼近方案(PTAS)（de Klerk et al.，2006)。另外，在低维情况下，（de Loera et al.，2008)中的完全多项式时间的近似方案可能是有用的。当（de Loera et al.）是单位立方体，π是2次多线性多项式时，除非N P=ZP P，否则没有适用的近似算法。

当球面为单位球面，π为3次多线性多项式时，除非P=NP，否则没有适用的近似算法。关于这些结果的简单证明，见调查（de Klerk，2008)；对于大量其他情况下最著名的近似算法，我们参考最近的博士论文(Li，2011)。总之，现有的多项式优化工具在解决我们的列生成子问题时似乎并不有用。在下一小节中，我们提出了一种替代的、实用的方法，它也适用于非多项式的设置。5.2随机化列生成现在我们证明了使用随机抽样可以以很高的概率找到具有负降低代价的列。该结果不需要目标函数为多项式的基函数。随机化列生成方法（算法2）在第一阶段使用(Mehrotra and Papp,2013）中的方法来生成初始（可行，但不一定是最优的）情景集和概率。关键观察是，如果函数h(x,·)和fiare在有界的ζ上连续可扩展，则降成本函数（14）（作为ζ的函数）也具有有界导数。因此，如果有许多独立的均匀随机样本ζjε，导致π(ζj)≤0，将有助于我们以高概率得出每个ζ的π(ζ）≤ε。在下面的定理中(c，r)表示以c为中心半径为r的（欧几里得，d维）球。定理11。假定函数h(x，·)和fiare在闭有界的参数态态上连续可扩展，并设C为降成本函数梯度上的一个上界:maxζ此外，假设一个特定的~ζ∈satisofysπ(~ζ）>ε。然后，一致随机选择的ζ∈satisπ(ζ）≤0，概率至多为1-p，其中Ep=minζ∈vol(B(ζ,ε/c))/vol()>0。特别地，如果Rdis是一个凸集，满足B(c，r)B(c，r)且中心为c，半径为r和r的凸集，我们得到了p>(2π(d+2))-1/2rε2RC d.证明。如果π(～ζ）>ε，则在其邻域内的每一ζ处，π(ζ）>0。因此，该断言在p(ε，C)=minζ的情况下成立。这个最小值是存在的，因为态态是封闭和有界的；它是正的，因为交点对每个中心ζ是一个非空闭凸集。为了得到p上的下界，我们需要从交点的体积下界开到交点的体积下，即交点的体积下界，即交点的体积下界，即交点的体积下界，即交点的体积下界，即交点的体积下界，交点的体积下界，交点的体积下界。考虑一个以ζ为顶点的右圆锥，它的底是B（c,r）和与连接candζ的直线正交的超平面的(d-1）维交点。这个锥包含在ζ内，并且它的所有点都在离ζ2r或更小的距离上。以ε/(2rc)的比值使该锥面相对于圆心ζ收缩，得到包含在πB(ζ,ε/c)中的锥面。用这个锥体的体积作为vol(B(ζ）的下界，ε/c)和半径为r的d维球演化的符号Vd(r),我们得到了vol(Ⅵ)B(ζ,ε/c))vol(Ⅵ)≥(d+1)-1vd-1(r)rVd(r)ε2rc d=π(d-1)/2à((d+2)/2)(d+1)πd/2à((d+1)/2)εr2 rc d=π-1/2à((d+2)/2)2à((d+3)/2)εr2 rc d>π-1/2·(2d+4)-1/2εr2 rc d,在最后一个不等式中有一些冗长（但直接）的算术，利用gamma函数的对数凸性，定理11和定理10允许我们限制一致随机样本的个数ζ,我们需要得出一个低错误概率的结论，即（12）的最优解是（2）的ε-最优解。这是一个显式的，但很保守的界：在每次迭代中给定p，并且已知h的梯度和f的组成项上的全局界，在每次迭代中都可以很容易地计算出kπ(·)k上的一个上界C。（当对偶变量p先验有界时，也可以得到每次迭代都有效的Aglobal界。）这为算法2的列生成提供了（概率）停止准则。

请注意，定理10和11中使用的ε与使用算法2求解（1）的终止准则中使用的ε相同。为了使用定理11，我们需要一个e（？）cient算法从集合中均匀地采样。这一点很明显，如果（？）具有非常简单的几何形状，例如，当（？）是一个d维矩形盒、单纯形或椭球时。利用多项式混合次数的随机游动，也可以从一般多面体集和凸集生成均匀随机样本。一般多面体集由其刻面不等式给出，一般多面体集也可以从凸集生成均匀随机样本。例如，见调查(Vempala，2005)关于多面体的均匀抽样方法。最近在（Kannan and Narayanan,2012）中发现了多面体的强多项式方法；凸集出现的弱多项式方法(Lov\'Asz和Vempala，2006)。（Huang and Mehrotra,2013）也给出了关于凸集上均匀抽样的详细和最新的参考文献。我们现在可以得出结论，使用算法1可以得到(DRO)的半infirnite凸程序公式，算法2和euticent均匀抽样方法服务于假设2所要求的oracle的概率版本。算法2（求解（2）-（3）的随机化列生成方法）。参数:M，每次迭代的最大随机样本数。（有关选择此参数的详细信息，请参阅thetext。）步骤1。使用（Mehrotraand Papp，2013)中的算法1找到（2）中所支持的可行发行版。设S={ζ,...,xK}为其支持。求解原始-对偶对(12)-(13)，得到最优W、P+和P-。步骤3。采样均匀随机点ζ,直到找到一个具有正的降成本h（x,ζ）-(p+-p-)Tf(ζ）或达到最大样本数M。如果在前一个步骤中找到了降低成本为正的aζ,则将其加到S上,增加Ek,然后返回步骤2。否则Stop.6数值结果6.1半入式凸优化问题半入式编程文献中的大多数标准基准问题都是线性的。当问题(SICP)为线性时，算法1简化为中心切平面算法（除了更一般的定心）；因此，我们只考虑凸非线性检验问题。本部分的结果是基于一个中心切割平面和中心切割曲面算法的实现，使用AMPL建模语言和MOSEK和CPLEX凸优化软件。算法之间的比较仅基于迭代次数。所有示例的运行时间在所有实例中都是可比的，在标准台式计算机上不到5秒，除了示例3的20维和40维实例之外，其中中心切割平面法需要比算法1更多的时间来收敛。我们从一个说明性的例子开始，比较Kortanekand No(1993)的中心切割平面算法和我们的中心切割曲面算法。示例1(Tichatschke and Nebeling，1988)。最小化(x-2)+(x-0.2)服从(5sin(π√t)/(1+t))x-x≤0±t∈[0,1]x∈[-1,1],x∈[0,0.2]。（16）切割面切割平面σ可行性最优性相对可行性最优性相对论Cutts切割误差切割切割误差-41 23 10-4.2837 24 10-4.856-51 29 10-5.4137 29 10-5.083-61 34 10-6.3567 37 10-6.157-71 39 10-7.3048 43 10-7.174表1：中央切割面和中央切割面算法的比较，在例1中，中心参数s(k)=1。对于切割面算法来说，σ是与算法1相同的最优解距离测量方法；两个算法都达到σ<10-7。相对误差列显示了与真实最优目标函数值的相对误差。

这两种算法都表现出明显的线性收敛性，但切割表面算法只需要一次切割，迭代次数更少。该例子最初来自（Tichatschke and Nebeling，1988)，此后在文献中被频繁使用。（在最初的论文中，问题在infornite约束集中以t∈[0,8]代替t∈[0,1]出现。我们怀疑这是一个印刷错误：这不仅是一个不自然的选择，而且它使问题变得非凸。）最优解是x=(0.20523677,0.2）。这个问题特别简单，因为在最优解处只有一个割是有效的（它对应于t≈0.2134)，这也是每x最大的不等式。我们用最小值上的平凡上界5初始化这两个算法，对应于可行解(0，0)。TBL.1给出了这两种算法的进展情况（两种算法都使用常数中心参数s(k)=1）,证明了这两种算法都具有经验线性收敛速度。中心切割平面法产生更多的切割（包括T点的多个可行切割）。另一方面，切割曲面算法在第一次迭代中只生成T处的一条切割，然后通过迭代中心可行域直到建立最优性。例2（最小围球）。经典的最小包围球和smallestenclosing椭球问题要求最小体积的球体或椭球包含一组给定的点。它们都承认著名的二阶锥规划和半有限元规划公式。一个自然的推广是：给定一个闭参数曲面p(t)，t∈t（有一些给定的t Rn)，founding包含曲面所有点的最小体积球面或椭球面。这些问题也有一个半internite凸编程公式。以x为中心，半径为r的最小围球由最小r的最优解给出，服从kx-p(t)k≤r，Δt∈t，而最小围椭球由最大（det A)(1/n)服从A<0和kx-ap(t)k≤1，Δt∈t，在后一公式中A<0表示矩阵A是正半整数。objectivefunction log（det(A))也可以用来代替det(A)1/n；这两个公式是等价的。在（Papp and Alizadeh,2011）中表明，当p的每个分量都是多项式或三角函数时，这些问题也承认半规划(SDP)公式-4-2-4-2(a)-40-20-40-20(b)图1：参数曲线（17）和（18）及其最小围圆。单个变量的多项式。这就得到了一个多项式时间解，但当所涉及的多项式（或三角多项式）的次数太大时，该公式就会避免病态条件。此外，SDP公式所依赖的非负（三角）多项式的平方和表示不能推广到多元多项式，中心曲面切割算法没有半实物规划算法的运行时间保证，但它适用于更一般的情况（包括多元多项式所对应的多维索引集），而且不存在病态问题。我们给出了两个复杂度较低的例子。首先，考虑二维参数curveP(t)=(c cos(t)-cos(ct),c sin(t)-sin(ct)),c=4.5,t∈[0,4π]。（17）这条对称曲线有一个以原点为中心的最小包围圆，它在7个点处与曲线相交。（图1(a))TBL。2给出了这两种算法的收敛速度（在两种算法中使用常数定心参数(k)=1）。最小值的初始上界被设置为2(C+1)，由目标的一个简单的逐项界得到。

在这个例子中，两个算法的最优性切割的数目大致相同，但在可行切割的数目上有不同，因此在总的迭代次数上也有不同。现在考虑前面问题的一个非对称的、高度的变体，如图1所示。1(b):p(t)=(c cos(t)-cos(ct),sin(20t)+c sin(t)-sin(ct)),c=40,t∈[0,2π]。（18）圆心不再在原点上，圆的封闭形式描述是diuthult toaccure。（Papp and Alizadeh,2011）的基于半编程的解决方案在理论上是可能的，但实际上是不可行的，因为其中涉及到很高的三角多项式。TBL.3给出了这两个算法的收敛速度（在切割曲面算法中使用常数中心参数s(k)=1）。在下一个例子中，我们考虑了上述问题的推广，二阶锥约束维数大于2的问题，当建立可行集的多面体近似成本较高时，研究切割曲面在较高维度中可能特别有利的假设。切割曲面切割平面σ可行性最优性相对可行性最优性相对可行性最优性相对论切割误差切割切割误差-46 16 10-5.705-56 20 10-6.84513 18<10-10-66 23<10-1014 22<10-1014 22<10-1014 27<10-1014 86 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10-1014 28<10对于切平面算法，σ是与算法1中最优解的距离相同的度量；两种算法都在达到σ<10-8时终止。切割面切割平面σ可行性最优性相对可行性最优性相对论切割误差切割切割误差-46 23 10-7.51715 21 10-5.321-56 26 10-8.46315 24 10-8.46315 29<10-1017 27<10-10-76 32<10-1017 30<10-10-87 35<10-1017 34<10-1017表3：中央切割面和中央切割面算法在示例2的曲线上的比较，中心参数s(k)=1。对于切平面算法，σ是与算法1中最优解的距离相同的度量；两种算法均在达到σ<10-8时终止。相对误差列表示真实最优目标函数值的相对误差。例3。考虑sicpminx∈[-1,1]nmaxt∈[0,1]nxi=1(ixi-i/n-sin(2πt+i)),很容易看出最优解是x=(1/n,1/n,...,1/n),最小值的初始上界U=4n可以通过在x=0处取目标的一个逐项界得到。我们用这个界初始化中心切割表面和中心切割平面算法。和上面的例子一样，我们在两个算法中都使用了定心参数(k)=1。4给出了在n的停止条件σ<10-6之前所必需的可行割数和最优割数。很明显，在这个例子中，切割平面算法的可行割数（和总割数）随维数的增长比切割曲面算法快得多。这与这样一个事实相一致，即除非应用强定心，否则需要建立可行集的agood多面体近似（用于切割平面）或圆锥曲线近似（用于切割曲面），这需要比SurfaceCuts更多的平面切割。在下一节中，我们考虑进一步定心的e-cert ect。n=5 10 20 40切割面13+19 16+17 15+19 15+22切割面93+14 290+15 1179+15>10000.表4：关于n（决策变量个数）的取值，例3中的中心切割面和中心切割面算法的比较。表中的每个条目的格式都是可行性削减的数量+最优性削减的数量，用centeringparameter s(k)=1获得。

这两个算法在达到σ<10-6或10000次割后都终止了。6.1.1定心参数的E-ect在示例1和2中，大多数生成的割是最优割，而不是可行性割，这表明我们在每个迭代k中对定心参数的默认设置s(k)=1可能不是最优的。在另一个极端，s(k)=0期望在除最后一个迭代之外的所有迭代中产生不可行解。如第3节所讨论的，另一个定心参数的自然选择是违反不等式范数的梯度，这是由Kortanek和No在他们的中心割平面算法中提出的。最后，我们的收敛性证明了我们也可以使用这个梯度范数的附加分数。例3还表明，在可行切割和最优切割之间保持平衡的定心参数可能对这两种算法是不适用的，而且定心对切割表面可能不如对切割平面重要（这必须避免在远离最优的点周围建立可行集的昂贵的多面体近似）。在这一节中，我们进一步（经验）检验了定心参数的E-效果。上述最小的例子用无定心的切割曲面算法仅在两次迭代中求解；例如，在例1中，切割曲面算法生成一个最优曲面算法（与定心切割曲面算法在同一点T处），然后生成一个最优曲面算法，然后证明最优性。对于一个非平凡的例子，考虑例2中最小围球问题的第二个实例，参数曲线在（18）中定义，并使用算法1以及Kortanek和No的中心切割平面算法，使用定心参数s(k)再次求解相应的SICP问题。TBLS.5和6给出了该参数给定值的可行割数和最优割数。（停止判据为σ<10-8。）s(k)-9-7-5-3-2-11。10切割表面可行性切割9 8 7 7 7 7 7 7 9 10最佳切割2 2 3 4 6 11 35 190 149 6切割计划可行性切割18 18 16 16 16 17 17 23 27最佳切割2 2 3 4 6 11 34 195 182 7表5：本文讨论了以中心切割面的切割数目为中心的ECT算法和使用恒定中心参数的中心切割平面算法。值得注意的是，在（Kortanek and No，1993)中提出的以梯度范数为中心参数的中心切割平面算法在本例中的性能特别差。（参见表6的最后一列。）即使这种方法也可以从调整中获益（在本例中，降低）定心参数。现在让我们考虑示例3，并用定心参数的选择再次解决它。s(k)/kàg(x(k),t(k))k10-9-7-5-3-2-11。切割表面可行性切割7 7 7 7 7 7 7 9 10最优性切割2 3 4 11 33 183 137 9切割平面可行性切割18 18 16 16 16 16 26 22最优性切割2 3 6 10 30 155 152 4表6：以中心切割表面中的切割数为中心的ECT算法和使用梯度范数的常数分数作为定心参数的中心切割平面算法。最后一列中的数字表示原始的中心切割平面算法为proposedin（Kortanek and No，1993)。即使是中心切割平面算法也从调整中心参数中得到了很大的好处。tbl。4在上一节中给出了s(k)=1的结果。TBL.7显示了没有居中的情况，而TBLS。8-10显示了使用梯度法线的直接分数定心的结果。n=5 10 20 40切割面14+1 17+1 22+1 22+1 1切割面94+1 402+1 497 2+1>10000，表7：使用s(k)=0（无定心）的实施例3的结果。表中的每个条目都显示了可行性削减的数目+最优性削减的数目。

停止准则σ<10-6.n=5 10 20 40切割面13+8 15+11 16+20 11+47切割面87+6 304+9 1139+16 4510+34表8：使用s(k)=10-2k[k]k从实施例3得到的结果。表中的每个条目都显示了可行性削减的数量+最优性削减的数量。停止准则σ<10-6.n=5102040切割面15+2414+4813+12310+369切割面99+18279+36922+873483+232表9：使用s(k)=10-1k[k]k从实施例3得到的结果。表中的每个条目都显示了可行性削减的数量+最优性削减的数量。停止判据σ<10-6。结果显示了一些有趣的现象。首先，切割曲面算法比切割平面更不适合于强定心，尽管它确实适合于一些定心。同样明显的是，在中间解决方案成为中心（可行）之前，切割平面需要更高的中心参数值。在极端情况下，没有定心（表7)，两种方法在整个算法中都产生不可行点，直到找到ε-可行点。在这种情况下，算法在最后一次迭代中以最优切割结束。n=5 10 20 40切割面12+175 12+383 11+886 8+3115切割面92+102 250+247 823+705 299 0+1971表10：使用s(k)=k[k]k的示例3的结果。结果还表明，中心切割平面算法对定心参数的选择比切割曲面算法更敏感。最后，在高维情况下，无论切割平面法采用何种定心方式，切割平面都无法与平坦的无定心切割面竞争。这是由高维凸可行集不能用少量的平面切割很好地逼近这一事实解释的。这是一个我们期望曲面法在一般情况下优于切割平面的设置。6.2鲁棒性，为了说明中心切割曲面算法在矩鲁棒优化中的应用（第2节），我们返回示例1，并将其转化为一个具有鲁棒随机约束的问题：示例4.最小化(x-2)+(x-0.2)服从EP[(5sin(πPζ）/(1+ζ）)x-x]≤0±P∈pmx∈[-1,1],x∈[0,0.2],(19)，其中pM是一组概率分布，其支持的多项式矩为m阶:pmdef={P ep[ζi]=1/(i+1),i=0。当m=0时，给出了该问题的经典鲁棒优化形式，与原例1等价。在另一个极端，p∞只包含支持在[0,1]上的均匀分布。因此，对于m=∞解(19)，就等于解一个具有连续情景集的随机规划问题。（回忆定理1。）我们通过将连续场景集替换为离散场景集，解决了该问题的高精度确定性逼近，对应于数值积分的256点高斯规则；因此，这种情况不需要A sicp的解。对于m的值增加的问题（19）的解对应于越来越不保守（或风险厌恶）的解。当我们施加越来越多的矩约束时，这些问题的解是如何演变的，从鲁棒优化解走向随机规划解，这是有指导意义的。特别是，这个简单的问题说明了矩信息的价值超越了矩和二阶矩。有趣的是，与此同时，没有增加必要的切割次数来寻找最优值。结果被总结在TBL中。11.

请注意，x的最优值和目标函数之间的相当大的差值，在添加了少量的矩约束后。m最优性削减可行性削减xxz0 4 3 0.20527 0.2 3.22111 5 3 0.24654 0.2 3.07462 5 2 0.24712 0.2 3.07263 5 2 0.26242 0.2 3.01924 5 2 0.26797 0.2 2 0.26978 0.2 2.299376 4 2 0.27042 0.2 2.99376 42 0.27042 0.2 2.9914∞N/A N/A 0.27181 0.2 2.9866表11：问题（19）的解与有限矩约束的比较。m=0是传统的鲁棒优化，m=∞对应于传统的随机规划，在不同的风险规避水平下m个屈服解的中间值。6.2.1投资组合优化示例使用由（Delage and Ye,2010）引发的投资组合优化示例，说明了算法1和算法2在(DRO)求解中的应用，其中定心s(k)=10-3,停止条件σ<10-8,但m=∞除外（见正文）。在我们的实验中，我们从30种道琼斯资产中随机选择了三种资产，并跟踪了一年来每天重新平衡的动态配置投资组合的表现。我们将结果分为两部分：我们使用2008年和2009年的数据进行模拟，研究了最优投资组合在非常不稳定的市场条件下（2008年总体下降，2009年大幅上升）的性质。在这两种情况下，我们研究了使用di-everent矩约束优化的投资组合（或者，使用示例4的符号，我们使用di-everent集Pm）。我们跟踪了一个只使用figrst和second moments约束优化的投资组合，以及一个第三和第四边缘时刻也受到约束的投资组合。取样图如图所示。2、其中选择的资产是AXP，HPQ，结果显示了预期的趋势：较保守的投资组合（在所有与观测到的收益和二阶矩兼容的收益分布中，为最坏情况而优化）通常投资较少，该算法在Matlab R2012a（Windows 7 64位）中实现，主问题的求解采用内部Point-PointSolver IPOPT 3.10.2,oracle子问题的求解采用线性规划solverCPLEX 12.5,并在Intel Xeon 3.06GHz CPU的台式计算机上运行。TBLS.12和13分别给出了算法性能的统计摘要，对于最多为2阶矩约束的实例和最多为4阶矩约束的实例。切割面算法的停止准则是σ<10-3。不出所料，该算法的瓶颈是随机切割生成预言:Algorithm2比解决主问题（即非常小的凸优化问题）需要更长的时间来发现相应约束被违反的分布。然而，切割面算法实现了非常快的收敛（大多数情况下需要不到5次迭代），因此大多数问题可以在一分钟内解决。0.60.70.80.91.1(a)年20080.91.11.21.31.4(b)年2009图2：与市场表现相比，两个矩稳健投资组合的表现每天重新平衡。市场（固体，绿色）是道琼斯指数在实验开始时（第31天）具有1值。红色虚线显示了一个投资组合的价值，该投资组合使用了最近30天的回报信息和第二时刻信息进行优化。

（因此曲线从第31天开始。）蓝点虚线显示了使用相同时刻优化的投资组合的价值，也显示了最近30天回报的第三和第四边缘时刻。不出所料，在市场条件不好的时候，更保守的投资组合比第二个投资组合表现更好，而且只有在这种情况下。两个稳健投资组合都通过不投资避免了2008年的大幅下跌。分钟25%中值75%maxmaster问题时间[秒]0.1708 0.52 0.77 1.14 2.05 Master问题迭代2 2 4 5 10子问题时间[秒]0.0140 1.47 21.28 43.77 180.77子问题迭代1 27 54 87.25 186总挂钟时间[秒]9.4851 19.854 75.089 109.81 312表12：在矩约束达到2阶的投资组合优化示例上矩稳健优化算法的汇总统计。每个问题实例对应2008年或2009年的某一天；该表显示了每个实例的迭代计数和定时结果。分钟25%中值75%maxmaster问题时间[秒]0.2049 0.412 0.602 0.775 1.04主问题迭代2 2 2 2 5子问题时间[秒]0.0182 9.551 15.1 28.1 88.2子问题迭代1 3 43 87 986总挂钟时间[秒]9.6945 11.192 17.666 29.738 136.87表13：对矩约束达到4.7阶的投资组合优化算例的矩鲁棒优化算法的总结统计结论：在非常温和的假设下证明了中心切割面算法的收敛性，这些假设对于保持问题的凸性和内部非空是必不可少的。在次梯度不可用的约束条件中使用非di-in-everency函数，以及使用in-in-everency维数约束集的可能性，将半in-everency程序设计的适用性扩展到了新的领域。我们发现，在切割平面算法中，曲面切割的数目可以大大低于线性切割的数目，这弥补了每次迭代都要解决一个凸优化问题而不是线性规划问题，并且我们还发现对中参数的选择对切割曲面算法不太重要；切割曲面和切割平面的算法都来自于本文的更一般的分析，它允许从Kortanek和No提出的梯度范数中直接选择这个参数。我们的主要动机是分布鲁棒优化，但我们希望其他涉及概率分布约束的应用和其他涉及高维指数集T的问题将会出现。多元分布的分布鲁棒优化是一个相对较新的领域，甚至还没有正确的算法框架来处理出现的问题。最近文献中提出的方法包括内点法、程序设计法和椭球法，但这些方法不适用于阶矩约束大于2的情况。我们的算法是完全新颖的，因为它是一种用于分布鲁棒优化的半动态规划方法，也是迄今为止最普遍适用的算法。虽然不能指望基于半动态规划的方法能像针对特殊情况提出的多项式时间方法那样有效，但对匹配场景生成和分布优化算法的进一步研究可能会改善我们的方法的有效性。简单的启发式也可能是有益的。例如，如果已经找到了几个割集（对应于概率分布P、..、Pk)，并将其添加到主问题中，那么在搜索整个domain（domain）上支持的分布中的下一个割集之前，我们可以在分布P、.的支持并集上支持的分布中搜索。...,PK。