第三章无约束非线性规划课件.ppt

《第三章无约束非线性规划课件.ppt》由会员分享，可在线阅读，更多相关《第三章无约束非线性规划课件.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#无约束非线性规划无约束非线性规划第一节 最优性条件第二节 一维搜索第三节 最速下降法和共轭梯度法第四节 牛顿法和拟牛顿法(变尺度法)第五节 信赖域法#引言本章讨论如下的优化模型min( )nx Rf x其中其中 是是 的实值连续函数，通常假定具有的实值连续函数，通常假定具有二阶连续偏导数。二阶连续偏导数。fx#预备知识#预备知识#预备知识#最优性条件#最优性条件定理的逆不成立，即梯度为零的点不一定是局部解。#最优性条件#迭代法求解无约束优化问题的常用方法是数值解法，而数值解法中最为常见的是迭代法。迭代法思想：(0)(0)0(1)(0)(0)(1)(1)01(2)( )( ),.kf xxdx

2、xdxdxx首首先先给给出出的的极极小小点点一一个个初初始始估估计计通通过过某某种种方方式式产产生生一一个个使使目目标标函函数数值值减减小小的的方方向向确确定定一一个个实实数数从从而而可可以以确确定定新新的的迭迭代代点点，这这样样下下去去我我们们由由、 可可以以确确定定，. (1)( )( )( )( )(0)(1)( )()().().kkkkkkkk xxddx f xf xf x 其其中中称称为为步步长长，称称为为搜搜索索方方向向。通通过过迭迭代代方方式式得得到到点点列列 使使得得#迭代法( )( )( ),()kkk xxxf x若若产产生生的的点点列列逼逼近近我我们们要要求求的的极极

3、小小点点则则称称这这个个序序列列为为极极小小化化序序列列。满满足足所所对对应应的的函函数数值值是是逐逐次次减减小小的的算算法法称称为为下下降降算算法法。( )( )lim0kkkx xxx初初始始点点的的选选取取依依赖赖于于方方法法的的收收敛敛性性能能。一一个个算算法法称称为为收收敛敛的的，如如果果算算法法产产生生的的序序列列满满足足其其中中是是最最优优化化问问题题的的最最优优点点。一一个个算算法法如如果果对对于于任任意意给给定定的的初初始始点点都都能能够够收收敛敛，就就说说这这个个算算法法全全局局收收敛敛或或整整体体收收敛敛。有有些些算算法法只只有有当当初初始始点点接接近近或或充充分分接接近

4、近最最优优解解时时才才有有收收敛敛性性，称称这这样样的的算算法法为为局局部部收收敛敛的的方方法法。#最优性条件(0)( )( )( )( )( )( )( )( )( )(1)( )( )0,( )(0)().kkkkkkkkkkkkkkkxkxdf xxdxd f(xd)f xxxd迭迭代代算算法法的的步步骤骤第第一一步步：给给定定最最优优解解的的一一个个初初始始估估计计，选选择择初初始始点点，置置；第第二二步步：如如果果满满足足最最优优解解估估计计的的终终止止条条件件，停停止止迭迭代代；第第三三步步：确确定定下下降降方方向向使使得得目目标标函函数数从从出出发发，沿沿方方向向，在在射射线线上

5、上选选取取步步长长，使使得得则则令令第第四四步步：得得到到(1)( )( )12.kkkkxxdkk最最优优解解的的一一个个更更好好的的估估计计，置置后后转转步步#迭代算法( )( )( )( )kkkf xxdf x在在大大多多数数的的算算法法中中，的的选选取取是是使使下下降降得得最最多多，即即沿沿射射线线求求的的极极小小值值，这这是是单单变变量量 的的函函数数求求极极小小点点的的一一维维搜搜索索问问题题，称称为为，也也称称为为线线搜搜索索。迭代的终止条件在不同的最优化方法中也是不同的。迭代的终止条件在不同的最优化方法中也是不同的。理论上，根据最优性的一阶必要条件，以及算法的设理论上，根据最

6、优性的一阶必要条件，以及算法的设计思想，可以用计思想，可以用( )()kf x来终止迭代，其中来终止迭代，其中0是给定的精度要求。是给定的精度要求。#一维搜索#一维搜索二分法 对于区间a,b上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法（bisectionbisection）例2 借助计算器或计算机用二分法求方程2x+3x=7 的近似解(精确到0.1).#一维搜索二分法那么我们一起来总结一下二分法的解题步骤那么我们一起来总结一下二分法的解题步骤给定精确度，用二分法求函数f(x

