《高级运筹学》无约束非线性规划课件.ppt

1、无约束非线性规划无约束非线性规划 20152015年年5 5月月研究生研究生高级运筹学高级运筹学课件课件本章内容本章内容第一节：最优性条件第一节：最优性条件第二节：一维搜索第二节：一维搜索第三节：最速下降法和共轭梯度法第三节：最速下降法和共轭梯度法第四节：牛顿法和拟牛顿法第四节：牛顿法和拟牛顿法第一节第一节:最优性条件最优性条件本章仅讨论如下无约束非线性规划问题：min()nx Rf x假定f(x)具有二阶连续偏导数。现有多元函数 f(x1,x2,xn),若点 x(0)=(x10,x20,xn0)T 存在一邻域(x(0),使对任意x(x(0),均有f(x(0)f(x),则称 x(0)是 f(x

2、)的局部极小点。一、一、无约束极小化问题的最优性条件无约束极小化问题的最优性条件无约束极小化问题的最优解必是f(x)的局部极小点。(0)()0f x利用局部极小点的一阶必要条件，求多元函数极值问题往往化成求解 局部极小点的一阶必要条件：设函数f(x)在点x处可微，且x(0)为局部极小点，则必有()0f x即12()0()0()0nf xxf xxf xx的问题该方程组很难求解，一般不采用此法。求解无约束非线性规划问题常用数值解法中的迭代法1.迭代法的基本思想：给定f(x)的极小点位置的一个初始估计x(0)，依次计算产生一系列点x(k)（1,2,),希望点列x(k)的极限x*就是f(x)的一个极

3、小点。计算公式：(1)()()kkkkxxd其中:kkd搜索方向步长不同算法的区别在于得出搜索方向和步长的方式不同。二、迭代法2.选择搜索方向和步长的原则：（1）目标函数值逐次减小，这种算法称为下降算法。(0)(1)()()()()kf xf xf x（2）算法具有收敛性。即：序列中的某一点，或序列的极限点是函数的极小点。3.迭代法的基本步骤：(1)选择初始点x(0);(2)如已得到的迭代点x(k)不是最优解，确定从x(k)点出发 的搜索方向d(k)，使f(x)沿d(k)方向可以找到x(k+1)，目标函数有所下降。(3)在射线x(k)+d(k)(0)上选取步长k,使()()()()()kkkk

4、f xdf x从而确定下一个点(1)()()kkkkxxd(4)检验新得到的点x(k+1)是否为最优或近似最优，若是则停止迭代，否则继续迭代。检验方法：(1)|()|kf x第二节：一维搜索第二节：一维搜索在求解无约束非线性规划的算法中，要进行一系列如下格式在求解无约束非线性规划的算法中，要进行一系列如下格式的迭代计算的迭代计算:(1)()()kkkkxxd当方向当方向d(k)给定，求最佳步长给定，求最佳步长 k,就是求一元函数就是求一元函数()()()()kkf xd 的极小点问题的极小点问题。这一过程称为一维搜索这一过程称为一维搜索。一、一维搜索的定义一、一维搜索的定义二、一维搜索的方法：

5、二、一维搜索的方法：1.精确线搜索，即解方程：精确线搜索，即解方程：()0dd 2.试探法；按照某种方式找试探点，通过一系列试探试探法；按照某种方式找试探点，通过一系列试探点的比较确定极小点。点的比较确定极小点。3.函数逼近法：用较简单的曲线近似代替原来的曲线，函数逼近法：用较简单的曲线近似代替原来的曲线，用近似曲线的极小点来估计原曲线的极小点。用近似曲线的极小点来估计原曲线的极小点。三、一维搜索的基本思想：三、一维搜索的基本思想：1.1.单谷单谷(峰）区间峰）区间 在给定区间内仅有一个谷值在给定区间内仅有一个谷值(极大或极小极大或极小)的函数称为单的函数称为单谷函数，其区间称为单谷区间谷函数

6、，其区间称为单谷区间xabx*f(x)函数值：大小大图形：高低高单谷区间中一定有极小点2.2.一维搜索的基本思想一维搜索的基本思想 （1 1）确定初始单谷区间）确定初始单谷区间 （2 2）根据区间消去法原理逐步缩小此区间）根据区间消去法原理逐步缩小此区间 （3 3）根据迭代精度要求确定最优解的近似值）根据迭代精度要求确定最优解的近似值*1,()2kkkkbaxab(1)确定初始单谷区间的进退法确定初始单谷区间的进退法 对对f(x)任选一个初始点任选一个初始点a1及初始步长及初始步长h h，通过比较这，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函两点函数值的大小，确定第三点位置，比

7、较这三点的函数值大小，确定是否为数值大小，确定是否为 “高高低低高高”形态形态Step1.Step1.选定初始点选定初始点a1，初始步长，初始步长h，计算，计算 f 1f(a1),f 2f(a1+h)Step2.Step2.比较比较f 1和和f 2。（a）如）如f 1 f 2,向右前进；加大步长向右前进；加大步长 h 2 h，转，转step3 向前探测向前探测 （b）如）如f 1 f 2,向左后退；向左后退；h-h，转（，转（3）向后探测，）向后探测，（c）如）如f 1 f 2，极小点在，极小点在a1 a1 h 之间。之间。Step3.产生新的探测点产生新的探测点 a3a1h，f3f(a3);

8、Step4.比较函数值比较函数值 f2与与f3：（a）如）如f20时，时，a,b=a1,a3;hf3,加大步长加大步长 h2 h，a1=a2,a2=a3,转转step3 继继 续探测续探测(2)消去法的基本原理消去法的基本原理单谷区间确定后，假定在区间内任取两点单谷区间确定后，假定在区间内任取两点a1,b1;且且 a1 b1。计算函数值，计算函数值，f1f（a1），），f2f（b1）有下列三种情况有下列三种情况：f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1综合为两种情况：综合为两种情况：若若f(a1)f(b1),则取则取 a,b1为缩短

9、后的搜索区间。为缩短后的搜索区间。若若f(a1)f(b1),则取则取 a1,b为缩短后的搜索区间。为缩短后的搜索区间。四、四、黄金分割法黄金分割法 （0.6180.618法）法）黄金分割律是公元前六世纪，希腊的大数学家毕达哥拉斯发现黄金分割律是公元前六世纪，希腊的大数学家毕达哥拉斯发现的：如果把一条线段分成两部分，长段和短段的长度之比是的：如果把一条线段分成两部分，长段和短段的长度之比是1:0.6181:0.618，整条线段和长段的比也是，整条线段和长段的比也是1:0.6181:0.618时，才是和黄金一时，才是和黄金一样最完美的分割，进行分割的这个点就叫黄金分割点样最完美的分割，进行分割的这

10、个点就叫黄金分割点 黄金分割法适用于黄金分割法适用于a,ba,b区间上的任何单谷函数求极小值问区间上的任何单谷函数求极小值问题。对函数除要求题。对函数除要求“单谷单谷”外不作其他要求，甚至可以不连续。外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广因此，这种方法的适应面相当广.黄金分割法也是建立在区间消去法原理基础上的试探方法。黄金分割法也是建立在区间消去法原理基础上的试探方法。在搜索区间在搜索区间a,ba,b内适当插入两点内适当插入两点 1,2，将区间分成三段；，将区间分成三段；利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索利用区间消去法，使搜索区间缩小，通过迭代计算，使搜

11、索区间无限缩小，从而得到极小点的数值近似解区间无限缩小，从而得到极小点的数值近似解黄金分割法还要求在保留下来的区间内再插入一点所形成黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布的区间新三段，与原来区间的三段具有相同的比例分布1 2 将区间分成三段21510.6182 黄金分割法要求插入两点：黄金分割法要求插入两点：111222(1)(),()(),()abaffabaff黄金分割法区间消去示意：aba1a2f(a1)f(a2)aba1a2f(a1)f(a2)黄金分割法的搜索过程：黄金分割法的搜索过程：1 1）给出初始搜索区间及收敛精度）给出

12、初始搜索区间及收敛精度，将，将 赋以赋以0.6180.618。2 2）按坐标点计算公式计算）按坐标点计算公式计算 1，2;并计算其对应的函数值并计算其对应的函数值f1,f2。3 3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。个新的试验点及其函数值。如果如果f1f2,则新区间则新区间a,a,2 2,令令b=b=2,2=1,f2=f1,记记N0=0;如果如果f1 f2,则新区间则新区间 1,b,令令 a=1,

13、1=2,f1=f2,记记N0=1;4 4）若）若b-a-1.1252-0.2360.2360.5281-1.125-1.12540.0560.2360.3480.528-1.125-1.12560.1680.2360.2790.348-1.125-1.12370.1680.279经过经过6次迭代，次迭代，b-a=0.1110.16,满足精度要求，取满足精度要求，取1(0.1680.279)0.232x 问题的精确最优解为问题的精确最优解为 0.25。五、牛顿法五、牛顿法牛顿法的基本思想：在迭代点附近，用二次函数（目标函牛顿法的基本思想：在迭代点附近，用二次函数（目标函数的二阶泰勒展开式）近似目

14、标函数数的二阶泰勒展开式）近似目标函数f(x),进而求出极小进而求出极小点的估计值。点的估计值。牛顿法是函数逼近法中的一种。牛顿法是函数逼近法中的一种。考虑问题考虑问题：1min()Rf 212kkkkkffff 在迭代点在迭代点 k k附近，令附近，令然后以二次函数然后以二次函数()的极小点作为的极小点作为f()极小点的一个近似，极小点的一个近似，根据极值的必要条件根据极值的必要条件()()()()0kkkff 得1kkkkffkkkff以此作为下一个迭代点，即以此作为下一个迭代点，即牛顿法的迭代公式牛顿法的迭代公式()()()()0kkkff 对牛顿法的几何解释对牛顿法的几何解释f()的极

15、小点*应满足极值必要条件f(*)=0。所以求f()的极小点也就是求解方程f()=0 的根。在k处用一抛物线k()代替曲线f()相当于用一斜线k()代替曲线f()。抛物线顶点k+1 作为一个近似点应处于斜线k()与 轴的交点处。这样各个近似点是通过对f()作切线求得与轴的交点而找到的，所以牛顿法又称作切线法。0111(1)0(2)(),()()(3)()(4)|,(5)(5)1,(2)kkkkkkkkkkffffkk*给定、，令计算求 若则求得近似解=停止计算 否则转令转牛顿法的计算步骤牛顿法的计算步骤牛顿法的特点 牛顿法最大的优点是收敛速度快。但是在每一点处都要计算函数的二阶导数，因而增加了每

16、次迭代的工作量。特别是用数值微分代替二阶导数时，舍人误差会影响牛顿法的收敛速度。牛顿法要求初始点选得比较好（离极小点不能太远），否则有可能使极小化序列发散或收敛到非极小点。2.minxex1.用0618法求 在（0，1）上的极小点，精度 取0.03.432(0)(0)min461642.53xxxxxx2.用牛顿法求 分别 取初始点=和=练习练习第三节：最速下降法和共轭梯度法求解无约束非线性规划问题的迭代算法包含两个关键步骤，求解无约束非线性规划问题的迭代算法包含两个关键步骤，得到迭代点得到迭代点x(k)后：后：(1)如何选择搜索方向如何选择搜索方向d(k)？(2)在选定的搜索方向上，如何进行

17、一维搜索？（已介绍）在选定的搜索方向上，如何进行一维搜索？（已介绍）常用的确定搜索方向的方法。常用的确定搜索方向的方法。最速下降法最速下降法共轭梯度法共轭梯度法牛顿法牛顿法拟牛顿法（变尺度法）拟牛顿法（变尺度法）一、最速下降法一、最速下降法问题问题：在x(k)处，沿什么方向d(k)，函数f(x)下降最快？结论结论：负梯度方向是函数的最速下降方向。最速下降法就是以x(k)处的负梯度方向作为搜索方向，即令()()()kkdf x 求解问题1min()nx Rf xfC最速下降法的具体步骤：最速下降法的具体步骤：(1)()()()()()()(1)()()1.,1;2.(),*,();3.,1,2.

18、kkkkkkkkkkxkf xxxdf xxdxxdkk 选选定定初初始始点点确确定定精精度度要要求求，令令若若则则停停 输输出出否否则则令令在在处处沿沿方方向向作作一一维维搜搜索索得得 转转其中，在第三步中，可以直接使用精确线搜索其中，在第三步中，可以直接使用精确线搜索。()()argmin()kkkf xd即令()()()(1)()()0kkkk Tkdf xddf xd()()()0kkdf xdd可以解出k.由可以看出，d(k)和d(k+1)是正交的。例例2 用最速下降法求用最速下降法求 的极小点。迭代两的极小点。迭代两次，计算各迭代点的函数值、梯度及其模，并验证相邻两次，计算各迭代点

19、的函数值、梯度及其模，并验证相邻两个搜索方向是正交的。个搜索方向是正交的。221212(,)4f x xxx解：设初始点为解：设初始点为(0)(1,1)Tx11222(,)8xf x xx(0)(1,1)Tx由00(0)0()2 8()8.24621()28TTf xf xdf x（）（）（）（，）（-，-）(1)(0)(0)0 xxd其中0由(0)(0)22min()min(12)4(1 8)f xd利用一阶必要条件(0)(0)()4(12)64(1 8)520680df xdd 0680.13077520解得(1)120.738460.13077180.04616x 11(1)1()1.4

20、76920.36923()1.52237()1.47692 0.36923TTf xf xdf x（）（）（）（，）（-，）(2)(1)(1)1xxd由(1)(1)()0df xdd求得10.42500(2)0.738461.476920.110760.425000.046160.369230.11076x22(2)2()0.22152 0.88608()0.91335()0.221520.88608TTf xf xdf x（）（）（）（，）（-，-）验证相邻两个搜索方向的正交性(1)(0)()(1.47692)(2)(0.36923)(8)0Tdd(2)(1)()(0.22152)(1.47

21、692)(0.88608)(0.36923)0Tdd 最速下降法的优点最速下降法的优点1.程序设计简单，计算量小，存储量小，对初始点没有程序设计简单，计算量小，存储量小，对初始点没有特别要求特别要求2.有着很好的整体收敛性，即使对一般的目标函数，它有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛也整体收敛最速下降法的缺点：最速下降法的缺点：最速下降法是线性收敛的，并且有时是很慢的线性收敛最速下降法是线性收敛的，并且有时是很慢的线性收敛原因：虽然最速下降（负梯度）方向确实是从当前迭代点出发作微小移动时函数值下降最快的方向，然而由于采用精确线搜索，每次迭代点的移动并非总是微小的，因而迭代过

22、程中并未得到使函数值“最速下降”的好处。相邻两次迭代的搜索方向彼此正交，容易产生锯齿型迭代移动，这种绕弯路向最优解移动的路径，形象的表明最速下降法的收敛速度是不理想的。结结 论：论：最速下降法是基本算法之一，而非有效的实用算法最速下降法是基本算法之一，而非有效的实用算法最速下降法的本质是在迭代点处用线性函数来近似目最速下降法的本质是在迭代点处用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近高阶逼近练习：用最速下降法求解 22112212min243xx xxxx取初始点x(1)=(1,1)T,迭代两次。二、共轭梯度法二、共轭

23、梯度法共轭梯度法是针对二次函数121()(,.,)2TTTnf xx Qxb xcxx xx的无约束非线性规划问题，考虑出一种搜索方向的合理选取方法，然后形式地推广到一般可微函数。对于变量分离的函数1122()()().()nnfxfxfxfx从任意一点x(1)出发，分别沿着每个坐标轴方向进行一维搜索（共进行n次搜索）以后，一定能得到minf(x)的最优解。对于二次函数121()(,.,)2TTTnf xx Qxb xcxx xx如果Q为实对称正定矩阵，则可以选择一组基p1,p2,pn,满足0()Tijp Qpij在新的基下，f(x)就成为变量分离的形式。于是，从任何一个初始点x(1)出发，分

24、别沿着每个pi方向作线搜索，经过一轮后，肯定能得到最优解。定义：设Q为n 阶实对称正定矩阵，若n维方向x和y满足0Tx Qy 则称方向x和y是Q-共轭的。问题问题：如何构造出两两Q-共轭的方向？在每个迭代点x(k)处，以负梯度-f(x(k)和前一个搜索方向pk-1的适当组合，构成和前面k-1个搜索方向p1,p2,pk-1均两两Q-共轭的搜索方向pk。即：(1)1()pf x(1)1()kkkkpf xp(1)()TkkkTkkp Q f xp Qp其其中中推导过程：1()2TTf xx Qxb xc()f xQxb,()()()nx yRf yf xQ yx，有(1)(1)1(2)()212(

25、),),.(,),.,kkkxpf xxpxpp ppQ 从任意初始点和出发，得到(且非零向量两两 共轭(1)()kkkkxxp令()argmin()kkkf xp其中()(1)(),()0jjjTjjdf xpjpf xd 有(1)()0Tkkpf x(1),()0Tkjjkpf x下面证明，对任意(1)(1)(1)(1)()()()kjkjf xf xQ xx由于(1)(1)(1)(1)()()()kjkjf xf xQ xx(1)(1)(1)(1)(1)()()(1)(2)(1)11()()()()()()()()0TkTjTkjjjjTkkkkjjjkkTTjiiijiijijpf x

26、pf xp Q xxp Q xxxxxxp Qpp Qp (1)()(1)()kkkkkkkkxxpxxp(1)()0kf x当时，令(1)1()kkkkpf xp(1)()TkkkTkkp Q f xp Qp其其中中1,0Tjkjkp Qp可以证明对任意有(1)1(1)()()()0TTkTkkkkkkTkTkkkkp Qpp Qf xp Qpp Qf xp Qp1jk对于(1)()0Tkjpf x()11()jjjjpf xp(1)(1)(1)(1)(1)(1()11()1)1()()()()0()()()()()()TkkTjjkTkTkTkjjjjjTjjf xpf xpfpf xf

27、xpf xf xf xxf x 1()()(01)jkTfjxf xk(1)(1)1()()TTkTTkjkjkjkjp Qpp Qf xp Qpp Qf x(1)1()kkkkpf xp 12,.,-=0Tjkkp ppQp Qp由于两两共轭，因此上式中(1)(1)1(1)(1)()(1)(1)()()=()()()()()()()0TTkkTjjkjjjjkTjjkTjjp Qpp Qf xf xQpf xQ xxf xf xf x 1=00,jTjkp Qp由于因此有1min()2TTf xx Qxb xc求求解解的的共共轭轭梯梯度度法法的的步步骤骤(1)(1)11.,(),1;nxRp

28、f xk 任任选选初初始始点点令令()2.()0,;kf x若若则则停停 否否则则()(1)()(),TkkkkkkkTkkpf xxxpp Qp(1)(1)1()(),TkkkkkkkTkkp Q f xpf xpp Qp 3.1,2.kk转转回回可以证明，在中途不停机的情况下，这样得到的p1,p2,pn，是两两Q-共轭的，因此x(n+1)一定是原问题的最优解。()(1)()(),TkkkkkkkTkkpf xxxpp Qp(1)()0Tkkpf x(1)(1)()kkf xQxb(1)(1)()()()()()0TkTkkkTkTkkkkkkkTkkkkxpxpf xpQxbpQbpQbQ

29、ppf xQp()()TkkkTkkpf xp Qp精确线搜索结果的推导精确线搜索结果的推导对于一般可微函数的f(x)，在每一迭代点x(k)可以近似的视为二次函数()()()()2()()1()()()()()()()2kkTkkTkkf xf xf xxxxxf xxx因此设想利用共轭梯度法也能得到好的效果。此时，式子中的Q应该以x(k)点处的Hesse矩阵代替，计算量太大。解决方法：修改迭代公式，使之不含Q，修改后的计算公式：2(1)2()()()kkkf xf x1min(),f xfC求求解解的的共共轭轭梯梯度度法法的的步步骤骤(1)(1)11.,(),1;nxRpf xk 任任选选初

30、初始始点点令令()2.()0,;kf x若若则则停停 否否则则(1)()()(),argmin()kkkkkkkxxdf xd2(1)(1)(1)()2()()()()kkkkkf xdf xdf x 3.1,2.kk转转回回为了保证算法具有某种收敛性，注意到共轭梯度法的第一步和最速下降法相同，最速下降法具有收敛性。通常采用如下的起点周期性变化的共轭梯度法：从初始点x(1)出发依次用共轭梯度法产生迭代点x(2),x(3),x(n+1)后，以x(n+1)作为新的x(1)，周期性重复以上步骤。由于搜索方向不一定是下降方向，因此，这样做可以减少迭代误差的累积，达到良好的计算效果。例3 用共轭梯度法求

31、解22(0)12min()4,(1,1)Tf xxxx取取解：共轭梯度法的第一步和最速下降法相同，由例2知；00.13077(1)0.738460.04616x(0)(0)02()8pdf x 11.47492()0.36923f x（）1()1.52237f x（）|f(x(1)|较大，还需迭代，下一个搜索方向：(1)100()pf xp(1)000020(),0817.7323040.03408520TTp Q f xQp Qp其其中中11.4769221.545080.034080.3692380.09659p(2)(1)11xxp(1)11min()0.47794af xp(2)0.7

32、38461.5450800.477940.046160.096590 x (2)()0f x停止迭代，x(2)即为所求极小点22(1)1222(1)112211min,(4,4).22min225,(2,2).TTxxxxx xxx1.用共轭梯度法求解下列问题：（）取初始点（）取初始点(1)(1)(2)(2)(2)12(2)2.(),1(1,1,2),()()2,2Tf xddxf xf xxxx 将共轭梯度法用于三个变量的函数第 次迭代的搜索方向为沿作精确线搜索，得到点又设那么按共轭梯度法的规定，从出发的搜索方向是什么？一、牛顿法一、牛顿法第四节第四节 牛顿法和拟牛顿法（变尺度法）牛顿法和拟

33、牛顿法（变尺度法）1min()2TTf xx Qxb xc()f xQxb考虑当Q正定时*1xQ b 对于一般二阶连续可微函数，在x(k)的局部()()()()2()()1()()()()()()()2kkTkkTkkf xf xf xxxxxf xxx当2f(x(k)正定时，*()2()1()()()kkkxxf xf x 据此设计出牛顿法()2()()()()()()kkkf xf xf xxx 2min(),f xfC求求解解的的牛牛顿顿法法的的步步骤骤(1)1.,1;nxRk任任选选初初始始点点()()2()2.(),0,;()()kkkkkgf xgG xf x 计计算算若若则则停停

34、 否否则则计计算算(1)()()1(),kkkkxxG xg令令3.1,2.kk转转回回若f(x)是一元函数，则牛顿法就是用切线法解方程f(x)=0在实际使用牛顿法时，如何合适选取初始点是一个难以在实际使用牛顿法时，如何合适选取初始点是一个难以解决的问题。解决的问题。当当f(x(k)0且且2f(x(k)正定时，正定时，牛顿方向牛顿方向-G(x)-1 g 是一是一个下降方向个下降方向牛顿法的收敛性与初始点的选取有关。若初始点选取牛顿法的收敛性与初始点的选取有关。若初始点选取合适，则收敛很快（至少二阶收敛）。若初始点选择合适，则收敛很快（至少二阶收敛）。若初始点选择不好，则可能不收敛。不好，则可能

35、不收敛。2()()()0TTf xf xf x于是可以把牛顿法中的指定后继点迭代公式于是可以把牛顿法中的指定后继点迭代公式(1)()()1(),kkkkxxG xg修改为，沿方向修改为，沿方向()1()()kkkG xgd作线搜索得后继点，即作线搜索得后继点，即(1)()()()(),argmin()kkkkkkkxxdf xd22()(1)()3(),|()(),*(*)0.kkfCf xxx f xf xxxf x定定理理设设且且正正定定 记记为为由由修修改改牛牛顿顿法法所所得得迭迭代代点点列列若若水水平平集集有有界界 则则必必有有聚聚点点且且任任何何聚聚点点满满足足二、拟牛顿法（变尺度法

36、）二、拟牛顿法（变尺度法）修改牛顿法具有全局收敛性，但每步确定搜索方向时都修改牛顿法具有全局收敛性，但每步确定搜索方向时都要计算要计算Hesse矩阵及其逆矩阵矩阵及其逆矩阵()2()1()()()kkkdf xf x 1959年年,Davidon提出设想仅用每次迭代中得到的梯度信息提出设想仅用每次迭代中得到的梯度信息来近似来近似Hesse矩阵，基于此导致了一类非常成功的拟牛顿矩阵，基于此导致了一类非常成功的拟牛顿法法算法原理：算法原理：将确定搜索方向将确定搜索方向d(k)公式中的公式中的 2f(x(k)-1 用用n阶矩阵阶矩阵Hk代代替，从而在第替，从而在第k步迭代时，步迭代时，()()()(

37、1)()()(),kkkkkkkdHf xxxd k由线搜索得到。初始点由线搜索得到。初始点x(1)和初始矩阵和初始矩阵H1是预先给定是预先给定的，的，Hk在迭代中利用已得迭代点及目标函数值，最多再在迭代中利用已得迭代点及目标函数值，最多再利用一阶导数按某种规则获得。利用一阶导数按某种规则获得。确定确定Hk的一种自然想法是，将的一种自然想法是，将Hk 作为作为 2f(x(k)-1 的近似的近似来构造，注意到来构造，注意到 2f(x(k)是对称的，且有近似关系是对称的，且有近似关系(1)()2()(1)()()()()()kkkkkf xf xf xxx()(1)2()1()(1)()()()k

38、kkkkxxf xf xf x 即()()(1)1:(),kkkkkkkkgf xggxx记记则则Hk 应满足条件应满足条件1.对称正定的；对称正定的；2.满足拟牛顿方程满足拟牛顿方程kkkH另外，设想另外，设想Hk由由Hk-1经过简单修正得到，经过简单修正得到，Hk=Hk-1+Ek;校正矩阵校正矩阵Ek应该对称，且满足应该对称，且满足1kkkkkEH满足上式的对称矩阵有无穷多个，因此拟牛顿法是一满足上式的对称矩阵有无穷多个，因此拟牛顿法是一族算法。族算法。DFP算法是其中最常用最有效的方法之一。算法是其中最常用最有效的方法之一。设校正矩阵的形式为设校正矩阵的形式为 TTkkkkkkkEU U

39、VV其中其中 k,k 为待定参数，为待定参数，Uk,Vk为待定向量，这种形式显为待定向量，这种形式显然是对称的，把上式代入拟牛顿方程然是对称的，把上式代入拟牛顿方程1TTkkkkkkkkkkkU UVVH不妨取不妨取1TkkkkkTkkkkkkU UVVH 为使上式成立，简单的做法是取为使上式成立，简单的做法是取11,kkkTTkkkkUU 1111,kkkkTTkkkkkVHVH DFPDFP算法中的校正矩阵算法中的校正矩阵Ek和矩阵和矩阵Hk的计算公式为：的计算公式为：111TTkkkkkkkTTkkkkkHHEH 1111TTkkkkkkkkTTkkkkkHHHHH DFP算法的步骤算法

40、的步骤(0)00(0)(0)1.(),(),0;nxRHHIdf xk 任任取取初初始始点点和和一一般般取取()(1)()()2.()0,;kkkkkkf xxxd若若则则停停 否否则则令令其其中中由由线线搜搜索索求求得得4.1,2.kk转转回回(1)()(1)()11111111111(1)(1)13.,()()()kkkkkkTTkkkkkkkkTTkkkkkkkkxxf xf xHHHHHdHf x 计计算算例4 用DFP算法求解22(0)12min()4,(1,1)Tf xxxx取取解：取H0=I,DFP算法第一步与最速下降法相同(1)0.738460.04616x(0)2()8f x

41、 11.47492()0.36923f x（）2008G122()8xf xx(0)11x 以下作第二次迭代(1)(0)10.261541.04616xx(1)(0)10.52308()()8.36923f xf x 01 10111011101TTTTHHHHH 118.89236T 1011170.31762TTH 110.068400.273610.273611.09445T 01 101 10.273614.377784.3777870.04401TTHH 11.003800.031490.031490.12697H所所以以(1)(1)11.49416()0.09340dHf x(2)(1)(1)1xxd令令(1)(1)1()0,0.49423df xdd利利用用求求得得，所所以以(2)(1)(1)0.000000.494230.00000 xxd(2)(2)()0,f xx由由于于于于是是停停，即即为为最最优优解解。22121212T1.()(6)(233)-4 6f xxxxxx x设求点（，）处的牛顿方向。2.用DFP方法求下列问题的极小点122(0)122min,(3,2).Txx xxx取初始点