0和H k
G
1 k
?
如 何 确 定H k？
拟Newton条 件
拟Newton条 件 H k Gk1
分析：Gk1 需满足的条件，并利用此条件确定Hk 。
记g( x) f ( x), gk f ( xk ) Gk f 2 ( xk ), 则因为
f ( x) f ( xk1 ) f ( xk1 )T ( x xk1 ) 1 ( x x k1 )T 2 f ( x K 1 )( x x k1 ) 2
由拟牛顿条件Hk1 yk (Hk uk vkT ) yk sk
uk vkT yk sk H k yk
uk必在sk Hk yk上。
假定sk
Hk yk
（ 0
否
则
，H
已
k
满
足
拟
牛
顿条件
）
则
有
v
T k
要求 Hk
yk 对
0 Hk1 H 称 Hk1 Hk
则有：f ( xk1 ) f ( xk )。
问 题 二 ：如 何 克 服 缺 点 （2） 和 （3）?
二 、 拟Newton算 法 (变 尺 度 法)
1. 先考虑Newton迭代公式： x k1 x k Gk1f ( x k )
在Newton迭 代 公 式 中 ， 如 果 我用们 正 定 矩 阵H k 替 代Gk1， 则 有 ：
Step 4. 判断 xk1 是否满足终止准则：
yes: 计算 stop, x* : xk1
No : 转step 5 。
step 5. 令 gk1 f ( x k1 ) , gk f ( x k ) , yk f ( xk1 ) f ( xk ) gk1 gk , sk xk1 xk 。
当Gk 可逆时，x k 1 x k Gk1 gk 。
step3.由 方 程 组Q( x ) gk Gk ( x x k ) 0 解 出x k1
step4. 若 || f ( xk1 ) || ,停止，x* xk1 ;
否则，令k : k 1,转step 2。
4. 算法特点
▪ 收敛速度快，为二阶收敛。 ▪ 初始点要选在最优解附近。
按照校正公式H k1 H k H k , 计算H k1使得H k1满足 拟Newton条件 或拟Newton方程：H k1 yk sk 。 令 k : k 1，转step 2.
Hk 的确定。 三、对称秩一校正（SR1）
如何确定Hk？ 秩1校正法 H k1 H k H k H k uk vkT 待定：uk，vk Rn
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
g( x) g( xk1 ) 2 f ( xk1 )( x xk1 )
gk gk1 Gk1 ( x k x k1 ) Gk11 ( gk1 gk ) x k1 x k , 这 样 我 们 想 到 Hk1(gk1 gk ) xk1 xk 。
记yk gk1 gk , sk x k1 x k ,则有
Hk1 yk sk 拟Newton条件或拟Newton方程。
4、拟Newton算法 (变尺度法)的一般步骤；
Step 1. 给定初始点x0 ,正定矩阵H0 ,精度 0，k : 0
Step 2. 计算搜索方向d Hkf ( x );
k
k
step 3. 令 x k1 x k tk d k , 其中 tk : f ( xk tk d k ) min f ( xk t d k )。
x k1 x k H k f ( x k ) 2. 考 虑 更 一 般 的 形 式 ：
x k1 x k t k H k ( x k )
xk1 xk tk Hkf ( xk )
Hk I时 梯度法 最速下降方向 d k f ( xk ), 度量为 x xT I x
H k Gk1时 Newton法 Newton方向 d k Gk1f (xk ), 度量为 x xT Gk x
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 ( xk )T ,Gk 2 f ( xk )。
令 Q(x) gk Gk (x xk ) 0
若Hesse矩阵Gk正定，即Gk 0，
则G
1 k
0， 此 时 有
x k1
xk
G
1 k
g
k
这就是Newton 迭代公式。
比较迭代公式 xk1 xk tk d k , 有
d k Gk1gk , 而 tk 1。
3. 算法步骤
step1. 给 定 初 始 点x 0， 精 度 0,k : 0
step2. 计 算gk f ( x k )和Gk 2 f ( x k )
一、Newton 法
1. 问题
min f ( x) xRn
f ( x)是Rn上二次连续可微函数 即f ( x)C 2(Rn )
2. 算法思想
x0 x1 xk xk1
为了由xk产生xk1，用二次函数Q( x)近似f ( x)。
f ( x) Q( x) f ( xk ) f ( xk )T ( x xk )
当Gk 0 时，有 f ( xk )T d k f ( xk )T Gk1gk gkTGk1gk 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法为变尺度算法。
3. 如 何 对H k附 加 某 些 条 件 使 得 ： （1） 迭 代 公 式 具 有 下 降质性 Hk 0
（2）H k的 计 算 量 要 小 （3） 收 敛 速 度 要 快
H k1 H k H k
( H k H k1 H k )
Hk
G
1 k
如 何 保 证H k