7、)零点近似解的步骤如下：,给定精确度 ；确定区间a,b,验证( )( )0f af b求区间(a,b)的中点 ；1x计算f( )；1x若f(1x)=0，则1x就是函数的零点；若1( )()0f af x，则令b=1x(01( ,)xa x)；此时零点若1()( )0f xf b，则令a=1x(此时零点01(, )xx b)；判断是否达到精确度：即若|a-b|eps & k fu a = l; l = u; u = a + 0.618*(b - a); else b = u; u = l; l = a + 0.382*(b-a); end k = k+1; tol = abs(b - a);en

8、dif k = 100000 disp(找不到最小值！); x = NaN; minf = NaN; return;endx = (a+b)/2;minf = subs(f, findsym(f),x);format short;黄金分割法源程序黄金分割法源程序#一维搜索牛顿法( )kf xxTaylor牛牛顿顿法法的的基基本本思思想想是是利利用用目目标标函函数数在在迭迭代代点点 处处的的二二次次展展开开作作为为模模型型函函数数，并并用用这这个个二二次次模模型型函函数数的的极极小小点点序序列列去去逼逼近近目目标标函函数数的的极极小小点点。2222( ),(),1()( )()()()2,( )

9、( )( )()()0 =+= nkkkkTTkkkkkkkkkf xxRHessef xxTaylorff xdqdf xf xddf xddxxqdf xqdf xf xdd设设二二次次连连续续可可微微，矩矩阵阵正正定定。我我们们在在附附近近用用二二次次展展开开近近似似其其中中为为的的二二次次近近似似。将将上上式式极极小小化化, , 即即 得得1()()kkf xf x#一维搜索牛顿法2112111 = =()() = ()()( )() = () kkkkkkkkkkkkd xxf xf xxxf xf xf xfxxxfx即即从从而而若若为为一一元元函函数数，则则有有迭迭代代式式211

10、.(),(), = kkkkkkkkGf xgf xxxGg这这就就是是牛牛顿顿法法迭迭代代公公式式。相相应应的的算算法法成成为为牛牛顿顿法法令令则则牛牛顿顿法法迭迭代代公公式式为为#一维搜索牛顿法 对于正定二次函数，牛顿法一步即可达到最优解。对于正定二次函数，牛顿法一步即可达到最优解。对于一般非二次函数，牛顿法并不能保证经过有限次迭对于一般非二次函数，牛顿法并不能保证经过有限次迭代法求得最优解，但如果初始点充分靠近极小点，牛顿代法求得最优解，但如果初始点充分靠近极小点，牛顿法的收敛速度一般是很快的。法的收敛速度一般是很快的。01min( ),1.,0,0;2.|()|,;()3.= ()4.

11、1,2.kkkkkkf x xRstepxkstepfxxfxstepxxfxstepkkstep牛牛顿顿法法用用基基本本牛牛顿顿法法求求无无约约束束问问题题的的基基本本算算法法步步骤骤给给定定初初始始点点精精度度令令若若停停止止，极极小小点点为为令令；令令转转#牛顿法程序function x,minf = minNewton(f,x0,eps)format long;if nargin = 2 eps = 1.0e-6;enddf = diff(f);d2f = diff(df);k = 0;tol = 1;while toleps dfx = subs(df,findsym(df),x0)

12、; if diff(d2f) = 0 d2fx = double(d2f); else d2fx = subs(d2f,findsym(d2f),x0); end x1 = x0 - dfx/d2fx; k = k + 1; tol = abs(dfx); x0 = x1;endx = x1;minf = subs(f,findsym(f),x);format short;#最速下降法和共轭梯度法 1874Cauchy最最速速下下降降法法是是以以负负梯梯度度方方向向作作为为下下降降方方向向的的极极小小化化算算法法，又又称称梯梯度度法法，是是年年法法国国科科学学家家提提出出的的。最最速速下下降降

13、法法是是无无约约束束最最优优化化中中最最简简单单的的方方法法。()0.( )( )()()(|),()()(|).kkkkTkkkkkkTkkkkkk f(x)xgf xf xxTaylorf xf xgxxoxxxxdf xdf xg dod 设设目目标标函函数数在在附附近近连连续续可可微微，且且将将在在处处展展开开, , 记记则则上上式式可可写写为为 #最速下降法0,()().( )TkkkkTTkkkkkkkkTkkkkTTkkkkkkkkdg ddf xdf xg dg df xxCauchySchwartz |g d |d |g |dgg dg dgg 显显然然，若若满满足足则则是是

