最优化理论与算法(第三章)

1第三章牛顿法§3.1最速下降法一、最速下降法在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向，产生的算法称为最速下降法，它是无约束最优化算法中最简单、最基本的算法。算法描述：1）给出初始点0nxR，允许误差0，0k；2）计算kkdg，若kg，Stop令*kxx；3）由一维搜索确定步长因子k，使得0()min()kkkkkfxdfxd4）令1kkkkxxd，1kk，goto2).二、最速下降算法的收敛性定理3.1设1fC，则最速下降算法产生的点列kx的每个聚点均为驻点。证明：设x是kx的一个聚点，则存在子序列1kKx，使得1limkkKxx令()kkdfx，由1fC，知1()kKfx是收敛序列，故1kKd有界，且1lim()kkKdfx由定理2.6有2()(())()0Tfxfxfx故有()0fx。定理3.2设()fx二次连续可微，且2()fxM，则对任何给定的初始点0nxR，最速下降算法或有限终止，或lim()kkfx，或lim()0kkfx。2证明：不妨设k，()0kfx。由定理2.5有211()()()2kkkfxfxfxM于是1201001()()()()()2kkkiiiiifxfxfxfxfxM令k，由{()}kfx为单调下降序列，则要么lim()kkfx，要么lim()0kkfx。最速下降算法若采用不精确一维搜索，仍有下列总体收敛性定理。定理3.3设1fC，则采用不精确一维搜索得到的点列kx的每个聚点均为驻点。证明：直接由定理2.14可得。注：1)最速下降算法的收敛性也可由前述关于模式算法收敛性结果定理2.7直接获得；2）最速下降算法的主要优点是方法简单、直观，有好的总体收敛性，但收敛很慢。三、最速下降算法的收敛速度1.先考虑二次函数情形定理3.4对极小化问题1min()2TfxxGx，其中G为nn对称正定矩阵，1，n分别为G的最大与最小特征值。设*x是最优解，则最速下降算法的收敛速度至少是线性的，且下面的界成立：*2211*221()()()(1)()()(1)()knknfxfxfxfx，*1*(1)(1)kkxxxx其中11nGG（为矩阵G的条件数）。证明：由()fxGx，有()kkfxGx。故1()()kkkkkkkkkkkkxxdxfxxGxIGx其中k使(())(())kkkfIGxfIGx，0若设()1kPtt，()Qtut其中,uR。则有()QGIuG，而(0)Q，3利用这些，可知1()()(())()(0)kkkkQGfxfIGxfxQ，（要求0u）21()()1()()(())(())2(0)(0)2(0)TTkkkkQGQGxGxQGxGQGxQQQ设12,,n是G的特征值，而(1,,)iuin是对应得标准特征向量（两两正交的单位向量）。令()1nkkiiixau，则上式可进一步表示为：()()2111(())(())2(0)nnkTkiijjijaQGuGaQGuQ()()2111(())(())2(0)nnkTkiiijjjijaQuGaQuQ（将G作用到内每一项）()()2111(())(())2(0)nnkTkiiijjjjijaQuaQuQ2()2211()2(0)nkiiiiaQQ（由iu是标准正交向量组）对()Qtut，可适当选取,u，使1()1,()1nQQ。事实上，只须令1()1()1nQQ即可求得1112,nnnu从而112()nntQt。显然()Qt单调上升。由1()1,()1nQQ，及12,,n，即得()1(1,,)iQin。由22()2()1221111()()2(0)2(0)nnkkkiiiiiiifxaQaQQ及2()()()()()11111111()()()()()222nnnnnkTkkTkkkiijjiijjjiiijijifxauGauauaua4即得12()()(0)kkfxfxQ.再由2211(0)nnQ最后得2111()()nkknfxfx0k.由1101nn，并注意到()fx是正定二次函数（()0fx），则有()0()kfxk。再由()fx为严格凸二次函数（正定二次型），故当且仅当0x时，()0fx，由此可推得必有*0kxx.再注意到*()0fx，则有2*111*1()()()()()()kknkknfxfxfxfxfxfx从而定理第一式得证。下面再证定理第二式，记*kkexx，k。由G是对称正定的，故有1TTTnkkkkkkeeeGeee由*0x，则2()TTkkkkkeGexGxfx故有12()TTnkkkkkeefxee，k注意到：2111()()nkknfxfx因而有22*1111112*112()2()kTkkknnTkknnkkfxxxeeeexxfx最后得*1*(1)(1)kkxxxx（其中1n）。这表明：最速下降算法至少具有线性收敛速度。5定理3.5（Kantorovich不等式）设G是n阶对称正定矩阵，1和n分别为其最大和最小特征值，则nxR，有211214()()()()TnTTnxxxGxxGx。证明：参见袁亚湘等《最优化理论与方法》第三章附录，略。以上对特殊形式的二次函数1()2TfxxGx的收敛速度进行讨论，对一般的二次函数1()2TTfxxGxbx利用Kantorovich不等式可得类似的结论，其证明思路如下：设*x是极小点，则*x满足*0Gxb且()fx可表示为****11()()()22TTfxxxGxxxGx记**1()()()2TExxxGxx，则()Ex与()fx仅相差一个常数，它们有相同的最优解，且使用最速下降算法时，每次迭代方向产生的迭代序列均完全相同。现在考察对()Ex的极小化，这时最速下降算法的迭代公式为：1TkkkkkTkkggxxggGg（这里TkkkTkkgggGg为最优步长因子）其中kkgGxb。直接计算可得：211121()()()4()()()()TkkkknTTkkkkknExExggExgGggGg（由Kantorovich不等式）故有：21112114()1()()()nnkkknnExExEx（1）由（1）即得：()0kEx（或*()()kExEx）。由G正定，当且仅当*xx时，**1()()()02TExxxGxx利用()Ex一致凸性，可证必有：*kxx。这表明：算法产生的点列kx是整体收敛到*x的。由（1）有：2*111*1()()()()()()kknkknfxfxExfxfxEx（2）注意到：***1()02TfxxGx，6由（2）有22*11111()()1()nnkknnfxfxfx211()nknfx（3）再令*kkexx（k），则1TTTnkkkkkkeeeGeee，k注意到2()TkkkeGeEx即有：22**12()nkkkxxExxx，k从而有：22*1111112*112()()2()()kknknnknnkkExxxExExxxEx，（令1n）最后得：*1*(1)(1)kkxxxx，定理证毕。当目标函数为非二次函数时，最速下降算法的收敛速度依然是线性的。定理3.6设()fx满足定理2.8的假设条件，若最速下降算法产生的点列kx收敛于*x，则收敛速度至少是线性的。§3.2牛顿法一、牛顿算法的基本思路牛顿算法的基本思路是：利用目标函数在当前迭代点kx处的二次近似的极小点作为()fx的近似极小点。设kx是当前迭代点，2()kfx正定，则21()()()()()()()2TTkkkkkkfxfxfxxxxxfxxx记()21()()()()2kTTkkkqsfxfxssfxs，其中ksxx，极小化()()kqs得211(())()kkkkksfxfxGg7进而得牛顿算法的迭代公式:11kkkkxxGg.关于牛顿算法的若干评注①牛顿算法可视为椭球范数kG下的最速下降算法。事实上，欧氏空间nR中一般范数下的方向导数定义为：0()()()limTTkkkkfxsfxfxsgsdfdssss（它显然与范数有关）显然，minnTksRgss的最优解就是函数()fx在kx处对应于范数的最速下降方向。容易理解，这个解与所取的范数有关。a)当取欧氏范数（2范数）时，可证kksg是最速下降方向；b)若取椭球范数kG，最速下降方向则为1kkksGg。事实上，1111(,)kkkkkkkkTTkkGkkGGkkkkkkGGGGGGgsGgsgsgGGsGgssss即nsR，有1kkTkkkGGgsGgs（意味着1kkkGGg为方向导数下界）另一方面，若取1kksGg时11121()()kkkkkkkTTTkkkkkkkkkGGGGkkGGGgsgGgGgGGgsssssGgs方向导数达到下界1kkkGGg，故1kkksGg是对于椭球范数kG的最速下降方向。②牛顿算法实际上就是非线性方程组的牛顿迭代法。由于min()nxRfx等价于求解非线性方程组()0fx设kx是当前迭代点，若()0kfx，则kx是方程组的解，否则将()fx在kx处线性化，得2()()()()0kkkfxfxfxxx8将上述线性方程组的解作为()0fx的近似解，得21()()kkkxxfxfx故有211()()kkkkxxfxfx，这恰好就是牛顿迭代公式。二、牛顿法的收敛性定理3.7设(2)fC，kx充分靠近极小点*x，而*()0fx，2*()fx正定，若进一步假设Hessian矩阵()Gx满足Lipschitz条件。则由牛顿法产生的序列kx收敛于*x，且具有二阶的收敛速度。证明：由*11***00(())()()(())()kkkkkkdgxxxgxgxdGxxxxxdd及()Gx满足Lipschitz条件，可得1****02**()()()()[(())()]()()()()()kkkkkkkkkkkgxgxGxxxGxxxGxxxdgxGxxxoxx故有2**0()()()()kkkkgxGxxxoxx（*）由于(2)fC，*2*()Gfx正定，故当kx充分靠近*x时，kG正定，且1kG有上界。事实上，设()()1,,kkn是kG的特征值，且()1k最大，()kn最小，则1kG的特征值为()()