版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
§10，使用导数的最优化方法最优化理论与算法第十章使用导数的最优化方法最速下降法法共轭梯度法拟
法信赖域法10.1最速下降法10.1最速下降法考虑无约束问题
min
f(x),
xRn(10.1.1)其中f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。10.1最速下降法－1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，方向导数Df
(x,
d
)
f
(x)T
d
(1.2)求函数f(x)在点x处下降最快的方向,归结为求min
f
(x)T
ds.t
d
1
(1.3)由Schwartz不等式,f
(x)T
d
f
(x)
d
f
(x)
f
(x)T
d
f
(x)
(1.4)10.1最速下降法－2由上式知.当(1.5)d
f
(x)f
(x)时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.注意:在不同的尺度下最速下降方向是不同的.10.1最速下降法－3最速下降算法最速下降算法的迭代公式为(1.6)(
k
)kx(
k
1)
x(
k
)
d其中d
(
k
)是从x(
k
)出发的搜索方向,此处取在点x(
k
)的最速下降方向,即
d
(
k
)
f
(x(
k
)
).(1.7)min(
k
) (
k
)k(
k
)kf
(x(
k
)
f
(x(
k
)0
d
)
d
(
k
)
)
是从x
出发沿方向d
进行一维搜索的步长,即满足10.1最速下降法－4min(k
)kk(k
)k
d
)
f
(x(k
)
f
(x(k
)
d
(
k
)
)Step2算法描述Step1,给定初始点x(k
)
En
,允许误差
0,置k
1Step2,计算搜索方向d
(k
)
f
(x(k
))Step3,若d
(k
)
,停止,否则,从x(k
)出发,沿d
(k
)进行一维搜索,求
,
使得Step4,
令x(k
1)
x(
k
)
d
,置
0k
:
k
1,转例1.1
用最速下降法求解下列问题10min
f
(x)
2x2
x21
2初点x(1)
(1,1)T
,
1第一次迭代目标函数f(x)在点x处的梯度f
(x)
4x1
2x
2
令搜索方向d
(1)
f
(x(1)
)
42
d
16
4
2 5
1/101从x(1)出发,沿方向d
(1)进行一维搜索,求步长
,即f
(x(1)x(1)min()0
d
(1)
)
d
(1)
1
4
1
4
1
2
1
2
()
2(1
4)2
(1
2)2令()
16(1
4)
4(1
2)
01
5
/18(1)11/
9
x(2)
x(1)
d
4
/
9
在直线上的极小点9d
(
2)d
(
2)
f
(x(
2)
)
4
/
9
8
/
9
4
5
1/10第二次迭代f
(x)在点x
处的从x(2)出发,沿方向d
(2)进行一维搜索:f
(x(2)x(2)min()
0
d
(2)
)
d
(2)
1/
9
4
/
9
(1
4)/
9
4
/
9
8
/
9
(4
8)/
9
()
2
(1
4)2
16
(1
2)281
8116
648181令()
(1
4)
(1
2)
02
5
/12(2)22
1x(3)
x(2)
d27
1
得到27d
(3)d
(3)
f
(x(3)
)
4
227
1
45
1/10第三次迭代f
(x)在点x
处的从x(3)出发x
d2令()
0
2
5
/18此时(3)221/
92
1x(4)
x(3)
d27
4
/
9
243
4
824310f
(x(4)
)
5
1已经满足精度要求,得近似解21x
243
4
问题的最优解为x*=(0.0)算法的收敛性Theorem1.1
设f
(x)是连续可微的实函数,解集合=x
f
(x
)
0,最速下降法产生的序列{x(k
)}含于某个紧集,则序列{x(k
)}的每个聚点xˆ
.证明:最速下降算法A可表示为A=MD其中D(x)=(x,-f(x)),是En
En
En的
.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是En
En
En.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当f(x)
0时,M是闭
.由于f(x)是连续可微实函数,故D连续,据Th8.1.1推论2,A在x(f(x)0)处是闭的.其次,当x时,d=-f(x)0,则f(x)T
d<0,因此对于yA(x),有f(y)<f(x),由此知f(x)是关于A和的下降函数,最后,按假设,{x(k)}含于紧集因此根据Th8.2.1,算法收敛
A
a
2
A
a
Theorem1.2
设f
(x)存在连续二阶偏导,x是局部极小点,Hessian矩阵2
f(x
)的最小特征值a
0,最大特征值为A,算法产生的序列{x(k
)}收敛于x.则目标函数序列{f
(x(k
))}以不大于
的收敛比线性的收敛于f
(x
).在上述定理中,若令r=A/a,则
A
a
2
r
1
2
A
a
r
1
1
r是对称正定矩阵2
f
(x)的条件数.定理表明:条件数越小,收敛越快;条件数越大,收敛越慢.最速下降法存在锯齿现象xx(2)x(1)容易证明,用最速下降法极小化目标函数时,相邻两个搜索方向是正交的.令kd
(
k
)
)T
d
(
k
)()=f
(x(
k
)
0
f
(x(
k
1)
)T
f
(x(
k
)
)
0
d
(k
1)
f
(x(k
1))与d
(k
)
f
(x(k
))正交()
f
(x(k
)
d
(k
)
)d
(k
)
f
(x(k
)
)
10.2
法
1(x
x(
k
)
)T
2
f
(x(
k
)
)(x
x(
k
)
)2其中2
f
(x(k
))是f
(x)在点x(k
)处的Hessian矩阵10.2.1
迭代格式设f(x)是二次可微函数,x
Rn
.又设x(k
)是f(x)的极小点的一个估计,将f
(x)在x(k
)点Taylor展开,取二阶近似:f
(x)
(x)=f
(x(k
)
)
f
(x(
k
)
)T
(x
x(
k
)
)+x(k
1)
=x(k
)
2
f
(x(k
)
)1f
(x(k
)
)
(10.2.2)(10.2.1)算法(Newton法)Step1,给定初始点x(0),允许误差
0,置k
1;Step2,若
f
(x(k
)
)
,停止,得解x(k
)
;否则,令x(k
1)
x(k
)
2
f
(x(k
))1f
(x(k
))
,
k
:
k
1,转2
10.2
法
(x)=0为求
(x)的驻点,令即f
(x(k
)
)
2
f
(x(k
)
)(x
x(k
)
)=0设2
f
(x(k
))可逆,则得(10.2.3)下求A度量下的最速下降方向,为此,考虑min
f
(x)T
ds.t d
T
Ad
110.2
法注意:
法的迭代格式也可以从最速下降方向的角度来理解.下面介绍一下A度量及其意义下的最速下降方向.设A为对称正定矩阵,向量d的A范数定义为d
dT
AdA由A,A-1对称正定,故存在对称平方根A1/2
,A-1/2,使得2
A
21
1
1
1A
A2
A2
,
A－1
A于是11
1
12
A2
d1
1d
T
Ad
d
T
A2
f
(x)T
d
f
(x)T
A
1
1
(
A
2
f
(x))T
A2
d10.2
法1令y
A2
d,则(10.2.3)可写成
1去掉绝对值符号,有1
1
(A
2
f
(x))T
y
A
2
f(x)
1
1
1(A
2
f
(x))T
y
A
2
f(x)y
A
2
f
(x)min
(A
2
f
(x))T
ys.t
yT
y
1
(10.2.4)根据Schwartz不等式,得到10.2
法即1
112
2
2T
f
(x)
A
A d
A
f
(x)
1
f
(x)T
d
A
2
f
(x)为得到在点x处下降最快的方向,按下式选取d(10.2.5)
A1f
(x)d
1(f
(x)T
A1f
(x))2这时上式等号成立,由此确定的方向即度量A意义下的最速下降方向
10.2
法若取kA
G
2
f
(xk
)的最速下降方向,其步长为
f
(xk
)
.Gk
Gk则法的搜索方向实际上是关于向量椭球范数10.2法
10.2
法
例用法求解下列问题min
(x
1)4
x21
2取初点x(1)(0,1)1012x2
4(x
1)3
12(x
1)2f
(x)
,2
f
(x)
0
2
第1次迭代f
(x(1)
)
-4,2
f
(x(1)
)
12 0
2
0 2
10.2法x(2)
x(1)
2
f
(x(1)
)1f
(x(1)
)012 0
1
-4
1/
3
1
0
2
2
0
0
0x(3)
x(2)
2
f
(x(2)
)1f
(x(2)
)1/
3
48/9 0
1
32
/
275
/
9
0
2
0
第2次迭代00f
(x(2)
)
32
/
27,2
f
(x(2)
)
48/9 0
2
10.2法0
0
0x(4)
x(3)
2
f
(x(3)
)1f
(x(4)
)5
/
9
64/27 0
1
256
/
72919
/
27
0
2
第3次迭代0
0f
(x(3)
)
256
/
729,2
f
(x(2)
)
64/27 0
2
继续下去,第4次迭代,…得到点列收敛于(1,0),此为最优解.10.2
法1(2)(1)
2
f
(x(k
)
)1
k
,f
(x
)
f
(x)
2
f
(x)(x
x)
k2x
x则法产生的序列收敛于x.10.2.2
局部收敛性定理10.2.1
设f
(x)是二次可微函数,
x
En
.x满足f
(x
)
0,且2
f
(x(k
))1
存在,又设初始点x(1)充分接近x
,使得存在k1,k2
>0,满足k1k2
<1,且对每一个x
X
x x
x
x(1)
x
成立:10.2
法证明:根据(10.2.2)，算法 定义为A(x)
x
f
(x)定
集合
{x},令函数
(x)=
x
-
x下证(x)是关于解集合和算法A的下降函数.令x
X
,且x
x
,又令y
A(x).根据算法A的定义及f
(x
)
0的假设,有y
x
x
2
f
(x)1f
(x)
x
(x
x
)
2
f
(x)1[f(x)
(x
)]
f
2
f
(x)1[(x
)
f
(x)
2
f
(x)(x
x)]
(b)10.2
法于是可得(c)(x
)
f
(x)
2
f
(x)(x
x)y
x
2
f
(x)1
k1k2
x
x
x
x从而(x)是关于解集合和算法A的下降函数由(c)可知,
y
X
,故迭代产生的序列{x(k
)}
X
.根据定义知X
是紧集,故迭代产生的序列含于紧集.此外算法
A在紧集X
上是闭的.综上,迭代产生的序列{x(k
)}必收敛于x
10.2
法
定理(局部收敛定理)设函数f
C
2
(Rn
),它在x
*的梯度f(x*)
0,Hesse矩阵2
f(x*)正定.若初始点x0充分靠近x*,并且Hesse矩阵G(x)
2
f
(x)满足Lipschitz条件,即存在L
0,使得x,y
Rn
,有G(x)
G(
y)
L x
y
,则对k,迭代格式(10.2.2)有意义,且迭代点序列{xk
}以二阶的收敛速度收敛到x
*.10.2法当法收敛时,有下列关系2x(
k
1)
x
c
x(k
)
xc是某个常数,因此算法至少是2阶收敛的特别的,对于二次凸函数,用 法求解,经一次迭代即达到极小点.设有二次凸函数2其中A是对称正定矩阵f
(x)
1
xT
Ax
bT
x
c10.2
法先用极值条件求解.令得最优解下用f
(x)
Ax
b
0x
A1b法解,任取一初始点x(1)x(2)
x(1)
A1(Ax(1)
A1f
(x(1)
)
x(1)
b)
A1b显然,x(2)
x.即一次迭代即达极小点.定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限次迭代后可到达函数的极小值点,称此算法具有二次终止性.于是 法具有二次终止性10.2法法可能不收敛注意,当初始点远离极小点时,阻尼
法基本思想:增加了沿 方向的一维搜索.迭代公式为(k
)k
dx(k
1)
=x(k
)k方向,
是由其中d
(k
)
2
f(x(k
))1f(x(k
))为一维搜索所得的步长,即满足(k
)(k
)kf
(x(k
)
d
d
(k
)
))=min
f
(x10.2
法)(
k
)kmin
f
(x(k
)
d
(
k
)
)
f
(x(
k
)
d算法(阻尼
法)Step1,给定初始点x(0),允许误差
0,置k
1;Step2,计算f
(x(k
)),2
f
(x(k
))1Step3,若
f(x(k
)
)
,停止,得解x(
k
);否则,令d
(k
)
2
f
(x(
k
)
)1f
(x(
k
)
)Step4,从x(k
)出发,沿方向d
(k
)作一维搜索:(
k
)kx(
k
1)
x(
k
)
d令Step5,置k
:
k
1,转210.2法10.2.3
修正例用阻尼法法求解下列问题1min
f
(x)x4
x
x
(1
x
)21
2
21f
(x(1)
)
0,2
f
(x(1)
)
02
12
取初点x(1)(0,0)T.在该点,函数的梯度和Hessian阵为方向d
(1)
2
f
(x(1)
)1f
(x(1)
)11
00
2
12
2
0
10.2
法1()=0
=0显然,用阻尼法不能产生新点,而点x(1)=(0,0)
T并不是问题极小点.可见从x(1)出发,用阻尼法求不出问题的极小点,原因在于Hessian
矩阵
2f
(x(1))非正定从x(1)出发,沿方向d
(1)进行一维搜索,令()=f(x(1)
d
(1)
)=164
+1再令10.2法考虑(10.2.2),记搜索方向d(k)=x-x(k)2
f
(x(k
)
)d
(k
)
f
(x(k
)
)
(d)阻尼 法所用搜索方向是上述方程的解d
(k
)
2
f
(x(k
)
)1f
(x(k
)
)
(e)此处假设逆矩阵2
f
(x(k
))1
存在10.2法kkkG
d
(k
)
f
(x(
k
)
)
(f)解决Hessian矩阵
f
(x修正2
f
(x(k
)),构造一个对称正定矩阵G
,在方程(d
)中用G
取代矩阵2
f
(x(k
))1
:(g)
d
(k
)
G1f
(x(k
)
)(h)2
(k
)k
kG
f
(x
)
Ik再沿此方向作一维搜索如何构造Gk
?比如,可令其中I是单位阵,k是一个适当的正数.10.2
法算法修正法2 (
k
)k
k
kd
(
k
)
(B
)1f
(x(
k
)
)Step1,给定初始点x(0),允许误差
0,置k
0;Step2,计算梯度gk
=f
(x(k
)
),若
f
(x(k
)
)
,停止,得解x(k
);否则转step3Step3,
计算Hesse矩阵G
f
(x
),置矩阵B
G
E
,其中Ek
为修正矩阵(当Gk正定时,它取0),计算修正k方向(
k
)k(k
)kmin
f
(x(k
)
d
(k
)
)
f
(x(
k
)
d
)x(k
1)
x(k
)kStep4,从x(k
)出发,沿方向d
(k
)作(精确或非精确)一维搜索:令
d
,置k
:
k1,转210.2
法x定理(全局收敛定理)
设f
:
Rn
R在某开集D上二阶连续可微,且修正
法的初始点
x0
D使得0f
的水平集S
0
{x
D
|
f
(x)
f
(x
)是紧集.若矩阵f
(
x
)序列满足有界分
性,则lim
f
(xk
)
0.10.3共轭梯度法1共轭方向与扩张子空间定理定义10.3.1
设A是n×n对称矩阵,若Rn
中的两个方向d1
和d2满足
(d
1)T
Ad
2
=0
（10.3.1）则称这两个方向关于A共轭,或称它们关于A正交.若d
(1),d
(2),...,d
(k
)是En中k个方向,它们两两关于A共轭,即d
(i
)T
Ad
(
j
)
0,i
j,
i,
j
1,
2,..k.
(10.3.2)则称这组方向是A共轭,或称它们为A的k个共轭方向10.3
共轭梯度法几何意义设有二次函数2f
(x)
1
(x
x
)T
A(x
x
)
(10.3.3)1
2(x
x
)T
A(x
x
)
c是以x为中心的椭球面,f(x
)
A(x
x
)
0A正定,故x是f(x)的极小值点.其中A是n×n对称正定矩阵,x是一个定点.f(x)的等值面由于10.3共轭梯度法设x(1)是在某等值面上一点,此面在点x(1)处的法向量f
(x(1)
)
A(x(1)
x
)又设d
(1)是在该等值面在点x
(1)处的一切向量.d(2)
=
x
-
x
(1)显然,d
(1)与f
(x)正交d
(1)T
Ad
(2)
0即等值面上一点x(1)处的切向量与由这点指向极小点的向量关于A共轭.10.3共轭梯度法x1x2d
(
2)d
(1)x(1)x10.3共轭梯度法xk
1
xk算法1
共轭方向法步1(初始化),给定初始点x0
Rn
,计算f(x0
),给定一个搜索方向d
0
0,使得f
(x0
)T
d
0
0;置k
0
步2(线搜索),求解一维极小化问题min
f
(xk
d
k
);R
k
d
,
若f
(x
)
0或k
n
1,
停止,否则转步3k k
1步3(计算共轭方向),计算一个非零方向dk
1
Rn
,使得(d
k
1
)T
Gd
j
0(j
0,1,...,k);置k
1
k转步2定理10.3.1
设A是n阶对称正定矩阵,d
(1)
,
d
(2)
,...,
d
(
k
)是k个A共轭的非零向量,则这个向量组线性无关.10.3共轭梯度法f
(x)
1
xT
Ax
bT
x
cx(1)2其中A是n阶对称正定矩阵,d
(1),d
(2),...,d
(k
)是A共轭的非零向量.以任意的x(1)
Rn为初始点,依次沿d
(1),d
(2),...,d
(k
)进行一维搜索,得到点列x(1),x(2),...,x(k
1),则x(k
1)是函数f
(x)在定理10.3.2(扩张子空间定理)设有函数k(i
)i
ii1
x
x
d ,
(,
)线性流形
上的唯一极小点.特别地,当k
n时,
x(k
1)是函数f
(x)在En上的唯一极小点.其中是d
(1),d
(2),...,d
(k
)生成的子空间.10.3共轭梯度法x(1)证明:由于f
(x)严格凸,要证明x(k
数f
(x)在线性流形
上的唯一极小点,只要证在x(k
1)点,f
(x(k
1))与子空间.
正交.用归纳法证之,为方便,用gj表示函数f(x)在x(j)处的梯度,即(10.3.6)g
j
f
(x
)(
j
)证明gk
1
k
,对k归纳当k
1,由一维搜索的定义知g2
1.假设k
m<n时gm1
m
,下证gm2
m1.10.3共轭梯度法利用上式可以将gm+2
和d
(i)的内积写成(10.3.8)
m2
m1
m1d
(i)
g
d
(i)T
g d
(i)T
Ad
(m1)当i=m+1时,由一维搜索定义,知d
(m1)T
g
0m2(10.3.9)(10.3.10)当1
i<m+1时,由归纳假设知d
(i)T
g
0m1(10.3.11)由于d
(1),d
(2),...,d
(m1)关于A共轭,则d
(i)T
Ad
(m1)
=0由二次函数梯度的表达式和点x(k+1)的定义,有(10.3.7)
m2
m1m1
m1g
Ax(m2)
A(x(m1)
d
(m1)
)
b
g
Ad
(m1)10.3共轭梯度法由10.3.8-11,知即d
(i)T
gm2
0gm2
m1.根据上述证明,x(k
1)是f(x)在x(1)
上的极小点.由于kf
(x)严格凸,故必为此流形上的唯一极小点.当k
n,d
(1)
,
d
(2)
,...,
d
(n)是En的一组基,此时必有g
0,n1从而x(n1)是函数在En上的唯一极小点.(
j
)k
1=0,
j
k推论:
在Th10.3.2的条件下,
gT
d10.3共轭梯度法2
线性共轭梯度法与二次终止性上述定理表明,对于二次凸函数,若沿一组共轭方
向(非零向量)搜索,经有限步迭代必到达极小点.Hesteness和Stiefel于1952年为解线性方程组而提出基本思想:把共轭性与最速下降法相结合,利用已知点处的梯度构造一组共轭方向,并沿着这组方向进行搜索,求出目标函数的极小点10.3共轭梯度法先 对于二次凸函数的共轭梯度法,考虑问题min
f
(x)
1
xT
Ax
bT
x
c
(10.3.12)2x
En
,A对称正定,c是常数.求解方法首先,任意给定一初始点x(1),计算出目标函数在该点的梯度,若
g1
0,则停止计算,否则,令d
(1)
f(x(1)
)
g
(10.3.13)1沿d
(1)搜索,得点x(2)
.计算在x(2)处的梯度,若
g
02则利用-g
和d
(1)构造搜索方向d
(2),再沿d
(2)搜索.210.3共轭梯度法(103.14)(k
)(k
)
(k
)k
k
df
(x(k
)d
)=min
f
(x
d
(
k
)
)一般地,若已知点x(k
)和搜索方向d
(k
),则从x(k
)出发沿d
(1)进行搜索,得x(k
1)
x(k
)其中步长k
满足(10.3.15)(
Ax(k
1)
b)T
d
(k
)
0记
()
f
(x(k
)
d
(k
)
)令
()
f
(x(k
1)
)T
d
(k
)
0即下求k的表达式10.3共轭梯度法(10.3.16)(10.3.17)
00(
k
)T (
k
)kk
k
k
(
A(x(
k
)
d
)
b)
d
(g
Ad
k(
k
)
)T
d
(
k
)gT
d
(k
)d
(k
)T
Ad
(
k
)(10.3.18)k
1d
(
k
1)
g
+
d
(
k
)k
1
k计算f
(x)在x(k
1)处的梯度,若
g
0,则停止计算k
1否则,利用-g
和d
(
k
)构造下一搜索方向d
(
k
1)
,并使d
(k
1)和d
(k
)关于A共轭,按此设想.令10.3共轭梯度法(10.3.19)
k
1
kd
(k
)T
Agd
(k
)T
Ad
(k
)上式两端左乘d
(k
)T
A,并令d
(k
)T
Ad
(k
1)
d
(k
)T
Ag
+
d
(k
)T
Ad
(k
)
0k
1
k再从x(k
1)出发,沿方向d
(k
1)搜索.综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3.14,3.17-3.19就能伴随计算点的增加,构造出一组搜索方向.10.3共轭梯度法定理10.3.3
对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1
i
m),下列关系成立:1,
d
(i
)T
Ad
(
j
)
0,2,
gT
g
0,i
j3,
gT
d
(i
)
gT
gi
i
ij
1,
2,...,i
1j
1,2,...,i
1(蕴涵d
(i
)
0)证明:显然m1,下用归纳法(对i)证之.(1)1当i
1时,由于d
g
,从而3)成立,对i
2时,关系1)和2)成立,从而3)也成立.10.3共轭梯度法证明对于i+1设对某个i<m,这些关系均成立,也成立.先证2),(i)ix(i1)
x(i)
d由迭代公式两端左乘A,再加上b,得(10.3.20)(i)i1g
gi
i
Ad其中i
由式(10.3.17)确定,即(10.3.21)i
i
i
i
0gT
d
(i)gT
gd
(i)T
Ad
(i)d
(i)T
Ad
(i)10.3共轭梯度法(10.3.22)
考虑到(10.3.20)和(10.3.18),则T(i
)i1
j
iij(i
)T
(
j
)gTg
g
Adg
g
T
gi
j
i
j1d
A(dd
(
j1)
)(i)T
(1)(注:j=1时上式为gT
g
g
T
g
d
Ad
)i1
1
i
1
i
Tii
ii1
id
(i
)T
Ad
(i
)
g
g
g
T
g
0当j
i时,由归纳假设d
(i
)T
Ad
(i1)
0,根据(10.3.21)10.3共轭梯度法当j<i时,根据归纳假设,式(10.3.22)等号右端各项均为0gTi1
jg
0故T(i
)T
(
j
)ijAdi1再证1),运用(10.3.18)和(10.3.20),则Td
(i1)T
Ad
(
j
)
g
d
(i
)
Ad
(
j
)i1
ig
j1
g
j
g
d当j=i时,把(10.3.19)代入上式第一个等号的右端,立得
d
(i1)T
Ad
(
j
)
010.3共轭梯度法当j<i时,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此d
(i1)T
Ad
(
j
)
0最后证3),易知(i)Tggi1
i1
i1
ii1
i1T
d
(i1)
gT
gg
d综上,对i+1,上述三种关系成立由上可知,Fletcher
Re
eves共轭梯度法所产生的搜索方向d
(1).d
(2),...,d
(m)是A共轭的,根据Th10.3.2,经有限步迭代必达极小点.10.3共轭梯度法注意,初始搜索方向选择最速下降方向十分重要,如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.例考虑下列问题12
3min2x2
1
x2
x2取初始点和初始搜索方向分别为1
1x(1)
1,
d
(1)
2
1
0
10.3共轭梯度法显然,d
(1)不是目标函数在x(1)处的最速下降方向.用FR法构造两个搜索方向.(1)(1)1下面,从x
出发,沿方向d
进行搜索,求步长
,使满足:(1)
(1)1f
(x(1)0)
min
f
(x
d
d
(1)
)121
1/
3
2
/
3
(1)
d
1/
3 ,
g
1/
31(1)21d
(2)
g
d得1
23
x(2)
x(1)令10.3共轭梯度法根据公式(10.3.19),有21(1)Td
Agd
(1)T
Ad
(1)
因此1
2
/
3
2
/
3
16
9
1
5
/
9
d
(2)
1/
3
1
2
5
/
9
9
0
1
(2)(2)2从x
出发,沿方向d
进行搜索,求步长
,使满足:(1)(2)2f
(x(1)0
d
)
min
f
(x
d
(2)
)2
2126得10.3共轭梯度法(2)239
/
78
9
/
78
18
/
78
x(3)
x(2)
d9
/
78 ,
g
5
/
26
5
/
26
令d
(3)
g
d
(2)3
2根据公式(10.3.19),有32676(2)Td
Agd
(2)T
Ad
(2)
4510.3共轭梯度法因此
18
/
78
5
/
9
131
d
(3)
9
/
78
45
5
/
9
1
53
676
676
5
/
26
1
175
可以验证但d
(1)与d
(3)不关于A共轭,于共轭.注意,在FR法中,初始搜索方向必须取最速下降方向10.3共轭梯度法可以证明,对于正定二次函数,运用FR法时不作矩阵运算就能求出因子i定理10.3.4
对于正定二次函数,FR法中因子i具有下述表达式22(10.3.24)
i1
iiig, (i
1,
g
0)g证明:(i
)T(i
)i(i
)id
AggT
A(x(i1)
i1d
(i
)T
Ad
(i
)
i1
i
d
(i
)T
A(x(i1)
x
)
/
x
)
/
10.3共轭梯度法2(10.3.23)
i1
i1
i
i1
i1
i
iggT(g
g
)
g
)d
(i
)T
(g
d
(i
)T
g根据定理10.3.3,
d
(i
)T
g
gi
i2
.因此22,
(10.3.24)
i1
iigg10.3共轭梯度法k k
1d
(k
)
g
d
(
k
1)FR法(对二次凸函数)1,给定初点x(1),置k
1.(k
)2,计算gk
f
(x
).若
gk
0,停止计算,得点x
x(k
)；否则,进行下一步.3,构造搜索方向.令其中,当k
1时,k
1
0,当k
1时按公式(10.3.24)计算k
1.10.3共轭梯度法(k
)kx(k
1)
x(k
)
d4,令其中按公式(10.3.17)计算步长k
.5,若k
n,则停止计算,得点x
x(k
1)否则,置k
:
k
1,转2例3.2用FR法求解下列问题min
f
(x)
x2
2x21
2初点x(1)(5,5)T10.3共轭梯度法令第一次迭代，目标函数f(x)在点x处的梯度f
(x)
2x1
4x
2
1d
(1)
g
1020
1从x(1)出发,沿方向d
(1)进行一维搜索,求步长
:10.3共轭梯度法1518gT
d
(1)
1
d
(1)T
Ad
(1)(10,
20)
10
20
2 0
10
(10,
20)
04
20
(1)1510 20
/
95
x(2)
x(1)
d5
18
20
5/
9
2第2次迭代目标函数在点x
(2)处的梯度
g
40
/
9
20
/
9
10.3共轭梯度法(1)2
1100
4d
(2)
g
d81
1
2从x(2)出发,沿方向d
(2)作一维搜索,求
:构造搜索方向d
(2).先计算因子
1212181gg(40
/
9)2
(20
/
9)2
4
2
102
202令29
819gT
d
(2)
2
d
(2)T
Ad
(2)
20
100
(2,
1)
4
1
2 0
4
20
100
2
81
(4,1)
04
1
10.3共轭梯度法(2)220
/
99
1004
0
x(3)
x(2)
d
20 81
1
0
5
/
9
(2)20
0
0显然点x
处目标函数的梯度g
,已达极小点
010.3
共轭梯度法0
0k=0,1,...
(10.3.3.1)kkkkkxk
1
xk
dd
k
1
gk
1
d其中初始方向d
g
,
步长参数
由一维搜索得到(Fletcher-Reeves(FR))k的计算公式通常有如下几种：(gk
1)T
g
k
1(gk
)T
g
k1,
k
3用于一般函数的共轭梯度法－非线性共轭梯度法一般迭代格式10.3共轭梯度法2,k
kgT(g
g
)gT
gk
k
1
k
1
k
----PRP(Polak-re-Polyar3,k
1
kgT(g
g
)(d
k
)T
(g
g
)
k
1
k
1
k
k-----SW(Sorenson-Wolfek
1(d
k
)T
2
f
(xk
1)g(d
k
)T
2
f
(xk
1)d
k4,
k
----Daniel5,kgTg(d
k
)T
g
k
1
k
1k-----Dixon10.3共轭梯度法(
j
)jjf
(
y(
j
)
f
(
y(
j
)d
)
min
d
(
j
)
)y(
j1)
y(
j
)
d
(
j
)j求
满足令FR共轭梯度法1,给定初始点x(1),允许误差
0.置y(1)
x(1)
,
d
(1)
f
(
y(1)
),
k
j
0.2,若
f
(
y(
j
)
)
,则停止计算,否则作一维搜索,10.3共轭梯度法3,如果j
<n,转步4,否则,转54,令其中
j
f
(
y置j
:
j
1,转步2.5,令x(
j1)
=y(n1)
,y(1)
x(k
1)
,
d
(1)
f
(
y(1)
)置j
1,k
:
k
1,转步2.可以证明,对一般函数,共轭梯度法在一定条件下是收敛的,10.3共轭梯度法)k
kk
T
kk
1
kf
(xk
d
)
f
(x
)
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度建筑工程安全生产责任追究合同
- 2025年度外贸合同书样本：国际货物运输保险合同
- 2025年度商业地产产权转让与物业管理合同
- 2025年度园林绿化养护临时用工合作协议
- 二零二五年度移动宽带网络用户满意度提升合同
- 工业园区升级补贴合同
- 2025年度建筑工程合同监理实施办法
- 2025年度商场顾客满意度调查与提升合同
- 2025年度房屋租赁安全免责合同（带宠物）
- 2025年导电银浆行业现状分析：导电银浆市场复合年增长率为20.12%
- 2025年中远海运物流有限公司招聘笔试参考题库含答案解析
- 2024年广州市海珠区卫生健康系统招聘事业单位工作人员笔试真题
- 一科一品一骨科护理
- 加气站安全培训课件
- 设备维修的基本技能培训
- 2025年中国邮政招聘笔试参考题库含答案解析
- 人教版（2024）七年级英语上册新教材的变化及教学建议课件
- 2025年中考语文一轮复习：九年级上册知识点梳理
- 2025年新闻部工作计划
- 中国近代史纲要西安财经大学练习题复习资料
- 中国成人ICU镇痛和镇静治疗指南解读
评论
0/150
提交评论