1 2
(
x

xk
)T
Hessf
(
xk
)(
x

xk ) R
15:30
一阶导数推广
二阶导数推广
5/41
预备知识 IV
f ( x) 1 ( Ax, x) (b, x) 2
n
n
=
1 2
aij xi x j bi xi
i, j1
i 1
gradf Ax b
2 f

x12
对任意 t∈R , 有
g(t) f (u tx) 1 ( A(u tx), u tx) (b, u tx)
2
t2
f (u) t( Au b, x) ( Ax, x)
2
当 t=0 时, g(0)= f(u)达到极小值, 所以 g′ (0) =0 ,即
( Au – b , x ) = 0 Au – b = 0
15:30
22/41
—— 共轭 ——
更加整体地考虑搜索方向的选择, 选择一组 关于A共轭的向量:
n 个向量 p0, p1 ,···, pn-1 共轭:
(Api , pj )=0 (i≠j; i, j = 0,1,···,n-1 )
n1
n1
我们有x* i pi且b=Ax* i Api
在 x 处,梯度方向是 f(x) 增长最快方向 负梯度方向是 f(x) 下降最快方向
f ( x) f ( xk ) (gradf ( xk ))T ( x xk ) f ( xk ) tk (gradf ( xk ))T dk , 其中dk为x xk单位向量,tk为步长。
(a,b) || a ||| b || cos a,b ,其中 a,b 表示向量a和b的夹角。
最速下降法
15:30
f(x1,x2)=100x12+x22
BB方法
15:30
局部思想:
最速下降法思想简单,但是收敛速度慢。本 质上是因为负梯度方向函数下降快是局部性质。
全局思想: N 维空间的任意向量可以由N个线性无关的
向量线性表示。
15:30
20/41
The Best of the 20th Century: Editors Name Top 10 Algorithms, SIAM News
( x1

x1k
)

f ( xk ) x2
( x2

x2k
)

1 2
( x 2 f ( xk )
x1x1
1

x1k )( x1

x1k )
( x 2 f ( xk )
x1x2
1

( x 2 f ( xk )
x2x2
2

x2k )( x2
对任意 x∈R n , 只须证明 f (x) – f (u) ≥ 0
f ( x) f (u) 1 ( Ax, x) (b, x) 1 ( Au, u)
2
2
1 ( A( x u),( x u)) 0 2
15:30
8/41
设 u 使 f(x) 取极小值。取非零向量 x∈R n,
f
( x(0)

t0r0 )

min tR
f
( x(0)

t
r0 )
记 g(t ) f ( x(0) ) t( Ax(0) b, r0 ) t 2 ( Ar0 , r0 ) / 2
为选取最佳步长 t0 ，令
g(t ) ( Ax(0) b, r0 ) t( Ar0 , r0 ) 0

x12
L
Hessf M O

2 f
xnx1
L
2 f
x1xn

M
2 f

xn2
Hessf


2 x22 x32 4 x1 x2 x32
4 x1 x22 x3
4 x1 x2 x32 2 x12 x32 4 x12 x2 x3
4 4

rk

ik
( Api , rk ) ( Api , pi )
pi
rk
ik
piT Ark piT Api
pi
24/41
原始共轭梯度算法 第一步:取初值 x(0)∈R(n) , >0, 计算 r0 = b – Ax(0), 若 || r0||≤ 结束; 否则 p0r0, k 1, 转第二步;
求解得 t0 = ( r0 , r0) / (Ar0 , r0)
15:30
12/41
解对称正定方程组Ax = b 的最速下降算法: 第一步: 取初值 x(0)∈R(n) , >0,计算
r0 = b – Ax(0), k 0; 第二步: 计算 tk = (rk ,rk ) / (Ark , rk)
第二步: 计算 k1= (pk-1,b ) / (Apk-1, pk-1) x(k) = x(k-1) + k 1 pk-1 ;
第三步: 如果 k = n, 则结束;
否则计算 rk = b – Ax(k), 转第四步; 第四步: 如果 ||rk|| ≤ , 则结束;否则计算
j = -(Apj , rk ) / (Apj , pj ) , ( j = 0,···, k-1) pk = rk + ( 0 p0+ ···+ k1 pk-1 ) 15:30 k k+ 1,转第二步。

x2k )
R
n
f ( x) f ( xk )
( x f ( xk )
xi
i

xik )
i 1
n

1 2
( x 2 f ( xk )
xix j
i

xik )( x j

x
k j
)

R
i , j1
f (x)
f ( xk ) (gradf ( xk ))T ( x xk )
15:30
7/41
定理4.10(初等变分原理) 设A =(aij )n×n为实对称正 定矩阵, x, b Rn 则 x是二次函数
f ( x) 1 ( Ax, x) (b, x) 2
的极小值点 x 是线性方程组 Ax = b 的解。
证明: 设 u 是 Ax = b的解 Au = b f (u) 1 ( Au, u) 2
i0
i0
n1
对任意的pk , pkTb pkT Ax* i pkT Api k pkT Apk
i0
15:30
系数计算k

pkTb pkT Apk
23/41
—— 共轭向量组构造 ——
思路: 借鉴Gram-Schmidt正交化过程
u1 v1,
u v u , (u1,v2 )
x1 x12
x22 x2
x3 x3

2 x12 x22
15:30
4/41
泰勒展式:
预备知识 III
f ( x) f ( xk ) f ( xk )( x xk ) f ( xk )( x xk )2 R
f (x)
f
(xk
)

f ( xk ) x1
两个向量 p1, p2关于 A共轭: (Ap1, p2)=0
n 个向量 p0, p1 ,···, pn-1 共轭:
(Api , pj )=0
(i≠j; i, j = 0,1,···,n-1 )
非零向量 p0, p1 ,···, pn-1 ∈Rn
p0, p1 ,···, pn-1 关于 A 共轭
p0, p1 ,···, pn-1 线性无关
设A是 n 阶对称正定阵 ▪( Ax, y ) = ( x, Ay )= (A y, x )= ( y, Ax ); ▪( Ax，x ) ≥0, 且( Ax, x) = 0 x = 0
15:30
3/41
预备知识 II
梯度: f ( x) gradf ( x)
, ,L , f f
从初值点 x(0) 出发,以负梯度方向 r 为搜索方向 选择步长 t0, 使 x(1) = x(0) + t0r 为 f(x) 极小值点
最速下降方向: r = –f = b – Ax
15:30
11/41
取初值点 x(0), 取负梯度方向 r0 = b – A x(0)
求点: x(1) = x(0) + t0r0 使得
所以u 是方程组 Ax = b 的解。
15:30
9/41
瞎子与计算机
• 瞎子: 能感觉到脚下的坡度(这是海拔函数 在当前点的梯度值),但不知道山上其它点 的任何情况
• 计算机: 计算目标函数在该点的信息(如函 数值和梯度值), 但不知道其它点的信息
15:30
最速下降法(Gradient Descent)
• 方向(最速下降) (best rk) • 步长(精确搜索) (best tk) • x(k+1) = x(k) + tkrk 是否最好 ?
15:30
Rosenbrock 方程 f(x1,x2)=(1-x1)2+100(x2-x12)2
15:30
Rosenbrock 方程 f(x1,x2)=(1-x1)2+100(x2-x12)2
x(k+1) = x(k) + tk rk ; rk+1 = b – Ax(k+1) ;