变尺度法

1收敛速度快，为二阶收敛。(2)初始点的选取困难，甚至无法实施。。的存在性和计算量问题1(3)kG?)()((1)1kkxfxf牛顿法特点存在缺点及修正初始点要选在最优点附近。,||||||||2**1xxxxkk.0海塞阵的逆为梯度，，111kkkkkkGggGxx2?1)x(f)x(fkk如何使得问题一：)(min)(:Newton1kktkkkkkkkkdxfdxftdxx法稍作修正：如果对kkkkkkdxgGxx11Newton法中，有在,0)()(011kkTkkkTkkTkkgGggGxfdxfG有时，当是下降方向。正定时，当kkdG。则有：)()(1kkxfxf广义牛顿法3?32））和（如何克服缺点（问题二：)(Newton.111kkkkxfGxx迭代公式：先考虑)(Newton11kkkkkkxfHxxGH则有：，替代用正定矩阵迭代公式中，如果我们在)(.21kkkkkxfHxx考虑更一般的形式：6.3拟牛顿法(变尺度法)一、拟牛顿法的思想4)(1kkkkkxfHxxxGxxxfGdGHkTkkkkk111),(Newton度量为最速下降方向法时法为变尺度算法。也称拟NewtonxIxxxfdIHTkkk度量为最速下降方向梯度法时,)(,拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。5附加某些条件使得：如何对kH.3（正定）0kH)HHH(HHHkkkkkk111kkGH？如何确定和如何保证kkkkH?GHH10质）迭代公式具有下降性（1的计算量要小）（kH2）收敛速度要快（361NewtonkkGH条件拟则因为记),()(),()(2kkkkxfGxfgxfxg)xx(Gggkkkkk111这样我们想到,xx)gg(Gkkkkk1111。此条件确定需满足的条件，并利用kkHG1)()()()(111kTkkxxxfxfxf))(()(211121kKTkxxxfxx))(()()(1121kkkxxxfxgxg分析kkkkkxxggH111)(7则有记,,11kkkkkkxxxggg:)(Newton的一般步骤变尺度法算法二、拟0:0,,.1Step00kHx，误差正定矩阵给定初始点。其中令)(min)(:,.3Step1kkkkkkkkkkdxfdxftdxx;)(.2kkkxfHdStep计算搜索方向拟Newton条件或拟Newton方程:.1kkkxgH8.21:NewtonNewton,1111stepkkxgHHHHHHkkkkkkkk转，令。方程：或拟条件拟满足使得计算按照校正公式。令kkkkkkkkkkkkxxxggxfxfgxfgxfg11111,)()(,)(,)(.5StepStep4.判断是否满足终止准则：yes:计算stop,No:转step5。1kx1*:kxx则?:kH如何确定一个合适的问题9校正法秩？如何确定二2.kH的一个重要工作多变量无约束优化问题）（做了改进和年）（首次提出年）（3PowellFletcher19632Davidon19591TkkkTkkkkkkkvvuuHHHH1nkkkkRvu,R，，待定：DFP算法一、DFP法的提出10，我们有条件：拟根据kkkxgH1Newton()TTkkkkkkkkkHuuvvgxkkkkTkkkkTkkkgHxgvvguu即：kkkTkkkkkTkkkgHgvvxguu组解：，我们可以如下确定一满足上述方程的解很多。这样，我们可以取：1,,1,kTkkkkkkTkkkkgvgHvguxu11。即：kkTkkkkkkTkkkkgHggHvgxxu1,,1,kkTkkTkkkkTkkTkkkkgHgHggHgxxxHHH1DFP的校正公式：的够得到根据上述推导，我们能。性质：000kHH校正公式DFP12步：将拟牛顿法的第5三、DFP算法的步骤改为:.2step1:NewtonNewton,1111转，令。方程：或拟条件拟满足使得计算按照校正公式kkxgHHHHHHkkkkkkkk.2step,1:DFP.5Step转，计算的校正公式：按照kkHkkkTkkTkkkkTkkTkkkgHgHggHgxxxHH113四、变尺度法算法框图：1,0,)1()1(kHx对称yN1kk)()()1()()()()(kkkkkkkkdxxxf-Hd一维搜索得?)()1(kkxx)1()(kkHH产生修正解)1(kxStop14.11,4)(minDFP02221xxxxf初始点算法求解用。取21082)(,xxxfIH,04616.126154.0010xxx2200000)81(4)21())((min))((ttxfxfxftxf例解，为算法与梯度法相同：因第一步ttxfx8121)(DFP00。所以解得04616.073846.0,13.010x15。的校正公式：按照12697.003149.003149.000380.1DFP0000000000001gHgHggHgxxxHHTTTT。搜索方向09340.049416.1)(111xfHd。0000.00000.049423.0111112dxdxx是极小点。，所以因为220)(xxf。36923.852308.0)()(01010ggxfxfg。BFGS算法比DFP算法更好的是BFGS算法。因为这个算法给出的矩阵稳定性更好。这个算法是由Broyden,Fletcher,Goldfarb和Shanno等人给出的，其校正公式为（秩2矫正法）1kkkTTkkkkkkkBBBBuuvv,nkkkkRuvR待定:，，171NewtonkkkHxg根据拟条件：，我们有()TTkkkkkkkkkBuuvvxgTkkkkkTkkkkkkuuxgvvxBx满足上述方程的解很多，我们可以如下确定一组解：,1,,1TkkkkkTkkkkkkuguxvBxvx这样，我们可以取：。TTkkkkkkkkkkkBxuuxvvxg即，只要把DFP算法中涉及DFP校正公式的部分改为BFGS校正公式便得到BFGS算法。BFGS算法具有与DFP算法完全相同的性质，但是因为它的kH不易变为奇异，所以BFGS算法要比DFP算法具有更好的数值稳定性。BFGS算法是直到目前为止所公认的最好的拟Newton算法(变尺度算法)。采用不精确直线搜索技术的BFGS算法的全局收敛性已得到证明。1TTkkkkkkkkTTkkkkkggBxxBBBgxxBx所以，191111110,1TTTTTTAnuvnvAuAuvAuvAAuvAvAu定理：设为阶可逆矩阵，和是维列向量，若则扰动后的矩阵也可逆，且应用上述公式，BFGS中的求逆可以得到简化。20五、变尺度法的主要特点⑴只需用到函数的一阶梯度；（Newton法用到二阶Hesse阵）⑵下降算法，故全局收敛；⑶不需求矩阵逆；（计算量小）⑷一般可达到超线性收敛；（速度快）⑸有二次终结性。21;)(kkxfd搜索方向。步长)(min)(:kkkkkdxfdxf)(),(,,:21kkkkkkkkxfGxfggGdG其中可逆时当搜索方向2.牛顿法。步长1:。步长)(min)(:kkkkkdxfdxf3.拟牛顿法(变尺度法)1、梯度法（最速下降法）：多变量无约束优化搜索方法;)(:kkkxfHd搜索方向22多变量无约束优化搜索方法4.特殊拟牛顿法1——DFP算法：5.特殊拟牛顿法2——BFGS算法：kkTkkTkkkkTkkTkkkgHgHggHgxxxHH1,,11kkkkkkxxxggg其中1TTkkkkkkkkTTkkkkkggBxxBBBgxxBx236.共轭梯度法1——共轭梯度法eevesRFletcher,:1)1(gd搜索方向,)(1)1(kkkkdgd,)1()1()1(11AdddgTT其中)()(1)(kTkkTkkdAdgAd。）共轭梯度法PRP()(11kTkkkTkkggggg7.共轭梯度法2——）。共轭梯度法PRP(多变量无约束优化搜索方法24方性法质牛顿法DFP（拟牛顿法）共轭梯度法（重置初值）二次终止性质一步终止（=1）n步(精确一维搜索)终止n步(精确一维搜索)终止收敛fC(3)且有界凸，x0充分接近x*,k1fC(3)在L(x0)上有界凸，L(x0)有界（精确一维搜索）fC(3)在L(x0)上有界凸，L(x0)有界（精确一维搜索）局部收敛性同上二阶收敛同上，且f(x)是Lipschitz连续。超线性收敛。同上，超线性收敛优缺点要计算二阶偏导数计算量大。n大时存贮量亦大计算量少，程序简单；n大时存贮量也大计算程序简单，存贮量相对较小各种方法比较