梯度下降法
梯度下降法,就是利用负梯度方向来决定每次迭代的新的搜索方向,使得每次迭代能使待优化的目标函数逐步减小。梯度下降法是2范数下的最速下降法。
最速下降法的一种简单形式是:x(k+1)=x(k)-a*g(k),其中a称为学习速率,可以是较小的常数。 g(k)是x(k)的梯度。
直观的说,就是在一个有中心的等值线中,从初始值开始,每次沿着垂直等值线方向移动一个小的距离,最终收敛在中心。
对于某一个性能指数,我们能够运用梯度下降法,使这个指数降到最小。若该指数为均方误差,我们便得到了最小均方误差(LMS)算法。
多维无约束优化算法——梯度法
一、基本原理
通过变量轮换法、共轭方向法等的讨论,我们知道对多维无约束问题优化总是将其转化为在一系列选定方向进行一维搜索,使目标函数值步步降低直至逼近目标函数极小点,而
方向的选择与迭代速度、计算效率关系很大。人们利用函数在其负梯度方向函数值下降最快这一局部性质,将n维无约束极小化问题转化为一系列沿目标函数负梯度方向一维搜索寻优,这就成为梯度法的基本构想。据此我们将无约束优化迭代的通式
可分别得到两种表达形式的梯度法迭代公式 中的搜索方向取为负梯度向量或单位负梯度向量,即
(1)
(2)
式中,,分别为函数在迭代点处的梯度和梯度的模;两式中均为最优步长因子,各自分别通过一维极小化和
。
按照梯度法迭代公式(1)或(2)进行若干次一维搜索,每次迭代的初始点取上次迭代的终点,即可使迭
代点逐步逼近目标函数的极小点。其迭代的终止条件可采用点距准则或梯度准则,即当或时终止迭代。
二、迭代过程及算法框图
梯度法的具体迭代步骤如下:
(l)给定初始点,迭代精度,维数n。
(2)置。
(3)计算迭代点的梯度
计算梯度的模
计算搜索方向
(4)检验是否满足迭代终止条件
;否则进行下一步。 ?
若满足,停止迭代,输出最优解:
(5)从点出发,沿负梯度方向进行一维搜索求最优步长
,使
。
(6)计算迭代新点。
(7)置,返回步骤(3)进行下一次迭代计算。
梯度法的算法框图如图1所示。
三、效能特点
梯度法每次迭代都是沿迭代点函数值下降最快的方向搜索,因而梯度法又称为最速下降法。其实,这种方法搜索路线常很曲折,收敛速度较慢。这可由图2所示一般的二维二次目标函数的情况加以说明。从任意迭代点出发,沿其负梯度方向一维搜索到极小点,则点应为向量与目标函数等值线的性质可知的切点。下次迭代从应是目标函数等值线点出发,沿其负梯度方向在点的法线,因而一维搜索,根据梯度方向与必为正交向量。这就表明,梯度法迭代过程中前后两次迭代向量为正交。故梯度法迭代过程是呈直角锯齿形路线曲折走向目标函数的极小点。图2可以清楚的看出梯度法搜索开始时步长较大,愈接近极小点步长愈小,最后收敛的速度极其缓慢。所谓“最速下降”只是指函数在迭代点的局部特性,一旦离开了该迭代点,原先的负梯度方向就不再是最速下降方向。从整个迭代过程来看,负梯度方向并非是最速下降方向。对于目标函数等值线为同心圆、任选初始点(见图3(a))以及目标函数等值线为同心椭圆、初始点选在其对称轴或上(见图3(b))等特例,则采用负梯度方向一次搜索即达全域极小点
降方向。
梯度法尽管收敛速度较慢,但其迭代的几何概念比较直观,方法和程序简单,虽要计算导数,但只要求一阶偏导,存储单元较少。此外,当迭代点距目标函数极小点尚远时,无论目标函数是否具有二次性,梯度法开始迭代时的下降速度还是很快的。常常利用这个特点,将梯度法和其他方法配合使用构成更有效和实用的算法,在理论上梯度法仍不失为一种极为重要的基本优化方法。 ,对整个迭代过程而言亦是最速下