非线性约束最优化算法课件

本文框架最优化算法分类不等式约束组合变量消除优化函数和滤波马洛托斯现象二次校正和非单调方法本文框架最优化算法分类115.1最优化算法分类非线性最优化算法没有分类标准；对后面章节各种逼近做了分组，如下

所述：第16章，讨论二次线性规划（quadraticprogramming）求解问题的算法，它具有独特的性能。对有效集(activeset)，内点法(interior-point)和梯度投影法(gradientprojectionmethods)进行讨论。第17章,讨论罚函数(penalty)和增广拉格朗日(augmentedLagrangianmethods)方法，把目标函数和条件都结合归到罚函数里边，这样可以通过求解一系列非约束条件处理15.1问题。15.1最优化算法分类非线性最优化算法没有分类标准；对后面215.11罚函数和增广朗格朗日方法假如(15.1)中只有等式约束条件存在，那么二次罚函数定义：等式约束问题，定义：结合拉格朗日函数性质和二次罚函数（15.2）函数增广拉格朗日函数:15.11罚函数和增广朗格朗日方法假如(15.1)中只有等315.12连续二次规划方法第18章，讨论序列二次规划方法（sequentialquadraticprogramming）简称SQP.基本的SQP方法中定义Pk在(xk，λk)迭代的方向，从而得到解约束条件：15.12连续二次规划方法第18章，讨论序列二次规划方法（415.13非线性规划内点法第19章，讨论非线性规划内点法（interior-point）相对在14章讨论的线性规划来说，这种方法可以看做是原始对偶内点法（primal-dualinterior-point）的拓展，也可以看做是障碍法。约束条件：15.13非线性规划内点法第19章，讨论非线性规划内点法515.2不等式约束组合求解非线性规划最主要的难题是处理不等式约束，特别是在解中确定哪些约束条件是有效的。估测一个最优有效集A*，这是一组约束条件，在解处满足等式。这估测值叫做作用集，用w表示。在作用域约束条件强制为等式，约束条件在w处忽略，然后求解。最后验证是否有一个拉格朗日乘数，得到近似解X*，且W满足KKT条件（12.34）。这样把这X*看做（15.1）的局部解。例子：即使小数量的不等式约束，确定最优化有效集不是一个简单的任务。问题：约束条件：15.2不等式约束组合求解非线性规划最主要的难题是处理不等615.21W的八种可能选择用在下面的描述的作用作用域：按指数1到3有序标记，图15.1阐述了目标函数的形态，可行域是两轴和曲线包围的区域。可以看出在解中只有第一个约束条件有效，（x*，y*）=(1.953，0.089)τ即使对这个小的例子，考虑所有w可能的值很麻烦，图15.1表明，可以利用定义这个问题和他们的派生的函数知识消除，事实上在16章描述的有效集方法利用这种信息来进行一系列有根据的猜测作用域，避免w选择的明显偏离15.1的解。既内点法（障碍法）之后，一种不同的方法在19章考虑，这种方法生成的迭代远离通过不等式约束条件定义的可行定义域的边界，作为非线性规划的解释近似的阻碍作用被消弱，允许精度增加解的估计，在这种方法中避免了非线性规划组合的难题。15.21W的八种可能选择用在下面的描述的作用作用域：即使7第一种可能：求解方案中任何约束条件无效，也就是说w=Φ，由于▽f=(x-2，y-1/2)T，可以看到无约束f最小值在可行域外边，所以最优化有效集不能为空。有7种另外可能，其中三个约束条件是有效的，w={1，2，3}，图（15.1）对这个问题这样的情况没有发生，三个约束条件不共享一个相同的交叉点。通过单一的有效约束条件，得到三个更进一步的可能，那就是是{w=1}，{w=2}，{w=3}{W=2}，只有x=0的约束条件有效，如果在这种条件下使f执行最小化，得到（0，1、2）T这个点，检查（12.34）KKT条件，表明无论选择什么拉格朗日乘数，都不能满足在0，1、2）T的条件。（因为必须要λ1=λ3=0满足（13.34e）），通过这表明，设λ2=-2满足（12.34a），但是λ2的值不满足(12.34d)。{W=1，3}，得到单一的可行点（3，0）T，由于约束条件2在这个点无效，令λ2=0，解决（12.34a）用其他朗格朗日乘数，得到λ1=-16，λ3=16.5。，这些值是负数，不满足（12.34）所以（3，0）T不是（15.1）的解。{W=1}，求解等式约束条件问题，这问题中第一个约束条件是有效的，得到点（x，y）T=(1.953，0.089)T和拉格朗日乘数λ1=0.411。通过设定λ2=λ3=0，很容易得到，（12.34）的KKT其他条件是满足。于是得结论这个点是KKT点，由于拉格朗日的Hessian正定，很容易得到二阶充分条件满足。第一种可能：求解方案中任何约束条件无效，也就是说w=Φ，由于815.3变量消除

