版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
梯度法和共轭梯度法无约束最优化问题梯度法共轭方向法共轭梯度法一.
无约束最优化问题无约束最优化问题min
f
(x)
s.t.
x
˛
Rn其中f
(x)有一阶连续偏导数。解析法：利用函数的解析性质构造迭代公式。二.
梯度法（最速下降法）迭代公式：xk
+1
=
xk
+
lk
d
k如何选择下降最快的方向？f
(xk
)
函数值增加最快的方向f
(xk
)函数值下降最快的方向-函数值下降的方向xk梯度法（最速下降法）：1.
搜索方向：d
k
=-f
(xk
),也称为最速下降方向；k
kl2.
搜索步长
:
l
取最优步长,
即满足
f
(
xk
+
l
d
k
)
=
min
f
(
xk
+
ld
k
)。梯度法算法步骤：给定初始点x1
˛
Rn
,允许误差e
>0,令k
=1。计算搜索方向
d
k
=
-
f
(
xk
)
;若||
d
k
||
£e
,则停止计算，x
k为所求极值点；否则，求最优步长lk使得f
(xk
+lkd
k
)=min
f
(xk
+ld
k
)。l4.
令xk
+1
=xk
+lkd
k
,令k
:=k
+1,转2。l例.
用最速下降法求解:
min
f
(
x)
=
x2
+
3
x2
,设初始点为
x1
=
(
2,1)T
,1
2求迭代一次后的迭代点
x2
。解：
f
(
x)
=(
2
x1
,
6
x2
)T
,\
d
1
=
-
f
(
x1
)
=(
-
4
,-
6
)T
.\
x1
+
ld
1
=(
2
-
4l
,1
-
6l
)T
.令
j
(l)
=
f
(
x1
+
ld
1
)
=
(2
-
4l)2
+
3(1
-
6l)2
，求解
min
j
(l)62=
131令j
(l)
=
-8(
2
-
4l)
-
36(1
-
6l
)
=
0
lT,
)31
3136
-
811+
l
d
=(12\
x
=
x收敛性klf
(
xk
+
l
d
k
)
=
min
f
(
xk
+
ld
k
)则有
f
(
xk
+
lkd
k
)T
d
k
=
0
。性质.证明：令j
(l)=f
(xk
+ld
k
)，所以j
¢(l)
=
f
(
xk
+
ld
k
)T
d
k
.
f
(
xk
+
lkd
k
)
=
min
f
(
xk
+
ld
k
)l\
j
¢(lk
)
=
f
(
xk
+
lkd
k
)T
d
k
=
0
.设
f
(
x)
有一阶连续偏导数，若
步长
lk
满足注：因为梯度法的搜索方向(d
k
+1
)T
d
k
=0
d
k
+1
^
d
k
。f
(xk
+lk
d
k
)，所以d
k
+1
=
-锯齿现象在极小点附近，目标函数可以用二次函数近似，其等值面近似椭球面。x*x
2x
3x1注
最速下降方向反映了目标函数的一种局部性质。它只是局部目标函数值下降最
快的方向。最速下降法是线性收敛的算法。1.
何谓共轭方向？几何解释设有二次函数2f
(
x)
=
1
(
x
-
x)T
A(
x
-
x)其中A
是n·n
对称正定矩阵，x
是一个定点。则函数f
(x)的等值面1
(
x
-
x)T
A(
x
-
x)
=
c2是以x
为中心的椭球面。x三、共轭方向法由于f
(
x
)
=
A(
x
-
x
)
=
0
,因为A
正定，所以
2
f
(
x
)
=
A
>
0
,因此x
是f
(x)的极小点。2
f
(
x
)
=
A
,而x2f
(
x
)
=
1
(
x
-
x
)T
A(
x
-
x
)设x(0)是在某个等值面上的一点，d
(1)是Rn中的一个方向，x
(1)。搜索得到点x
(0)沿着d
(1)以最优步长ox1xd
(1)(1)xd
(2)x
(0)则d
(1
)是点x(1
)所在等值面的切向量。该等值面在点
x(
1
)
处的法向量为
f
(
x1
)f
(
x(1)
)
=
A(
x(1)
-
x).o1xxd
(1)f
(x(1))正交，则d
(1)与f
(x(1))=0
。即d
(1)T(1)(
2)令
d
=
x
-
x
,所以
d
(1)T
Ad
(2)
=
0
。x(1)向量与由这一点A
共轭。即等值面上一点处的切指向极小点的向量关于d
(2)-
f
(
x1
)2.
共轭方向定义设A
是n
·
n
的对称正定矩阵，对于Rn中的两个非零向量d
1
和d
2，若有
d
1T
Ad
2
=
0
，则称
d
1和d
2关于A共轭。设d
1
,d
2
,,dk
是Rn
中一组非零向量，如果它们两两关于A共轭，即
d
i
T
Ad
j
=
0
,
i
„
j
,
i
,
j
=
1,
2
,,
k。则称这组方向是关于A共轭的，也称它们是一组A共轭方向。注：如果A是单位矩阵，则I d
2
=
0
d
1T
d
2
=
0d
1T
d
1
^
d
2共轭是正交的推广。定理1.
设
A是
n阶对称正定矩阵，d
1
,
d
2
,,
d
k
是k
个
A
共轭的非零向量，则这个向量组线性无关。证明设存在实数a
1
,a
2
,
,a
k
，使得ki
=1iia
d
=
0
,d
j
T
A
，则有上式两边同时左乘ki
=1iAd
=
0
,Tjia
d可化简为因为d
1
,d
2
,
,d
k
是k
个A
共轭的向量，所以上式a
d
jT
Ad
j
=
0
.j因为d
j
„0,而A是正定矩阵，所以d
j
T
Ad
j
>0，所以a
j
=0,
j
=1,2,,k。因此d
1
,d
2
,,d
k
线性无关。定理2.2设有函数
f
(
x)
=
1
xT
Ax
+
bT
x
+
c
，其中A是n阶对称正定矩阵。d
(1),d
(2),,d
(k
)是一组A共轭向量。以任意的x
(1)˛
Rn为初始点，依次沿d
(1),d
(2),,d
(k
)进行搜索，得到点x(2),x(3),,x(k
+1),则x(k
+1)是函数f
(x)在x(1)+Bk
上的极小点，其中k(i
),
li
˛
R
}Bk
=
{
x
|
x
=
lidi
=1是由d
(1),d
(2),,d
(k
)生成的子空间。特别地，当k
=n时，x(n+1)是f
(x
)在R
n
上的唯一极小点。推论
在上述定理条件下，必
有i
=1,2,,k。f
(
x(k
+1)
)T
d
(i
)
=
0
,3、共轭方向法对于极小化问题2min
f
(
x)
=
1
xT
Ax
+
bT
x
+
c
,其中A是正定矩阵，称下述算法为共轭方向法:(1)取定一组A
共轭方向d
(1),d
(2),
,d
(n
)；x
(k
)确定点x
(k
+1),(2)任取初始点x
(1),依次按照下式由ld
(
k
)k
f
(
x(
k
)
+
l
d
(
k
)
)
=
min
f
(
x(
k
)
+
l
d
(
k
)
)kx
=
x(
k
)
+
l(
k
+1
)直到某个
x(k
)
满足
f
(
x(k
)
)
=
0。注由定理2可知，利用共轭方向法求解上述极小化问题，至多经过n
次迭代必可得到最优解。四.共轭梯度法：二次函数情形非二次函数情形如何选取一组共轭方向？Fletcher
-Reeves
共轭梯度法:2min
f
(
x)
=
1
xT
Ax
+
bT
x
+
c其中x
˛
Rn
,A是对称正定矩阵，b
˛
Rn，c
是常数。基本思想：将共轭性和最速下降方向相结合，利用已知迭代点处的梯度方向构造一组共轭方向，并沿此方向进行搜索，求出函数的极小点。以下分析算法的具体步骤。1、二次函数情形f
(
x
(1)
)；(1)任取初始点x
(1)，第一个搜索方向取为d
(1)
=
-f
(
x(k
+1)
)，(2)
设已求得点
x(k
+1)
，若
f
(
x(k
+1)
)
„
0
，令
gk
+1
=则下一个搜索方向d
(k
+1)按如下方式确定:d
(k
+1)
=
-gk
+1
+
bk
d
(k
)令
(1)如何确定bk？要求d
(k
+1)和d
(k
)关于A共轭。则在（
1）式两边同时左乘
d
(
k
)
T
A
，得0
=
d
(k
)T
Ad
(k
+1)
=
-d
(k
)T
Ag
+
b
d
(k
)T
Ad
(k
)k
+1
k(2)d
(k
)T
Ad
(k
)d
(k
)T
A
gbk
=
k
+1解得(3)
搜索步长的确定
:已知迭代点x
(k
)和搜索方向d
(k
),利用一维搜索确定最优步长lk
，(3)d
(k
)T
Ad
(k
)即求解
min
f
(
x(k
)
+
ld
(k
)
)。l记
j
(l)
=
f
(
x(k
)
+
ld
(k
)
)
,令
j
¢(l)
=
f
(
x(k
)
+
ld
(k
)
)T
d
(k
)
=
0，即有
[
A(
x(k
)
+
ld
(k
)
)
+
b
]T
d
(k
)
=
0，令
gk
=
f
(
x(k
)
)
=
Ax(k
)
+
b，则有[
gk
+
lAd
(k
)
]T
d
(k
)
=
0，gT
d
(k
)解得
lk
=
-
k
定理3
对于正定二次函数
f
(
x)
=
1
xT
Ax
+
bT
x
+
c，FR算法在m
£
n次2一维搜索后即终止，并
且对所有的
（i
1
£
i
£
m），下列关系成立d
(i
)T
Ad
(
j
)
=
0
,
j
=
1,
2
,,
i
-
1;gi
T
g
j
=
0
,
j
=
1,
2
,,
i
-
1;gT
d
(i
)=-gT
g
。i
i
i注（1）由定理3
可知搜索方向d
(1),d
(2),
,d
(m
)是A
共轭的。(2)算法中第一个搜索方向必须取负梯度方向，否则构造的搜索方向不能保证共轭性。(3)由定理3的（3）可知，gT
d
(
i
)
=
-
gT
g
=
-
||
g
||2
<
0
,i
i
i
i所以d
(i
)是迭代点x(i
)处的下降方向。(4)由定理3
，FR
算法中bi的计算公式可以简化。d
(i
)T
Ad
(i
)d
(i
)T
A
gbi
=
i
+1d
(i
)T
Ad
(i
)T
Ad
(i
)g=
i
+1
(i
)i)
/
l
]Td
A[(
x
-
x(i
)
(i
+1)gi
T
A[(
x(i
+1)
-
x(i
)
)
/
l
]=
+1
i
gi
=
f
(
x(i
)
)
=
A
x(i
)
+
b
.d
(i
)T
(
ggi
T
(
g
-
g
)i
+1bi
=
+1
i
+1
i
i-
g
)\iT-
d
(i
)||
gi
+1
||2g=(4)||
gi
+1
||22i||
g
||=FR
算法步骤：任取初始点x(1)，精度要求e，令k
=1。令g1
=
f
(
x(1)
)
,若||
g1
||<e,停止，x(1)为所求极小点；否则，令d
(1)=-g1
,利用公式（3）计算l1
，令x(2)=x(1)+l1
d
(1)。令gk
+1
=
f
(
x(k
+1)
)
,若||
gk
+1
||<e,
停止，x(k
+1)为所求极小点；否则，令d
(k
+1)=-gk
+1
+bk
d
(k
),其中bk
用公式（4）计算。令k
:=k
+1。利用公式（3）计算lk
，令x(k
+1)=x(k
)+lk
d
(k
),转3。例用FR
算法求解下述问题：min
f
(
x)
=
2
x
2
+
x
21
2初始点取为x(1)=(2,2)T
。解：d
(1)T
Ad
(1)f
(
x)
=
(
4
x1
,
2
x2
)T
.第1
次迭代：令
d
(1)
=
-g1
=
(
-
8
,-
4
)T
,gT
d
(1)而
l1
=
-
1
21
2
2
0 2
x
0
x1
,f
(
x)
=
1
(
x
,
x
)
40
.0
2
\
A
=
4
=
-
0 2
-
40
-
8(
-
8
,-
4
)
4-
4(
8
,
4
)
-
8185=x(2)
=
x(1)
+
l1
d
(1)所以18=
(
2
,
2
)T
+
5
(
-
8
,-
4
)TT,
)9
9=
(
-
2
8第2次迭代：9
92
g
=
(-
8
,
16
)T
.||
g1
||2||
g
||2\.814)282
+
42(
)2
+
(-
8
16b1
=
2
=
9
9
=\
d
(2)
=
-g2
+
b1
d
(1)TT498
-
16=
(
9
,
)
+
81
(
-
8
,-
4
)81=
40
(1,-
4
)Td
(2)T
Ad
(2)gT
d
(2)
l2
=
-
2
=
-
0 2
-
481-
481
9
940
(
-
8
,
16
)
1
(
40
)2
(1,-
4
)
40
1
209=x(3)
=
x(2)
+
l2
d
(2)\9
9
20
81, )T
+
9
·
40
(1,-
4
)T=(
-
2
8=
(
0
,
0
)T
g3
=
(
0
,
0
)T\
x(3)即为所求极小点。2.
用于一般函数的共轭梯度法min
f
(
x)s.t.
x
˛
R
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 路侧停车劳务外包合同
- 2025年氢燃料船舶动力系统安全检查指南
- 智慧公交刷卡扫码一体机2025年的合同协议
- 生活日常-血糖正常值范围
- 护理日语用药指导
- 2025年房屋买卖合同示例二篇
- 月经不调的物理治疗手段
- 护理员用药护理操作指南
- 年处理20万吨生活垃圾炉渣资源化利用项目可行性研究报告模板立项申批备案
- 椎管内肿瘤患者的化学治疗与护理管理
- 开放性骨折的护理常规
- 2025年入党积极分子培训考试试卷及答案（三）
- 关于加强医药卫生领域廉政建设的意见（2025年版）解读
- 2024建筑外墙饰面层缺陷检测与评定标准
- 2024年全国高考英语试题及答案-全国卷2
- 重庆B卷2022年中考语文现代文阅读真题及答案
- 《事故汽车常用零部件修复与更换判别规范》
- DL-T623-2010电力系统继电保护及安全自动装置运行评价规程
- 液压与液力传动全套课件
- 弯头知识课件
- SBT 11215-2018 商品交易市场建设与经营管理术语
评论
0/150
提交评论