第四章-无约束非线性问题的解法-工程优化课件-西电.ppt

1、本章要点：本章要点：最速下降法的基本思想及特点最速下降法的基本思想及特点牛顿方向牛顿方向NewtonNewton法基本思想及特点法基本思想及特点共轭方向、共轭方向法的基本定理共轭方向、共轭方向法的基本定理共轭梯度法基本思想共轭梯度法基本思想拟拟NewtonNewton法的基本思想法的基本思想第四章第四章 无约束非线性问题的解法无约束非线性问题的解法 min()nx Rf x 学习的重要性：学习的重要性：1、直接用于无约束的实际问题；直接用于无约束的实际问题；2、其基本思想和逻辑结构可以推广到约束问题；其基本思想和逻辑结构可以推广到约束问题；3、约束问题可以转化成无约束问题求解。约束问题可以转化

2、成无约束问题求解。方法分类：方法分类：1、间接法：、间接法：对简单问题，求解必要条件或充分条件；对简单问题，求解必要条件或充分条件；2、迭代算法：、迭代算法：零阶法：只需计算函数值零阶法：只需计算函数值 f(x)一阶法：需计算一阶法：需计算 f(x)二阶法：需计算二阶法：需计算 2f(x)直接法直接法梯度法梯度法 本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较本章主要介绍无约束最优化方法，它的应用比较广泛，理论比较成熟。另一方面，通常可以把一些约束优化问题转化为无约束问题来成熟。另一方面，通常可以把一些约束优化问题转化为无约束问题来处理，所以它是最优化方法中的基本方法。处理，所以它是

3、最优化方法中的基本方法。这些方法通常要用到函数的一阶或二阶导数这些方法通常要用到函数的一阶或二阶导数。在实际问题中，也常遇到函数的解析表达式比较复杂，有的甚至在实际问题中，也常遇到函数的解析表达式比较复杂，有的甚至写不出明显的解析表达式，因而导数很难求出或无法求出，这时基于写不出明显的解析表达式，因而导数很难求出或无法求出，这时基于梯度的方法不能用，需要采取另一种所谓的梯度的方法不能用，需要采取另一种所谓的直接法（或直接搜索法）。直接法（或直接搜索法）。直接法直接法是仅仅利用函数值的信息，去寻找最优解的一类方法。在后面是仅仅利用函数值的信息，去寻找最优解的一类方法。在后面第九章有介绍。第九章有

4、介绍。考虑无约束优化问题：考虑无约束优化问题：min()nx Rf x 直接搜索法直接搜索法收敛速度一般比较慢，需要计算大量的函数值。收敛速度一般比较慢，需要计算大量的函数值。梯度梯度反映了函数值变化的规律，充分利用反映了函数值变化的规律，充分利用梯度信息梯度信息构造算法，构造算法，能加速收敛。能加速收敛。使用函数的梯度（一阶导数）或使用函数的梯度（一阶导数）或Hesse矩阵（二阶导数）的矩阵（二阶导数）的优化算法统称为梯度法。优化算法统称为梯度法。算法目标：算法目标：求出平稳点求出平稳点（满足（满足 f(x)=0的的x*）。）。由于由于 f(x)=0 一般是非线性方程组，解析法往往行不通，一