处理约束最优化问题，用边界条件消除问题中的变量是正常的，用更少的自由度得到一个简单问题。然而由于消除法可能改变问题或者引入病态条件必须小心使用目标函数：约束条件：得到两个变量的函数：15.3变量消除

处理约束最优化问题，用边界条件消除问题915.31非线性消除的缺点问题思考：约束条件：通过消除y求解，得到下面等式：很明显，随着x趋近负无穷时，h(x)趋近负无穷。盲目应用这个转换，得到这个问题无线，但是这个问题不能忽略约束条件（x-1）3=y2，这个含蓄的表明x≧1界值，这个解是有效的。因此，如果希望消除y，必须加入x≧1这个界值。这个问题说明了用非线性消去变量，可能导致很难追踪错误的结果。基于这个原因，大多数最优化算法中不用非线性消去法。相反，许多约束条件的线性的算法会用到消去法去解一些简单问题。现在就系统的概述下用线性约束去得到变量消除的目的。15.31非线性消除的缺点问题思考：约束条件：通过消除y1015.32用线性约束简单消去思考线性函数的约束条件的最小化问题，约束条件是线性等式约束：约束条件：A是一个m×n的矩阵，m≦n。简单起见假设A是满秩（假如情况不是这种情况，得到这个问题要么矛盾，要么约束条件多余的，能删除而不影响问题的解)在这种假定下，我们可以找到线性独立矩阵Ａ的m列的一个子集。如果将这些列向量组合到一个的B矩阵，定义一个的P置换矩阵。Ｐ矩阵是将这些列与Ａ的第一个列进行交换的矩阵，表达式:N表示Ａ矩阵n-m剩余列。(这里的注释和第13章一致，讨论线性规划背景的相似概念)15.32用线性约束简单消去思考线性函数的约束条件的最小11定义下面形式下的子向量

：(15.8)xB为基变量，B为基矩阵。注意PPT=I可以将约束条件Ax=b改写如下：重排这个式子，通过下面的表达式可以减少所给的基变量：(15.9)从而，通过选择任意xN值，计算约束条件Ax=b的可行点，然后可以通过(15.9)设置xB。因此，(15.4)问题和非约束问题等价。(15.10)上述讨论说明了线性等式的约束条件的非线性最优化问题是从数学观点来的，非约束问题同样，下面就讨论非约束问题定义下面形式下的子向量：上述讨论说明了线性等式的约束条件的1215.34线性等式的非约束问题的非线性最优化思考：（15.11a）约束条件：(15.10)定义转置矩阵P得

的组成从新排列，xT=(x3，x6，x1，x2，x4，x5)T，得到AP矩阵的系数:基矩阵B是对角阵，因此，很容易求取转置(15.12)15.34线性等式的非约束问题的非线性最优化思考：13替换(15.11a)中的x3，x6，问题变成如下：

