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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
提出并分析了一般半无限凸优化问题的中心切割曲面算法，并利用该算法对不确定性集由矩有界的概率分布组成的分布鲁棒优化问题提出了一种新的算法。任意阶矩以及非多项式矩都可以包括在公式中。我们证明了这会产生一个风险厌恶程度递减的优化问题层次，经典鲁棒优化在谱的一端，随机规划在谱的另一端。虽然我们的主要动机是解决具有矩不确定性的分布鲁棒优化问题，但一般半无限凸规划的切割面方法也是一个独立的兴趣。该方法适用于由无限维索引集索引的不可微半无限约束问题。算例表明，即使在求解约束可微且由低维索引集索引的传统半无限凸规划问题时，该算法仍具有潜在的应用潜力，并与Kortanek和No的中心切割平面算法进行了比较。通过对切割曲面算法收敛速度的分析，我们将作者提出的矩匹配场景生成算法推广为一种概率算法，该算法在满足矩约束的前提下寻找最优的概率分布。这种分布优化方法和中心切割面算法的结合产生了一系列分布鲁棒优化问题的解决方案，这些问题比目前提出的问题更加普遍。
---
英文标题：
《A cutting surface algorithm for semi-infinite convex programming with an
  application to moment robust optimization》
---
作者：
Sanjay Mehrotra, David Papp
---
最新提交年份：
2014
---
分类信息：

一级分类：Mathematics        数学
二级分类：Optimization and Control        优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Quantitative Finance        数量金融学
二级分类：Portfolio Management        项目组合管理
分类描述：Security selection and optimization, capital allocation, investment strategies and performance measurement
证券选择与优化、资本配置、投资策略与绩效评价
--

---
英文摘要：
  We present and analyze a central cutting surface algorithm for general semi-infinite convex optimization problems, and use it to develop a novel algorithm for distributionally robust optimization problems in which the uncertainty set consists of probability distributions with given bounds on their moments. Moments of arbitrary order, as well as non-polynomial moments can be included in the formulation. We show that this gives rise to a hierarchy of optimization problems with decreasing levels of risk-aversion, with classic robust optimization at one end of the spectrum, and stochastic programming at the other. Although our primary motivation is to solve distributionally robust optimization problems with moment uncertainty, the cutting surface method for general semi-infinite convex programs is also of independent interest. The proposed method is applicable to problems with non-differentiable semi-infinite constraints indexed by an infinite-dimensional index set. Examples comparing the cutting surface algorithm to the central cutting plane algorithm of Kortanek and No demonstrate the potential of our algorithm even in the solution of traditional semi-infinite convex programming problems whose constraints are differentiable and are indexed by an index set of low dimension. After the rate of convergence analysis of the cutting surface algorithm, we extend the authors\' moment matching scenario generation algorithm to a probabilistic algorithm that finds optimal probability distributions subject to moment constraints. The combination of this distribution optimization method and the central cutting surface algorithm yields a solution to a family of distributionally robust optimization problems that are considerably more general than the ones proposed to date.
---
PDF下载：
--> English_Paper.pdf (655.37 KB)

2022-4-16 14:00:29 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：凸规划 Optimization distribution Quantitative Applications

Sanjay Mehrotra*d Avid Papp 810月30日摘要我们提出并分析了一种用于一般半in凸优化问题的中心切割曲面算法，并用它开发了一种新的分布鲁棒优化算法，其中不确定性集由矩上有给定界的概率分布组成。该公式包括任意阶矩以及非多项式矩扫描。我们证明了这会产生一个风险厌恶程度递减的优化问题层次，经典鲁棒优化在谱的一端，随机规划在谱的另一端。虽然我们的主要动机是解决具有矩不确定性的分布鲁棒优化问题，但一般半凸规划的割面法也是一个独立的兴趣。该方法适用于由内维索引集约束的半内维非定常问题。通过与Kortanek和No的中心切割平面算法的比较，证明了OUR算法在求解传统的半线性凸规划问题时的潜力，这些问题的约束条件是不可克服的，而且是由一个低维的索引集来索引的。在分析切割面算法收敛速度的基础上，我们将作者提出的矩匹配场景生成算法推广为一种概率算法，该算法在矩约束的条件下，对最优概率分布进行优化。该分布优化方法与中心切割曲面算法的结合给出了一系列分布鲁棒优化问题的解决方案，这些问题比目前提出的方法更加普遍。关键词：半内规划、鲁棒优化、分布鲁棒优化、随机规划、矩匹配、列生成、切割曲面法、切割平面法、矩问题1引言我们提出了一种新的求解一般半内凸优化问题的切割曲面算法，该算法适用于对问题形式的较温和的假设，扩展了Kortanek和No(1993)的算法。我们的主要动机是解决大量分布鲁棒优化问题，这些问题可以被提出为具有凸但不一定是不可计数的维度集索引的可凸约束的SICPs*西北大学，工业工程和管理科学系，美国伊利诺伊州埃文斯顿。电子邮件:mehrotra@iems.northernth.edu}西北大学，工业工程和管理科学系，美国伊利诺伊州埃文斯顿。电子邮件:dpapp@iems.northwestern.edu。目前在哈佛医学院和马萨诸塞州总医院。概率分布。在本节的其余部分，我们介绍了所考虑的SICPs；在第2节讨论了与鲁棒优化的联系。我们考虑了一个以下形式的一般半凸优化问题：关于决策变量x（其坐标用x表示），使xsubject为g(x,t)≤0±t∈Tx∈x(SICP)，其中sx和t，且函数g:x×t7→R满足以下条件：假设1.1。集合X Rnis凸、闭、有界。存在一个Slater点(X，η>0)，满足X∈X和g(X，t)≤-η，对于每一个t∈t；3。

函数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不能继承的一种性质。在我们的激励应用程序中也是如此。

对于这类问题，使用由原始凸问题(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节的结束语中，分布鲁棒优化和矩鲁棒优化随机优化和鲁棒优化是用于处理不确定数据的决策问题的两类优化模型。广义地说，鲁棒优化通过在规定的场景集内为最坏情况进行优化来处理不确定性，而随机优化则假定不确定数据遵循特定的概率分布。

在(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可以看作是紧支集概率分布的矩唯一决定分布这一著名定理的推广。

对于无界支持的分布，只有当所讨论的矩唯一决定概率分布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。

对于（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。

假设算法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,...也单调减小。

对于每个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*+δ。

引用引理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）中完成证明所需要的。通常的切割方法，特别是我们的中心切割曲面方法，只更新在向主问题添加最优切割的那些迭代中找到的最佳可行（或在我们的情况下，ε-可行）解，而在其余的迭代中，当找到可行切割时，更新的是可行集。