r 所以 r(k) (k1) 是相互垂直的
锯齿现象
在极小点附近，目标函数可以用二次函数近似，其等值面近似 椭球面。
x2 x1
x*
x3
注 最速下降方向反映了目 标函数的一种局部性质。它只是 局部目标函数值下降最快的方向。 最速下降法是线性收敛的算法。
梯度法（最速下降法）：
1. 搜索方向：r(k) f (x(k) ) ,也称为最速下降方向；
• （2）在确定搜索方向上，用什么方法进行一 维搜索?
基本迭代格式 xk1 xk tk dk
几个概念
1。梯度：
f(x)是定义在Rn上的可微函数，称以f(x)的n个偏 导数为分量的向量，为f(x)的梯度，记作▽ f(x)
即
T
f
(
x)
f (x) x1
,
f (x) x2
,
...,
f (x) xn
什么情况下迭代可以停止了呢？
(r (k ) )T r (k ) 或者 || f ( x (k) ) ||
由于 r(k1) b Ax(k1) b A(x(k) tk r(k ) ) r(k ) tk Ar(k )
(r (k ) )T r (k 1) (r (k ) )T (r (k ) tk Ar (k ) ) 0
3.3.5 最速下降法和共轭梯度法
－－多变量函数寻优法
1.等价的极限问题
设 x * 是方程组 Ax b 的精确解
即：Ax* b
若A是正定对称矩阵，则当且仅当x=x*时，二次函数
F0 (x) (x x*)T A(x x*) xT Ax 2bT x (x*)T Ax *
达到极小值。F0 (x*) 0
2。梯度向量：
称
f
(
x0
)
f (x0 x1
)
,
f (x0 x2
)
,
...,
f (x0 xn
)
T
为f(x) 在x0处的梯度向量。
3。梯度▽ f(x)的模：
|| f ( x) ||
f ( x x1
)
2
f ( x) x2
2
,
f ( x xn
)
2
几个梯度公式
• 1。f(x)＝C（常数），则▽f(x)＝0。 • 2。 f(x)=bTx，则 ▽f(x)＝b； • 3。 ▽ (xTx)＝2x； • 4。若A是实对称方阵，则有▽ (xTAx)＝2Ax；
解： f ( x) ( 2x1 ,6x2 )T , r1 f (x1) ( 4, 6 )T .
x1 tr1 ( 2 4t ,1 6t )T .
令 g(t) f (x1 tr1) (2 4t)2 3(1 6t)2 ，
求解 min g(t)
t
令 g(t) 8( 2 4t) 36(1 6t ) 0
t1
13 62
x2
x1
t1r1
(
36 , 31
8 31
)T
3.共轭梯度法
定理 2. 设有函数 f ( x) 1 xT Ax bT x c ， 2
其中 A是 n阶对称正定矩阵。d (1) , d (2) ,..., d (k) 是一组A共轭向量。
所以 r(0) (b Ax(0) )
是 x(0) 下降速度最快的方向。
因此沿直线 x x(0) tr(0)
求F(x)的极小值点x*。也就选择t使得; g(t) F (x) F (x(0) tr (0) ) (x(0) tr (0) )T A(x(0) tr (0) ) 2bT (x(0) tr (0) ) F (x(0) ) 2tr (0) (r (0) )T t 2 (r(0) )T Ar(0)
当cos 1 时，gkTdk 取极小值． dk gk .
结论：负梯度方向使 f x 下降最快，亦即最速
下降方向．
优化设计追求目标函数值最小，搜索方向取该点的负梯度 方向，使函数值在该点附近的范围内下降最快。
F
(
x0
)
f (x0 x1
)
,
ห้องสมุดไป่ตู้
f (x0 x2
)
,
...,
f (x0 xn
)
T
2( Ax(0) b) 2r(0)
X E n 求解的基本思想 ( 以二元函数为例 )
f (x1 x2 )
连 续 可 微
0
x1
x2
f (X0) f (X1) f (X2)
X0
31
X1
X2
x2
5
0
x1
关于无约束极小问题普遍使用下降迭代算法, 每一类下降选代算法中包含两个关键步骤：
得到一个迭代点x(k)后， • （1） 如何选择搜索方向d(k)？
2. 搜索步长 : tk
取最优步长,
即满足
f (x(k)
tk
r
(k)
)
min t
f (x(k)
tr(k) ) 。
梯度法算法步骤：
1. 给定初始点 x(0) Rn ,允许误差 0, 令k 1。
2. 计算搜索方向 t(k) f (x(k) ) ;
3. 若|| r(k) || ,则停止计算，x(k)为所求极值点；否则，求最优步长 tk
使得
f
(x(k)
tkr(k) )
min t
f
(x(k)
tr(k) )。
4. 令 x(k1) x(k ) tk r(k ) , 令 k : k 1, 转2。
例. 用最速下降法求解: min f ( x) x12 3x22 ,设初始点为x1 ( 2,1)T , 求迭代一次后的迭代点 x2。
2.最速下降法
讨论如何从 x(0) 出发，求F(x)的极小值点。
基本迭代格式 xk1 xk tk dk
问题的提出
在点 xk 处，沿什么方向 dk , f x下降最快?
分析：f xk dk f xk gkTdk o dk 0
考查： gkTdk gk dk cos
gk f ( xk )
达到极小值点，即 g(t) 0
t0
(r (0) )T r (0) (r (0) )T Ar (0)
从而得到新的近似点 x(1)
用同样的方法就可以得到 x(2)
一般的
x(k 1)
tk
x(k) tk r(k) (r (k ) )T r(k ) (r(k ) )T Ar(k )
r(k) b Ax(k)
极小值与函数相同
F (x) xT Ax 2bT x
所以求解 Ax b
等价于求函数的极小值 F (x) xT Ax 2bT x
设A是对称正定矩阵，则函数族
{F (x) c; x Rn , c R}
代表 Rn 中的一族n维球面，x*是这个球面的中心
求解无约束最优化问题的基本思想
min f X