最优化之最速下降法.ppt

最优化之最速下降法
第一页，共15页
最速下降法的由来
最速下降法的方向选择
最速下降法的算法步骤
最速下降法的实例
最速下降法
由Nordri®（ ） 设计提供
第二页，共15页
LOGO
最速下降法的由来
由Nordri®（ ） 设计提供
考虑无约束问题
其中，函数法f(x)具有一阶连续偏导数。
人们在处理这类问题时，总希望从某一点出发，选择一个目标函数值下降最快的方向，以利于尽快达到极小点，基于此种愿望，早在1847年法国数学家Cauchy提出了最速下降法。后来，Curry等人作了进一步研究，得出现在众所周知的一种最基本算法。
第三页，共15页
最速下降法的由来
其主要思想
每次沿负梯度方向进行搜索
●
●
等值线(面)
●
第四页，共15页
LOGO
最速下降法的方向选择
最速下降法用负梯度为方向
作为搜索方向。设 f(x) 在XK附近连续可微，dk为搜索方向向量，
.由泰勒展开式得
那么目标函数 f(x)在Xk处沿方向dk下降的变化率为
由Nordri®（ ） 设计提供
第五页，共15页
LOGO
最速下降法的方向选择
其中 为gk与dk的夹角。要使得变化率最小，只有当cos值为-1时，才能达到，也即dk应取得负梯度方向。
第六页，共15页
，容许误差 。令k:=1.
2. 计算 。若 ，停算，输出Xk作为近似最优解。
=-gk。
。
， 转步长1。
最速下降法的步骤
第七页，共15页
由式 得，

即新点xk+1处的梯度是正交的，也就是说，迭代点列所走 的路线是锯齿型的，故收敛速度是很慢的。
第八页，共15页
步长因子
步4中，步长因子 的确定即可以采用精确线搜索又可以采用非精确线搜索。
采用精确线搜索时


那么 应该满足


由此我们可以求出步长因子。
第九页，共15页
函数 f（x1,x2）=(1-x2)^2+100*(x2-x1^2)^2,它叫罗森布罗克方程。
第十页，共15页