(15.13)从Ａ系数矩阵(不含有X3和X6两个变量)中选择其它两列作(15.11b)系统中消除的基础。然而，这些选择，B-1N将会变得更复杂。用高斯消元法选择一组m非独立列，在线性代数中的用语，能计算出这个矩阵的行阶梯型，选择中心轴列做为基矩阵的列。理想情况下，希望B矩阵很好分解和适定性。为了这个目的，用稀疏高斯消去算法去，保持稀疏、控制舍入误差。替换(15.11a)中的x3，x6，问题变成如下：(15.14从(15.8)和(15.9)中可以看出在线性约束条件(15.6)中任意可行点可以被写成：(15.14)(15.15)注意z有n-m线性非独立列(由于在低维中存在单位矩阵的存在)满足AZ=0因此，Z是空矩阵A的基础矩阵。加上Y和Z的列组成是一个线性非独立集。我们也可以看到是线性约束条件一个特解.从(15.8)和(15.9)中可以看出在线性约束条件(15.15换句话说，这个简单消去法说明了可行点可以作为Ax=b(15.14的第一项)的特解加上沿着约束条件(15.14的第二项)的空集(或者相切)总的概括。这(15.13)，(15.14)的关系表明特解Yb是从控制x的n-m个在０点的组成，别的部分是松弛的，直到它们满足约束条件；Yb的特解有时称作坐标松弛步长。见图15.3坐标松弛步长Yb通过选择不基矩阵B去成为A矩阵的第一列，若果选择B作为A的第二列，那么坐标松弛步长将沿着X2轴。简单消去法不费时，但是数值不稳定会产生。如果图15.3中这个可行集是由几乎平行与X1轴的一条线组成的话，沿着这个坐标轴的坐标松弛是一个比较大的数量级。计算x作为不同的大矢量，给出数值取消。在这种情况下选择沿着x2轴的特解会比较好，也就是说选择不同的基。因此，一般情况下，选择最好的基底并不是一个简单的任务。当这个基矩阵约束条件很少时，在定义过程中会引起数值错误。为了克服过分协调松弛步长的危险。我们可以定义这个特解Yb作为约束条件的最小基准步长。这种方法是现在所描述的纵多消去法中的特殊情况。换句话说，这个简单消去法说明了可行点可以作为Ax=b(15.1615.35线性约束条件的一般消减法对(15.14)和（15.15）归类，选择矩阵Y∈Rn×m和Z∈Rn×(n-m)，具有以下性质：(15.16)这些属性表明，正如（15.15）Z的列是空矩阵A的基底。因为A有满秩，所以A[YIZ]=[AYI0]，所以AY矩阵也是非奇异矩阵，现在表示线性约束Ax=b任何形式的解，如下：(15.17)对向量XY∈Rm和xZ∈Rn-m，通过15.17的取代到约束条件Ax=b得到：因此通过非奇异矩阵，可以直接被写成下式：(15.18)通过代替表达式(15.17)，得到任意一个向量的形式:(15.19)15.35线性约束条件的一般消减法对(15.14)和（117xz∈Rn-m的任意选择满足约束条件Ax=b。因此，这个问题(15-6)可以被重新当做如下的非约束问题：(15.20)理想的，选择Y使AY尽可能的满足Ax=b条件，因为它需要对这个因式分解给出特解Y（AY）-1b。用一个AT的QR因式分解来计算Y和Z，AT有如下形式为：(15.21)[Q1Q2]是正交矩阵。子矩阵Q1和Q2有正交列，它们分别为n×m和n×(n-m)，而R是n×m的上三角矩阵和非奇异矩阵，是一个m×m矩阵。（在附录(A.54)详细的讨论。）做如下定义：(15.22)因此，Y和Z的形式是Rn的一个正交基矩阵。假如我们将(15.20)展开并做一部分从排列，我们可以得到:xz∈Rn-m的任意选择满足约束条件Ax=b。因此，这个问题18因而，Y和Z有期望性质，这样AY的条件数和R一样，A也是一样的。从(15.19)中可以看出Ax=b的任何解能被表示成:对xz向量，计算这R-T∏-Tb并不是很费时，用单一的三角代换就得到了简单的估算表明这个特征值Q1R-T∏-Tb能被写成(15.22)因此，这个约束条件Ax=b的最小范数解是下式的解：(15.23)因而，Y和Z有期望性质，这样AY的条件数和R一样，A也是一样19这是最小值范数解，图(15.5)给出了这步的图解。从数值稳定性的观点来看，消去法通过正交基矩阵(15.22)是比较理想的。主要耗时的是在(12.21)QR因子因式分解中与下降方法有关计算。不好的是，在这个问题中矩阵大和稀疏，在简单消去法中，计算稀疏QR因子因式分解过程比稀疏高斯消去法更耗时。因此，别的一些消去分类在这两种方法中寻求平衡而得到了发展；可以看练习15.7.这是最小值范数解，图(15.5)给出了这步的图解。从数值稳定2015.36不等式约束的作用如果不等式约束呈现出等式约束时变量消去法并不总是有效地。例如，问题(15.10)，(15.11)有附加约束条件x≧0，消去变量x3和x6后，就能只剩下在(15.13)中的最小化函数问题，约束条件是：因此，消去等式约束(15.11)的作用是使得不等式约束要比简单边界x≧0复杂。对许多算法来说，这个转换并不是没有一点益处。然而，假如问题(15.11)包含一般不等式约束条件3x1+2x3≧1，这个(15.12)消去法，转换问题将会变成(15.12)中的函数最小化问题在，不等式约束条件：（15.23）在等式约束消去之后，这个不等式约束并不能变的很复杂，因此，消去法是值得去做的。15.36不等式约束的作用如果不等式约束呈现出等式约束时2115.4优化函数和滤波对于非线性规划问题(15.1)，的优化函数是受欢迎的选择是这个l1罚函数函数被下式定义为罚函数函数被下式定义为：（15.24）注释[z]-=max{0，-x}。正标量μ罚参数，这决定了分配满足相对目标函数的最小的约束条件的权重。由于一些列球型参数μ能确定优化函数，这个非线性规划问题(15.1)的解是φ(x，μ)的一个小域。注意这个l1优化方程φ1不可微的，因为这个绝对值和[]-函数是存在的，但是它有重要精确性质。15.4优化函数和滤波对于非线性规划问题(15.1)，的2215.43准确的优化函数假如对任意μ>μ*中有一个正的标量μ*，这个优化函数φ（x，μ）就能确定，任何一个非线性规划问题(15.1)的局部解是φ（x，μ）的局部最小值。在定理17.3展示的那样，在一定的假设，l1优化方程φ（x，μ）确定，μ*的极限值是被给λi*表示和最优解x*有关的拉格朗日多项式。因为最佳拉格朗日乘数是建立在包含调整罚函数参数的规则的l1优化方程的算法，然后事先不知道，有理由相信这不是足够大的（或者不是极大）。这些规则建立在最优化算子的选择，将在下一章讨论。15.43准确的优化函数假如对任意μ>μ*中有一个正的标2315.44精准l2函数的增广拉格朗日对于等式约束的情况，优化函数用如下形式：这个函数不可微分，因为2-规范不是平方值，其衍生类在x=0没有定义。一些优化函数不仅平滑而且精确。确保属性持有，必须在优化函数中加附加条件。对等式约束条件问题，弗莱彻的增广拉格朗日，通过下面的给定：15.44精准l2函数的增广拉格朗日对于等式约束的情况，24μ＞0是罚参数A（x）表示c(x)的雅克比行列式，尽管这个优化函数有一些有趣的理论属性，它有实际的限制，包括在（15.27）λ（x）求解代价。与众不同的优化函数是在x，λ的增广拉格朗日，对等式约束问题有如下形式：μ＞0是罚参数25通过比较LA（x+，λ+，μ）和当前迭代（x，λ）的值来评估测试点的合格性，严格的讲，感觉上LA不是优化方程，一般来讲非线性规划问题的解（x*，λ*）不是LA（x+，λ+，μ）的最小值，仅仅是一个驻点。尽管一些连续的二阶规划方法用LA通过修改模型λ和μ参数成功的作为优化方程，但还是不考虑这做一个优化方程，相反，把焦点主要放在非光滑精确罚函数Φ1Φ2。通过比较LA（x+，λ+，μ）和当前迭代（x，λ）的值来评估26通过线性搜索算法产生的实验步长x+=x+αp，如果这在优化方程Φ（x，μ）产生足够减小，那么这算法是可接受的。方法一：定义这个概念类似于在非约束最优化（3.4）条件，然而在这一步这个数量不能相对太小以致不能预测函数的变化。L1和l2优化函数不可微，但有方向导数。（看（A.51）背景的方向导数）直接写Φ（x，μ）在p方向的方向导数：D（Φ（x，μ），p）用线性搜索法，足够减少的条件要求是迭代步长参数α>0，足够小以致如下不等式对于η∈（0，1）满足：通过线性搜索算法产生的实验步长x+=x+αp，如果这在优化方27经过p步长后，信赖域方法常用二阶模型q(p)来评估优化函数Φ，如18.5部分。足够的减少条件能用这个模型减少的形式规定，如下：非线性约束最优化算法ppt课件2815.45滤波滤波技术是一步接受原理建立在多目标最优化问题的基础上。从观测非线性规划推导有两个目的：目标函数的最小化函数和满足约束条件。定义不可行域估量：把这两个目标写成：不同于优化函数，这结合所有问题到单一的最小化问题，滤波方法在（15.32）分开保持这两个目标。如果

不受控前一个通过算法产生的

，滤波方法接受测试步长x+做一个新的迭代，这些概念被定义如下：15.45滤波滤波技术是一步接受原理建立在多目标最优化问题29定义15.2fk≦fl和hk≦hl则，（fk，hk）是被（fl，hl）控制，滤波是对（fl，hl）的列表，如此没有任何一对占主导地位，迭代xk是对滤波可接受的。当迭代xk是对滤波可接受，我们一般加（fk，hk）到滤波，移除被（fk，hk）支配的任何对，图示15.6展示了滤波中每一对（fl，hl）用黑点表示。每一个滤波形成一个矩形区域，这个结合定义一个组队对滤波不可接受。更特殊的，如果（f+，h+）在实线的下面或者左边（图15.6），测试点x+是可接受的。比较滤波和优化函数方法，在图15.7绘制了组对（f，h）的轮廓线，这样f+uh=fk+uhk，xk是当前迭代，该区域线的左边和双集一致，减少优化函数φ（x，μ=f(x)+μh(x)，很明显，这个集完全不同与接受点。如果通过线搜索方法所产生一个试验步长x+=xk+αkpk给出给一对(f+，h+)，这是可接受的滤波波，设置xk+1=x+，否则，执行回溯线性搜索。在信赖域方法中，如果滤波这步骤不可行，信赖区域减少，计算新步骤。定义15.230当迭代xk是对滤波可接受，我们一般加（fk，hk）到滤波，移除被（fk，hk）支配的任何对，图示15.6展示了滤波中每一对（fl，hl）用黑点表示。每一个滤波形成一个矩形区域，这个结合定义一个组队对滤波不可接受。更特殊的，如果（f+，h+）在实线的下面或者左边（图15.6），测试点x+是可接受的。当迭代xk是对滤波可接受，我们一般加（fk，hk）到滤波，移31如果通过线搜索方法所产生一个试验步长x+=xk+αkpk给出给一对(f+，h+)，这是可接受的滤波波，设置xk+1=x+，否则，执行回溯线性搜索。在信赖域方法中，如果滤波这步骤不可行，信赖区域减少，计算新步骤。这个滤波技术需要作一些改进，从而获得全局收敛性和良好的实用性能。首先，我们需要确保我们不接受一点(f、h)对是非常接近当前的一对(fk，hk)或在滤波中的其他对。通过修改可行准则和实现充分下降条件。滤波是接受测试迭代x+，如果滤波中所有(hf，hj)，有如下条件：如果通过线搜索方法所产生一个试验步长x+=xk+αkpk给出32β∈(0，1)。虽然这条件在实践使用中有效，说β=10−5，分析的目的，通过下面的式子，它可能有利于取代第一个不平等的。通过线性搜索方法生成的搜索方向的可能需要足够小步长αk，这样滤波才可行。这种现象可以导致算法陷入停滞和失败。为了防止这种情况，如果回溯线搜索生成一个步长比极值αmin小，该算法切换到可行性恢复阶段。非线性约束最优化算法ppt课件33可行性恢复阶段主要目的是减少相反的约束条件，也就是说，找到一个近似的解决问题的办法。现在列举滤波步骤，假设由信赖域方法生成迭代的，参见18.5节信赖域方法约束优化讨论。算法15.1(一般滤波方法)选择起点x0，初始信赖域半径Δ0设置k←0，重复，直到满足收敛测试可行性恢复阶段主要目的是减少相反的约束条件，也就是说，找到一34If步骤生成子问题不可行用可行性恢复阶段计算xk+1else计算试验迭代x+=xk+pkIf(f+，h+)滤波可以接受设置xk+1=x+并添加(fk+1，hk+1)滤波选择Δk+1，Δk+1≥Δk从滤波中删除所有主导对由(fk+1，hk+1)Else丢弃这一步骤中，If步骤生成子问题不可行35设置xk+1=xk选择Δk+1<ΔkEndifEndifk←k+1，endrepeat这个简单的滤波步骤的其他改进用于实践，建立在算法的选择上，将在后续的章节中讨论。设置xk+1=xk3615.5

马洛托斯现象一些算法基于优化函数或滤波可能在迅速收敛失败，因为丢弃朝着解的方向进的步骤。这种不良现象通常被称为马洛托斯效应，因为它是被马洛托斯[199]首次发现。通过下面的例子说明，在哪些步骤pk，如果接受这将产生二阶收敛，导致目标函数值和违反约束条件的增加15.5马洛托斯现象一些算法基于优化函数或滤波可能在迅速37考虑问题可以验证(见图15.8)最佳解是x∗=(1，0)T，对应的拉格朗日乘子λ*=3/2，让我们考虑xk=(cosθ，sinθ)形式的迭代xk，这对于任何θ值可行。假设算法的计算步骤如下:测试点考虑问题38通过使用基本三角转换，有因此因此，这一步的方法的解与Q二阶收敛速度一致。然后，有因此，在图15.8中可以看到，这一步目标函数值和约束违反增加。这种行为发生在任何θ非零值，即使任意初始点接近解。通过使用基本三角转换，有39在上面的示例中，任何算法，需要优化函数减少的形式：h(・)是一个非负函数，满足h(0)=0，将丢弃(15.35)好步骤。(这样的优化函数的例子包括φ1和φ2罚函数)。(15.35)步骤也将被上述的滤波原理丢弃，因为(f(xk+pk)，h(xk+pk))是由(fk，hk)控制。因此，所有这些方法有马洛托斯现象。在上面的示例中，任何算法，需要优化函数减少的形式：40如果没有采取补救措施，马洛托斯现象可能从解中通过干扰好步骤或防止超线性收敛，减缓优化方法。避免马洛托斯现象的策略包括如下：用不受马洛托斯现象的优化函数，。例子是弗莱彻的增广拉格朗日函数(15.26)。用二阶校正，pk增加步p’k，在c(xk+pk)计算，减少了约束违反。允许优化函数φ增加某些迭代，也就是说，可以使用非单调。在下一节中将讨论最后的两种方法。如果没有采取补救措施，马洛托斯现象可能从解中通过干扰好步骤或4115.6二阶校正和非单调技术通过添加修正项，减少了约束违反，各种算法能够克服马洛托斯现象有关难题。用等式约束条件问题描述这方法，约束条件是c（x）=0，Rn趋近RIεI给定步长pk，p’k的二阶校正步长定义：Ak=A(xk)是c在xk雅可比。注意p’k的属性，在xk+pk点它满足了线性化的约束c，也就是说：事实上，p’k是这个等式的最小范数解。15.6二阶校正和非单调技术通过添加修正项，减少了约束违42校正步长p’k的效果是对Ixk−x∗I3的规则减少Ic(x)I量，，主要步骤pk满足Akpk+pk+c(xk)=0。这个估计表明，从xk到xk+pk+p’k将减少优化函数，至少靠近解。此增强功能包括约束函数c在xk+pk额外的评估和从(15.36)所需的线性代数来预订步长p’k。现在描述用线性搜索和二阶修正步长的优化函数算法。假设pk和搜索方向计算的罚参数μk，pk是优化函数下降方向，也就是说，D(φ(xk，μ)，pk)<0。在18和19章，将讨论如何完成这些目标。算法的主要特征是，如果完整的步骤αk=1，在优化函数不会产生满意的下降，在回溯沿着pk原来的方向之前尝试二阶校正步骤。校正步长p’k的效果是对Ixk−x∗I3的规则减少Ic(x)43算法15.2(用二阶校正的通用算法)。选择参数η∈(0，-0.5)和τ1τ2与0<τ1<τ2<1，选择初始点x0设置k←0，重复，直到满足收敛测试:计算一个搜索方向pk，设置αk←1，新点←假，while新点=falseifφ(xk+αkpk，μ)≤φ(xk，μ)+ηαkD(φ(xk，μ)，pk)设置xk+1←xk+αkpk设置新点t←正确，Elseifαk=1从(15.36)计算p’k，Ifφ(xk+pk+p’k，μ)≤φ(xk，μ)+ηD(φ(xk，μ)，pk)设置xk+1←xk+pk+p’k，算法15.2(用二阶校正的通用算法)。44设置新点←正确，Else选择新αk[τ1αkτ2αk]，ENDELSE选择新αk在[τ1αk，τ2αk]，EndEndwhileEndrepeat在该算法中，如果在优化函数作用没有减少完整的二阶校正步长p’k丢弃。放弃pk+p,k方向追踪，因为它不能保证是优化函数的下降方向。该算法的变化应适用于二阶修正步长，只有(15.29)条件充分下降，在规范约束条件下增长的结果是违反的。二阶校正策略在实践中是有效的。执行额外的约束函数评估的和在（15.36）额外的回执代价胜过增加健壮性和效率。设置新点←正确，45非单调性的策略马洛托斯现象造成的低效也可以避免，偶尔的接受增加优化函数步骤，这些措施被称为松弛步骤。耐性有限制，然而如果优化函数足够的减少没有获得一定数量的松弛步长的迭数(t’迭代)返回迭代，在松弛步长前返回迭代步长，执行正常的迭代，在优化函数中用线性搜索或其他方法强制减少。与二阶修正相比，唯一目的是提高约束条件的满意度，这种非单调策略总是常规算法的步长pk，目的都是提高可