14、下下降降方方向向，它它使使得得当当 取取定定后后，的的值值越越小小，即即的的值值越越大大，函函数数在在处处下下降降量量越越大大。由由不不等等式式：可可知知，当当且且仅仅当当时时，最最小小，最最大大，从从而而是是。最最速速下下降降方方以以- -向向为为下下降降方方最最速速向向的的方方法法叫叫下下降降法法。#最速下降法(),. .1minTkTkdfdg xddgdstd事事实实上上，最最速速下下降降方方向向也也可可以以这这样样来来考考虑虑。因因为为目目标标函函数数沿沿方方向向 的的变变化化率率是是故故最最速速下下降降的的单单位位方方向向 是是问问题题 的的解解。注注意意到到 coscos0cos

15、1. TkkkkkkkkTkkkkd gdgggdgd gdg其其中中是是与与 之之间间的的夹夹角角。极极小小化化上上式式，便便得得到到当当，即即时时，极极小小，这这时时，#最速下降法101.1.,1,0;2.;,3.;4.;5.12. kkkkknkkkkkkkkxxgstepxRkstepdggstepstepxxdstepkkstep最最速速下下降降法法的的迭迭代代格格式式为为： 其其中中步步长长因因子子由由线线性性搜搜索索策策略略确确定定最最速速下下降降算算法法给给定定初初始始点点精精度度0令0令计计算算如如果果停停止止；由由线线性性搜搜索索求求步步长长因因子子计计算算令令，转转#最速

16、下降法2210012.,(), ()()cos kkkkkkkkkkdMf xdMkf xf xdgM定定理理 设设是是下下降降方方向向，是是精精确确线线性性搜搜索索的的步步长长因因子子。若若存存在在常常数数使使得得对对所所有有，则则2222201()()(),(01)21()2.=+ + =TTkkkkkkkkkTkkkkTkkkkf xdf xgddf xddf xgdM dgdM d证证明明：由由假假设设可可知知对对有有令令由由于于是是精精确确线线性性搜搜索索的的步步长长因因子子，故故有有#最速下降法222222222212112212 ()()()() = =cos.kkkkkkkTk

17、kkTTkkkkkkkkkkf xf xdf xf xdgdM dgdgdgMM dgdgM20.2( )( ),lim(),lim0. k.kkkf xf xMMxf xg下下面面的的定定理理论论证证了了最最速速下下降降算算法法的的总总体体收收敛敛性性定定理理 设设函函数数二二次次连连续续可可微微，且且其其中中是是某某个个正正常常数数，对对于于任任给给的的初初始始点点最最速速下下降降法法或或有有限限终终止止，或或者者或或#最速下降法21112011111()()21()()( )()2lim(),lim0. k . kkkkkkiiiiikkkf xf xgMf xf xf xf xgMf

18、xg证证明明：考考虑虑无无限限迭迭代代下下去去的的情情形形，由由定定理理 有有于于是是两两边边取取极极限限，于于是是或或者者或或从从而而定定理理成成立立. . 最最速速下下降降法法具具有有程程序序设设计计简简单单，计计算算工工作作量量小小，存存储储量量小小，对对初初始始点点没没有有特特别别要要求求等等优优点点。但但是是，最最俗俗下下降降方方向向仅仅是是函函数数的的局局部部性性质质，对对整整体体求求解解过过程程而而言言，这这个个方方法法下下降降非非常常缓缓慢慢。数数值值试试验验表表明明，当当目目标标函函数数的的等等值值线线接接近近于于一一个个圆圆( 球( 球) 时) 时，最最速速下下降降法法下下

19、降降较较快快；而而当当目目标标函函数数的的等等值值线线是是一一个个扁扁长长的的椭椭球球时时，最最速速下下降降法法开开始始几几步步下下降降较较快快，后后来来就就出出现现锯锯齿齿现现象象，下下降降十十分分缓缓慢慢。#40251475310.250.05357最速下降法1110, = 0TkkTTkkkkgdggdd事事实实上上，由由于于精精确确线线性性搜搜索索满满足足则则这这表表明明最最速速下下降降法法中中相相邻邻两两次次的的搜搜索索方方向向是是相相互互直直交交的的，这这就就产产生生了了锯锯齿齿形形状状. 越. 越接接近近极极小小点点，步步长长越越小小，前前进进越越慢慢. .1x2x3x4x5x#

