99
99
令 () 16 ( 1 4 ) 16 ( 4 8 ) 0
9 99
99 9
得
1
5 12
从而得
x2
x1
1 p1
(2, 27
2 )T 27
p 2 f (x2 ) 4 (2,1)T 27
p 2 4 5 0.1 27
故进行第三次迭代运算:
从x2=(2/27,2/27)T出发进行一维搜索，即构造
最速下降法
最速下降法，也称为梯度下降法，是由法国著名数学家Cauchy在 1847年提出的。
最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽 然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进 和修正而得到的。
最速下降法是用负梯度方向为搜索方向，算法非常简单，并且通常 对凸解析函数也有良好的收敛性。
改进后的算法
Step1: x0 Rn 精度ε>0，自然数N>=2,k=0
Step2： 计算 pk f (xk )
Step3： 如果 f (xk ) ，则转Step5；否则进行一维搜索
f
(xk
k
pk
)
min
0
f
(xk
p k
)
，令
x k1 x k k p k , k k 1
若k>=N,且k/3-[k/3]=0.则转Step4，否则转Step2.
() f (x 2 p 2 ) 2( 2 8 )2 ( 2 4 )2
27 27
27 27
令 () 32 ( 2 8 ) 8 ( 2 4 ) 0
27 27 27
27 27 27
得
2
5 18
从而得x3Fra bibliotekx22 p2
( 2 , 8 )T 243 243
p3 f (x3 ) ( 8 , 16 )T 243 243
Step4： 计算 s k xk xk2 ，进行一维搜索
f
(xk
k sk
)
min
0
f
(xk
s k
)
令 x k1 x k k s k , k k 1 ，转Step2
Step5： 停止，输出 x* xk
小结
1、优点： 计算简单，需记忆的容量小；对初始点要求低，稳定性高；远
离极小点时收敛快，常作为其它方法的第一步。
d () df (xk pk )
d
d
f1 (x1k
p1k ) p1k
f
2
(
x2k
p2k ) p2k
...
f
n
(
xnk
pnk ) pnk
f (xk pk )T pk
k是一元函数f(xk+ λ pk)的极值点，
d () d
| k
df
(xk
d
pk )
| k
0
▽f(xk +λ kpk)Tpk=0，即(pk+1)Tpk=0。也就是说，有目标函数在一维搜索产生 的新点xk+1= xk+ λ kpk处的梯度与产生该点时所用的搜索方向是正交的。
令 得 从而得
() 16(1 4) 4(1 2) 0
0
5 18
x1
x0
0
p0
( 1 , 4)T 99
p1 f (x1 ) ( 4 , 8)T 99
p1 4 5 0.1 9
故进行第二次迭代运算:
从x1=(-1/9,4/9)T出发进行一维搜索，即构造
() f (x1 p1 ) 2( 1 4 )2 ( 4 8 )2
最速下降法的基本思想
从任意一点xk出发，沿该点负梯度方向pk=-▽f(xk)进行一维搜索，
设f(xk+ λ kpk)=min f(xk+ λ pk) (λ >0)，令xk+1= xk+ λ kpk为f(x)新的近似最优 解。
再从新点xk+1出发，沿该点的负梯度方向pk+1=-▽f(xk+1)进行一维搜
例. 用最速下降法求函数f (x1, x2)＝2x12+x22 的极小点,取x0=[1,1]T , ε=0.1。 解 由题意得
f (x) (4x1 ,2x2 )T
p0 f (x0 ) (4,2)T
由于
p0 20 0.1
故进行第一次迭代 从x0=(1,1)T出发进行一维搜索，即构造
() f (x0 p0 ) 2(1 4)2 (1 2)2
索，进一步求出新的近似最优解xk+2。 如此迭代，直到某点的梯度为零向量或梯度的范数小于事先给定
的精度为止。
给定x0，ε>0，k=0
算法
计算pk=-▽f(xk)
|| ▽ f(xk)||< ε N
f(xk+ λ kpk)=min f(xk+ λ pk) (λ >0)
Y 停止，打印xk
xk+1= xk+ λ kpk，k=k+1
p 3 4 5 0.0368 0.1 243
停止迭代 故最优解为
x x3 ( 2 , 8 )T 243 243
最速下降法的搜索路径呈直角锯齿形
设xk=(xk1 , xk2 …..xkn),pk=(pk1 , pk2 …..pkn),则 令θ(λ )= f(xk+ λ pk) = f(xk1 + λ pk1, xk2 + λ pk2 ,…., xkn + λ pkn)
2、缺点： 收敛速度较慢。尤其当目标函数等值面是很扁的椭圆、椭球或
类似图形时，收敛更慢。