文档介绍：第十章使用导数的最优化方法
◆最速下降法
●牛顿法
◆共轭梯度法
◆拟牛顿法
●信赖域法
101最速下降法
考虑无约束问题minf(x),xRn()
其中f(x)具有一阶连续偏导数。
在处理这类问题时,一般策略是,希望从某一点出发,选择
个目标函数值下降最快的方向,沿此方向搜索以期尽快达
到极小点,基于这一思想, Cauchy于1847年提出了最速下降
法。这是无约束最优化中最简单的方法。
-1
函数f(x)在点x处沿方向d的变化率可用方向导数表
示,当函数可微时有,方向导数
D(x,d)=Vf(x)d()
求函数f(x)在点x处下降最快的方向,归结为求
min Vf(x)d
st|l‖s1
由 Schwartz不等式,
Vf(x)'a s vf(xo)lal lf(x
VfO
(14)
101最速下降法-2
d
Vf(x)
Vf()
时等号成立故在点x处沿()所定义的方向变化
率最小,即负梯度方向为最速下降方向
注意:在不同的尺度下最速下降方向是不同的
101最速下降法-3
●最速下降算法
最速下降算法的迭代公式为
(k+1)
其中d)是从x出发的搜索方向,此处取在点x的最速下降
方向,即d)=-Vf(x*)
λ是从x出发沿方向d进行一维搜索的步长,即满足
f(x+hd)=minf(x+ad
-4
●算法描述
Sepl给定初始点x∈E”,允许误差E>0,置k
Sep2,计算搜索方向d=Vf(x)
Sgy3若|p,停止,否则,从x出发,沿d进行一维搜索
求λk,使得f(x)+1d()=minf(x)+2d6)
Srep4,令x+)=x)+2d(,置k:=k+1,转Sep2
min
f(x)=2x2+x
初点xD=(,1)2,E
第一次迭代
目标函数fx)在点x处的梯度
令搜索方向
6+4=2√5>1/10
从x出发沿方向d进行一维搜索,求步长λ,即
min
A≥0
q(2)***@f(x0)+nd0
x)+d(=
21-2
()=2(1-44)2+(1-2)2
令
q(4)=-16(1-44)-4(1-2)=0
=5/18
在直线上的极小点
1/9
第二次迭代
4/9
f(x)在点x2处的最速下降方向为
4/9
8/9
(2)
4
>1/10
从x2出发,沿方向d(2进行一维搜索:
minp(a)***@f(x)+nd z)
A≥>0
4/91「(-1+4)/9
d
4/9
8/9(4-8元)/9
0()=2(-1+4x)2+6(-2)
81
64
q’()=。(-1+4九)-,(1-2x)=0
A2=5/12