梯度下降法、牛顿迭代法、共轭梯度法复习过程

1、梯度下降法、牛顿迭代法、共轭梯度法（参见：神经网络-PGM-ANN-2009-C09性能优化）优化的目的是求出目标函数的最大值点或者最小值点，这里讨论的是迭代的方法梯度下降法首先，给定一个初始猜测值，然后按照等式X k广气+气Pk或Xk=（XkXk）kP.（2）逐步修改猜测。这里向量Pk代表一个搜索方向，一个大于零的纯量以k为学习 速度，它确定了学习步长。当用 Xk+1 = xk +戏k p k进行最优点迭代时，函数应该在每次迭代时都减小，即”（X k + 1 ） F （ X k ）考虑F (x) = F (x *) + V F (x) t (x - x *)/、 L 、/、+ 一 (x -

2、x *) T V 2 F (x)(x - x *) +（3）X = X *的F(X)在Xk的一阶泰勒级数展开：F (X k 1) = F (X k + AX k) a F (X k) + gT AX(4)其中，gT为在旧猜测值xk处的梯度gk 三 VF(X) x=xk(5)要使 F (X s 1) F (X k)只需要(4)中右端第二项小于0,即gT AX =a gT P 0 k k k k k(6)选择较小的正数ak。这就隐含gk 0。满足gTP 0的任意向量成为一个下降方向。如果沿着此方向取足够小步长，函数一 kk定递减。并且，最速下降的情况发生在g；p最小的时候，容易知道，当Pk= -

3、g k时g；P最 小，此时，方向向量与梯度方向相反。在(1)式中，令P = -g，则有X k广Xk=g对于式(7)中学习速率a的选取通常有两种方法：一种是选择固定的学习速率a， kk另一种方法是使基于学习速率0的性能指数或目标函数F(Xk+1)在每次迭代中最小化，即沿着梯度反方向实现最小化：Xk+1 = Xkakgk。注意：1、对于较小的学习速度最速下降轨迹的路径总是与轮廓线正交，这是因为梯度与轮廓 线总是正交的。2、如果改变学习速度，学习速度太大，算法会变得不稳定，振荡不会衰减，反而会增大。3、)稳定的学习速率4、对于任意函数，确定最大可行的学习速度是不可能的，但对于二次函数，可以确定 一个

4、上界。令特征函数为：F (x) = 1 XtAX + dTX + c(8)2那么梯度为VF (X) = AX + d代入最速下降法公式(7)中X = X a g = X a (AX + d) = (I a A) X ad(9)k+ik k k k k kkk k在动态系统中，如果矩阵I-aA的特征值小于1，则该系统是稳定的。可用赫森矩阵A的特征值来表示该矩阵的特征值，假设A的特征值和特征向量分别为%，气，七和q, z2, z ,那么 TOC o 1-5 h z b - aAz = (I - aX.)z.(10) 于是，最速下降法的稳定条件为|/-aX | 1(11)i,2如果二次函数有一个强极

5、小点，则其特征值为正数，上式可以化为aXi由于该式对于赫森矩阵的所有特征值都成立则a (12)Xmax分析：最大的稳定学习速度与二次函数的最大的曲率成反比。曲率说明梯度变化的快慢。 如果梯度变化太快，可能会导致跳过极小点，进而使新的迭代点的梯度的值大于原迭代点的 梯度的值(但方向相反)。这会导致每次迭代的步长增大。5、沿直线最小化选择学习速率的另一种方法是匕使得每次迭代的性能指数最小化，即选择匕使得下 式最小：F (Xk + aP对任意函数的这种最小化需要线性搜索。对二次函数解析线性最小化是可能的。上式对ak的导数为:ddakF(X + a P ) = NF(X )t |k k kX = Xk

6、P + a PtV2F(X )1Pk k kX =Xk k(13)令式(13)导数为零求得gTPkkP APtk k k(14)VF(X)t |X = X一一 kPt V 2 F ( X )1PX=X k kk这里Ak为xk的赫森矩阵：A = V2F(X)1 x x牛顿法,牛顿法基于二阶泰勒级数：F(X ) = F(X +AX )机 F(X ) + gTAX +1 AXtA AX(15)k+1k kk k k 2 k k k牛顿法的原理是求F(X)的二次近似的驻点，求这个二次函数对AXk的梯度并令它等于0,则有(16)解得:AX =Agk k k(17)于是，牛顿法定义为注意：牛顿法总是用一个

7、二次函数逼近F(X)，然后求其驻点，因此此方法总能够一步 找到二次函数的极小点，如果原函数为二次函数(有强极小点)，它就能够实现一步极小化如果F(X)不是二次函数，则牛顿法一般不能在一步内收敛，是否收敛取决于具体的函数和初始点#尽管牛顿法的收敛速度通常比最速下降法快，但其表现很复杂，除了收敛到鞍点的问题 外，算法还可能震荡和发散，如果学习速率不太快或每步都实现线性极小化，最速下降法能 保证收敛牛顿法的另一个问题是需要对赫森矩阵及其逆阵的计算和存储共轭梯度法牛顿法有一个性质成为二次终结法(quadratic temination)，即它能在有限迭代次数 内使得二次函数极小化，但这需要计算和存储二

8、阶导数，当参数个数很大时，计算所有二阶 导数是很困难的。假定对下述二次函数确定极小点：F (x) = 1 XrAX + dTX + c(18)2当且仅当P：APj = 0,k。j时，称向量集合对于一个正定赫森矩阵A两两共轭。因为对称矩阵的特征向量是两两正交的。已经证明，如果存在沿着一个共轭方向集Pj 的精确线性搜索序列，就能够在最多n此搜索内实现具有n个参数的二次函数的精确极小化。注意到对于二次函数，有(19)VF (X) = AX + dV 2F (X) = A由于Ag = g -g = AAX，又有 AX = (X -X ) = a P，选择a 使函数F(X)kk+1kkk k+1 k k

9、 k在Pk方向上极小化，则共轭条件可重写称a PtAP =AXtAP =AgTP = 0,k。j kk j k j kj注意，第一次搜索方向匕是任意的，而七是与%垂直的任意向量。所以共轭向量集的数量是无限的。通常从最速下降法的方向开始搜索：P =-g 00每次迭代都要构造一个与尾。,”正交的向量Pk。可以将迭代形式简化为Pk = gk +。kPk-1通常选择(21)咨或&gT P-1 k -1kgTgkkgT g -1 k-1 kgT gkk1gT g-1 k -1 k综上，算法可以归纳为:1、选择如P =-g的与梯度相反的方向作为第一次搜索方向 TOC o 1-5 h z 002、根据AX= (X - X ) = a P进行下一步搜索，确定a以使函数沿搜索方向极k+1k+1k k kk小化3、根据P =一g +& P确定下一个搜索方向，计算&k+1k+1k+1 kk+14、如果