第六章-最速下降法和牛顿法

建模方法与应用建模方法与应用主讲人：徐猛北京交通大学交通运输学院建模方法与应用6.1最速下降法6.2Newton型法6.求解无约束多变量极值问题建模方法与应用6.1最速下降法建模方法与应用1．基本思想假设无约束极值问题的目标函数)(xf有一阶连续偏导数，且具有极小点x；以kx表示极小点的第k次近似，为了求其第1k次近似点1kx，在kx点沿方向kp作射线kxx+kp，（0）称为步长。现将)(xf在kx处作泰勒展开，有：kffxx()()()kkfxpkTkfpx)(o（）其中o（）是的高阶无穷小。对于充分小的，只要0)(kTkfpx（4）即可保证kffxx()()()kkfxp。此时，若取kkxx1kp（5）就一定能使目标函数得到改善。建模方法与应用现在考察不同的方向kp，假设kp的模不为零，并设0)(kfx（否则kx是稳定点）；那么，使式（4）成立的kp有无穷多个，为了使目标函数能得到尽量大的改善，必须寻求能使kTkfpx)(取最小值的kp。由于kTkfpx)(=cos)(kkfpx，当kp与)(kfx反向（即1180cos0）时，kTkfpx)(取最小值。)(kkfxp被称为负梯度方向，在kx的某一小的邻域内，负梯度方向是使函数值下降最快的方向。6.1最速下降法建模方法与应用为了得到下一个近似点，在选定搜索方向之后，还要确定步长。的计算可以采用试算法，即首先选取一个值进行试算，看它是否满足不等式kkffxx()(1)()kkfxp；如果满足就迭代下去，否则缩小使不等式成立。由于采用负梯度方向，满足该不等式的总是存在的。另一种方法是通过在kx负梯度方向上的一维搜索，来确定使得kkffxx()(1)kp最小的，这种梯度法就是所谓的最速下降法。6.1最速下降法建模方法与应用2．基本步骤给定一个初始近似点0x及其精度0，若20)(xf，则0x即为近似极小点；若20)(xf，求步长0并计算1x=0x0)(0xf。求步长可以用一维搜索法、微分法，也可以利用试算法，或者根据某些函数确定步长，例如nn1(MSA)；若求最佳步长，则只能选用前两种方法。6.1最速下降法建模方法与应用一般地，若2)(kfx，则kx即为近似极小点；否则求步长k并计算1kx=kxk)(kfx。如此反复，直到达到要求的精度。若)(xf具有二阶连续偏导，在kx处将)(1kfx作泰勒展开，即：kfx())(kfx)(kfxTkf)(x)(kfx+21)()(kTkHfxx)(kxf对求导并令其为零，则有最佳步长k=)()()()()()()()()()(kkTkkTkfHfffxxxxx，可见最佳步长不仅与梯度有关，而且与海赛矩阵有关。6.1最速下降法建模方法与应用[例]试用梯度法求2221)1()1()(xxfx的极小点，1.0。解：取初始近似点T)0,0(0x，Tf)2,2()(0x8])2()2([)(2222)0(xf2002)(xH0=21168222002)2,2(22)2,2()()()()()()0()0()0()0()0(xfxHxfxfxfTT1x=0x0)(0xf=112200210])0()0([)(22221xf6.1最速下降法建模方法与应用0xx2x1极小点1x图12图12展示了该例的迭代过程，即从)0,0(0x经过负梯度方向一步到达极小点)1,1(1x。其实，对于等值线为圆的问题，不管初始近似点选在哪里，负梯度方向总是直接指向圆心，即圆心为极值点。这样，只要一次迭代即能达到最优。6.1最速下降法建模方法与应用[例]试用梯度法求2221212122264)(xxxxxxfx的极大点。解：该二次函数的绝对最优解),(3431x，迭代过程见图13，任何两个相邻点的梯度一定是正交的。设)1,1(0x，因有)426,244()(2121xxxxfx，所以有)0,2()(0xf。下一个迭代点1x是这样得到的：由)1,21()0,2()1,1()(001xxxf6.1最速下降法建模方法与应用有4)21(2)21(2)(21xf令函数)(1xf对的导数为零，可求得最佳步长411于是有)1,()1,21(211x，同理可进行后续的各步迭代。第二次迭代：)1,0()(1xf，412，),(45212x第三次迭代：)0,()(212xf，413，),(45833x第四次迭代：),0()(413xf，414，),(1621834x第五次迭代：)0,()(814xf，415，),(162132115x第六次迭代：因此步),0()(1615xf，所以0039.0])()0([)(256122161225xf由于25)(xf已经很小，所以过程可以在这一点结束。近似的极大点是),(162132115x。6.1最速下降法建模方法与应用由于负梯度方向的最速下降性和正梯度方向的最速上升性，人们很容易认为梯度方向是最理想的搜索方向。必须指出x点处的梯度方向，仅在x点的一个小邻域内才具有最速的性质，而对于整个优化过程来说，那就是另外一回事了。由上例可以看出，当二次函数的等值线为同心椭圆时，采用梯度法其搜索路径呈直角锯齿状；最初几步函数值变化显著，但是迭代到最优点附近时，函数值的变化程度非常小。因此，梯度法经常与其他方法联合使用，在前期使用梯度法，而在接近最优点时使用其他方法。2x1x),(3431*x)1,1(0x2121图136.1最速下降法建模方法与应用前面介绍了求解一维问题的Newton法，它很容易推广到多维的情况。这个方法也是求解无约束极值问题得最古老算法之一，已发展成为一类算法：Newton型方法。1.基本思想与迭代公式与一维问题类似，在局部，用一个二次函数近似代替目标函数)(xf，然后用近似函数的极小点作为)(xf的近似极小点。若非线性目标函数)(xf具有二阶连续偏导，kx为)(xf的一个近似极小点，在kx点取)(xf的二阶泰勒展开，即：)(xf)(kfxTkf)(xkxx+21kkxxxxx)(kTH(6)则其梯度为：6.2Newton型法建模方法与应用kxxxxx)()()(kkHff这一近似函数的极小点应满足：0)()(kxxxxkkHf从而)()(1kkkfHxxxx即)()(1kkkfHxxxx（7）如果)(xf是二次函数，则其海赛矩阵为常数，式（6）是精确的。在这种情况下，从任意一点出发，用式（7）只要一步即可求出)(xf的极小点（假设海赛矩阵正定）。6.2Newton型法建模方法与应用如果)(xf不是二次函数，式（6）仅是一个近似表达式。此时，按式（7）求得的极小点，只是)(xf的近似极小点。在这种情况下，常按下式选取搜索方向：)()(1kkkfHxxp（8）1kx=kxkkp（9）k：kfx(minkkP）（10）按照这种方式求函数)(xf极小点的方法称为牛顿法，式（8）所示的搜索方向称为牛顿方向。牛顿法收敛的速度很快，当)(xf的二阶导数及其海赛矩阵的逆矩阵便于计算时，这一方法非常有效。6.2Newton型法建模方法与应用[例]试用牛顿法求)(2)(2)(2221221xxxxfx的极小值。解：Txxxxxxf]4)(4,4)(4[)(221121x8448)(xH是正定矩阵取T)2,5(0x，则：3648)(0xf，8448)(0xH，611211216110)(xH00364825)()(611211216101001xxxxfH因Tf)0,0()(1x，故T)0,0(1x为)(xf的极小点，极小值是“0”。6.2Newton型法建模方法与应用[例]试用牛顿法求121222121232)(xxxxxfx的极小值。解：Txxxxf),23()(1221x1113)(xH是正定矩阵取T)0,0(0x，则：02)(0xf，1113)(0xH，2321212110)(xH110200)()(2321212101001xxxxfH因Tf)0,0()(1x，故T)1,1(1x为)(xf的极小点，极小值是“-1”。6.2Newton型法建模方法与应用2．阻尼Newton法在上面介绍的Newton法中，步长k总是取为1。在阻尼Newton法中，每一步迭代沿方向)()(1kkkfHxxp进行一维搜索来决定k，即取k，使得)(min0kkkkkffpxpx从而使用下面的迭代公式1kx=kx)()(1kkkfHxx来代替(8)-(10).阻尼Newton法保持了Newton收敛速度快的优点，又不要求初始点选的很好，因而在实际应用中取得较好的效果。6.2Newton型法建模方法与应用阻尼Newton法的计算步骤（1）给的初始点0x，精度0，令0k。（2）计算)(kfx，若)(kfx成立，则迭代停止，kx即为所求稳定点；否则，转（3）。（3）计算1)(xH和下降方向kp。（4）沿kp方向进行一维搜索，决定步长k：)(min0kkkkkffpxpx（5）令1kx=kxkkp，1kk，返回（2）。6.2Newton型法建模方法与应用[例]设211222121242,xxxxxxxf，求xfmin解：取T1,10x，则3)(0xf211242xxxf，12224xxxf由于Tf2,40x，4222)(02xxfH故2121211)(1xH，于是TfH1,3010xxp。31051,31200ffpx令0，得10。故T2,4001pxx。并且Tf0,01x即利用阻尼Newton法，经过迭代一次就达到了函数)(xf的极小点T2,4*x，对应的极小值为8)(*xf6.2Newton型法建模方法与应用6.2Newton型法建模方法与应用