20、最速下降法源程序运行结果运行结果#共轭梯度法1.1.算法原理算法原理 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。 共轭梯度法是介于最速下降法与牛顿法之间的一个方法共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数的信息，但克服了最速下降法收敛慢。它仅需利用一阶导数的信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算的缺点，又避免了牛顿法需要存储和计算HesseHesse矩阵并求逆的矩阵并求逆的缺点。共轭梯度法不仅是解大型线性方程组最有用的方法之缺点。共轭梯度法不仅是

21、解大型线性方程组最有用的方法之一，也是解大型非线性最优化问题最有效的算法之一。一，也是解大型非线性最优化问题最有效的算法之一。#共轭梯度法 共轭梯度法最早是由共轭梯度法最早是由HestenesHestenes和和Stiefel(1952)Stiefel(1952)提提出来的，用于解正定系数矩阵的线性方程组。在这个出来的，用于解正定系数矩阵的线性方程组。在这个基础上，基础上，FletcherFletcher和和Reeves(1964)Reeves(1964)首先提出了解非线首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较

22、快的收敛速度和二次终止性等优点，矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。现在共轭梯度法已经广泛地应用于实际问题中。,0T Q Qnnx yx yQ x Qy 共共轭轭设设 为为 阶阶实实对对称称正正定定矩矩阵阵，若若 维维方方向向向向量量满满足足则则称称方方向向是是共共轭轭的的。#共轭梯度法121212,.,.,.0,(,)nmmmTij d ddR d ddQ d dd d QdEijQ设设是是中中任任意意一一组组非非零零向向量量，如如果果则则称称是是共共轭轭的的，简简称称共共轭轭的的。显显然然，如如果果是是共共轭轭的的，则则它它们们是是线线

23、性性无无关关的的。如如果果，则则共共轭轭性性就就是是通通常常的的直直交交或或正正交交性性。下下面面介介绍绍一一般般的的共共轭轭方方向向法法：#共轭梯度法000000010111.,0,0,(),0;2.,3.,)min().4.Tkkkkkkkkkkkkstepxkgg xdd gstepgstepx f(xdf xd xxdstepd 算算法法( (一一般般共共轭轭方方向向法法) )给给出出初初始始点点计计算算和和初初始始下下降降方方向向使使得得如如果果则则停停止止迭迭代代；计计算算和和使使得得采采用用某某种种共共轭轭方方向向法法计计算算使使得得10,0,1,2,.,5.12.Tkj dQd

24、jkstepkkstep令令，转转#共轭梯度法 共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的。而这些搜索方向 仅仅是负梯度方向 与上一次迭代的搜索方向 的组合。因此存储量小，计算方便。kdkg- -1kd1( ),2,()TTnnf xx Qxb xcxRQbnc f(x)=Qx+bx,yR f(y)f(x)Q yx 考考虑虑二二次次函函数数其其中中为为实实对对称称正正定定矩矩阵阵， 为为 维维常常向向量量 为为实实数数，有有于于是是对对有有#共轭梯度法11()11212211( ,)(,).(,) a,rgmin(,.)() .,. ()0 ldf xkkkkkkkkkj

25、jTjjkx dx dx dxxdf xddf xd ddQddf xdj非非零零向向量量两两两两 共共轭轭。令令其其中中因因此此对对，有有 jk另另外外，对对，我我们们有有()()(),1111kjkjf xf xQ xx1111 ()()()TTTjkjjjkjdf xdf xd Q xx精精确确线线搜搜索索#共轭梯度法1111 ()()()TTTjkjjjkjdf xdf xd Q xx 1121.Tjkkkkjjd Qxxxxxx1111.Tjkkkkjjd Qddd1 kTjiiijd Qd1 kTijiijd Qd01()0,(1,2,., ).Tjkdf xjk表表明明1121(

26、)1,.,.kkkkkxdf xdkd ddQ因为共轭梯度法要求在每个迭代点 处的搜索方向是-与前一个搜索方向的线性组合，并且和前个搜索方向是两两 共轭的#共轭梯度法111111 ()()0()()0kkkkTTTkkkkkkkTkkkkkTkkdfxdd Qdd Qfxd Qdd Qfxd Qfxd故当时，令其中由确定，故由上式可- - 得： 1.kkddQ与是 共轭的111()()() ()()0, TTkjkkkjTTkkjkjf xf xddf xdf xdfjkx另外对有#共轭梯度法111111111()()()()() ()()(1,)0 TTTTjkjkkkjkkjkTTTjjk

