4、拟Newton算法 ( 变尺度法 )的一般步骤；
Step 1. 给定初始点x0 ,正定矩阵H0 ,精度 0，k : 0
Step 2. 计算搜索方向d k H kf ( x k );
step 3. 令 x k1 x k tk d k , 其中 tk : f ( x k tk d k ) min f ( x k t d k )。
(sk Hk yk
Hk )T yk
yk
)T
SR1校正：H k1
Hk
(sk
H k yk )(sk H k (sk H k yk )T yk
yk )T
SR1校正具有二次终止性， 即对于二次函数，它不 需要线搜索，
而具有n步终止性质 H n G 1 .
定理
设s0 , s1 ,
,
s
n
线性无关，那么对二次
满足上述方程的解很多 ，我们可以如下确定一 组解：
k uk ukT yk sk kvkvkT yk Hk yk
这样，我们可以取：
uk sk ,
k ukT y k 1,
vk H k y k , k vkT y k 1。
即：
uk sk , vk Hk yk ,
k
1 skT y k
x k1 x k t k H k f ( x k )
xk1 xk tk Hkf ( xk )
H k I时 梯度法 最速下降方向 d k f ( x k ) , 度量为 x xT I x
H k Gk1时 Newton法 Newton方向 d k Gk1f (xk ), 度量为 x xT Gk x
当Gk 0 时，有 f ( xk )T d k f ( xk )T Gk1gk gkT Gk1gk 0 ,
当Gk 0 时，d k是下降方向。
如果对Newton法稍作修正： xk1 xk tkd k tk : f ( x k tk d k ) min f ( x k t d k )
拟Newton条件
Hk
G
1 k
分析：Gk1 需满足的条件，并利用 此条件确定H k 。
记g( x) f ( x), gk f ( x k ) Gk f 2 ( x k ), 则因为
f ( x) f ( x k1 ) f ( x k1 )T ( x x k1 )
1 ( x x k1 )T 2 f ( x K 1 )( x x k1 ) 2
ykT H k ykT skT yk
)
sk skT skT yk
sk
y
T k
H
k
H k yk skT
skT yk
定理：
H0
0
sT k
yk
0, 则BFGS校正可以保证H k
0。
BFGS校正特点
迄今为止最好的拟牛顿 公式，具有DFP校正的各种性质。 此外，当采用不精确搜 索(Wolfe Powell)时，具有总体收 敛性。这个性质对于 DFP还未能证明。 在数值计算中，BFGS也优于DFP，尤其是常能与低精度 线 搜索方法结合使用。
例. 请用BFGS算法求解 min
f (x)
x12
4
x
2 2
,
初始点
x0
11,
选用精确线搜索 .
uv T
)1
A1
A1uv T A1 1 vT A1u
H k1
Hk
(1
ykT H k ykT skT yk
)
sk skT skT yk
sk
y
T k
H
k
Hk
yk skT
skT yk
五、BFGS校正(Broyden Fletcher Goldfard Shanno,1970)
H k1
Hk
(1
5. 存在缺点及修正
(1) f ( x k1 ) f ( x k ) ?
（2） 初始点的选取困难，甚至无法实施。
(3) Gk1的存在性和计算量问题 。
问题一： 如何使得 f ( x k1 ) f ( x k ) ?
在Newton法中，有 x k 1 x k Gk1 gk x k d k
一、Newton 法
1. 问题
min f ( x) xR n
f ( x)是Rn上二次连续可微函数 即f ( x) C 2(Rn )
2. 算法思想
x0 x1 xk xk1
为了由x k产生x k1，用二次函数Q( x)近似f ( x)。
f ( x) Q( x) f ( xk ) f ( xk )T ( x xk )
按照校正公式H k1 H k H k , 计算H k1使得H k1满足 拟Newton条件 或拟Newton方程：H k1 yk sk 。 令 k : k 1，转step 2.
H k 的确定。
三、对称秩一校正（ SR1）
如何确定H
？
k
秩1校正法
H k 1
Hk
H k
Hk
uk
v
T k
待定：uk，vk Rn
,
k
1 ykT H k
。 yk
根据上述推导，我们能 够得到H k的DFP的校正公式：
H k 1
Hk
skT sk skT yk
Hk yk ykT Hk ykT Hk yk
DFP校正公式
定理：
H0
0
sT k
yk
0, 则DFP校正可以保证H k
0。
3、DFP算法的步骤；
将变尺度法的第 5步改为：
step 5.
y0
f
( x1 )
f
(x0)
g1
g0
0.52308 。 8.36923
按照DFP的校正公式：
H1
H0
s0T s0 s0T y0
H 0 y0y0T H 0 y0T H 0 y0
1.00380 0.03149
0.03149。 0.12697
搜索方向
d1
H1f
(
x1 )
1.49416 0.09340
由拟牛顿条件
Hk1 yk
(Hk
uk
v
T k
)
yk
sk
uk
v
T k
yk
sk
Hk yk
uk必在sk H k yk上。
假定sk
Hk
yk
（ 0 否则，
H
已满足拟牛顿条件）
k
则有
v
T k
要求 H k
yk 0 Hk1 H 对称 H k1 H k
k (
(sk
Hk
yk
)v
T k
sk HvkTk yykk )(sk
1
函数，
SR1校正
方法至多n步终止，即 H n G 1 .
SR1校正特点
1.不需要做线搜索，而具 有二次终止性。
2.具有遗传性质 H i y j s j , j i. 3.不保证 H k 0, 只有（sk H k yk )T yk 0时，才正定。
H k 的确定。
四、DFP算法
1. DFP算法的提出： （1） 1959年Davidon首次提出 （2） 1963年Fletcher和Powell做了改进 （3） 多变量无约束优化问题 的一个重要工作
因为 x0 tf ( x0 ) 1 2t ， 1 8t
f ( x0 t0f ( x0 )) min f ( x0 tf ( x0 )) (1 2t )2 4(1 8t )2
解得 t0 0.13 ,
所以 x1 0.73846 。 0.04616
s0
x1
x0
0.26154 , 1.04616
1 ( x xk )T 2 f ( xk )( x xk )
2
f (xk)
gkT
(x
xk )
1(x 2
xk )T Gk ( x
xk )
其中 gk f ( x k )T ,Gk 2 f ( x k )。
令 Q(x) gk Gk (x xk ) 0
若Hesse矩阵Gk正定，即Gk 0，
则有：f ( x k1 ) f ( x k ) 。
问题二： 如何克服缺点（2）和（3）?
二、拟Newton算法 ( 变尺度法 )
1. 先考虑Newton迭代公式： x k1 x k Gk1f ( x k )
在Newton迭代公式中，如果我们 用 正定矩阵H k 替代Gk1，则有：
x k1 x k H k f ( x k ) 2. 考虑更一般的形式：
按照DFP的校正公式：
H k1
Hk
s
T k
sk
s
T k
yk
H
k
y
k
y
T k
H
k
y
T k
H
k
y
k
计算 H k，k : k 1, 转 step 2.
例. 请用DFP算法求解 min
f (x)
x12
4 x22 , 初始点
x0
1. 1
解：取H0 I ,
f
(
x
)
2 8
x1 x2
。
第一步DFP算法与梯度法相同：
2. 如何确定Hk？ 秩2校正法
Hk1 Hk Hk Hk k uk ukT kvkvkT
待定：k，k R, uk，vk Rn
根据 拟Newton条件：Hk 1 yk sk，我们有
( Hk k uk ukT kvkvkT ) yk sk
即：k uk ukT yk kvkvkT yk sk Hk yk
称Newton法为变尺度算法。
3. 如何对H k附加某些条件使得： （1）迭代公式具有下降性 质 H k 0