最优化：最速下降法和Newton法

最优化主讲：刘陶文课件制作：刘陶文唯楚有材於斯为盛学好最优化，走遍天下都不怕第三章无约束问题算法(I)——最速下降法、Newton法第一节最速下降法第二节Newton法及其修正形式(3.1))(minxfnRx给定无约束问题值效果有很大区别和数相应算法的收敛性理论法式对应不同的最优化算不同计算方最优化方法的核心下降方向的计算是整个计算我们来介绍下降方向的方法，在后面的几章里结构及步长计算的我们介绍了下降算法的在上一章里,,.,,第一节最速下降法1、思想：每次沿负梯度方向进行搜索kx●)(kxf*x●等值线(面)●1kx最古老的优化方法，十九世纪中叶由Cauchy提出负梯度方向也称为最速下降方向：PxfxfxfpxfxfpxfPxfPxfpRpTkpkkkkkkTkn)(min||)(||)(-||)(||)(-||)(||-||||||)(||-)(Schwarz-Cauchy,||||||||的解是下列问题时等号成立，即当取不等式得由且事实上，对任意以负梯度为搜索方向的算法称为最速下降法2、算法步骤最优化算法看来是如此的简单？.2,1:,4;33),(-.,||)(||2;0.0,1)(1.3k1k0转步令步由线性搜索计算步长步；然后转步计算否则算法终止，则得解若步令精度给定初始点步最速下降法算法kkdxxxfdxxfkRxkkkkkkknxxxfxT)(min.),(1.1.3)(题：法求解下面的最优化问降采用精确搜索的最速下取初始点例xxxfdxfxxxff--)(-21)(Q,)(搜索方向的梯度为：函数解xxxxQdddxfTT)(-次函数的步长公式为采用精确搜索极小化二)()()()()()()()()()()()()()(-kkkkkkkkkkkxxxxxxxdxx迭代公式为,1,0,)1(-231)(kxkkk的点列为计算出最速下降法产生由上面的迭代公式不难*)()0,0(,xxTk并且收敛的容易看出上面的序列是.,,最优解以较慢的速度无限接近但能优解代并没有求出其精确最最速下降法在有限次迭数极小化问题，对于简单的二元二次函从上面的例子看到事实上，上面的例子刻画了最速下降法的所有收敛特征.3,.4.2-1.4.2,||||||)(||,0,局收敛性降算法的全我们很容易得到最速下由定理所以且即方向与负梯度方向一致由于最速下降法的搜索kkkdxf3、最速下降法的收敛性全局收敛性0||)(||lim}{Powell-WolfeArmijo,,1.4.21.1.3kkkxfx满足代序列的迭搜索的最速下降法产生搜索或或那么采用精确搜索的条件成立设假设定理.,,见下面的两个定理具体至多是线性的最速下降法的收敛速度由前面的例子看到收敛速度估计3.3][19,.定理定理证明可参考文献收敛速度估计化问题的解严格凸二次函数极小下面的定理给出了其求QxxxxxxxxxxqQxxxfQRqQTQQkQkkTTn||||,3.2||-||-||-||}{)(min.,.,2.1.3***minmaxminmax是问题的惟一解其中）（满足速下降法产生的点列则由采用精确搜索的最问题：化考察如下二次函数极小的最大和最小特征值分别是和记对称正定设矩阵定理）（3.2||-||11-||-||**1QkQkxxxx.,(.,1,,1,,,)2.3(算法收敛很慢接近病态）较大时而当求出最优解算法只需一次迭代即可的所有特征值相等时即当特别最速下降收敛很快接近于当有关的条件数矩阵最速下降的收敛速度与看到由收敛速度估计式QQQ)](-)([11-)(-)()2.3(||-||21)-()-(21)(-)(0)()(,*2*12**T*****xfxfxfxfxxxxQxxxfxfqQxxfxqQxxfkkQ可以改写成所以则处且在由于对于二次函数从上图可以看出，最速下降法具有锯齿现象.)(,)](-)(o[)](-)([-)(-)(,)(,).(}{,3.1.3*minmaxminmax**2***的最大和最小特征值分别是和且其中有估计则正定且的解收敛到问题法产生的点列下降若采用精确搜索的最速二次连续可微设函数定理xfxfxfxfxfxfxfxfxxfkkkk对一般的非二次函数有下面的收敛速度估计：定理的证明参见文献[19,定理3.4]由上面的分析可知，最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步.思考题：.)(,,,,.,,)(}{的最小点就是函数而且这两条直线的交点分别共线，和奇次迭代点明偶次迭代点试证对称正定，所产生，这里元二次函数速下降法求解二是由采用精确搜索的最设序列xfxxxxRcRbRQRxcxbxQxxfxTk有点难啊0)()(-)()()](-)([)(-)()()()(-)()()](-)([)]([)-(-()(-)(----)()()()()()()(-),2()1((2)0)()((1))()(,)()(0)-()-(:1T111T12101T111T1210T1011T1210011T11021200110011011202TTTTT11110212xfxfxfQxfxfxfxfxfQxfxfQxfxfQxfxfxfQxfxxQxxxfxfddxxxxxxxfQxfxfxfQdxfxfxfxfxfQdxfxfbQxxfxfxxdxxxxQxxTkkkkkkkkkkkkkkkkkkkkkkkT）所以进一步得到和由又由精确搜索得得由于记证明：我们首先证明.limlimlim,,,,,,:,,,,,,,:,,,-||-),4()3(-||-)(||)(0)()()()((2)(4)0)-(-((3)0)-(-(*122*125312420420022412341322T31T224340212所以结论成立性知又由最速下降法的收敛共线所有奇次迭代点同理可得共线代点以此类推得所有偶次迭共线即得到和进一步结合，推出中：所以在得又由）类似可得）即xxxxxxxxxxxxxxxxxxxxxxxxxfxfRxfxfxfxfxxQxxxxQxxkkkkkkkkTT第二节Newton法及其修正形式1、思想：用近似二次函数的极小点作为原问题的新的近似解几何解释：11)()(kkkkxxQxfxxx极小点作为来近似，把二次函数的二次函数用与它最密切的处对的迭代过程，在到考虑从●●kx)(1二次曲面极小点kx)()(:)(kxfxf线等值面)()(:kxfxQ二次曲面)()(-,)()(-,0)-)(()()(,)()-)(()()()-)(()-()-()()()()||-(||)-)(()-()-()()()()(1-1-T2TkkkkkkkkkkkkkkkkkkkTkkkkkkkTkkkxfxfxxxxfxfxxxxxfxfxxQxfxxxfxfxQxxxfxxxxxfxfxQxxoxxxfxxxxxfxfxfxxf则为把二次函数的极小点作即的解为的极小点则正定若且二次近似函数处二阶泰勒展开式为在0)()(,Newton,)(.Newton)()(-.Newton)()(-221-21-21kkkkkkkkkkkkxfdxfxfxfxxfxfdxfxfxx的解并且是下列线性方程组方向处的一个下降在方向是函数则正定若方向处的称为其中法的迭代公式为古典我们称迭代公式迭代公式如下：得到搜索法中加入线性我们在古典为确保算法的下降性Newton,Newton,)()(--1kkkkkxfxfxx2、Newton法的算法步骤)(Newton2.3法算法.2,1:,4;3;(3.3)0)()(.,,||)(||2;0.0,1k1k20转步令步由线性搜索计算步长步得解解线性方程组否则算法终止则得解若步令精度给定初始点步kkdxxdxfdxfxxfkRxkkkkkkkkn21-1-1)(Q,2-1--)(22121xfxxxxxf经计算得：解TTTxxxxxxxxfN1)(2,.1)(1,0)(0,--21)(minewton1.2.3*)0(1212221该问题的最优解为和初始点分别取题：法求解下面的最优化问用精确搜索的例2122212211212-2)2(-)1---)(-dddddxxdxxQdddxfTT（次函数的步长公式为采用精确搜索极小化二1-2--2-1--21-1-1-)()(-Newton)(2)(1)(2)(1)(2)(11-1-2)(kkkkkkkkkxxxxxxxfxfd方向的表达式为又对不同的两个初始点，经一次迭代求出最优解，这是偶然还是必然的呢？.Newton,.21)(1.2.30的最小值点达到法最多经一次迭代即可确搜索的采用精出发则从任意初始点阶对称正定矩阵是其中设定理fxnQxqQxxxfTT是最小点即所以且精确搜索的步长则若的最小点即已经是最优解则若，则如果严格凸即正定证明：由于101-0000101-T001-T0000T0001-00001120)(-)()()(1)()()()()(-0)(-0,)(;,0,)()()(,)(,)(xxfQQxfQdxfxfxfQxfxfQxfQdddxfxfQdxffxxfQdxfxfdxxfQxfqQxxfTkkkkkkkk止性则称该算法具有二次终小值点达到函数的最算法经有限次迭代后可从任意初始点出发二次函数极小化问题时若一个算法求解严格凸定义,,,1.2.3标准作为算法有效性的一个是否具有二次终止性可..Newton算法也具有二次终止性我们后面要介绍的许多法具有二次终止性而止性，格凸函数不具有二次终最速下降法对一般的严下面我们来看看最速下降法与Newton法求解二次函数的比较注意等值线的形状中的二次函数考察:2R0x0x*x*x●●0x*x●最速下降法法Newton等值线3、Newton的收敛性:Newton局收敛性结果如下法关于非二次函数的全得到的收敛性，我们很容易由前面介绍的下降算法.}{.Powell-Wolfe,Armijo,,3.2Newton}{)}()(|{(3.4),,||||)(,0,2.2.3k02中的惟一全局最小点在收敛到则型搜索确定或型搜索或由精确搜索其中步长产生算法由设序列其中：使得且存在常数二次连续可微设函数定理fxxxfxfxxRddmdxfdmfkknT还是省略吧太简单了证明,:4、局部二次收敛性****22*2*1-21**0*2***}{)(||,-||||)(-)(||,0,Lipschtiz,.}{0,1,2,k),()(-)Newton(Newton,}||-|||{)(0,.)(,0)(3.2.3xxxUxxxLxfxfLxfxxxfxfxxx