27、jkjkjjTkjjd Qdd Qf xdd Qf xd Qdd Qdf xQdf xQ xxf xf xxjkf从有-而对112101,., Tjjkkkjkd Qdd dddQ 由于，故对有=0，即与是 共轭的。 这说明我们在每一个迭代点处产生的下降方向都这说明我们在每一个迭代点处产生的下降方向都是互相共轭的，这满足算法的要求。是互相共轭的，这满足算法的要求。#共轭梯度法1min( )2TTf xx Qxb xc1111121111(1).;(2)().().,.,?.TkkkTkkkkkkkkkkkkkkkkTTTkkkkkkkkkkkkd Q xxd df xddd ddQ xxdQd

28、d QdxxQdd Q xx f xd dQd 算算法法中中主主要要有有两两个个迭迭代代关关系系式式：其其中中要要满满足足与与是是 共共轭轭的的，则则另另外外，由由转转置置后后两两边边右右乘乘得得1()()()()0().TTkkkTTkkkkkkkTTkkkdf xf xdd Qddf xf xdfQdx 从从而而#共轭梯度法 综合以上，我们可以得到各个迭代点处下降方综合以上，我们可以得到各个迭代点处下降方向都是向都是Q Q共轭的共轭梯度算法。共轭的共轭梯度算法。0000111011.,0,(),;2.()()()()().,;0,3TTkkkkkTTkkkkTkkkTkkkkkkkkkkk

29、df xf xdd Qdd Qdd Q f xd Qdstepx kgf xdgstepf xstep sxxd df xtd 算算法法( (共共轭轭梯梯度度法法) )给给出出初初始始点点计计算算令令如如果果则则停停止止迭迭代代；计计算算和和使使得得4.12.epkkstep令令，转转HestenesStiefel公公式式#共轭梯度法有有许许多多种种共共轭轭梯梯度度法法，其其实实质质就就是是在在下下降降方方向向的的表表达达式式11()kkkkdf xd .k中中选选取取不不同同的的1111111111()()()0().kkkkkkkkTTkkkkTTTkkkkkkkkTTTkkkkkkkgg

30、f xf xQ xxQd d gdf xgggd Q f xgQd d Qdd Qddgg 注注意意到到及及所所以以有有CrowderWolfe公公式式#共轭梯度法另另外外几几个个常常用用公公式式有有11111TTkkkkkkTTkkkkkgggggdggd g Dixon公公式式11TkkkTkkggg gFletcher-Reeves公公式式11()TkkkkTkkgggg gPolak-Ribiere-Polyak公公式式111()TkkkTkkkggdggDai-Yuan公公式式#共轭梯度法.k FRPRP对对于于正正定定二二次次函函数数，若若采采用用精精确确线线搜搜索索，以以上上几几

31、个个关关于于的的共共轭轭梯梯度度公公式式等等价价。但但在在实实际际计计算算中中，公公式式和和公公式式最最常常用用2221212131min( )222x RFR f xxxx xx例例. .用用共共轭轭梯梯度度法法解解极极小小化化问问题题1( )( ).2TTf xf xx Qxb x提提示示: :首首先先将将写写成成的的形形式式0( 2,4)Tx 初初始始点点选选取取#共轭梯度法,( ),( ),f xf x有有一一种种想想法法对对于于一一般般的的二二阶阶可可微微函函数数因因为为在在每每一一点点的的局局部部，可可以以近近似似用用二二次次函函数数去去逼逼近近逼逼近近公公式式为为：21) ()(