5、般是非线性方程组，解析法往往行不通，所所以以梯度法梯度法通常是逐次逼近的迭代法。通常是逐次逼近的迭代法。假定：假定：f(x)和和 2f(x)连续存在连续存在4.1 最速下降法最速下降法(Cauchy法法)（一）（一）基本思想基本思想x(k+1)=x(k)+tk d(k)x(k)x*d(k)=f(x(k)x(k+1)d(k+1)=f(x(k+1)瞎子下山：瞎子下山：由于他看不到哪里由于他看不到哪里是山谷，不可能沿直接指向山是山谷，不可能沿直接指向山谷的路线走，他只能在当前位谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然里最陡就往哪里前进一

6、步，然后在新的位置上再用手杖寻找后在新的位置上再用手杖寻找最陡方向，再下降一步。这就最陡方向，再下降一步。这就是最速下降法的形象比喻。是最速下降法的形象比喻。？多变量最优化迭代解法的一般迭代公式：多变量最优化迭代解法的一般迭代公式：可用一维搜索技术解决可用一维搜索技术解决关键是如何确定搜索方向关键是如何确定搜索方向d(k)最速下降法迭代公式最速下降法迭代公式 x(k+1)=x(k)tk f(x(k)1847年年Cauchy提出。特点提出。特点是是直观易懂，但收敛速度慢。直观易懂，但收敛速度慢。下面看一下理论推导：下面看一下理论推导：设函数设函数f(x)在在xk附近连续可微，且附近连续可微，且g

7、k=f(xk)0，由，由Taylor展式展式()()()()()kkTkkf xf xxxf xo xx可知，若记可知，若记x-xk=tdk，则满足，则满足(dk)Tgk0的方向的方向dk是下降方向。当是下降方向。当t取定后，取定后，(dk)Tgk的值越小，即的值越小，即-(dk)Tgk的值越大，函数下降的越快。由的值越大，函数下降的越快。由Cauchy-Schwartz不等式不等式当且仅当当且仅当dk=-gk时，时，(dk)Tgk 最小，从而最小，从而-gk是是最速下降方向最速下降方向。kTkkkdgdg 最速下降法的迭代格式为：最速下降法的迭代格式为：(1)()()()kkkkxxtf x

8、 （二）（二）算法算法开始开始给定给定x(0),M,1,2,令令 k=0计算计算 f(x(k)|f(x(k)|Mx*=x(k)是是结束结束是是一维搜索求一维搜索求tk 精度为精度为 2 否否x(k+1)=x(k)tk f(x(k)k=k+10()min()kkkkktf xt gf xtg （三）（三）最速下降法的搜索路径呈直角锯齿形最速下降法的搜索路径呈直角锯齿形定理定理4.1 设从点设从点x(k)出发，沿方向出发，沿方向d作精确一维搜索，作精确一维搜索，tk为最优步长因子，即为最优步长因子，即 f(x(k)+tk dk)=min f(x(k)+t dk)则成立则成立 f(x(k)+tk d

9、)T d=0,即新点处的梯度与搜索方向垂直。即新点处的梯度与搜索方向垂直。即即 t0(1)()()()kkf xf x x(k+1)d(k)x(k)f(x)等值面等值面 f(x(k+1)tkd(k+1)二维情形二维情形下最速下降法搜索路径：下最速下降法搜索路径：由此可以看出，由此可以看出，最速下降法仅是算法的局部性质最速下降法仅是算法的局部性质。对于许多问题，全。对于许多问题，全局看最速下降法并非局看最速下降法并非“最速下降最速下降”，而是下降的较缓慢。数值试验表明，而是下降的较缓慢。数值试验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当当目标函数的等值线接近于一个圆（

10、球）时，最速下降法下降较快，而当目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快，目标函数的等值线是一个扁长的椭球时，最速下降法开始几步下降较快，后来由于出现后来由于出现“锯齿锯齿”现象，下降就比较缓慢。现象，下降就比较缓慢。x(0)x(1)x(2)f(x(k+1)T dk=0，即即 f(x(k+1)T f(x(k)=dk+1Tdk=0，这表明在相邻的两个迭代点上函数这表明在相邻的两个迭代点上函数f(x)的两个梯度方向是互相直交的，即，的两个梯度方向是互相直交的，即，两个搜索方向互相直交，这就产生了两个搜索方向互相直交，这就产生了锯齿形状锯齿形状。当接近极小点时，步长愈。当接近极

11、小点时，步长愈小，前进愈慢。小，前进愈慢。这就造成了这就造成了最优步长的最速下降法最优步长的最速下降法逼近极小点过程是逼近极小点过程是“之之”字形，并且越字形，并且越靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内靠近极小点步长越小，移动越慢，以至在实际运用中在可行的计算时间内得不到需要的结果。得不到需要的结果。这似乎与这似乎与“最速下降最速下降”的名称矛盾。其实不然，因为梯度是的名称矛盾。其实不然，因为梯度是函数局部性质函数局部性质，从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多从局部看，函数在这一点附近下降的很快，然而从整体看，则走过了许多弯路，因此反而是

12、不好的。弯路，因此反而是不好的。其原因就是其原因就是精确一维搜索（最优步长）精确一维搜索（最优步长）满足满足2212min()25f xxx 02,2Tx 00104,4,100Tfxfx 1x 0f x 0 x()f x 000min fxfx 220min 2425 2100 min()()8(24)5000(2100)0 06260.0200307231252 为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发为了清除最优步长最速下降法中两个搜索方向正交的不良后果，人们发现了不少方法，如：现了不少方法，如：(1)选择不同初始点选择不同初始点 例：问题：例：问题：取初点取初点为

13、求为求 ，沿沿方向从方向从出发求出发求 的极小点的极小点即进行线搜索即进行线搜索则则解得解得 210001.9198770.3071785 10Txxfx 1()3.686164.fx 然后再从然后再从 开始新的迭代，经过开始新的迭代，经过10次迭代，得最优解次迭代，得最优解 计算中可计算中可以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点时，以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点时，步长很小，目标函数值下降很慢。如果不取初点为步长很小，目标函数值下降很慢。如果不取初点为 而取而取1x*(0,0)Tx 0(2,2)Tx 0(100,0)Tx*(0,0)

14、Tx 0001222010002,50200,010020025 00400 1002001,0,02TTfxxxddxxfx 一步就得到了极小点。一步就得到了极小点。虽然后一初点较前一初点离最优点虽然后一初点较前一初点离最优点 远，但迭代中远，但迭代中不会出现上面的锯齿现象。这时：不会出现上面的锯齿现象。这时：1kkkkkf xf xf xf xf x （2）采用不精确的一维搜索：）采用不精确的一维搜索：用一维搜索求出的步长为用一维搜索求出的步长为 时，我们不时，我们不取取 ，而用，而用 的一个近似值作为的一个近似值作为 ,这样可使相邻两个迭代点处的这样可使相邻两个迭代点处的梯度不正交，从而

15、改变收敛性。梯度不正交，从而改变收敛性。可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一可见：造成距齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。件困难的事。*k*k 对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，对于最速下降法，有时为了减少计算工作量，不采用直线搜索确定步长，而采用固定步长而采用固定步长的方法，称为固定步长最速下降法。只要的方法，称为固定步长最速下降法。只要充分小，总有：充分小，总有：但但到底取多大，没有统一的标准，到底取多大，没有统一的标准，取小了，收敛太慢，而取小了，收敛太慢，而取大了，取大了，又会漏掉极小点。又会漏掉极小点

16、。不精确线搜索解决这个问题不精确线搜索解决这个问题*（四）（四）收敛性分析收敛性分析定理定理4.2 设目标函数设目标函数 f(x)一阶可微，且水平集一阶可微，且水平集 有界，则最速下降法或者在有限步迭代后终止；或者得到点列有界，则最速下降法或者在有限步迭代后终止；或者得到点列 ，它的任何极限点都是它的任何极限点都是f(x)的驻点。的驻点。00()()Gx f xf xkx证明：见文中定理证明：见文中定理4.1的证明的证明推论推论4.1 如果函数如果函数f(x)为凸函数，则应用最速下降法，或者在有限步为凸函数，则应用最速下降法，或者在有限步迭代后终止；或者得到点列迭代后终止；或者得到点列 的任何

17、极限点都是全局极小点的任何极限点都是全局极小点。下面讨论最速下降法用于二次函数时的收敛性分析。下面讨论最速下降法用于二次函数时的收敛性分析。kx证明：见课本证明：见课本P69推论推论4.2用于二次函数时的收敛性分析用于二次函数时的收敛性分析111nnq 并且并且2111()()()nkknf xf x 1011|knnknxx 0 xkx0k 定理定理4.3：对于二次函数对于二次函数 Q为对称正交，为对称正交，分别分别为其最小最大特征值，从任意初点为其最小最大特征值，从任意初点 出发，对此二次函数，用最速下降出发，对此二次函数，用最速下降法产生的序列法产生的序列 ，对于，对于 有有12(),T

18、f xx Qx 12,由于由于0kx，则，则而函数而函数 的极小点恰好是的极小点恰好是 。故最速下降法对于。故最速下降法对于二次函数关于任意初点均收敛，而且是线性收敛的。二次函数关于任意初点均收敛，而且是线性收敛的。1()2TfxxQ x*0 x 1200Q 22112211()22TfxxQ xxx 210 12,fx xc 22122212122xxcc 这个函数的等值线为这个函数的等值线为 (c0)，改写为：改写为：其中其中 下面说明最速下降法收敛下面说明最速下降法收敛 性的几何意义。考虑具有对称正定矩阵的函数性的几何意义。考虑具有对称正定矩阵的函数12 c 22 c 12 12 22c

19、22 c0 x1x 这是以这是以 和和 为半轴的橢圆，从下为半轴的橢圆，从下面的分析可见面的分析可见 两个特征值的相对大小决定最两个特征值的相对大小决定最速下降法的收敛性。速下降法的收敛性。（1）当）当 时，等值线时，等值线变为圆变为圆 此时此时 因而由上述定理知：因而由上述定理知：21210q 1100|0 xx 即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标函数时，从任意初始点出发，只需迭代一步就到了极小点函数时，从任意初始点出发，只需迭代一步就到了极小点。1x2x1x2x（2）当）当 时时,等值线为椭圆。此

20、时对于一般的初始点将产生锯齿现象。等值线为椭圆。此时对于一般的初始点将产生锯齿现象。（3）当）当 ，等值线是很扁的椭圆，此时等值线是很扁的椭圆，此时21211q 12 0 x1x2x对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。对于一般的初始点收敛速度可能十分缓慢，锯齿现象严重。（五）优缺点（五）优缺点1、优点：、优点：计算简单，需记忆的容量小；对初始点要求低，稳定性高；计算简单，需记忆的容量小；对初始点要求低，稳定性高；远离极小点时收敛快，常作为其它方法的第一步。远离极小点时收敛快，常作为其它方法的第一步。2、缺点：、缺点：收敛速度较慢（线性或不高于线性）。原因是最速下降方向收敛速度较

21、慢（线性或不高于线性）。原因是最速下降方向只有在该点附近有意义。只有在该点附近有意义。最速下降方向最速下降方向只是局部下降最快的方向，在全局来看，下降速度是比只是局部下降最快的方向，在全局来看，下降速度是比较慢的。尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时，较慢的。尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时，收敛更慢。收敛更慢。例例4.1 用最速下降法求函数用最速下降法求函数 f(x1,x2)x12+4x22 的极小点，（迭代两次），的极小点，（迭代两次），并验证相邻两个搜索方向是正交的。初始点取为并验证相邻两个搜索方向是正交的。初始点取为x(0)=1,1T。解：解：梯度梯度

22、f(x)2x1,8x2 T。1.第一次迭代：第一次迭代：f(x(0)2,8 T，x(1)=x(0)+t0 p(0)=x(0)t0 f(x(0)1,1T t0 2,8 T 用一维搜索求用一维搜索求t0，对简单，对简单f(x)，可用解析法求解：，可用解析法求解：0(t)520t680 t0 0.130769x(1)=0.738462,0.046152T设设 0(t)f(x(1)f(1,1T t2,8 T)(12t)2+4(18t)22.第二次迭代：第二次迭代：f(x(1)1.476924,0.369216 Tx(2)=x(1)t1 f(x(1)=0.7384621.476924t10.046152

23、+0.369216t1 1(t)f(x(2)(0.7384621.476924t)2+4(0.046152+0.369216t)2 1(t)2.317625t+5.453173t0 t1 0.45005x(2)=0.110762,0.110767T f(x(2)0.221524,0.886136 T3.验证相邻两个搜索方向是正交的：验证相邻两个搜索方向是正交的：f(x(0)T f(x(1)=2,8 1.476924,0.369216 T=0.00012 0 f(x(1)T f(x(2)=1.476924,0.369216 0.221524,0.886136 T=0.000001 02212()

24、10f xxx -1.5-1-0.500.511.5-15-10-5051015-202-15-10-5051015建议大家对二次函数编程实践建议大家对二次函数编程实践(无需集成一维搜索算法无需集成一维搜索算法)建议大家对一般函数结合一维搜索方法编程实践建议大家对一般函数结合一维搜索方法编程实践.4.2 Newton法（二阶方法）法（二阶方法）？由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别好的由最速下降法可知，从全局角度来看，负梯度方向一般不是一个特别好的方向，有没有更好的方向方向，有没有更好的方向?()()2()31()()()()()2kkTTkf xf xf xxxf x

25、xox ()(;)kfx xf(x)在在x(k)处的处的二次近似函数二次近似函数（一）基本（一）基本Newton法法取取 f(x;x(k)的平稳点作为的平稳点作为f(x)最优点的一个近似点最优点的一个近似点令令 f(x;x(k)=f(x(k)+2f(x(k)x=0设函数设函数f(x)的的Hesse矩阵可逆，由上式可得：矩阵可逆，由上式可得：设函数设函数f(x)是二次可微函数，是二次可微函数，,nxR 又设函数又设函数x(k)是是f(x)的极小点的一个的极小点的一个估计，我们把设函数估计，我们把设函数f(x)在在x(k)展成展成Taylor级数，并取二阶近似：级数，并取二阶近似：x x(k)=x

26、=2f(x(k)1 f(x(k)Newton法迭代公式：法迭代公式：x(k+1)=x(k)2f(x(k)1 f(x(k)x(k)f(x(k)f(x;x(k)x(k+1)或或 x(k+1)=x(k)H(x(k)1g(x(k)H(x(k)1g(x(k)!当当f(x)是二次函数时，一次迭代就可达到平稳点是二次函数时，一次迭代就可达到平稳点！!当当f(x)是单变量函数时，本方法即为一维搜索的是单变量函数时，本方法即为一维搜索的Newton法法！这样，知道这样，知道x(k)后，算出在这一后，算出在这一点处目标函数的梯度和点处目标函数的梯度和Hesse矩矩阵的逆，代入便得到后继点阵的逆，代入便得到后继点x

27、(k+1)。Newton法的二次终止性法的二次终止性设有二次凸函数设有二次凸函数f(x)=1/2xTAx+bTx+c 其中其中A对称正定矩阵。对称正定矩阵。我们先用极值条件求解。令我们先用极值条件求解。令()0f xAxb 得最优解：得最优解：*1xA b 下面用下面用Newton法求解。任取初始点法求解。任取初始点x(1)，根据，根据Newton法迭代公式有：法迭代公式有：(2)(1)1(1)(1)1(1)1()()xxAf xxAAxbA b 显然，显然，(2)*1xxA b 即一步迭代达到最优解。即一步迭代达到最优解。以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经以后还会

28、遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经过有限次迭代比达到极小点。这种性质称为过有限次迭代比达到极小点。这种性质称为二次终止性二次终止性。结束结束 基本基本Newton法的算法框图：法的算法框图：开始开始给定给定x(0),令令 k=0计算计算g(k)=f(x(k)x*=x(k)是是p(k)=H(x(k)1g(k)x(k+1)=x(k)+p(k)k=k+1否否计算计算 H(x(k)|g(k)|例例4.2 用基本用基本Newton法求函数法求函数 f(x1,x2)8x12+4x1x2+5x22 的极小点。的极小点。初始点取为初始点取为x(0)=10,10T。解：解：f(x)16x1+

29、4x2,4x1+10 x2 T 2f(x)H(x)=16 4 4 10H(x)1=10 4 4 161144 x(1)=x(0)H(x(0)1 f(x(0)1010=10 4 4 16114420014000因为因为f(x)是二次函数，所以一步迭代就达到平稳点，又因为是二次函数，所以一步迭代就达到平稳点，又因为H(x(1)是正是正定矩阵，所以定矩阵，所以x(1)是极小点。是极小点。02,2Tx 0102022420|,50100050 xxfxfxx 110200102402121000050 xxfxfx *1xx则：则：221,21225f x xxx 例例4.3：用：用Newton法求法

30、求 的极小点。的极小点。解：取初点解：取初点代入代入Newton迭代公式得迭代公式得：此即为问题的最优点此即为问题的最优点关于关于Newton法的几点说明：法的几点说明：1、基本、基本Newton法要求法要求Hesse矩阵具有逆矩阵。矩阵具有逆矩阵。如果如果H(x(k)是正定的，则是正定的，则H(x(k)1必存在，从而算法是可行的，并且保证求得必存在，从而算法是可行的，并且保证求得的平稳点是极小点。的平稳点是极小点。然而在迭代过程中要求然而在迭代过程中要求H(x(k)是正定的这一条件不一定能保证，只有当初始是正定的这一条件不一定能保证，只有当初始点合适时才能满足。一般在极小点附近的点合适时才能

31、满足。一般在极小点附近的Hesse矩阵容易为正定的。矩阵容易为正定的。所以所以基本基本Newton法在极小点附近才比较有效法在极小点附近才比较有效。2、Newton法的搜索方向法的搜索方向H(x)1 f(x)不一定是下降方向。不一定是下降方向。因为若是下降方向，则应有因为若是下降方向，则应有 f(x)TH(x)1 f(x)0，但由于，但由于H(x)1不一定是正定的，所以上式不一定成立。不一定是正定的，所以上式不一定成立。3、Newton法的最大优点是：当初始点选得合适时收敛很快，具有二法的最大优点是：当初始点选得合适时收敛很快，具有二阶收敛速度，是目前讲过的算法中最快的一种，且不需一维搜索。阶

32、收敛速度，是目前讲过的算法中最快的一种，且不需一维搜索。对初始点要求高，一般要求初始点离极小点较近，否则不收敛。有时即使对初始点要求高，一般要求初始点离极小点较近，否则不收敛。有时即使是收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。是收敛的，但因初始点离极大点或鞍点较近，会收敛于极大点或鞍点。4、方向、方向H(x)1 f(x)称为称为Newton方向，是一个好方向，对二次函数方向，是一个好方向，对二次函数此方向直指平稳点。此方向直指平稳点。对于目标函数是二次函数的无约束优化问题，从任意初始点出发，利用对于目标函数是二次函数的无约束优化问题，从任意初始点出发，利用Newton法一步

33、迭代即可得到最优解，也就是法一步迭代即可得到最优解，也就是Newton法具有二次终止性。法具有二次终止性。5、牛顿算法可视为椭球范数、牛顿算法可视为椭球范数kG 下的最速下降算法。下的最速下降算法。nR 事实上，欧氏空间事实上，欧氏空间 中一般范数中一般范数 下的方向导数定义为：下的方向导数定义为：0()()()limTkkkkTgdff xdf xf xddddd （它显然与范数（它显然与范数 有关）有关）minnTkd Rgdd()f x kx 显然，显然，的最优解就是函数的最优解就是函数在在处对应于范数处对应于范数的最速下降方向。容易理解，这个解与所取的范数有关。的最速下降方向。容易理解

34、，这个解与所取的范数有关。a)当取欧氏范数（当取欧氏范数（2范数）时，可证范数）时，可证kkdg 是最速下降方向；是最速下降方向；kG 1kkkdG g b)若取椭球范数若取椭球范数，最速下降方向则为最速下降方向则为事实上，事实上，1111(,)kkkkkkkkTTkkkkkkGGGGkkGGkkGGgdgG G dG gddddG gdG gd ndR 1kkTkkkGGgdGdg 1kkkGG g 即即 ，有，有（意味着（意味着为方向导数下界）为方向导数下界）1kkkdG g 11121()()kkkkkkkTTkkkkTkkkkkGGGGkkGGGgdgG gG gGG gdddddG

35、gd 1kkkGG g 1kkkdGg kG 另一方面，若取另一方面，若取时时方向导数达到下界方向导数达到下界，故，故是对于椭球范数是对于椭球范数下的最速下降方向。下的最速下降方向。min()nx Rf x()0f x kx ()0kf x kx()f x kx 2()()()()0kkkf xf xf xxx ()0f x 21()()kkkxxf xf x 121()()kkkkxxf xf x 6、牛顿算法实际上是非线性方程组的牛顿迭代法。、牛顿算法实际上是非线性方程组的牛顿迭代法。等价于求解非线性方程组等价于求解非线性方程组设设是当前迭代点，若是当前迭代点，若，则，则是方程组的解，否则

36、将是方程组的解，否则将在在处线性化，得处线性化，得将上述线性方程组的解作为将上述线性方程组的解作为的近似解，得的近似解，得 故有故有 这恰好就是牛顿迭代公式。这恰好就是牛顿迭代公式。由于求解由于求解若若由以上分析可知，固定的步长因子不能保证目标函数有合理的改善，甚由以上分析可知，固定的步长因子不能保证目标函数有合理的改善，甚至不能保证算法下降，因此有必要对牛顿算法作一些改进，一个最直接至不能保证算法下降，因此有必要对牛顿算法作一些改进，一个最直接的改进是：在牛顿算法中加入一维搜索。的改进是：在牛顿算法中加入一维搜索。（二）修正（二）修正(阻尼阻尼)Newton法法?怎样才能使怎样才能使Newt

37、on法成为一个下降算法法成为一个下降算法？修正修正Newton迭代公式：迭代公式：x(k+1)=x(k)tk H(x(k)1 f(x(k)沿沿Newton方向一维方向一维搜索得到的最优步搜索得到的最优步长长 保证了保证了 f(x(k+1)f(x(k)，且不必要求且不必要求H(x)为正定矩阵。为正定矩阵。?出现出现(1)H(x(k)1不存在；或不存在；或(2)tk=0 时怎么办时怎么办？改用最速下降法改用最速下降法，即，即 p(k)=f(x(k)修正修正Newton法与基本法与基本Newton法的优点是：法的优点是：缺点：要求计算缺点：要求计算Hesse矩阵及其逆矩阵，计算量大，尤其当维数矩阵及

38、其逆矩阵，计算量大，尤其当维数n较大时。较大时。收敛快，程序简单。前者更实用可靠。收敛快，程序简单。前者更实用可靠。结束结束 阻尼阻尼Newton法的算法框图：法的算法框图：开始开始给定给定x(0),令令 k=0计算计算g(k)=f(x(k)x*=x(k)是是一维搜索求一维搜索求tkx(k+1)=x(k)+tk p(k)k=k+1否否计算计算 H(x(k)，若可逆，若可逆p(k)=H(x(k)1g(k);否否则则p(k)=g(k);|g(k)|0()min()kkkkktf xt pf xtp 012max 2,2,2,.()()()kkkkkTkkkts tf xt pf xtpg 常用如下

39、常用如下Armijo不精确搜索不精确搜索2()f x00()()Gx f xf x kx()kf x kx*x证明：见文证明：见文P70中定理中定理4.3的证明的证明.阻尼阻尼Newton法的收敛性法的收敛性定理定理4.4 设设 f(x)存在连续二阶偏导数，函数的存在连续二阶偏导数，函数的Hessian矩阵矩阵 正定正定,且水平集且水平集有界，则阻尼牛顿法或者有界，则阻尼牛顿法或者在有限步迭代后终止；或者得到的无穷点列在有限步迭代后终止；或者得到的无穷点列有如下性质有如下性质1）为严格单调下降序列；为严格单调下降序列；2）有唯一极限点有唯一极限点，它是，它是 f(x)的最小点。的最小点。New

40、ton法与最速下降法结合法与最速下降法结合(1)Marquart法法最速下降法的优点：对初始点要求不高，稳定性好；远离最优点时收敛较快。最速下降法的优点：对初始点要求不高，稳定性好；远离最优点时收敛较快。缺点是离最优点较近时收敛很慢。缺点是离最优点较近时收敛很慢。牛顿法的优缺点刚好与最速下降法相反。牛顿法的优缺点刚好与最速下降法相反。1963年年Marquardt提出将最速下降法与提出将最速下降法与Newton法结合，开始用最速下降法，法结合，开始用最速下降法，在接近最优点时用在接近最优点时用Newton法。法。在迭代公式在迭代公式x(k+1)=x(k)+tk p(k)中，取步长中，取步长tk

41、1，搜索方向为，搜索方向为p(k)2f(x(k)+kI1 f(x(k)其中其中 k同时起控制搜索方向和步长的作用，同时起控制搜索方向和步长的作用，I为单位矩阵为单位矩阵(1)开始阶段取很大，如开始阶段取很大，如 0=104，p(0)2f(x(0)+0I1 f(x(0)f(x(0)1 0(2)在迭代过程中，让在迭代过程中，让 k0，p(k)2f(x(k)1 f(x(k)（一）方法思想（一）方法思想最速下降法最速下降法 Newton法法 具体在每一步是否缩小具体在每一步是否缩小 k，要通过检验目标函数值来决定，要通过检验目标函数值来决定：若若f(x(k+1)f(x(k)，取，取 k+1 1，重作第

42、，重作第k步迭代。步迭代。（二）算法（二）算法开始开始给定给定x(0),M，,令令 k=0，0=104 x*=x(k)是是结结束束p(k)=2f(x(k)+kI1 f(x(k)否否否否 kM是是计算计算 f(x(k)|f(x(k)|x(k+1)=x(k)+p(k)f(x(k+1)0，给定方向给定方向p1，在与，在与p1平行的两平行的两条直线上（如图），条直线上（如图），f(x)的最小点为的最小点为x1，x2，则，则 p1TAp2=0,（p2=x2-x1）证：证：因为因为 g1=Ax1+b，g2=Ax2+b，则则 g2-g1=A(x2-x1)，又因为又因为x1，x2为为f(x)在此二直线上的最小

43、点，则在此二直线上的最小点，则 p1Tg1=0，p2Tg2=0，所以，所以 p1T(g2-g1)=0，综上可得综上可得 p1T(g2-g1)=p1TA(x2-x1)=0，所以所以 p1TAp2=0,（p2=x2-x1）。）。x1x2p1p2注：注：该示意图说明沿任意该示意图说明沿任意p1得到极小点后，沿其共轭方向得到极小点后，沿其共轭方向p2必找到二维问必找到二维问题的极小点！题的极小点！定义：定义：设设A是是nn阶对称正定矩阵，阶对称正定矩阵，若若 AI（单位矩阵），则（单位矩阵），则 p(0)T p(1)=0，即，即 p(0)与与p(1)是正交的。是正交的。“共轭共轭”是是“正交正交”概念

44、的推广概念的推广=|p(0)|.|p(1)|cos（1）p(0),p(1)为两个为两个n维向量，若成立维向量，若成立 p(0)T A p(1)=0 则称向量则称向量p(0)与与p(1)为为A共轭共轭或或A正交正交，称这两向量的方向为，称这两向量的方向为A共轭方向共轭方向。下面给出共轭的一般定义：下面给出共轭的一般定义：（2）若有一组向量）若有一组向量p(0),p(1),p(m)，满足，满足 p(i)T A p(j)=0，（ij，i,j=1,2,m）则称向量组则称向量组p(0),p(1),p(m)为为A共轭共轭（或（或A正交正交）的向量组。）的向量组。例例1：设：设(0)(1)2111,1202

45、App (0)(1)2111 1,02,101222TpA p则则 p(0)与与 p(1)是是 A 共轭的。共轭的。解：因为解：因为验证验证 p(0)，p(1)为为 A 共轭向量。共轭向量。（二（二）共轭方向的性质共轭方向的性质共轭方向法的基本定理共轭方向法的基本定理定理定理4.5：设设A为为nn阶对称正定矩阵，阶对称正定矩阵，p(1),p(2)，,p(m)为为m个相互个相互A共轭共轭 的的n维非零向量维非零向量（即（即p(i)0,i=1,2,m,且且p(i)T A p(j)=0，i j），），则此向量组必则此向量组必线性无关线性无关。推推 论：论：在在n维空间中，互相共轭的非零向量的个数不超

46、过维空间中，互相共轭的非零向量的个数不超过n个。个。引理引理4.6（n维直交定理）维直交定理）(1)若若p(0),p(1),p(n-1)是线性无关的是线性无关的n维向量组；维向量组；(2)若若n维向量维向量x和和p(0),p(1),p(n-1)都直交；都直交；则则 x=0。miiiip ()100 命题：命题：设设A为为nn阶对称正定矩阵，阶对称正定矩阵，p(0),p(1)，,p(n-1)为为n个相互个相互A共轭共轭的的n维非零向量维非零向量（即（即p(i)0,i=0,1,n-1,且且p(i)T A p(j)=0，i j），则任意），则任意n维向维向量量 x 可表示：可表示：定理定理4.6：若

47、若p(0),p(1),p(n-1)是是n个非零的个非零的A共轭向量共轭向量，则二次目标函数，则二次目标函数 f(x)=c+bTx+1/2 xTAx的最优点的最优点 x*为为i Tnii TiipbxppAp ()1*()()()0!可得到非二次函数最优点的一个近似点；其中可得到非二次函数最优点的一个近似点；其中A是是Hesse矩阵！矩阵！?上式用于非二次函数，可否得到最优点上式用于非二次函数，可否得到最优点？i Tnii TiipAxxppAp ()1()()()0定理定理4.7:设设A为为n阶阶对称正定矩阵对称正定矩阵，对于二次目标函数，对于二次目标函数 f(x)=c+bTx+1/2 xTA

48、x，从任意初始点从任意初始点x(1)出发，逐次进行一维搜索，即出发，逐次进行一维搜索，即 min f(x(i)+t p(i)=f(x(i)+ti p(i)i0 若搜索方向若搜索方向p(1),p(2),p(n)是非零的是非零的A共轭向量，则至多进行共轭向量，则至多进行n次迭代必可次迭代必可得到极小点得到极小点x*，即有，即有 x(i+1)=x(i)+ti p(i),i=1,2,n x*=x(k),1kn+1 上述搜索方法具上述搜索方法具有二次收敛性有二次收敛性?对非二次函数，采用上述方法，对非二次函数，采用上述方法，n 次迭代是否也可得到极小点次迭代是否也可得到极小点？?如何简便地找出如何简便地

49、找出n个个A共轭的向量共轭的向量？定理定理:假设假设1.n元函数元函数f(x)=c+bTx+1/2 xTAx 中的矩阵中的矩阵A是对称正定的；是对称正定的；2.向量向量p(0),p(1),p(m-1)(mn)是互相是互相A共轭的；共轭的；3.x(0),x(1)是不同的任意两点，分别从是不同的任意两点，分别从x(0),x(1)出发，依次沿出发，依次沿p(0),p(1),p(m-1)作作精确一维搜索精确一维搜索，设最后一次一维搜索的极小点分别为，设最后一次一维搜索的极小点分别为x(0)*和和x(1)*,那么，那么，向量向量 p=x(0)*x(1)*与与p(0),p(1),p(m-1)互为互为A共轭

50、。共轭。已知前已知前m个共轭方向，个共轭方向，就可以找到第就可以找到第m+1个共轭方向个共轭方向p(1)x(0)x(1)p(0)p(0)x(0)*x(1)*x*x(0)x(1)p(0)p(0)p(1)p(1)x(0)*x(1)*p(2)x*（三（三）Powell共轭方向法共轭方向法表表4.1 Powell共轭方向法的迭代过程共轭方向法的迭代过程阶段起点阶段起点x(k,0)n+1次一维搜索过程次一维搜索过程新共轭方向新共轭方向)(kpPowell共共轭方向法的基本思想轭方向法的基本思想)1,1(),1()1,1()2,1()2,1()1,1()0,1()0()0,1(),1()1()1()2()