《非线性约束最优化算法.pptx》由会员分享，可在线阅读，更多相关《非线性约束最优化算法.pptx（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本文框架本文框架最优化算法最优化算法分类分类不等式约束组合不等式约束组合变量消除变量消除优化优化函数函数和和滤波滤波马洛托斯现象马洛托斯现象二二次校正和非次校正和非单调单调方法方法第1页/共50页15.1 15.1 最优化算法分类最优化算法分类非线性最优化非线性最优化算法没有分类标准；算法没有分类标准；对对后面后面章节各种章节各种逼近做了分组，逼近做了分组，如下如下 所所述述：I.I.第第1616章章，讨论，讨论二次线性二次线性规划规划（quadratic programming）求解问题的算法问题的算法，它，它具有独特具有独特的性能。对的性能。对有有效效集集(active set)，内点内点
2、法法(interior-point)和和梯度投影法梯度投影法(gradient projection methods)进行进行讨论讨论。II.II.第第1717章章,讨论讨论罚函数罚函数(penalty)和和增广增广拉格朗日拉格朗日(augmented Lagrangian methods)方法方法，把目标函，把目标函数和条件都结合归到罚函数里边，这样可以通过求解一系列非约束条件处理数和条件都结合归到罚函数里边，这样可以通过求解一系列非约束条件处理15.115.1问题问题。第2页/共50页15.11 15.11 罚函数罚函数和和增广增广朗格朗日方法朗格朗日方法假如假如(15.1)15.1)中只
3、有等式约束中只有等式约束条件存在条件存在，那么二，那么二次次罚函数罚函数定义定义：等式约束问题，定义等式约束问题，定义：结合拉格朗日函数性质和二次罚函数（结合拉格朗日函数性质和二次罚函数（15.215.2）函数）函数增广拉格朗日函数增广拉格朗日函数:第3页/共50页15.12 15.12 连续连续二次规划方法二次规划方法第第1818章章，讨论讨论序列二次规划方法二次规划方法（sequential quadratic programming）简称SQP.基本的SQP方法中定义Pk在(xk，k)迭代的方向，从而得到解约束条件：第4页/共50页15.13 非线性规划内点法第19章，讨论非线性规划内点
4、法（interior-point）相对在14章讨论的线性规划来说，这种方法可以看做是原始对偶内点法（primal-dual interior-point）的拓展，也可以看做是障碍法。约束条件：第5页/共50页15.2 不等式约束组合求解非线性规划最主要的难题是处理不等式约束，特别是在解中确定哪些约束条件是有效的。估测一个最优有效集A*，这是一组约束条件，在解处满足等式。这估测值叫做作用集，用w表示。在作用域约束条件强制为等式，约束条件在w处忽略，然后求解。最后验证是否有一个拉格朗日乘数，得到近似解X*，且W满足KKT条件（12.34）。这样把这X*看做（15.1）的局部解。例子：即使小数量的不
5、等式约束，确定最优化有效集不是一个简单的任务。问题：约束条件：第6页/共50页15.21 W的八种可能选择用在下面的描述的作用作用域：按指数1到3有序标记，图15.1阐述了目标函数的形态，可行域是两轴和曲线包围的区域。可以看出在解中只有第一个约束条件有效，（x*，y*）=(1.953，0.089)即使对这个小的例子，考虑所有w可能的值很麻烦，图15.1表明，可以利用定义这个问题和他们的派生的函数知识消除，事实上在16章描述的有效集方法利用这种信息来进行一系列有根据的猜测作用域，避免w选择的明显偏离15.1的解。既内点法（障碍法）之后，一种不同的方法在19章考虑，这种方法生成的迭代远离通过不等式
6、约束条件定义的可行定义域的边界，作为非线性规划的解释近似的阻碍作用被消弱，允许精度增加解的估计，在这种方法中避免了非线性规划组合的难题。第7页/共50页第一种可能：求解方案中任何约束条件无效，也就是说w=，由于f=(x-2，y-1/2)T，可以看到无约束f最小值在可行域外边，所以最优化有效集不能为空。有7种另外可能，其中三个约束条件是有效的，w=1，2，3，图（15.1）对这个问题这样的情况没有发生，三个约束条件不共享一个相同的交叉点。通过单一的有效约束条件，得到三个更进一步的可能，那就是是w=1，w=2，w=3W=2，只有x=0的约束条件有效，如果在这种条件下使f执行最小化，得到（0，1、2
7、）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。通过设定
8、2=3=0，很容易得到，（12.34）的KKT其他条件是满足。于是得结论这个点是KKT点，由于拉格朗日的Hessian正定，很容易得到二阶充分条件满足。第8页/共50页15.3 变量消除处理约束最优化问题，用边界条件消除问题中的变量是正常的，用更少的自由度得到一个简单问题。然而由于消除法可能改变问题或者引入病态条件必须小心使用I.目标函数：II.约束条件：III.得到两个变量的函数：第9页/共50页15.31 非线性消除的缺点问题思考：问题思考：约束条件：约束条件：通过消除通过消除y y求解，得到下面等式：求解，得到下面等式：很明显，随着很明显，随着x x趋近负无穷时，趋近负无穷时，h(x)h
9、(x)趋近负无穷。盲目应用这个转换，趋近负无穷。盲目应用这个转换，得到这个问题无线，但是这个问题不能忽略约束条件（得到这个问题无线，但是这个问题不能忽略约束条件（x-1x-1）3 3=y=y2 2，这，这个含蓄的表明个含蓄的表明x1x1界值，这个解是有效的。因此，如果希望消除界值，这个解是有效的。因此，如果希望消除y y，必，必须加入须加入x1x1这个界值。这个界值。这个这个问题说明了用非线性消去变量，可能导致很难追踪错误的结果。基问题说明了用非线性消去变量，可能导致很难追踪错误的结果。基于这个原因，大多数最优化算法中不用非线性消去法。相反，许多约束于这个原因，大多数最优化算法中不用非线性消去
10、法。相反，许多约束条件的线性的算法会用到消去法去解一些简单问题。现在就系统的概述条件的线性的算法会用到消去法去解一些简单问题。现在就系统的概述下用线性约束去得到变量消除的目的。下用线性约束去得到变量消除的目的。第10页/共50页15.32 用线性约束简单消去思考线性函数的约束条件的最小化问题，约束条件是线性等式约束：约束条件：A A是是一一个个mnmn的的矩矩阵阵，mnmn。简简单单起起见见假假设设A A是是满满秩秩（假假如如情情况况不不是是这这种种情情况况，得得到到这这个个问问题题要要么么矛矛盾盾，要要么么约约束束条条件件多多余余的的，能能删删除除而而不不影影响响问问题题的的解解)在在这这种
11、种假假定定下下，我我们们可可以以找找到到线线性性独独立立矩矩阵阵的的m m列列的的一一个个子子集集。如如果果将将这这些些列列向向量量组组合合到到一一个个 的的B B矩矩阵阵，定定义义一一个个 的的P P置置换换矩矩阵阵。矩矩阵阵是将这些列与的第一个是将这些列与的第一个 列进行交换的矩阵，列进行交换的矩阵，表达式表达式:N N表示矩阵表示矩阵n-mn-m剩余列。剩余列。(这里的注释和第这里的注释和第1313章一致，讨论线性规划背章一致，讨论线性规划背景的相似概念景的相似概念)第11页/共50页定义下面形式下的子向量：(15.8)xB为基变量，B为基矩阵。注意PPT=I可以将约束条件Ax=b改写如
12、下：重排这个式子，通过下面的表达式可以减少所给的基变量：(15.9)从而，通过选择任意xN值，计算约束条件Ax=b的可行点，然后可以通过(15.9)设置xB。因此，(15.4)问题和非约束问题等价。(15.10)上述讨论说明了线性等式的约束条件的非线性最优化问题是从数学上述讨论说明了线性等式的约束条件的非线性最优化问题是从数学观点来的，非约束问题观点来的，非约束问题同样，下面就讨论非约束问题同样，下面就讨论非约束问题第12页/共50页15.34 线性等式的非约束问题的非线性最优化思考：（15.11a）约束条件：(15.10)定义转置矩阵P得 的组成从新排列，xT=(x3，x6，x1，x2，x4
13、，x5)T，得到AP矩阵的系数:基矩阵B是对角阵，因此，很容易求取转置(15.12)第13页/共50页替换替换(15.11a)(15.11a)中的中的x3x3，x6x6，问题，问题变成如下：变成如下：(15.13)(15.13)从系数矩阵从系数矩阵(不含有不含有X3X3和和X6X6两个变量两个变量)中选择其它两列中选择其它两列作作(15.11b)15.11b)系系统中消除的基础。然而，这些选择，统中消除的基础。然而，这些选择，B-1NB-1N将会变得更复杂将会变得更复杂。用用高斯消元法选择一组高斯消元法选择一组m m非独立列，在线性代数中的用语，能计算出非独立列，在线性代数中的用语，能计算出这
14、个矩阵的行阶梯型，选择中心轴列做为基矩阵的列。理想情况下，这个矩阵的行阶梯型，选择中心轴列做为基矩阵的列。理想情况下，希望希望B B矩阵很好分解和适定性。为了这个目的，用稀疏高斯消去算法矩阵很好分解和适定性。为了这个目的，用稀疏高斯消去算法去，保持稀疏、控制舍入误差。去，保持稀疏、控制舍入误差。第14页/共50页从(15.8)和(15.9)中可以看出在线性约束条件(15.6)中任意可行点 可以被写成：(15.14)(15.15)注意注意 z z有有 n-mn-m线性非独立列线性非独立列(由于在由于在低维低维中存在单位矩中存在单位矩阵的存在阵的存在)满足满足AZ=0AZ=0因此因此，Z Z是空矩
15、阵是空矩阵A A的基础矩阵。的基础矩阵。加加上上Y Y和和Z Z的列组成是一个线性的列组成是一个线性非独立集非独立集。我们。我们也可以看到也可以看到 是线性约束是线性约束条件一条件一个特解个特解.第15页/共50页换句话说，这个简单消去法说明了可行点可以作为Ax=b(15.14的第一项)的特解加上沿着约束条件(15.14的第二项)的空集(或者相切)总的概括。这(15.13)，(15.14)的关系表明特解Yb是从控制x的n-m个在点的组成，别的 部分是松弛的，直到它们满足约束条件；Yb的特解有时称作坐标松弛步长。见图15.3坐标松弛步长Yb通过选择不基矩阵B去成为A矩阵的第一列，若果选择B作为A
16、的第二列，那么坐标松弛步长将沿着X2轴。简单消去法不费时，但是数值不稳定会产生。如果图15.3中这个可行集是由几乎平行与X1轴的一条线组成的话，沿着这个坐标轴的坐标松弛是一个比较大的数量级。计算x作为不同的大矢量，给出数值取消。在这种情况下选择沿着x2轴的特解会比较好，也就是说选择不同的基。因此，一般情况下，选择最好的基底并不是一个简单的任务。当这个基矩阵 约束条件很少时，在定义 过程中会引起数值错误。为了克服过分协调松弛步长的危险。我们可以定义这个特解Yb作为约束条件的最小基准步长。这种方法是现在所描述的纵多消去法中的特殊情况。第16页/共50页15.35 线性约束条件的一般消减法对(15.
17、14)和（15.15）归类，选择矩阵YRnm和ZRn(n-m)，具有以下性质：(15.16)这些属性表明，正如（15.15）Z的列是空矩阵A的基底。因为A有满秩，所以AY I Z=AY I0，所以AY矩阵也是非奇异矩阵，现在表示线性约束Ax=b任何形式的解，如下：(15.17)对向量XYRm和xZRn-m，通过15.17的取代到约束条件Ax=b得到：因此通过非奇异矩阵，可以直接被写成下式：(15.18)通过代替表达式(15.17)，得到任意一个向量 的形式:(15.19)第17页/共50页xzRn-m的任意选择满足约束条件Ax=b。因此，这个问题(15-6)可以被重新当做如下的非约束问题：(1
18、5.20)理想的，选择Y使AY尽可能的满足Ax=b条件，因为它需要对这个因式分解给出特解Y（AY）-1b。用一个AT的QR因式分解来计算Y和Z，AT有如下形式为：(15.21)Q1 Q2是正交矩阵。子矩阵Q1和 Q2有正交列，它们分别为nm和n(n-m)，而R是nm的上三角矩阵和非奇异矩阵，是一个mm矩阵。（在附录(A.54)详细的讨论。）做如下定义：(15.22)因此，Y和Z的形式是Rn的一个正交基矩阵。假如我们将(15.20)展开并做一部分从排列，我们可以得到:第18页/共50页因而，Y和Z有期望性质，这样AY的条件数和R一样，A也是一样的。从(15.19)中可以看出Ax=b的任何解能被表
19、示成:对xz向量，计算这R-T-Tb并不是很费时，用单一的三角代换就得到了简单的估算表明这个特征值Q1R-T-Tb能被写成(15.22)因此，这个约束条件Ax=b的最小范数解是下式的解：(15.23)第19页/共50页这是最小值范数解，图(15.5)给出了这步的图解。从数值稳定性的观点来看，消从数值稳定性的观点来看，消去法通过正交基矩阵去法通过正交基矩阵(15.22)(15.22)是比较理想的。主要耗时的是是比较理想的。主要耗时的是在在(12.21)QR(12.21)QR因子因式分解中因子因式分解中与下降方法有关计算与下降方法有关计算。不好不好的是，在这个问题中的是，在这个问题中 矩矩阵大和稀
20、疏，在简单消去法中，阵大和稀疏，在简单消去法中，计算稀疏计算稀疏QRQR因子因式分解过程因子因式分解过程比稀疏高斯消去法更耗时。因比稀疏高斯消去法更耗时。因此，别的一些消去分类在这两此，别的一些消去分类在这两种方法中寻求平衡而得到了发种方法中寻求平衡而得到了发展；可以看练习展；可以看练习15.7.15.7.第20页/共50页15.36 不等式约束的作用如果不等式约束呈现出等式约束时变量消去法并不总是有效地。例如，问题(15.10)，(15.11)有附加约束条件x0，消去变量x3和x6后，就能只剩下在(15.13)中的最小化函数问题，约束条件是：因此，消去等式约束(15.11)的作用是使得不等式
21、约束要比简单边界x0复杂。对许多算法来说，这个转换并不是没有一点益处。然而，假如问题(15.11)包含一般不等式约束条件3x1+2x31，这个(15.12)消去法，转换问题将会变成(15.12)中的函数最小化问题在，不等式约束条件：（15.23）在等式约束消去之后，这个不等式约束并不能变的很复杂，因此，消去法是值得去做的。第21页/共50页15.4 优化函数和滤波对于非线性规划问题(15.1)，的优化函数是受欢迎的选择是这个l1罚函数函数被下式定义为罚函数函数被下式定义为：（15.24）注释z-=max0，-x。正标量罚参数，这决定了分配满足相对目标函数的最小的约束条件的权重。由于一些列球型参
22、数能确定优化函数，这个非线性规划问题(15.1)的解是(x，)的一个小域。注意这个l1优化方程1不可微的，因为这个绝对值和-函数是存在的，但是它有重要精确性质。第22页/共50页15.43 准确的优化函数假如对任意*中有一个正的标量*，这个优化函数（x，）就能确定，任何一个非线性规划问题(15.1)的局部解是（x，）的局部最小值。在定理17.3展示的那样，在一定的假设，l1优化方程（x，）确定，*的极限值是被给i*表示和最优解x*有关的拉格朗日多项式。因为最佳拉格朗日乘数是建立在包含调整罚函数参数的规则的l1优化方程的算法，然后事先不知道，有理由相信这不是足够大的（或者不是极大）。这些规则建立
23、在最优化算子的选择，将在下一章讨论。第23页/共50页15.44 精准l2函数的增广拉格朗日对于等式约束的情况，优化函数用如下形式：这个函数不可微分，因为2-规范不是平方值，其衍生类在x=0没有定义。一些优化函数不仅平滑而且精确。确保属性持有，必须在优化函数中加附加条件。对等式约束条件问题，弗莱彻的增广拉格朗日，通过下面的给定：第24页/共50页0是罚参数A（x）表示c(x)的雅克比行列式，尽管这个优化函数有一些有趣的理论属性，它有实际的限制，包括在（15.27）（x）求解代价。与众不同的优化函数是在x，的增广拉格朗日，对等式约束问题有如下形式：第25页/共50页通过比较LA（x+，+，）和当
24、前迭代（x，）的值来评估测试点的合格性，严格的讲，感觉上LA不是优化方程，一般来讲非线性规划问题的解（x*，*）不是LA（x+，+，）的最小值，仅仅是一个驻点。尽管一些连续的二阶规划方法用LA通过修改模型和参数成功的作为优化方程，但还是不考虑这做一个优化方程，相反，把焦点主要放在非光滑精确罚函数12。第26页/共50页通过线性搜索算法产生的实验步长x+=x+p，如果这在优化方程（x，）产生足够减小，那么这算法是可接受的。方法一：定义这个概念类似于在非约束最优化（3.4）条件，然而在这一步这个数量不能相对太小以致不能预测函数的变化。L1和l2优化函数不可微，但有方向导数。（看（A.51）背景的方
25、向导数）直接写（x，）在p方向的方向导数：D（x，），p）用线性搜索法，足够减少的条件要求是迭代步长参数0，足够小以致如下不等式对于（0，1）满足：第27页/共50页p经过p步长后，信赖域方法常用二阶模型q(p)来评估优化函数，如18.5部分。足够的减少条件能用这个模型减少的形式规定，如下：第28页/共50页15.45 滤波滤波技术是一步接受原理建立在多目标最优化问题的基础上。从观测非线性规划推导有两个目的：目标函数的最小化函数和满足约束条件。定义不可行域估量：把这两个目标写成：不同于优化函数，这结合所有问题到单一的最小化问题，滤波方法在（15.32）分开保持这两个目标。如果 不受控前一个通过
26、算法产生的，滤波方法接受测试步长x+做一个新的迭代，这些概念被定义如下：第29页/共50页定义15.2A.fkfl和hkhl则，（fk，hk）是被（fl，hl）控制，B.滤波是对（fl，hl）的列表，C.如此没有任何一对占主导地位，迭代xk是对滤波可接受的。当迭代xk是对滤波可接受，我们一般加（fk，hk）到滤波，移除被（fk，hk）支配的任何对，图示15.6展示了滤波中每一对（fl，hl）用黑点表示。每一个滤波形成一个矩形区域，这个结合定义一个组队对滤波不可接受。更特殊的，如果（f+，h+）在实线的下面或者左边（图15.6），测试点x+是可接受的。比较滤波和优化函数方法，在图15.7绘制了组
27、对（f，h）的轮廓线，这样f+uh=fk+uhk，xk是当前迭代，该区域线的左边和双集一致，减少优化函数（x，=f(x)+h(x)，很明显，这个集完全不同与接受点。如果通过线搜索方法所产生一个试验步长x+=xk+kpk给出给一对(f+，h+)，这是可接受的滤波波，设置xk+1=x+，否则，执行回溯线性搜索。在信赖域方法中，如果滤波这步骤不可行，信赖区域减少，计算新步骤。第30页/共50页当迭代xk是对滤波可接受，我们一般加（fk，hk）到滤波，移除被（fk，hk）支配的任何对，图示15.6展示了滤波中每一对（fl，hl）用黑点表示。每一个滤波形成一个矩形区域，这个结合定义一个组队对滤波不可接受
28、。更特殊的，如果（f+，h+）在实线的下面或者左边（图15.6），测试点x+是可接受的。第31页/共50页如果通过线搜索方法所产生一个试验步长x+=xk+kpk给出给一对(f+，h+)，这是可接受的滤波波，设置xk+1=x+，否则，执行回溯线性搜索。在信赖域方法中，如果滤波这步骤不可行，信赖区域减少，计算新步骤。这个滤波技术需要作一些改进，从而获得全局收敛性和良好的实用性能。首先，我们需要确保我们不接受一点(f、h)对是非常接近当前的一对(fk，hk)或在滤波中的其他对。通过修改可行准则和实现充分下降条件。滤波是接受测试迭代x+，如果滤波中所有(hf，hj)，有如下条件：第32页/共50页(0
29、，1)。虽然这条件在实践使用中有效，说=105，分析的目的，通过下面的式子，它可能有利于取代第一个不平等的。通过线性搜索方法生成的搜索方向的可能需要足够小步长k，这样滤波才可行。这种现象可以导致算法陷入停滞和失败。为了防止这种情况，如果回溯线搜索生成一个步长比极值min小，该算法切换到可行性恢复阶段。第33页/共50页可行性恢复阶段主要目的是减少相反的约束条件，也就是说，找到一个近似的解决问题的办法。现在列举滤波步骤，假设由信赖域方法生成迭代的，参见18.5节信赖域方法约束优化讨论。算法15.1(一般滤波方法)选择起点x0，初始信赖域半径0设置k0，重复，直到满足收敛测试第34页/共50页If
30、 步骤生成子问题不可行用可行性恢复阶段计算xk+1else计算试验迭代x+=xk+pk If(f+，h+)滤波可以接受设置xk+1=x+并添加(fk+1，hk+1)滤波选择k+1，k+1k从滤波中删除所有主导对由(fk+1，hk+1)Else丢弃这一步骤中，第35页/共50页设置xk+1=xk选择k+1kEnd ifEnd if kk+1，end repeat这个简单的滤波步骤的其他改进用于实践，建立在算法的选择上，将在后续的章节中讨论。第36页/共50页15.5 马洛托斯现象一些算法基于优化函数或滤波可能在迅速收敛失败，因为丢弃朝着解的方向进的步骤。这种不良现象通常被称为马洛托斯效应，因为它
31、是被马洛托斯199首次发现。通过下面的例子说明，在哪些步骤pk，如果接受这将产生二阶收敛，导致目标函数值和违反约束条件的增加第37页/共50页考虑问题可以验证(见图15.8)最佳解是x=(1，0)T，对应的拉格朗日乘子*=3/2，让我们考虑xk=(cos，sin)形式的迭代xk，这对于任何值可行。假设算法的计算步骤如下:测试点第38页/共50页通过使用基本三角转换，有因此因此，这一步的方法的解与Q二阶收敛速度一致。然后，有因此，在图15.8中可以看到，这一步目标函数值和约束违反增加。这种行为发生在任何非零值，即使任意初始点接近解。第39页/共50页在上面的示例中，任何算法，需要优化函数减少的形
32、式：h()是一个非负函数，满足h(0)=0，将丢弃(15.35)好步骤。(这样的优化函数的例子包括1和2罚函数)。(15.35)步骤也将被上述的滤波原理丢弃，因为(f(xk+pk)，h(xk+pk)是由(fk，hk)控制。因此，所有这些方法有马洛托斯现象。第40页/共50页如果没有采取补救措施，马洛托斯现象可能从解中通过干扰好步骤或防止超线性收敛，减缓优化方法。避免马洛托斯现象的策略包括如下：I.用不受马洛托斯现象的优化函数，。例子是弗莱彻的增广拉格朗日函数(15.26)。II.用二阶校正，pk增加步pk，在c(xk+pk)计算，减少了约束违反。III.允许优化函数增加某些迭代，也就是说，可以
33、使用非单调。在下一节中将讨论最后的两种方法。第41页/共50页15.6 二阶校正和非单调技术通过添加修正项，减少了约束违反，各种算法能够克服马洛托斯现象有关难题。用等式约束条件问题描述这方法，约束条件是c（x）=0，Rn趋近RII给定步长pk，pk的二阶校正步长定义：Ak=A(xk)是c在xk雅可比。注意pk的属性，在xk+pk点它满足了线性化的约束c，也就是说：事实上，pk是这个等式的最小范数解。第42页/共50页校正步长pk的效果是对IxkxI3的规则减少Ic(x)I量，主要步骤pk满足Akpk+pk+c(xk)=0。这个估计表明，从xk到xk+pk+pk将减少优化函数，至少靠近解。此增强
34、功能包括约束函数c在xk+pk额外的评估和从(15.36)所需的线性代数来预订步长pk。现在描述用线性搜索和二阶修正步长的优化函数算法。假设pk和搜索方向计算的罚参数k，pk是优化函数下降方向，也就是说，D(xk，)，pk)0。在18和19章，将讨论如何完成这些目标。算法的主要特征是，如果完整的步骤k=1，在优化函数不会产生满意的下降，在回溯沿着pk原来的方向之前尝试二阶校正步骤。第43页/共50页算法15.2(用二阶校正的通用算法)。选择参数(0，-0.5)和12与0 1 2(xk)(*回到xk和沿着pk*搜索)找到k这样(xk+3)(xk)+kD(xk)，pk)，计算xk+3=xk+kpk
35、，kk+3，ss k，else从xk+2计算pk+2方向找到k +2这样(xk+3)(xk+2)+k+2d(xk+2)，pk+2)，设置xk+3xk+2+k+2pk+2，kk+3，ssk，end endend（repeat）第48页/共50页算法没有要求S集，引用只只是识别迭代，足够的优化函数得到减少。注意，至少迭代的三分之一在S有自己的指数。利用这个事实，可以展示各种约束最优化方法，用观察法得到全局收敛。还表明，足够大的k，步长k=1和收敛速度是超线性。在实践中，它有利因素是在优化函数允许增加更多迭代。T值如5或者8是典型的。正如这样的讨论表明，观测法的小心执行有一定程度的复杂性，但是增加的复杂性是值得的，因为方法具有良好的实用性能。观察法的潜在优势是二阶校正策略上是它可能需要更少的约束函数评估。在最好的情况下，大多数的步骤将是完整的步骤，很少会需要返回到较早的点。第49页/共50页感谢您的观看！第50页/共50页