32、)()2TTkkkkkkf(x)f(xf(xxxxx f(xxx2),),),()kkkkQf(xbf(xcf(xXxx 记记则则12TT f(X)=X QXbc X2).kkQf(xQ 但但的的运运算算量量太太大大，影影响响算算法法的的运运行行，所所以以必必须须将将修修改改, ,使使之之不不含含#共轭梯度法1()TkkkTkkd Q f xd Qd1TkkkTkkkQdgQdd111TkkkTkkkgggggd11TkkTkkggg g212()()kkf xf x1min( ), f x fC所所以以对对于于极极小小化化问问题题的的共共轭轭梯梯度度法法的的步步骤骤为为#共轭梯度法21210

33、000011argmin()()()1.,0,(),;2.()0,3.,4.1);.(2kkkkkkkkkkkkkkkf xdf xstepx kgf xdgstepf xstep f xxxd stepkkst df xdep 给给出出初初始始点点计计算算令令如如果果则则停停止止迭迭代代；计计算算和和使使得得令令，转转#共轭梯度法源程序#共轭梯度法小结1min2, ,.TTn f(x)=x Gxb xcGn nb xRcRf问问题题其其中中 是是对对称称正正定定矩矩阵阵则则 的的梯梯度度为为 f(x)=g(x)=Gx+b00,dg 令令则则1000(1) xxdL L L L L L L L

34、 L L L L100(2)T g d L L L L L L L由由精精确确线线搜搜索索性性质质可可得得1100(3) dgd L L L L L L L令令0100(4)T d Gd L L L L L L L L L选选择择使使得得0(3),Td G在在式式两两边边同同乘乘以以得得#共轭梯度法小结110101100001000(5)TTTTTTgggg Gdg gd Gddggg gL L L L L L20,0,1.(3)Tig di由由共共轭轭方方向向法法的的基基本本定定理理，利利用用可可知知20210,0(6)TT g gg g L L L L L L L L L L L L220

35、011(7) dgdd L L L L L L L L L L又又令令0120,0,1.Tid Gdi选选择择和和 ，使使得得从从而而有有2212201121110(8)TTTTgggg g dggg gL L L L L L L；k一一般般地地，在在第第 次次迭迭代代，令令#共轭梯度法小结10(9)kkkiii dgd L L L L L L L L L L L L0,0,1,.,1.Tikid Gdik选选择择 ，使使得得也也假假定定0,0,0,1,.,1(10)TTkiki g dg gik L L L(9),0,1,.,1.Tjd G jk对对式式两两边边左左乘乘则则101,0,1,.

36、,1(11)TTkjjkjkTTjjjjgggg Gdjkd GddggL L L1(10),0,0,1,.,20,0,1,.,1TkjTkj g gjk g gjk由由#共轭梯度法小结0,0,1,.,2jjk故故得得和和11111(12)TTkkkkkk-1TTkkkkkgggg gdggggL L L L L L L L因因此此，共共轭轭梯梯度度法法的的公公式式为为1kkkk xxd11kkkkdgd .TkkkkTkkg dd Gd 其其中中，在在二二次次函函数数情情形形一一般般地地由由精精确确线线性性搜搜索索得得到到.k而而 由由五五大大公公式式确确定定#牛顿法针对最小化问题 min

37、( )nx Rf xTaylor牛牛顿顿法法的的基基本本思思想想采采用用的的是是在在每每个个迭迭代代点点处处利利用用目目标标函函数数的的二二次次展展开开，并并将将其其极极小小化化。22( ),().,1()( )()()()(1)2,( )( )nkkkkTTkkkkkkkf xxRHesseGf xxTaylorff xdq df xf xddf x ddxx q df x 设设是是二二次次可可微微实实函函数数, ,矩矩阵阵正正定定我我们们在在 附附近近用用二二次次展展开开近近似似其其中中为为的的二二次次近近似似。#牛顿法121211 ()(),(2)1()(),(2) ,(3)kkkkkk

38、kkkkkkkxxf xf xGf xgf xxxG g 将将(1)(1)式式右右边边极极小小化化得得这这就就是是牛牛顿顿法法迭迭代代公公式式。在在这这个个公公式式中中，步步长长因因子子。令令，则则式式也也可可写写成成011221min( ),1.,0,0;2.(),;3.()= ()()4.1,2.nkkkkkkkf x xRstepxkstepf xxstepf xxxf xf xstepkkstep 牛牛顿顿法法用用基基本本牛牛顿顿法法求求无无约约束束问问题题的的基基本本算算法法步步骤骤给给定定初初始始点点精精度度令令若若停停止止，极极小小点点为为计计算算, ,令令；令令转转#牛顿法,对

39、对于于正正定定二二次次函函数数，牛牛顿顿法法一一步步即即可可达达到到最最优优解解。对对于于非非二二次次函函数数，牛牛顿顿法法并并不不能能保保证证经经有有限限次次迭迭代代求求得得最最优优解解但但由由于于目目标标函函数数在在极极小小点点附附近近近近似似于于二二次次函函数数，故故当当初初始始点点靠靠近近极极小小点点时时，牛牛顿顿法法的的收收敛敛速速度度一一般般是是快快的的。22( )( ),()0,()( )0(, ,( )( )(), )iiijkjjkfCxxf xf xG xLipschitzi j GxHesseGGxxiGyxj kxxy设设充充分分靠靠近近如如果果正正定定，且且Hesse

40、Hesse矩矩阵阵满满足足条条件件，即即存存在在使使得得对对所所有有有有其其中中是是矩矩阵阵的的元元素素。则则对对一一切切 ，牛牛顿顿法法迭迭代代有有定定义义，且且所所得得序序列列收收敛敛到到 ，并并且且具具定定理理 牛牛有有二二阶阶顿顿法法收收敛敛定定理理收收敛敛速速度度。#牛顿法源程序运行结果运行结果#拟牛顿法(变尺度法) 牛顿法成功的关键是利用了牛顿法成功的关键是利用了HesseHesse矩阵提供的曲矩阵提供的曲率信息，但计算率信息，但计算HesseHesse矩阵工作量大，并且有的目标矩阵工作量大，并且有的目标函数的函数的HesseHesse矩阵很难计算，甚至不好求出，这就导矩阵很难计算

41、，甚至不好求出，这就导致了一个想法致了一个想法: :能否仅利用目标函数值和一阶导数的能否仅利用目标函数值和一阶导数的信息，构造出目标函数的曲率近似，使方法具有类信息，构造出目标函数的曲率近似，使方法具有类似牛顿法的收敛速度快的优点。拟牛顿法就是这样似牛顿法的收敛速度快的优点。拟牛顿法就是这样的一类算法。由于它不需要二阶导数，拟牛顿法往的一类算法。由于它不需要二阶导数，拟牛顿法往往比牛顿法更有效。往比牛顿法更有效。拟牛顿条件拟牛顿条件 和牛顿法的推导一样，考虑目标函数 在当前点 处的二次模型。( )f xkx#拟牛顿法(变尺度法)1( )()2TTkkkk mdf xg dd B d,kBn n

42、Hesse其其中中是是对对称称正正定定矩矩阵阵，是是矩矩阵阵的的近近似似 它它将将在在每每次次迭迭代代中中进进行行校校正正。极极小小化化这这个个模模型型得得1kkkdB g 从从而而新新的的迭迭代代点点为为11kkkkkkkkxxdxB g.kkkBHesseG其其中中是是线线性性搜搜索索步步长长因因子子。上上述述迭迭代代称称为为拟拟牛牛顿顿迭迭代代, ,它它与与牛牛顿顿迭迭代代的的主主要要区区别别在在于于在在上上式式中中用用HesseHesse近近似似代代替替了了牛牛顿顿迭迭代代中中的的矩矩阵阵#拟牛顿法(变尺度法)1( )nnk f:RRDRf xx设设在在开开集集上上二二次次连连续续可可

43、微微，在在附附近近的的二二次次近近似似为为1111111( )()()()()2TTkkkkkkf xf xgxxxxGxx对对上上式式两两边边求求导导得得111( )()kkkg xgGxx,kxx令令得得111()(1)kkkkkGxxggL L L L L L L L令令11,kkkkkksxxygg(1)式式成成为为1(2)kkkGsyL L L L L L L L L#拟牛顿法(变尺度法)1,( )kf xB显显然然 如如果果是是正正定定二二次次函函数数，上上述述关关系系式式(2)(2)精精确确成成立立. .现现在在我我们们要要求求在在拟拟牛牛顿顿法法中中构构造造出出来来的的Hess

44、eHesse近近似似满满足足这这种种关关系系，从从而而得得到到1(3)kkkBsyL L L L L L L L L.上上式式称称为为拟拟牛牛顿顿条条件件或或拟拟牛牛顿顿方方程程1,kkHB如如果果令令则则拟拟牛牛顿顿条条件件变变为为1(4)kkkHysL L L L L L L L L拟拟牛牛顿顿迭迭代代为为11kkkkkkkkxxdxB g#拟牛顿法(变尺度法)或或1kkkkkkkkxxdxH g11(3)kkBx拟拟牛牛顿顿条条件件使使二二次次模模型型具具有有如如下下插插值值性性质质：如如果果满满足足拟拟牛牛顿顿条条件件，那那么么在在点点的的二二次次模模型型11111111( )()()

45、()()2TTkkkkkkkmxf xgxxxxBxx满满足足1111111()(),(),()kkkkkkkkkmxf xmxgmxg上上式式中中第第一一、二二个个等等式式是是显显然然的的，第第三三个个等等式式是是利利用用拟拟牛牛顿顿条条件件(3)(3)得得到到的的。#拟牛顿法(变尺度法)一一般般的的拟拟牛牛顿顿算算法法如如下下拟牛顿算法拟牛顿算法000111,(),0,: 0;3.().4.5.()6.:12.nn nkkkkkkkkkkkkkkkkstep1xRBHRkstep2gstepB dgddH gstepxxdstepBBHHstepkkstep . .给给出出初初始始点点或或

46、. .如如果果，停停止止；解解得得搜搜索索方方向向或或计计算算由由线线性性搜搜索索求求步步长长因因子子，令令；校校正正产产生生或或校校正正产产生生，使使得得拟拟牛牛顿顿条条件件(3)(3)或或(4)(4)成成立立；令令，转转#拟牛顿法(变尺度法)00,HesseBBI在在上上述述拟拟牛牛顿顿法法中中，初初始始矩矩阵阵近近通通常常取取为为单单位位矩矩阵阵, ,即即这这样样拟拟牛牛顿顿法法的的第第一一次次迭迭代代等等价价于于一一个个最最速速下下降降迭迭代代. .拟拟牛牛顿顿法法有有下下列列优优点点23(2)(3)(4)(5)kkk BHG O(n ).(O(n ) ( (1 1) ) 仅仅需需一一

47、阶阶导导数数. .( (牛牛顿顿法法需需要要二二阶阶导导数数) )或或保保持持正正定定，使使得得方方法法具具有有下下降降性性质质; ; ( (在在牛牛顿顿法法中中可可能能不不正正定定) )每每次次迭迭代代需需要要次次乘乘法法运运算算 牛牛顿顿法法需需要要次次乘乘法法运运算算搜搜索索方方向向是是相相互互共共轭轭的的，从从而而具具有有二二次次终终止止性性. .具具有有超超线线性性收收敛敛性性。#拟牛顿法(变尺度法)DFPDFP校正是第一个拟牛顿校正，是校正是第一个拟牛顿校正，是19591959年由年由DavidonDavidon提出的，后来由提出的，后来由FletcherFletcher和和Pow

48、ell(1963)Powell(1963)解释和发解释和发展的展的.BFGS.BFGS校正是目前最流行的也是最有效的拟牛顿校正是目前最流行的也是最有效的拟牛顿校正，它是由校正，它是由Broyden,Fletcher,GoldfarbBroyden,Fletcher,Goldfarb和和SchannoSchanno在在19701970年各自独立提出的拟牛顿法。年各自独立提出的拟牛顿法。11556.( ),.( )( )kTTkkTTkkkkkkkHesseHHHauubvva bHyH yauu ybvv ys考考虑虑目目标标函函数数的的矩矩阵阵的的逆逆近近似似序序列列设设对对称称秩秩二二校校正

49、正为为：其其中中为为给给定定的的数数 假假设设满满足足拟拟牛牛顿顿条条件件(4)(4)#拟牛顿法(变尺度法),u vu v这这里里并并不不唯唯一一确确定定，但但的的明明显显选选择择是是11,TTkkkkkau ybv yus vH y 即即可可使使(6)(6)式式成成立立。于于是是确确定定出出1111,.TTTTkkkkkkkabu ys yv yy H y 因因此此，我我们们得得到到1TTkkkkkkkkTTkkkkks sH y y HHHs yy H yDFP公公式式#拟牛顿法(变尺度法)kkGB.另另外外，考考虑虑的的近近似似序序列列设设对对称称秩秩二二校校正正为为TTkkBBauub

50、vv1, kkkka bBBsy11, 其其中中为为给给定定的的常常数数, ,令令满满足足拟拟牛牛顿顿条条件件则则TTkkkkkkkBsB sauu sbvv sy1 TTkkkkkuy vB s au sbv s,1,1 显显然然，取取即即可可, ,从从而而TTTkkkkkkabu sy ss B s111, kB因因此此得得到到关关于于的的校校正正公公式式TTkkkkkkkkTTkkkkky yB s s BBBy ss B s1 BFGS公公式式#拟牛顿法(变尺度法)DFP算算法法0010.,;nnstepxRHI给给出出初初始始点点0023.( );stepf xxstep如如果果，停