使用导数的最优化方法学习教案

1、会计学1使用使用(shyng)导数的最优化方法导数的最优化方法第一页，共73页。一一. 无约束最优化问题无约束最优化问题(wnt)无约束最优化问题无约束最优化问题nRxtsxf .)(min有有一一阶阶连连续续偏偏导导数数。其其中中)(xf 无约束非线性规划问题的求解方法分为(fn wi)解析法和直接法两类。解析法解析法 需要计算函数的梯度，利用函数的解析性质需要计算函数的梯度，利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、共轭梯度法、牛顿(ni dn)法、变尺度法等解析法、变尺度法等解析方法方法 直接法直

2、接法 仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直接方法。第1页/共72页第二页，共73页。 无约束非线性规划问题的求解方法分为(fn wi)解析法和直接法两类。 一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向(fngxing)是解无约束非线性规划问题的核心问题，搜索方向(fngxing)的不同选择，形成不同的求解方法。本章主要介绍解析法;另一类只用到目标函数值,不必(bb)计算导数,通常称为直接方法,放在第11章讨论.第2页/共72页第三页，共73页。nExxf)(min本章考虑如下的下降本章考虑如下的下降(xijing)算法：

3、算法：; 1,) 1 ()1()1(kdx令选定搜索方向给定初始点)()(min)()()2()()(0)()(kkkkdxfdxf，求一维搜索问题令：.k得到解为步；转第令处的搜索方向否则，选取在是最优解，停；若令：2, 1,)3()1()1()1()()()1(kkdxxdxxkkkkkkk算法。选取不同，得到不同的搜索方向)(kd主要(zhyo)介绍最速下降法、牛顿法，共轭梯度法，拟牛顿法等第3页/共72页第四页，共73页。10.1 最速下降法最速下降法 10.1.1 最速下降方向最速下降方向 考虑无约束问题nExxf)(min(6.1.2)其中函数 具有一阶连续偏导数. 人们在处理这类

4、问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是(zhn sh)基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向. )(xf第4页/共72页第五页，共73页。 人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法最速下

5、降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最最速下降方向速下降方向. 我们知道,函数 在点 处沿方向 的变化率可用方向导数来表达,对于可微函数,方向导数等于梯度与方向的内积,即)(xfxddxfdxDfT)();(6.1.2)因此,求函数 在点 处的下降最快的方向,可归结为求解下列非线性规划:)(xfx1.)(mindtsdxfT(6.1.3)第5页/共72页第六页，共73页。根据Schwartz不等式,有)()()(xfdxfdxfT去掉绝对值符号,可

6、以得到)()(xfdxfT(6.1.4)由上式可知,当)()(xfxfd(6.1.5)时等号成立.因此,在点 处沿(6.1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向负梯度方向为最速下降方向. 这里要特别指出,在不同尺度下最速下降方向是不同的.前面定义的最速下降方向,是在向量 的殴氏范数 不大于1的限制得到的,属于殴氏度量意义下的最速下降方向.如果改用其他度量,比xd2d第6页/共72页第七页，共73页。如,设 为对称正定矩阵,在向量 的 范数 不大于1的限制下,极小化 ,则得到的最速下降方向与前者不同.AdA21)(AdddTAdxfT)( 10.1.2 最速下降算法最速下降算法

7、 最速下降法的迭代公式是)()() 1(kkkkdxx(10.1.6)其中 是从 出发的搜索方向,这里取在点 处的最速下降方向,即)()()(kkxfd)(kd)(kx 是从 出发沿方向 进行一维搜索的步长,即 满足k)(kx)(kdk)(min)()()(0)()(kkkkkdxfdxf(10.1.11)(kx第7页/共72页第八页，共73页。 计算步骤计算步骤如下: 1.给定初点 ,允许误差 ,置 .nEx) 1 (01k 2.计算搜索方向)()()(kkxfd 3.若 ,则停止计算;否则,从 出发,沿 进行一维搜索,求 ,使)(kd)(kx)(kdk)(min)()()(0)()(kkk

8、kkdxfdxf 4.令 ,置 ,转步2.)()() 1(kkkkdxx1: kk 例例10.1.1 用最速下降法解下列问题:22212)(minxxxf.101,) 1 , 1 () 1 (Tx初点第8页/共72页第九页，共73页。解：解：,)2,4()(21Txxxf.)2,4()()1(1Txfd.)21 ,41()1()1(Tdx，令22)1()1()21()41 (2)()(dxf)(min求解0)21(4)41(16)(令1851Tdxx)94,91()1(1)1()2(22212)(minxxxf) 1 , 1 ()1(x第二次迭代(di di)：.)9/8,9/4()()2()

9、2(Txfd1 . 0789. 15/54)9/8()9/4(22)2(dTdx984941)2()2(，令81)21 (1681)41(2)()(22)2()2(dxf第9页/共72页第十页，共73页。Tdx984941)2()2(，令81)21 (1681)41(2)()(22)2()2(dxf)(min求解，令081)21 (6481)41(16)(1252Tdxx11272)2(2)2()3(第三次迭代(di di)：.)27/4,27/8()()3()3(Txfd1 . 03313. 027/54)27/4()27/8(22)3(d进行一维搜索：沿从)3()3(dx)()(min)3

10、()3(dxf求解21412721227411272)3()3(dx第10页/共72页第十一页，共73页。21412721227411272)3()3(dx，令2222)3()3(27)21 (427)41(8)()(dxf22212)(xxxf，027)21 (1627)41(64)(2218528880341243241912721227418511272)3(3)3()4(dxx212438842432)()4(xf,)2,4()(21Txxxf0736. 052438)()4(xf412432x似解满足精度要求，得到近00*x精确解第11页/共72页第十二页，共73页。)()(min)

11、()(kkdxf求解在最速下降(xijing)法的一位搜素中0)()()(T)()(kkkddxf由k解得步长满足：故步长k0)()(T)()(kkkkddxf)()()1(kkkkdxx0)()(T)1(kkdxf)()()(kkxfd其中0)(T)1(kkdd即在最速下降(xijing)法中相邻两次搜索方向是正交的。第12页/共72页第十三页，共73页。)()(min)()(kkdxf对于一维搜索cxbAxxxfTT21)(对于(duy)二次严格凸函数其中A为n维对称(duchn)正定矩阵可以(ky)求出步长因子k)()()(kkxfd其中满足：由步长k0)()(T)()(kkkkddxf

12、bAx)(xf由0)()()()(kTkkkdbdxA解得：)()()()()()()()()()()(kTkkTkkTkkTkkAdddxfAdddbAx)()()1( kkxfxf）（)()(2)()()()()(21kTkkTkAddxfxf（本章习题7）第13页/共72页第十四页，共73页。锯齿锯齿(jch)现象现象 最速下降法的迭代点在向极小点靠近(kojn)的过程中，走的是曲折的路线：后一次搜索方向d(k+1)与前一次搜索方向 d(k)总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到(d do)验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一

13、般都要发生。 最速下降法的收敛性第14页/共72页第十五页，共73页。 从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始(kish)逐渐变小。因而收敛速度不快。 已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛(shulin)的(定理10.1.2)，而且恰好是线性收敛(shulin)的。第15页/共72页第十六页，共73页。锯齿现象锯齿现象，其其等等值值面面近近似似数数可可以以用用二二次次函函数数近近似似在在极极小小点点附附近近，目目标标函函椭球面。椭球面。1x*x2x3x它它只只是是。标标

14、函函数数的的一一种种局局部部性性质质最最速速下下降降方方向向反反映映了了目目快的方向。快的方向。局部目标函数值下降最局部目标函数值下降最注注的的算算法法。最最速速下下降降法法是是线线性性收收敛敛第16页/共72页第十七页，共73页。10.2 牛顿法牛顿法 6.2.1 牛顿法牛顿法 设 是二次可微实函数, .又设 是 的极小点的一个估计,我们把 在 展成Taylor级数,并取二阶近似:)(xfnEx)(kx)(xf)(xf)(kx)()(21)()()()()()()(2)()()()(kkTkkTkkxxxfxxxxxfxfxxf其中 是 在 处的Hessian矩阵.为求 的平稳点,令)()(

15、2kxf)(xf)(kx)(x0)(x0)()()()(2)(kkkxxxfxf即(10.2.1)第17页/共72页第十八页，共73页。设 可逆,有(10.2.1)得到牛顿法的迭代公式)()(2kxf)()()(1)(2)()1(kkkkxfxfxx(10.2.2)其中 是Hessian矩阵 的逆矩阵. 这样, 知道 后,算出在这一点处目标函数的梯度和Hessian矩阵的逆,代人(10.2.2),便得到后继点 ,用 代替 ,再用(10.2.2)计算,又得到 的后继点.依此类推,产生序列 .在适当的条件下,这个序列收敛.1)(2)(kxf)()(2kxf)(kx)1( kx1kk)1( kx)(

16、kx 第18页/共72页第十九页，共73页。22112)()()(. 2)(. 1kxxxxxfxfxfkxf则牛顿法产生(chnshng)的序列收敛于 .x 实际上,当牛顿法收敛时,有下列(xili)关系:2)()1(xxcxxkk其中 C 是某个常数.因此,牛顿法至少2级收敛,参看文献(wnxin)19.可见牛顿法的收敛速率是很快的.第19页/共72页第二十页，共73页。例例 用牛顿用牛顿(ni dn)法解下列问题法解下列问题:2241) 1(minxx.) 1 , 0()1(Tx 我们(w men)取初点解：)()()(1)(2)()1(kkkkxfxfxx2312) 1(4)(xxxf

17、24)()1(xf200) 1(12)(212xxf20012)(2xf)()()1(1)1(2)1()2(xfxfxx242/10012/11003/113/110第2次迭代(di di)：027/32)()2(xf2009/48)()2(2xf第20页/共72页第二十一页，共73页。第2次迭代(di di)：027/32)()2(xf2009/48)()2(2xf)()()2(1)2(2)2()3(xfxfxx027/322/10048/903/103/1)2(x09/5继续迭代(di di)，得到,.081/65,027/19)5()4(xx最终(zu zhn)收敛到最优解x*=(1,0

18、)T第21页/共72页第二十二页，共73页。我们(w men)先用极值条件求解.令0)(bAxxf下面用牛顿法求解. 任取初始(ch sh)点x(1) , 根据牛顿法的迭代公式：特别(tbi)地,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点.设有二次凸函数cxbAxxxfTT21)(其中A是对称正定矩阵。)()()(1)(2)()1(kkkkxfxfxx求迭代点x(2) bAx1得到是最小值点吗？bAx1为什么？xbAbAxAxxfAxx1)1(1)1()1(1)1()2()()(即1次迭代达到极小点.第22页/共72页第二十三页，共73页。)()(12xfxfd不一定是下降方向,经迭代

19、,目标函数值可能上升.此外,即使目标函数值下降,得到的点 也不一定是沿牛顿方向的最好点或极小点.因此,人们对牛顿法进行修正,提出了阻尼牛顿法. 值得注意,当初始点远离极小点时,牛顿法可能不收敛.原因之一,牛顿方向 以后还会遇到一些算法,把它们用于二次凸函数时,类似于牛顿法,经有限次迭代必达到极小点.这种性质称为二次终止性二次终止性. )1( kx对于二次凸函数,用牛顿法求解,经1次迭代(di di)即达极小点第23页/共72页第二十四页，共73页。 10.2.2 阻尼牛顿法阻尼牛顿法 阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的一维搜索,其迭代公式是)()()1(kkkkdxx(6.2.

20、6)其中 为牛顿方向, 是由一维搜索得到的步长,即满足)(min)()()()()(kkkkkdxfdxfk)()()(1)(2)(kkkxfxfd 阻尼牛顿法的计算步骤计算步骤如下: 1.给定初始点 ,允许误差 ,置 . 2.计算 )1 (x01k1)(2)()(),(kkxfxf第24页/共72页第二十五页，共73页。 3.若 ,则停止迭代;否则,令)()(kxf)()()(1)(2)(kkkxfxfd 4.从 出发,沿方向 作一维搜索:)(kx)(kd)()(min)()()()(kkkkkdxfdxf令 .)()()1(kkkkdxx 5.置 ,转步2.1: kk 由于阻尼牛顿法含有一

21、维搜索,因此每次迭代目标函数值一般有所下降(决不会上升).可以证明,阻尼牛顿法在适当的条件下具有全局收敛性,且为2级收敛.第25页/共72页第二十六页，共73页。、共轭梯度、共轭梯度(t d)(t d)法法第26页/共72页第二十七页，共73页。10.3.1 共轭方向共轭方向(fngxing)法法1. 共轭方向共轭方向(fngxing)和共轭方和共轭方向向(fngxing)法法定义定义共轭。共轭。关于关于和和，则称，则称若有若有AddAddT21210 ARdddnk它它们们两两两两关关于于中中一一组组非非零零向向量量，如如果果是是设设,21。共共轭轭，即即kjijiAddjTi,2,1,0

22、共轭方向。共轭方向。组组共轭的，也称它们是一共轭的，也称它们是一则称这组方向是关于则称这组方向是关于AA注：注：002121 dddIdTT21dd 共轭是正交的推广共轭是正交的推广(tugung)。，和和中中的的两两个个非非零零向向量量的的对对称称正正定定矩矩阵阵，对对于于是是设设21ddRnnAn 是是单单位位矩矩阵阵，则则如如果果 A第27页/共72页第二十八页，共73页。几何几何(j h)意义意义设有二次函数设有二次函数)()(21)(xxAxxxfT 对对称称正正定定矩矩阵阵，是是其其中中nnA 是一个定点。是一个定点。x的的等等值值面面则则函函数数)(xfcxxAxxT )()(2

23、1为中心的椭球面。为中心的椭球面。是以是以 x由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因为为的的极极小小点点。是是因因此此)(xfxx,)(2Axf 而而第28页/共72页第二十九页，共73页。几何几何(j h)意义意义设有二次函数设有二次函数)()(21)(xxAxxxfT 对对称称正正定定矩矩阵阵，是是其其中中nnA 是一个定点。是一个定点。x的的等等值值面面则则函函数数)(xfcxxAxxT )()(21为中心的椭球面。为中心的椭球面。是以是以 x由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因为为的的极极小小点点。是是因因此此)

24、(xfxx,)(2Axf 而而第29页/共72页第三十页，共73页。点，点，是在某个等值面上的一是在某个等值面上的一设设)0(x处的法向量为处的法向量为该等值面在点该等值面在点)1(x. )()()1()1(xxAxf o1x2xx)1(d)0(x中的一个方向，中的一个方向，是是nRd)1(。以以最最优优步步长长搜搜索索得得到到点点沿沿着着)1()1()0(xdx所所在在等等值值面面的的切切向向量量。是是点点则则)1()1(xd正交，正交，与与则则)()1()1(xfd , 0)()1()1( xfdT即即,)1()2(xxd 令令)1(x所以所以, 0)2()1( AddT共共轭轭。小小点点

25、的的向向量量关关于于向向量量与与由由这这一一点点指指向向极极即即等等值值面面上上一一点点处处的的切切A)2(dcxxAxxxfT)()(21)(第30页/共72页第三十一页，共73页。共共轭轭的的非非零零个个是是阶阶对对称称正正定定矩矩阵阵，是是设设AkdddnAk,21性无关。性无关。向量，则这个向量组线向量，则这个向量组线. 1 . 3 .10定理证明证明，使使得得设设存存在在实实数数k ,21,01 kiiid ，则则有有上上式式两两边边同同时时左左乘乘AdTj,01 kiiTjiAdd 可化简为可化简为共轭的向量，所以上式共轭的向量，所以上式个个是是因为因为Akdddk,21.0 jT

26、jjAdd ，是正定矩阵，所以是正定矩阵，所以而而因为因为0,0 jTjjAddAd所以所以。kjj,2,1,0 线性无关。线性无关。因此因此kddd,21第31页/共72页第三十二页，共73页。2 . 3 .10定理，设设有有函函数数cxbAxxxfTT 21)(共共轭轭向向量量。一一组组是是阶阶对对称称正正定定矩矩阵阵。是是其其中中AdddnAk)()2()1(,进进行行搜搜索索，为为初初始始点点，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函数数则则得得到到点点kkkBxxfxxxx )1()1()1()3()2()(,极小点，其中极小点，其中,

27、|1)(RdxxBikiiik 是是时时，当当，生生成成的的子子空空间间。特特别别地地是是由由)1()()2()1(, nkxnkddd上上的的唯唯一一极极小小点点。在在nRxf)(推论推论有有在上述定理条件下，必在上述定理条件下，必。kidxfiTk,2,1,0)()()1( 第32页/共72页第三十三页，共73页。)(*)1(*1)1(*1)1()(*)1(*1)1()(*)()1(.kkkkkkkkkkkkkdddxddxdxx), 1()(*)()1(kidxxiiii证：设), 1 , 0(0)()()1(kidxfiTk若上的极小点。在是函数要证kkBxxfx)1()1()(,|1

28、)(RdxxBikiiik ,)1(kBxx对于)()1(1)1 (1)1 (kkkkdddxx)()()1( kxfxf要证)()()()()1()1()1(kTkkxxxfxfxf)(1)1(*)1()()()(ikiTkiikdxfxf则必有)()()1( kxfxf,)1(kBxx对于), 1 , 0(0)()()1(kidxfiTk下证第33页/共72页第三十四页，共73页。), 1 , 0(0)()()1(kidxfiTk下用归纳法证的极小点，沿方向在为由), 1 , 0()()()()1(kidxxfxiii为问题中的即*)(*)()1(iiiiidxx的解。)()(min)()

29、(iidxf0)()(T)(*)(iiiiddxf.,.,2 , 1, 0)()(T)1(kidxfii显然成立。时当0)(,1)()1(kTkdxfk. 1,.,2 , 1,0)(,)()(midxfnmkiTm成立有时假设当.,.,2 , 1,0)(,1)()1(midxfmkiTm成立证时则当)(*)()1()1()(mkmmmAdbAxbAxxf)(*)()(mkmAdxf)()(*)()()(T)1()()()(iTmkiTmimAdddxfdxfmi时，故当，由归纳假设，0)()()(iTmdxf0)()()(iTmAdd又, 0)()(T)1(imdxfmi时，故当0)()(T)

30、1(mmdxf而.,.,2 , 1,0)()()1(midxfiTm成立故第34页/共72页第三十五页，共73页。，设设有有函函数数cxbAxxxfTT 21)(共共轭轭向向量量。一一组组是是阶阶对对称称正正定定矩矩阵阵。是是其其中中AdddnAk)()2()1(,推论(tuln)：进进行行搜搜索索，为为初初始始点点，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函数数则则得得到到点点kkkBxxfxxxx )1()1()1()3()2()(,|1)(RdxxBikiiik 上上的的唯唯一一极极小小点点。在在nRxf)(nkkidxfiTk，且有), 1

31、 , 0(0)()()1(0)()1(nxf时，当，特别地nk 极小点，其中极小点，其中点。经有限次迭代必得极小沿一组共轭方向搜索，即对于二次凸函数，若第35页/共72页第三十六页，共73页。共轭方向(fngxing)法对对于于极极小小化化问问题题:法法为为共共轭轭方方向向法法是是正正定定矩矩阵阵，称称下下述述算算其其中中 A,21)(mincxbAxxxfTT ；共轭方向共轭方向取定一组取定一组)()2()1(,)1(ndddA,)2()1()()1( kkxxx确确定定点点依依次次按按照照下下式式由由任任取取初初始始点点 )(min)()()()()()()()1(kkkkkkkkkdxf

32、dxfdxx 。满足满足直到某个直到某个0)()()( kkxfx注注至多经过至多经过求解上述极小化问题，求解上述极小化问题，可知，利用共轭方向法可知，利用共轭方向法由定理由定理2。次次迭迭代代必必可可得得到到最最优优解解n第36页/共72页第三十七页，共73页。 )(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx ；共轭方向取定一组)()2()1 (,ndddA对于上述(shngsh)正交方向法，它是下降算法吗？不难得到(d do)：, 0)()(T)1(kkdxf由)()()()()()(kTkkTkkAdddxfcxbAxxxfTT21)()()(21)()

33、()()(yxAyxyxyfyfxfTT由)()(21)()()()()()1()()1()()1()()1(kkTkkkkTkkkxxAxxxxxfxfxf）（)()(2)()()()(21kTkkTkAdddxf, 0)()()1(kkxfxf）（，若0)()()(kTkdxf).()()1( kkxfxf）（则故正交方向法，它是下降(xijing)算法。第37页/共72页第三十八页，共73页。？共轭方向如何构造一组)()2()1 (,ndddA可由一组线性无关向量组，类似(li s)于schmidt正交化过程，。共轭方向构造一组)()2()1(,ndddA.13具体步骤见本章习题共轭方向

34、的方法。下一节介绍另一种构造cxbAxxxfTT21)(min化问题对于二次凸函数的极小第38页/共72页第三十九页，共73页。10.3 共轭梯度法共轭梯度法 10.3.2 共轭梯度法共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法. 下面,重点介绍Fletcher-Reeves共轭梯度法共轭梯度法,简称FR法法. 共轭梯度法的基本思想基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本

35、性质,这种方法具有二次终止性. 我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形.第39页/共72页第四十页，共73页。. 共轭梯度(t d)法 如何选取如何选取(xunq)一组共轭方向？一组共轭方向？:共轭梯度法共轭梯度法eevesRFletcher 代点代点向相结合，利用已知迭向相结合，利用已知迭将共轭性和最速下降方将共轭性和最速下降方基本思想：基本思想：进行搜索，求出进行搜索，求出共轭方向，并沿此方向共轭方向，并沿此方向处的梯度方向构造一组处的梯度方向构造一组函数的极小点。函数的极小点。以下分析以下分析(fnx)算法的具体步骤。算法的具体步骤。cxbAxx

36、xfTT 21)(min是是常常数数。，是是对对称称正正定定矩矩阵阵，其其中中cRbARxnn ,我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形第40页/共72页第四十一页，共73页。；，第一个搜索方向取为，第一个搜索方向取为任取初始点任取初始点)()1()1()1()1(xfdx ，令令，若若，设设已已求求得得点点)(0)()2()1(1)1()1( kkkkxfgxfx:)1(按按如如下下方方式式确确定定则则下下一一个个搜搜索索方方向向 kd)1()(1)1(kkkkdgd 令令共轭。共轭。关于关于和和要求要求Addkk)()1( ？如如何何确确定定k ，

37、得，得）式两边同时左乘）式两边同时左乘则在（则在（AdTk)(1)()(1)()1()(0kTkkkTkkTkdAdAgdAdd )2()()(1)(kTkkTkkdAdgAd 解解得得cxbAxxxfTT 21)(min初始搜索方向(fngxing)为最速下降方向(fngxing)第41页/共72页第四十二页，共73页。:)3(搜搜索索步步长长的的确确定定，步步长长利利用用一一维维搜搜索索确确定定最最优优和和搜搜索索方方向向已已知知迭迭代代点点kkkdx ,)()(。即求解即求解)(min)()(kkdxf , )()()()(kkdxf 记记，令令0)()()()()( kTkkddxf

38、，即即有有0)()()()( kTkkdbdxA ，则则有有令令bAxxfgkkk )()()(，0)()( kTkkdAdg )3()()()(kTkkTkkAdddg 解解得得第42页/共72页第四十三页，共73页。3 . 3 .10定理次次算法在算法在，对于正定二次函数对于正定二次函数nmFRcxbAxxxfTT 21)(），下下列列关关系系成成立立（且且对对所所有有的的一一维维搜搜索索后后即即终终止止，并并mii 1;1,2,1,0)1()()( ijAddjTi;1,2,1,0)2( ijggjTi。iTiiTiggdg )()3(注注共共轭轭的的。是是可可知知搜搜索索方方向向）由由

39、定定理理（Adddm)()2()1(,31则则构构造造的的搜搜索索必必须须取取负负梯梯度度方方向向，否否算算法法中中第第一一个个搜搜索索方方向向)2(方方向向不不能能保保证证共共轭轭性性。）可可知知，的的（由由定定理理33)3(,0|2)( iiTiiTigggdg处处的的下下降降方方向向。是是迭迭代代点点所所以以)()(iixd第43页/共72页第四十四页，共73页。的的计计算算公公式式可可以以简简化化。算算法法中中，由由定定理理iFR 3)4()()(1)(iTiiTiiAddgAd )()()(1iTiiTiAdddAg / )( / )( )()1()()()1(1iiiTiiiiTi

40、xxAdxxAg .)()()(bxAxfgiii )()(1)(11iiTiiiTiiggdggg iTiigdg)(21| )4(|221iigg )1964,Re(|221evesFletcherggiii第44页/共72页第四十五页，共73页。)1964,Re(|221evesFletcherggiii式：外，还有下列等价表达除表达式有多个等价式，定理中，对于二次凸规划，上述221|iiiigg)1972,()()(1)(11wolfeseensenggdgggiiTiiiTii)1967,()()()(1DanielAddAdgiTiiTii)()(11dixongdggiTiiTi

41、i)1969,()()(11PPRgggggiTiiiTii常用两个公式(gngsh):著名的FR和PPR公式(gngsh)第45页/共72页第四十六页，共73页。算算法法步步骤骤：FR。，令，令精度要求精度要求，任取初始点任取初始点1. 1)1( kx 为为所所求求极极小小点点；停停止止，若若令令)1(1)1(1,|, )(. 2xgxfg 。令令，）计计算算利利用用公公式式（否否则则，令令)1(1)1()2(11)1(3,dxxgd 为所求极小点；为所求极小点；停止，停止，若若令令)1(1)1(1,|, )(. 3 kkkkxgxfg ）计计算算。用用公公式式（其其中中否否则则，令令4,)

42、(1)1(kkkkkdgd 。转转，令，令）计算）计算利用公式（利用公式（3,3. 4)()()1(kkkkkdxx 。令令1: kk)3()()()(kTkkTkkAdddg)4(|221iiiggcxbAxxxfTT21)(min求解二次凸规划(guhu)的FR 共轭梯度法求解二次凸规划的FR 共轭梯度法迭代(di di)多少次才可以达到最优解？第46页/共72页第四十七页，共73页。算算法法求求解解下下述述问问题题：用用例例FR22212)(minxxxf 。初初始始点点取取为为Tx)2,2()1( 解：解：.)2,4()(21Txxxf 次迭代：次迭代：第第1,)4,8(1)1(Tgd

43、 令令)1()1()1(11AdddgTT ,2004),(21)(2121 xxxxxf.2004 A而而 482004)4,8(48)4,8(185 .2004A，或利用0)()()()()(kTkkddxfk求出, )()()()(kkdxf 记记第47页/共72页第四十八页，共73页。)1(1)1()2(dxx 所以所以TT)4,8(185)2,2( T)98,92( 次迭代：次迭代：第第 2.)916,98(2Tg 21221|gg .81448)916()98(2222 )1(12)2(dgdTT)4,8(814)916,98( T)4,1(8140 .)2,4()(21Txxxf

44、 ,)4,8(1)1(Tgd)1(12)2(dgd第48页/共72页第四十九页，共73页。)2()2()2(22AdddgTT 412004)4,1()8140(41)916,98(81402209 )2(2)2()3(dxx TT)4,1(8140209)98,92( T)0,0( Tg)0,0(3 即为所求极小点。即为所求极小点。)3(x第49页/共72页第五十页，共73页。. 用于一般(ybn)函数的共轭梯度法nRxtsxf .)(min共轭梯度法进行修改：共轭梯度法进行修改：对用于正定二次函数的对用于正定二次函数的确确定定。）计计算算，需需由由一一维维搜搜索索不不能能利利用用公公式式（

45、搜搜索索步步长长3)2(i 。速下降方向，即第一个搜索方向仍取最)() 1 ()1()1(xfd算算：其其它它搜搜索索方方向向按按下下式式计计,)()()1()1(iiiidxfd 。其其中中2)(2)1(|)(|)(|iiixfxf )3()()()(kTkkTkkAdddg第50页/共72页第五十一页，共73页。）计算。用公式（其中令4, 1)(1)1(kkkkkdgdk. 用于一般函数(hnsh)的共轭梯度法nRxtsxf .)(min。速下降方向，即第一个搜索方向仍取最)() 1 ()1()1(xfd)4(|221iiigg)(min)2()()(kkdxf但求解一维搜索问题确定。）计

46、算，需由一维搜索不能利用公式（搜索步长3i)3()()()(kTkkTkkAdddg第51页/共72页第五十二页，共73页。此此时时可可采采取取一一定定能能满满足足停停止止条条件件，算算法法在在有有限限步步迭迭代代后后不不)3(如如下下措措施施：没没有有求求成成一一轮轮搜搜索索后后，如如果果还还次次迭迭代代为为一一轮轮，每每次次完完以以n新的初始点，新的初始点，的最后一个迭代点作为的最后一个迭代点作为得极小点，则以上一轮得极小点，则以上一轮一轮搜索。一轮搜索。一个搜索方向，开始下一个搜索方向，开始下取最速下降方向作为第取最速下降方向作为第注注，如如算算采采用用其其它它形形式式的的公公式式计计在

47、在共共轭轭梯梯度度法法中中，也也可可i 。）共轭梯度法共轭梯度法PRPgggggiTiiiTii()(11 第52页/共72页第五十三页，共73页。10.3 共轭梯度法共轭梯度法 10.3.2 共轭梯度法共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法. 下面,重点介绍Fletcher-Reeves共轭梯度法共轭梯度法,简称FR法法. 共轭梯度法的基本思想基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点

48、.根据共轭方向的基本性质,这种方法具有二次终止性. 我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形. 考虑问题第53页/共72页第五十四页，共73页。cxbAxxxfTT21)(min其中 , 是对称正定矩阵, 是常数.nExAc 具体求解方法如下: 首先,任意给定一个初始点 ,计算出目标函数 在这点的梯度,若 ,则停止计算;否则,令)1(x)(xf01g1)1()1()(gxfd(10.3.12)沿方向 搜索,得到点 .计算在 处的梯度,若 ,则利用 和 构造第2个搜索方向 ,再沿 搜索.)1(d)2(x)2(x02g2g)1(d)2(d)2(d 一般地,若

49、已知点 和搜索方向 ,则从 出发,沿 进行搜索,得到)(kx)(kd)(kx)(kd)()()1(kkkkdxx(10.3.14)第54页/共72页第五十五页，共73页。其中步长 满足k)(min)()()()()(kkkkkdxfdxf我们可以求出 的显式表达.令k)()()()(kkdxf求 的极小点,令)(0)()()()1(kTkdxf(10.3.15)根据二次函数的梯度的表达式,(6.3.15)即00(0)()()()()()()()1(kTkkkkTkkkkTkdAdgdbdxAdbAx(10.3.16)第55页/共72页第五十六页，共73页。由(6.3.16)得到)()()(kT

50、kkTkkAdddg(10.3.17) 计算 在 处的梯度.若 ,则停止计算;否则,用共轭.按此设想,令)(xf)1( kx01kgAddddgkkkkk关于和，并使构造下一个搜索方向和)()1()1()(1)(1)1(kkkkdgd(10.3.18)上式两端左乘 ,并令0)()(1)()1()(kTkkkTkkTkAddAgdAdd由此得到AdTk)()()(1)(kTkkTkkAddAgd(10.3.19)第56页/共72页第五十七页，共73页。 再从 出发,沿方向 搜索.)1( kx)1( kd综上分析，在第个搜索方向取负梯度的前提下, 重复使用公式(10.3.14),(10.3.17)

51、,(10.3.18)和(10.3.19),就能伴随计算点的增加,构造出一组搜索方向.下面将要证明,这组方向是关于 共轭的.因此,上述方法具有二次终止性.A 定理定理10.3.3 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在 次一维搜索后即终止，并且对所有 ,下列关系成立:nm )1 (mii)0(. 31, 2 , 10. 21, 2 , 10. 1)()()(iiTiiTijTijTidggdgijggijAdd蕴涵第57页/共72页第五十八页，共73页。 例例6.3.1 考虑下列问题：2322212121minxxx 取初始点和初始搜索方向分别为

52、021111)1()1(dx和 在FR法中，初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向，这一点绝不可忽视。 对于二次凸函数，FR法的计算步骤计算步骤如下： 1.给定初始点 ,置 .)1(x1k第58页/共72页第五十九页，共73页。 2.计算 ,若 ,则停止计算,得点 ;否则,进行下一步.)()(kkxfg0kg)(kxx 3.构造搜索方向,令)1(1)(kkkkdgd其中,当 时, ,当 时,按公式 1k01k1k)0, 1(221iiiigigg计算因子 .1k 4.令)()()1(kkkkdxx其中按公式(6.3.17)计算步长k第59页/共72页第六十页，共73页。

53、5.若 ,则停止计算,得点 ;否则,置 ,返回步2.nk )1( kxx1: kk 由第60页/共72页第六十一页，共73页。10.4 拟牛顿拟牛顿(ni dn)法法 6.4.1 拟牛顿(ni dn)条件前面(qin mian)介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵.第61页/共72页第六十二页，共73页。 Newton法的优缺点(qudin)都很突出。 优点：高收敛速度（二阶收敛）； 缺点(qud

54、in)：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。 拟Newton法是模拟(mn)Newton法给出的一个保优去劣的算法 拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵(j zhn)的方法中的最好方法。第62页/共72页第六十三页，共73页。矩阵。点处的在点为此处HessexxfxfGkkk)()(2)()(第63页/共72页第六十四页，共73页。式：拟牛顿法的基本迭代公kkkkkkkgHddxx)()()()1(,)(-)(kkkxfgH为对称矩阵，其中为下降方向：要求)() 1 (kd0-)(kkTkkTkgHgdg为正定矩阵故要求kHk