根据Schwartz不等式 (a12 a22 an2 )(b12 b22 bn2 ) (a1b1 anbn )2
故有 ( pT
p)(qTq）（pTq)2 ，从而
( pT
p)(qT q) ( pTq)2 qT q
0
(10.4.21)
p( j)T q( j) jd ( j)T (g j1 g j ) jd ( j)T g j 由于λj>0,gj≠0,Hj
j (H j g j )T
gj
j
g
T j
H
j
g
j
,
正定，从而
p( j)T q( j) 0
(10.4.22)
( yT p( j) )2 p( j)T q( j)
0
(10.4.23)
接下来证明（10.4.20）等式右端两项不能同时为零。 假设第一项为零，则p//q，即p=βq，（β为非零常数）
将
代入上式得到
证明：
思路：归纳法。用k归纳。先证k=1、2时两式成立，再假设 k=m时两式成立，证明k=m+1时也成立。
k
1时，H2 Ap(1)
(H1
p(1) p(1)T p(1) qT (1)
H1q q (1) (1)T H1
q H q (1)T
(1)
1×1
1
) Ap(1)
1×1
Ap(i) A( x(i1) x(i) ) g(i1) g(i) q(i) ,
搜索方向
最速下降法： 共轭梯度法： 牛顿法：
牛顿方向
牛顿方向
是如下问题的解
牛顿法的优缺点
收敛快 －－－ 二次收敛 程序简单
计算量大 －－－ 需要二阶导数 要求高 －－－ 需要二阶导数 需要计算Hesse矩阵，而此矩阵可能非正定， 可能导致搜索方向不是下降方向。
找替代牛顿法的方法
目标： 收敛快 程序简单
f ( x(k ) ) f ( x(k1) ) 2 f ( x(k1) )( x(k ) x(k1) )
p(k ) : x(k1) x(k) q(k ) : f (x(k1) ) f (x(k) )
q(k ) 2 f (x(k1) ) p(k ) p(k ) 2 f (x(k 1) )1 q(k )
（10.4.16）
DFP算法
容易验证，这样定义校正矩阵 Hk，得到的矩阵
Hk1 Hk
p(k) p(k)T p(k )T q(k )
Hk q(k ) q(k )T Hk （10.4.17） q(k)T Hk q(k )
满足拟牛顿条件(10.4.7)。(10.4.17)式称为DFP公式。
DFP方法的计算步骤：
并用(10.4.14)求出在点x(k+1)出发的搜索方向d(k+1)。
以此类推，直至|| f (x(k) ) || ，
是事先给定的允许误差。
DFP算法
Hk k u(k ) u(k )T kv(k ) v(k )T
p(k ) Hk1q(k )
(Hk
k u(k )u(k )T
v v (k ) (k )T k
yT H j y
( yT p( j) )2 p( j)T q ( j)
( yT H jq( j) )2 q ( j)T H j q ( j)
(10.4.18)
11
因为Hj是对称正定阵，故存在对称正定阵Hj1/2,使得
Hj
H
2 j
H
2 j
.
1
1
令
p
H
2 j
y,
q
H
2 j
q(i
)
,
(10.4.19)
则有 yT H j y pT p, yT H jq(j) pT q,
2
1
5 18
4 2
9
4
, 得到
g2
4 9
8
.
9
9
算出
p(1) x(2) x(1) 1d (1)
根据DFP定义的ΔHk，得
10 9
5 9
,
q(1)
g2
g1
40 9
10 9
,
H2
H1
p(1) p(1)T p(1)T q (1)
H1q (1)q (1)T H1 q (1)T H1q (1)
x(1) x(n1)
p(k ) x(k1) x(k ) q(k ) f ( x(k1) ) f ( x(k ) ) H k H k1 H k H k k : k 1
例10.4.1 用DFP方法求解如下问题：
min 2x12 x22 4x1 2
解：
初始点及初始矩阵分别取为：
x( 1 )
DFP算法的正定性及二次终止性
1、正定性 DFP方法构造的矩阵Hk是对称的正定矩阵
搜索方向 d (k) Hkf (x(k) ) 均为下降方向
每次迭代使函数值有所下降
定理10.4.1 若gi≠0(i=1,2,....,n)，则DFP方法构造的 矩阵Hi(i=1,2,,.....,n)为对称正定矩阵。
d (k) Hkf (x(k) )
然后沿d(k)方向搜索，求步长 k ,满足
f
(x(k)
k d (k) )
min
0
f
(x(k)
k d (k) )
从而确定出后继点 x(k1) x(k) k d (k)
求出点x(k+1)处的梯度 f (x(k1) ) 以及 p(k) 和q(k) ，再利用
(10.4.13)式计算 Hk+1 ，
（10.4.5） （10.4.6）
p(k ) Hk1q(k )
（10.4.7）
1.秩1校正 2.DFP(Davidon-Fletcher-Powell)算法：
秩2校正
3.BFGS(Broyden-Fletcher-GoldfarbShanno)公式及Broyden族
H1 I; Hk1 Hk Hk
（5）检验是否满足收敛准则，若 f (x(k1)) 时则停止迭代，
得到点 __
x x(k1)
；否则，进行步骤（6）。
（6）若k=n,则令 x(1) x(k1) ，返回步骤（2）；否则，进行步骤
（7）。
（7）令 gk1 f (x(k1) ), p(k) x(k1) x(k) , q(k) gk1 gk 。利用 （10.4.17）计算Hk+1,令k=k+1，返回步骤（3）。
同时 不需要二阶导数
找： 像牛顿 又不是牛顿 的家伙！！！
基本思想：
用不包含二阶导数的矩阵近似Hesse矩阵的逆。
拟牛顿条件
d (k) 2 f H( xk(k) )1f ( x(k) )
x x d (k1)
(k)
(k ) （10.4.1）
k
首先分析2 f (x(k) )1与一阶导数的关系：
当i=m+1时，因为Ap(m+1)=q(m+1)，代入上式得到
当i<m+1时，有Hm+1Ap(i)=p(i)成立及p(i)TAp(m+1)=0（已证）。在 式（10.4.29）中有 同时，把（10.4.29）中的Ap(i)乘入括号内，则有
2
1
,
H1
1 0
0 1
,
点x=x(x1,x2)T的梯度及在x（1）处的梯度：g
4(x1 1)
2x2
,
4 g1 2 ,
令搜索方向为
d (1)
H1 g1
4 2
从x（1）出发沿d（1）做一维搜索：min 0
f ( x (1) d (1) ),得到λ1=5/18。
令
8
x (2)
x (1)
1d (1)
计 算 步
骤：
重置
x(1) , 0
H1 In , d (1) f ( x(1) ), k 1
Y
f ( x(k) )
x x(k)
N
d (k ) H kf ( x(k ) )
k
arg min 0
f (x(k)
d (k) )
x(k1) x(k ) kd (k )
N
k n?
Y
证明：
思路：归纳法。在DFP方法中H1给定的n阶单位阵，只要假设Hj 是对称正定阵成立，证明Hj也是对称正定阵。
对任意非零量 y Rn ，
yT H j1 y
yT H j y
yT p( j) p( j)T p( j)T q ( j)

yT H j q ( j)q ( j)T H j y q ( j)T H j q ( j)
)q(k )
k u(k )u(k )T q(k ) kv(k )v(k )T q(k ) p(k ) Hkq(k )
令u(k )
p(k )；k
1 u(k )T q(k )
;v(k)
Hk q(k )； k
1 v(k )T q(k )
H k
p(k) p(k)T p(k )T q(k )
Hkq(k) q(k)T Hk q(k )T Hkq(k)
先证k=m+1时（10.4.24）成立。
当1=<i<=m时，有 Hm1Ap(i) p(i) ,
由此得出：p(i)T Ap(m1) p(i)T A(m1Hm1gm1) m1gmT 1Hm1Ap(i)
g p T (i)
m1 m1
m1gmT 1id (i).
(10.4.28)
因为有 gmT 1d (i) 0, i m 1,
在 点x ( k 1) 处 进 行 二 阶Tayl or展 开 ：
f ( x) f ( x(k1) ) f ( x(k1) )( x x(k1) ) 1 ( x x(k1) )T 2 f ( x(k1) )( x x(k1) )