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

2022-4-16 14:00:42

函数g(·，t)是凸的，且对每一个t∈t都是可次修正的；而且，这些次微分是一致有界的：存在一个B>0，使得对于每一个x∈x和t∈t，每一次梯度d∈GX(x,t）满足kdk≤B。注意，用变量向量x的一个分量代替以前的凸目标函数作为目标函数是不失一般性的；我们选择这种形式是因为它简化了算法的描述和收敛性分析。同样，我们可以在不丧失一般性的情况下假定η=1；否则，我们可以简单地用G/η代替G。（当然，这也会改变B的值。）我们还指出，T既不是凸维的，也不是圆维的，也不是g的第二个变元的凸性或凹性。由于其可行集是闭的、非空的、有界的，且目标函数是连续的，所以得到了(SICP)的最小值。我们的目的是在ε精度内找到一个(SICP)的最优解，我们的意思是：如果对于每一个t∈t，g(x,t)≤ε，我们说x∈x是ε-可行的；如果一个点xπεε=min{xx∈x,g(x,t)≤0±t∈t}是ε-可行的，我们说一个点xπε∈x是(SICP)的ε-最优解。我们对我们在规定的误差ε≥0内检测(SICP)候选解的近似不可行的能力做了一个初步假设。假设2。对于每一个不ε-可行的点x∈x，我们可以在一定的时间内得到满足g(x，t)>0的t∈t，而不要求我们对任意x能得到最违反的不等式g(x，t)>0或对应的arg maxt∈t{g(x，t)}。我们只规定，只要某个不等式被超过ε，我们就能够发现一个被违反的不等式。假设2比更“自然”的假设稍弱，假设有一个预言，它要么返回一个满足g(x，t)>ε的t∈t，要么得出结论，对于某些被违反的ε≥0的所有t∈t，g(x，t)≤ε。我们的形式是由瞬间鲁棒优化应用程序驱动的。正如我们在第5节中所看到的，矩鲁棒优化需要解决一个（在有限维）分布优化问题，这是一个非常需要精确解决的问题；然而，该部分提出的方法保证了如果存在一个完全违反的约束，那么在先验有界的时间内就会发现一些违反的约束。已经提出了几种解决半线性和半凸规划问题的算法，包括割平面法、局部约简法、交换法和同伦法。例如，请参见(L\'Opez and Still,2007）关于Semi-infoungnite凸规划的最新评论，其中包括大量参考文献的数值方法概述。现有的大多数算法都只考虑线性问题，因为一般凸问题(SICP)等价于半线性规划问题，最小化xsubject为UTx-gutut(u)≤0±T∈T和u∈dom gutx∈X,(SILP),其中gutut=g(·,T）的共轭函数。然而，我们认为，这种变换通常是非常内射的，因为如果X是n维的，T是d维的，并且（通常情况下）d n，那么半内约束集中的索引集就从d增加到相当高的d+n。另外，集合T和函数g可能具有特殊的性质，使其相对容易地发现违反的不等式g(x，T)≤0；不等式constraintsof(SILP)中的集合{(t，u)t∈t，u∈dom Gutolt}和共轭函数Gutolt不能继承的一种性质。在我们的激励应用程序中也是如此。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-4-16 14:00:48

对于这类问题，使用由原始凸问题(SICP)直接生成的非线性凸割（有时称为割面）比使用由等效线性公式(SILP)生成的割面更好。另一类半线性凸问题，其中使用割面比使用割面更有吸引力，其中X是一个高维非多面体集，其对X的多面体逼近是昂贵的。在这种情况下，由于（SILP）仍然是一个非线性凸规划，所以从半in-nite约束的线性重表述中获得的任何优势都消失了。即使X是多面体，并且只有约束是非线性的，在高维情况下，切割曲面也是有吸引力的，在高维情况下，切割平面可能需要大量的切割才能在最优值附近获得非线性约束的良好多面体逼近。必须求解大量线性主问题与必须求解少量非线性凸主问题之间的贸易关系并不清楚，而是依赖于问题。例3（第6节）给出了这样一个例子，即切割面法随着优化问题维数的增加而扩展，而切割面法则崩溃了。我们的算法是由（Kortanek and No，1993)的凸问题“中心切割面”算法推动的，该算法是Gribik算法(Gribik，1979)的扩展。Gribik算法是Firyeld中几个切割面算法的原型，并以各种方式进行了改进，如(Betr`o，2004)的“加速中心切割面”方法。我们的算法也可以看作是对传统凸约束生成方法的改进，在该方法中，受限制的主问题试图将其最优解驱动到可行集的当前外部逼近的中心。传统的constraintgeneration方法是我们算法的一个特例，所有中心参数都设置为零。从半集成编程的角度来看，我们的主要贡献是将中心切割平面算法扩展为允许非线性凸切割的切割曲面算法。尽管在我们的数值例子中，我们总是很快地找到最优解，但仍然保留了掉割的可能性，因为掉割是必要的。第二节讨论了分布鲁棒优化问题，给出了该问题的半凸形式，并说明了矩鲁棒问题的最优目标值收敛于随机规划的最优目标值的结果。在第3节中，我们描述了半工业凸规划中的切割曲面算法，并在第4节中证明了它的正确性，分析了它的收敛速度。该方法在分布鲁棒优化中的应用需要特定的列生成方法，这将在第5节中介绍。计算结果，包括标准的半凸基准问题和分布的鲁棒性最大化问题，在第6节后面；在第7.2节的结束语中，分布鲁棒优化和矩鲁棒优化随机优化和鲁棒优化是用于处理不确定数据的决策问题的两类优化模型。广义地说，鲁棒优化通过在规定的场景集内为最坏情况进行优化来处理不确定性，而随机优化则假定不确定数据遵循特定的概率分布。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:00:54

在(Scarf，1957)中引入的分布鲁棒优化可以看作是这些方法的组合，在这些方法中，用给定的数据可能遵循的概率分布集来寻找最坏情况下的最优决策。鲁棒随机规划也常用于描述相同形式的优化模型。形式上，假定不确定数据由一个支持在一个集合中的随机变量描述，服从一组概率分布P中的未知分布P。则广义分布鲁棒优化问题是一个形式为MINX∈XMAXP∈PEP[H(x)]的优化模型，或（等价）MINX∈XMAXP∈PZζ]H(x,ζ）P(Dζ）,其中H是期望最小化的随机代价函数或负效用函数，H是等价积分形式的响应权函数；H和H的参数x是我们的决策向量。我们假设所有的期望（积分）都存在，并且最小值和最大值都是很好的。在本文的其余部分，我们还将假定支持集（？）是封闭的和有界的。利用上述表示法，一般的随机优化问题（？）是简单的，而标准的鲁棒优化问题（？）是一个由所有概率分布组成的集（？）组成的集（？）。一般的分布鲁棒优化问题不仅可以看作是鲁棒优化和随机优化的一般推广，而且可以看作是一个在风险厌恶水平可调的情况下的优化模型。为了了解这一点，考虑一个概率分布集合的嵌套序列p·p··，其中pi是在态态上支持的所有概率分布的集合，并且p∞def=TM∞i=0pi是一个单例集合。在相应的问题序列(DRO)中，第一个是经典的鲁棒优化问题，它是所有问题中最保守（风险厌恶）的，针对最坏情况进行优化；最后一个是经典的随机优化问题，其中优化针对一个给定的分布。在中间层次上，模型与风险厌恶程度的降低相对应。这样一系列问题可以以许多自然的方式构成；我们将只关注当PI的序列通过约束潜在概率分布的越来越多的矩而被修改时的情况。这种情况下的(DRO)问题称为矩稳健优化问题。下面的定理1建立了这个序列的momentrobust优化问题收敛到闭域和有界域的随机优化问题的“收敛性”。设h和X如上，假定μ是封闭有界的，且h是连续的，设P是一个支持在μ上的概率分布，其矩为mk(P)def=r∞ζk···ζknnp(dζ.对于每一个i=0,1,。对于每一个多指标k，当0≤k+···+kn≤i时，设pidenment mk(Q)满足mk(Q)=mk(P)的概率分布集Q。最后，对于每一个i=0,1,。.将矩-鲁棒优化问题(DROi)定义为:minx∈Xmaxq∈Pizζ∈H(x,ζ）Q(dζ）。（DROi）则（DROi）的最优目标函数值序列收敛到随机规划x∈xzζ的最优目标函数值。（SP）在附录中给出了证明。值得注意的是，在上述定理中，函数h(x，·)可以用任意不依赖于x的连续函数f:7→R代替，证明了对于每一个连续函数f:7→R,limi→∞zζ∈f(ζ）qi(dζ）=zζ∈f(ζ）P(dζ）；换句话说，度量值的序列。.弱收敛于P，其中第i个测度的矩与P的矩一致的所有其他测度序列也是如此。因此，定理1可以看作是紧支集概率分布的矩唯一决定分布这一著名定理的推广。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-4-16 14:01:01

对于无界支持的分布，只有当所讨论的矩唯一决定概率分布P时，才能作出类似定理1的陈述。在最近的一篇评论文章（Kleiber and Stoyanov,2013）中，可以找到一系列确定分布的条件。在一个更现实的、数据驱动的环境中，不确定数据的矩的界限可以通过计算围绕经验分布样本矩的控制间隔来获得，也可以通过应用特定的考虑来获得，例如均值为零的测量或其他误差。2.1自从Scarf的开创性工作(Scarf，1957)以来，在大多数应用中，通过设置P的矩的界限来定义分布集合P；最近的例子包括（Delage and Ye，2010)、(Bertsimas et al.，2010)和（Mehrotra and Zhang，2013)。用标准统计方法可以很容易地得到任意阶矩的简单下界和上界（区间和椭球）；（Delage and Ye，2010)描述了一种可供选择的方法来推导出二阶矩和二阶矩的界限。然而，据我们所知，到目前为止，还没有一个算法能够求解具有二阶以上矩约束的集合P。最近的研究主要集中在多项式时间内求解具有矩约束的(DRO)的条件上。Delage和Ye(2010)考虑了均值向量和协方差矩阵周围的一种新类型的不确定性集，证明了对于一类在x中凸而在ζ中凹的propility质量函数h可以在多项式时间内（用椭球法）求解具有这种类型不确定性集的（DRO）。Mehrotraand Zhang(2013)推广了这一结果，给出了求解最小二乘问题的多项式时间方法（半有限规划），这些方法在x和ζ中都是凸的。通过测度的界、与参考测度的距离的界以及与在（Delage and Ye，2010)中所考虑的形式相同的矩约束来定义它们公式化的不确定性。贝尔西马斯等人。（2010）考虑了两阶段鲁棒随机模型，其中风险厌恶是在矩鲁棒框架下用firerst和二阶矩建模的。我们的方法不是多项式时间，但它可以应用于任意阶矩的界（可能是非多项式矩的界）可用的问题。这使得决策者能够更好地塑造P中的分布。4阶矩是容易解释的，已经被用来加强随机规划模型的制定。(Hoyland et al.）,2003）提出了一种利用二阶矩和4阶边缘矩改进随机规划模型的启发式方法。我们的方法是基于(DRO)的半内凸重列，2.作为半内凸规划的分布鲁棒优化考虑函数h在x中对每ζ凸的(DRO)的第二（积分）形式。如果（）和x是有界集，则最优目标函数值可以放在区间[zmin,zmax]内，且该问题可以写成半内凸优化问题：最小化zsubject to-z+zh(x,ζ）P(dζ≤0±P∈P(z,x)∈[zmin,zmax]×x,（1）是一个形式(SICP)的问题；集合P起T的作用；z扮演X的角色。注意，在上面的问题中，约束的索引集不是一个低维集，因为它在半内凸规划中很常见，而是一个内维集。因此，如果没有进一步的证明，我们就不能假定(SICP)中的违反不等式是容易找到的，但可以证明，只要h在态态的边界上有界，这个问题就满足假设1。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

mingdashike22

2022-4-16 14:01:07

对于（1）的假设2是指对于由算法给出的最优z的当前最优估计z(k)，我们可以得到一个P为rh(x,ζ）P(dζ）>z(k),条件是存在一个P为rh(x,ζ）P(dζ>z(k)+ε。当z(k)接近积分的最优值时，假设2逐渐转化为能够在规定的ε>0误差范围内获得P∈Pzh(x,ζ）P(dζ）（其中x是参数）。我们将在第5节的矩鲁棒优化上下文中集中讨论这个问题。在(DRO)的矩鲁棒公式中，集合P是通过一些（不必是多项式）矩的界来定义的：给定连续态7→R基函数f,。.和相应矩上的上下界向量`和u,我们设P=Pzàfi(ζ）P(dζ）∈[`i,ui],i=1,。...N.（3）低次多项式基的典型应用。例如，如果我们想在具有规定的均值向量和协方差矩阵的分布中优化最坏情况的分布，那么fican是n变量直到二次的单项式（包括constant1函数），`=u是规定的矩（包括“零次矩”，1)的向量。3一个半凸中心切割曲面算法在算法1中给出了我们的切割曲面算法的伪代码。在证明它的正确性之前，我们先要说明几点：首先，我们假设我们想要求解的(SICP)实例满足假设1和假设2。该算法也适用于分布鲁棒优化的半in-in-nite公式（1）。在这种情况下，假设1是满足的，只要h有界的子极点在态的边界上。正如前一节所讨论的，假设2转化为能够为形式（2）的问题找到ε-最优解。第二，算法1的正确性意味着只要假设2满足相同的ε-最优解，算法就可以计算到(SICP)的ε-最优解。在整个算法中，y(k-1)是迄今为止找到的最好的ε-可行解（或初始向量y(0))，它的初始坐标，y(k-1)是最好的ε-可行点的目标函数值的上界。y(0)的初始值是该最优值的任意上界U；y(0)的其他分量可以任意初始化。在算法的第二步，我们试图尽可能地改进当前的上界，并找出一个“中心”点x(k)，以极大地满足所有增加的不等式。在每一次迭代k中，要么在第5步增加一个新的割集，将最后一个不可行的x(k)割开（一个可行割集），要么在第6步发现x(k)是ε-可行解，并在第6步（一个最优割集）更新找到的最优ε-可行解y(k)。在任一种情况下，在可选的步骤7中，一些不活动的削减将被删除。参数β调整削减的力度；设置β=∞相当于完全跳过这一步。在第5步中，每一次迭代k都需要选择一个定心参数s(k)。为了保证方法的收敛性，该参数从零处有界，从上有界：对于每k,smin≤s(k)≤B，有些smin>0。（我们使用与次梯度范数相同的上界，这是没有损失一般性的。）另一个确保收敛的策略是构造一个次梯度d∈XG(x(k),t(k))和集s(k)=αkdk，其具有任意α∈(0,1]，这将给出定心参数的正值，但不一定有界于零。下面我们证明算法1在所有这些过程中都收敛。4正确性和收敛速度我们通过证明以下定理来证明算法的正确性。我们默认定心参数s(k)是根据上面提到的两个策略之一在步骤5中选择的。定理2。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:01:13

假设算法1在第K次迭代中终止。则y(k-1)是(SICP)的ε-最优解。定理3。假设算法1不终止。然后存在一个指数k，即序列(y(k+i))i=1,2,...完全由ε-可行解组成。定理4。假设算法1不终止。然后序列(y(k))k=1,2,...有一个累加点，每个累加点都是(SICP)的ε-最优解，因此，该算法要么经过无数次迭代得到ε-最优解，要么在极限范围内逼近一个。即使在第二种情况下，也通过一系列（最终）ε-可行解来逼近ε-最优解。算法1（中心切割曲面算法）参数：最优目标函数值(SICP)的严格上界U；假设1成立的B>0；假设2成立的公差ε≥0；和一个任意的β>1，该β>1指定削减的力度。（初始化。）集合k=1,y(0)=(U,0,...,0)∈Rn,而J(0)=.步骤2。（解决主问题。）在x+σ≤y(k-1)g(x,t(j))+σs(j)≤0±j∈j(k-1)x∈x的条件下，确定优化问题的最优解(x(k),σ(k))。（4）步骤3。（最优解？）如果σ(k)=0，停止并返回y(k-1)。（可行方案？）如果可能，求一个满足g(x(k),t(k))>0的t(k)∈t，如果没有这样的t(k)，则进行步骤6。步骤5。（可行性削减。）集合J(k)=J(k-1){k}和y(k)=y(k-1)；选择一个centeringparameter smin≤s(k)≤b（参见文本中的策略），转到步骤7。步骤6。（最优性切割；更新已知的ε-可行解。）设置J(k)=J(k-1)和y(k)=x(k)。（下降削减。）设D={jσ(j)≥βσ(k)和g(x(k))+σ(k)s(j)<0},设j(k)=j(k)\\D。将k增加1，进入步骤2。我们从一系列简单的观察开始证明。引理5。如果y(k)是对某些k的(SICP)的ε-可行解，则对于每个k≥k，y(k)也是ε-可行的。如果在步骤2中找到的点x(k)不是ε-可行的，则找到一个可行割，并将步骤5中的y(k)设置为最后找到的ε-可行解。否则，在步骤6中设置的y(k)=x(k)是ε-可行的。引理6。假设在第K次迭代开始时，我们有δdef=y(k-1)-x*>0，其中x*是(SICP)的一个最优解。则存在一个σ=σ(δ)>0（仅为δ的函数，而不是k的函数），从而在第2步（4）的最优解中，我们有σ(k)≥σ(δ)>0。设x是假设1所要求的Slater点，并考虑xλ=λx+(1-λ)x*对于λ∈(0,1]。将包含g的约束乘以1/η，我们可以在不丧失一般性的情况下假定，对于每个t∈t，x满足g(x，t)≤-1。由于xx的后来特性和x*的可行性，xλ是（4）在λ∈(0)之前的每一次迭代中的可行解，1]，并给出了不等式G(xλ),t(j))+λBS(j)≤λG(*x，t(j))+(1-λ)g(x*,t(j))+λ=λ(g（x）,t(j))+1)+(1-λ)g(x*,对于所有j∈j(0)TMj(1)TM··，利用g和s(j)≤B的凸性和第二个不等式的Slater条件，在第K次迭代中，如果y(k-1)-x*=δ>0，当λ>0个su小于满足0≤λ(x-x*)≤δ/2时，xλ也满足不等式y(k-1)-(xλ)=(x*+δ)-(λx+(1-λ)x*)=δ-λ(x-x*)≥δ/2。用λ表示λ的su小于值，且设σdef=min(λ/b,δ/2)，我们得出(xλ，σ)是（4）的可行解，因此（4）的最优解也满足σ(k)≥σ>0。我们的引理仅用于定理4的证明。引理7。假设算法1不终止。然后序列(σ(k))k=1,2,...单调减小到零，序列(y(k))k=1,2,...也单调减小。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:01:20

对于每个k,σ(k)≥0,因为对(x，σ)=(x*,0）是每次迭代的可行解。由此，再加上（4）的不等式，(y(k))k=1,2,...的单调性随之而来。由于(y(k))k=1,2,...是单调递减的，在步骤7中只从（4）中去掉非活动割，所以序列(σ(k))k=1,2,...是单调不递增的。因此(σ(k))k=1,2,...是收敛的。让我们（矛盾地）假定σ(k)&σ>0。然后，对于一个大的k，σ(k)<σβ，对于每k≥k，意味着在第k次迭代之后，在步骤7中没有削减。考虑在第j(j)和第k(k)迭代的第2步中得到的最优x(j)和x(k)，且k>j≥k。有两个案例，基于是否可行割g(x(j)，t(j))>0在jthiteration的第4步中找到或否。如果在JTIteration中没有找到可行性削减，x(k)=y(k-1)-σ(k)≤y(j)-σ(k)=x(j)-σ(k)在第k次迭代中遵循（4）的约束，因此，在第j次迭代中，若找到可行割，则为kx(k)-x(j)k≥σ(k)≥σ，那么一方面我们有(x(j)，t(j))>0，并且由于以后不删除此剪切，从（4）开始，在第k次迭代中我们还得到了(x(k),t(j))+σ(k)s(j)≤0。从这两个不等式出发，利用g(·,t(j))的凸性和Cauchy-Schwarz不等式，我们得到了对于每个d(j)∈XG(x(j),t(j))0≤σs(j)≤σ(k)s(j)<g(x(j),t(j))-g(x(k),t(j))≤-(d(j))t(x(k)-x(j))k(x(k)k·kx(k)-x(j)k，注意严格不等式蕴涵d(j)6=0。比较左右两边，我们得到σs(j)/kd(j)k<kx(k)-x(j)k。从这个不等式可以得出，只要定心参数s(j)远离零有界，并且kd(j)k有界（如假定的那样），我们有一个与j和k无关的σ>0满足σ<kx(k)-x(j)k。总之，无论在迭代j中添加可行或最优割，对于每k>j≥k，kx(k)-x(j)k≥min(σ，σ)>0，与序列(x(k))k=1,2,...有界因而有累加点的假设相矛盾。利用这些引理，我们准备证明我们的主要定理。定理2的证明。假设算法在第K次迭代中终止。首先，y(k-1)不是(SICP)的ε-可行解，这是一个矛盾。然后通过引理5，没有一点y(0)，..，y(k-2)是ε-可行的，因此，在每次迭代中，(4)约束中的上界是y(k-1)=U（最优解的严格上界）。因此，通过引理6，σ(k)>0，与算法终止的假设相矛盾。因此，y(k-1)是ε-可行的，现在假设y(k-1)是ε-可行的，但它不是ε-最优的，即y(k-1)>X*。于是引理6我们对每k有σ(k)>0，这与算法终止的假设相矛盾。定理3的证明。利用引理5证明了至少有一个y(k)是ε-可行的，否则，则整个算法所得到的x(k)或y(k)都不是ε-可行的。因此，在每次迭代中，(4)约束的上限仍然是y(k-1)=U（最优的严格上限）。引用引理6，我们得到σ(k)≥σ(u-x±)>0，矛盾引理7.定理4的证明。SICP可行集的紧性表明，如果算法不终止，则序列(x(k))k=1,2,...至少有一个累加点，子序列(y(k))k=1,2,...也至少有一个累加点。由定理3我们还知道这个序列最终是ε-可行点的，因此序列(y(k))k=1,2,...的每一个积累点也是ε-可行的（利用ε-可行解集也是紧的），设y是其中一个积累点，并矛盾地假定y不是ε-最优的，即y>x*。设δ=(y-x*)/2，其中x*表示(SICP)的一个最优解，利用引理5和δ>0的假设，存在一个较大的k，使得对于每个k>k，y(k)是(SICP)的ε-可行解，y(k-1)≥x*+δ。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:01:26

引用引理6，我们发现在这种情况下存在σ>0，使得σ(k)≥σ，对于每k>k，与引理7.4.1的收敛速度相矛盾，即在整个切割曲面算法中，序列σ(k)单调下降，收敛到零（引理7）。在这一节中，我们证明了该方法在可行割之间线性收敛，超出了满足σ(k)<η/b的迭代k。这与同类切割平面法的收敛性相吻合。有趣的是，这种分析可以用比（Kortanek-no）中心切平面法简单得多的方式进行。定理8。算法1的目标函数值在连续可行割之间线性收敛，超过满足σ(k)<η/b证明的迭代K。考虑迭代K中的主问题（4）及其对偶。设μ(k)是与约束相关联的对偶变量的最优值，设μ(k)jbe是与指数j∈j(k-1)对应的约束相关联的对偶变量的最优值。在不丧失一般性的情况下，可以假定(SICP)的目标x只被(SICP)中的约束从下面显式地限定，因此主问题（4）中的约束总是在最优时有效:σ(k)=y(k-1)-x(k)。（5）对应于原始变量σ的对偶约束给出μ(k)+xj∈j(k-1)s(j)μ(k)j=1。（6）利用这个方程和原始解和对偶解的最优性，我们得到：对于每个X∈X和每个σ，σ(k)≥σ-μ(k)(X+σ-y(k-1))-xjμ(k)jg(X,t(j))+σs(j)(7a)=μ(k)(y(k-1)-X)-xjμ(k)jg(X,t(j))(7b)≥μ(k)(y(k-1)-X)。(7C)现在假设在这个迭代中主问题产生一个ε-可行解x(k)。Theny(k)=x(k)，和eq。（5）加上（7）对于每个x∈x，Yydsy(K-1)-y(k)=y(K-1)-x(k)=σ(k)≥μ(k)(y(K-1)-x(x(K-1)-x)，并且对于最优的（8）从这个不等式出发，只要我们能将μ(k)从零界开，我们就能立即在目标值（在可行性割之间）上线性收敛。让我们使用记号M(k)=pj∈j(k-1)μ(k)j，并回忆(6)和(j)≤b.这些不等式意味着μ(k)=1-xj∈j(k-1)s(j)μ(k)j≥1-xj∈j(k-1)bμ(k)j=1-BM(k)。（9）将Slater点x代入(7b)可以得到另一个下界，使用g(x，t(j))≤-η:σ(k)≥μ(k)(y(k-1)-x)-xjμ(k)jg(x，t(j))≥μ(k)(y(k-1)-x)+ηm(k)≥μ(k)(x*-x)+ηm(k)，其结果是μ(k)≥ηm(k)-σ(k)x-x*，(10)取（9）和（10）的线性组合，其中coe>0和B(x-x*)>0消除m(k)下界:μ(k)≥η-Bσ(k)η+B(x-x*)。（11）右边的小数总是正的。由于假定分子从零到迭代k有界，序列μ(k)也是如此，这是我们在不等式（8）中完成证明所需要的。通常的切割方法，特别是我们的中心切割曲面方法，只更新在向主问题添加最优切割的那些迭代中找到的最佳可行（或在我们的情况下，ε-可行）解，而在其余的迭代中，当找到可行切割时，更新的是可行集。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:01:33

因此，将这些方法的收敛速度与可行方法的收敛速度进行比较，在每次迭代中更新最佳可行解决方案，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。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:01:40

（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，否则没有适用的近似算法。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:01:48

当球面为单位球面，π为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的列生成提供了（概率）停止准则。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-4-16 14:01:55

请注意，定理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。相对误差列显示了与真实最优目标函数值的相对误差。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:02:01

这两种算法都表现出明显的线性收敛性，但切割表面算法只需要一次切割，迭代次数更少。该例子最初来自（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)，由目标的一个简单的逐项界得到。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

大多数88

2022-4-16 14:02:08

在这个例子中，两个算法的最优性切割的数目大致相同，但在可行切割的数目上有不同，因此在总的迭代次数上也有不同。现在考虑前面问题的一个非对称的、高度的变体，如图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获得。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:02:14

这两个算法在达到σ<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的结果。表中的每个条目都显示了可行性削减的数目+最优性削减的数目。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:02:21

停止准则σ<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.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

何人来此

2022-4-16 14:02:27

请注意，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天的回报信息和第二时刻信息进行优化。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-4-16 14:02:33

（因此曲线从第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。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