一,Newton 法
)(m i n xf
nRx ?
上二次连续可微函数是 nRxf )(
)()( 2 nRCxf ?即
1,问题
。近似，用二次函数产生为了由 )()(1 xfxQxx kk ?
?? ????? ? 110 kk xxxx
))(()(
2
1
)()()()()(
2 kkTk
kTkk
xxxfxx
xxxfxfxQxf
????
??????
2,算法思想
)()(21)()( kkTkkTkk xxGxxxxgxf ???????
。其中 )(,)( 2 kkTkk xfGxfg ????
0)()( ????? kkk xxGgxQ
，此时有则
，正定，即矩阵若
0
0
1 ?
?
?
k
kk
G
GGH e s s e
kkkk gGxx 11 ?? ??
。迭代公式这就是 Ne w to n
令
有比较迭代公式,1 kkkk dtxx ???
,1 kkk gGd ??? 。而 1?kt
001 0 ???,k,x.s t e p,精度给定初始点
103 ?????? kkkk x)xx(Gg)x(Q.s t ep 解出由方程组
)x(fG)x(fg.s t e p kkkk 22 ???? 和计算
。可逆时，当 kkkkk gGxxG 11 ?? ??
3,算法步骤;,||)(||.4 1*1 ?? ??? kk xxxfs t e p 停止，若 ?
。转令，否则 4,1,s te pkk ??
? 收敛速度快, 为二阶收敛 。
（ 2） 初始点的选取困难, 甚至无法实施 。
。的存在性和计算量问题1(3 ) ?kG
( 1 ) 1 )x(f)x(f kk ??
4,算法特点
5,存在缺点及修正
? 初始点要选在初始点附近 。
1 )x(f)x(f kk ??如何使得问题一：
)(m i n)(:
1
kkk
k
k
k
k
k
kk
dtxfdtxft
dtxx
N e w t o n
???
???
法稍作修正：如果对
kk
kk
kk dxgGxx ???? ?? 11
N e w t o n 法中，有在
,0)()(0 11 ???????? ?? kkTkkkTkkTkk gGggGxfdxfG 有时，当
是下降方向。时，当 kk dG 0??
。则有,)()( 1 kk xfxf ??
32 ））和（如何克服缺点（问题二：
)(N e w t o n 变尺度法算法二、拟
)x(fGxx
Ne w t o n.
k
k
kk ??? ?? 11
1 迭代公式：先考虑
)x(fHxx
GH
N e w t o n
k
k
kk
kk
????
?
1
1,则有：替代正定矩阵
用迭代公式中，如果我们在
)x(fHtxx
.
k
kk
kk ???? 1
2 考虑更一般的形式：
xIxxxfd
IH
xfHtxx
Tkk
k
k
kk
kk
????
??
???
?
度量为最速下降方向
梯度法时
,)(
)(
1
xGxxxfGd
N e w t o nGH
k
Tk
k
k
kk
11
1
),( ??
?
????
??
度量为最速下降方向
法时
法为变尺度算法。称 N e w t on
）收敛速度要快（
的计算量要小）（
质）迭代公式具有下降性（
附加某些条件使得：如何对
3
2
1
3
k
k
H
H.
0?? kH
)HHH(
HHH
kkk
kkk
???
????
?
?
1
1
1??? kk GH
？如何确定
和如何保证
k
kkk
H
GHH
?
?? ? 10
1??? kk GHN e w to n 条件拟
条件拟 N e w to n
则因为记 ),()(),()( 2 kkkk xfGxfgxfxg ??????
)xx(Ggg kkkkk 111 ??? ???
这样我们想到,xx)gg(G kkkkk ??? ??? ? 111 1 。
kkkkk xxggH ??? ??? 111 )(
。此条件确定需满足的条件，并利用分析,kk HG 1?
)()()()( 111 ??? ???? kTkk xxxfxfxf
))(()(21 1121 ??? ???? kKTk xxxfxx
))(()()( 1121 ??? ???? kkk xxxfxgxg
则有记,,11 kkkkkk xxsggy ???? ??
的一般步骤；变尺度法算法、拟 )(N e w t o n4
001 00 ???,k,H,x.S t e p,精度正定矩阵给定初始点 ;)(.2
kkk xfHdS t e p ???计算搜索方向
。其中
令
)(m i n)(:
,.3 1
kkk
k
k
k
k
k
kk
dtxfdtxft
dtxxs t e p
???
???
。方程条件或拟拟 N e w to nN e w to nsyH kkk ??? 1
Step 4,判断 是否满足终止准则：
yes,计算 stop,
No, 转 step 5 。
1?kx
1?? k* x:x
.21:
,
1
11
1
s t e pkk
syHN e w t o n
N e w t o nHH
HHH
kkk
kk
kkk
转，令
。方程：或拟
条件拟满足使得计算
按照校正公式
??
?
???
?
??
?
。
令
kk
kkk
kk
k
k
k
k
k
xxsggxfxfy
xfgxfgs t e p
????????
????
?
?
?
?
?
1
1
1
1
1
,)()(
,)(,)(.5
校正法秩？如何确定 22 ?kH.
算法三,D F P
的一个重要工作多变量无约束优化问题）（
做了改进和年）（
首次提出年）（
算法的提出：
3
19632
19591
1
P o w e l lF l e t c h e r
D a v i d o n
D F P.
T
kkk
T
kkkk
kkk
vvuuH
HHH
?????
???? 1
nkkkk Rvu,R ????,，待定：
的确定。kH
，我们有条件：拟根据 kkk syHN e w to n ?? 1
kkTkkkTkkkk sy)vvuuH( ?????
kkkkTkkkkTkkk yHsyvvyuu ?????即：
kkk
T
kkk
kk
T
kkk
yHyvv
syuu
???
??
组解：，我们可以如下确定一满足上述方程的解很多
。
这样，我们可以取：
1,
,1,
???
??
k
T
kkkkk
k
T
kkkk
yvyHv
yusu
?
?
。
即：
kk
T
k
kkkk
k
T
k
kkk
yHy
yHv
ys
su
1
,
,
1
,
???
??
?
?
校正公式
的校正公式：的够得到根据上述推导，我们能
D F P
yHy
HyyH
ys
ss
HH
D F PH
kk
T
k
k
T
kkk
k
T
k
k
T
k
kk
k
????? 1
。性质,000 ??? kHH
算法的步骤；,D F P3
步改为：将变尺度法的第 5
.s t ep,k:kH
yHy
HyyH
ys
ss
HH
D F P.s t ep
k
kk
T
k
k
T
kkk
k
T
k
k
T
k
kk
21
5
1
转，计算
的校正公式：按照
??
????
.11,4)(m i n,02221 ????????? xxxxfD F P 初始点算法求解请用例
，因为
算法与梯度法相同：第一步
。解：取
?
?
?
?
?
?
?
?
???
??
?
?
??
?
?
???
t
t
xftx
DF P
x
x
xfIH
81
21
)(
8
2
)(,
00
2
1
0
。?
?
?
?
?
?
?
?
???????
?
?
?
?
?
?
?
?
???
3 6 9 2 3.8
5 2 3 0 8.0
)()(
,
0 4 6 1 6.1
2 6 1 5 4.0
01
01
0
01
0
ggxfxfy
xxs? 。所以解得 ?
?
??
?
?
?
??
?????????
0 4 6 1 6.0
7 3 8 4 6.0
,13.0
)81(4)21())((m i n))((
1
0
22000
0
0
xt
ttxftxfxftxf
。
的校正公式：按照
?
?
?
?
?
?
?
?
????
12697.003149.0
03149.000380.1
000
0000
00
00
01
yHy
HyyH
ys
ss
HH
D F P
T
T
T
T
。搜索方向 ?
?
??
?
? ??????
0 9 3 4 0.0
4 9 4 1 6.1)( 1
1
1 xfHd
。???????????? 0 0 0 0.0 0 0 0 0.04 9 4 2 3.0 111112 dxdtxx
是极小点。，所以因为 22 0)( xxf ??