7无约束最优化的解析法.docx
- 文档编号:5071004
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:20
- 大小:108.60KB
7无约束最优化的解析法.docx
《7无约束最优化的解析法.docx》由会员分享,可在线阅读,更多相关《7无约束最优化的解析法.docx(20页珍藏版)》请在冰点文库上搜索。
7无约束最优化的解析法
第七章无约束最优化的解析法
本章主要内容:
最速下降法及其收敛性与收敛速度Newton切线法及其收敛性
与收敛速度阻尼Newton法共轭梯度法及其收敛性变度量
法、最小二乘法
教学目的及要求:
掌握最速下降法并理解其收敛性与收敛速度,掌握Newton切
线法并理解其收敛性与收敛速度,了解阻尼Newton法;掌握共轭梯度法并理解其收敛性;了解变度量法、最小二乘法。
教学重点:
最速下降法.
教学难点:
变度量法.
教学方法:
启发式.
教学手段:
多媒体演示、演讲与板书相结合.
教学时间:
6学时.
教学内容:
§7.1最速下降法
考虑无约束最优化问题
minfx(,)(7.1.1)
其中f:
Rn>R具有一阶连续偏导数.
算法7-1(最速下降法)
Stepl选取初始数据•选取初始点x0,给定允许误差;,令k=0•
Step2检查是否满足终止准则.计算'f(Xk),若"(Xk):
:
:
;,迭代终止,Xk为问题(7.1.1)的近似最优解;否则,转Step3.
Step3进行一维搜索.取dk二」、f(Xk),求\和兀1,使得
f区"dQ=minf区,dk),
Xk1二人•’kdk•
令k:
=k1,返回Step2
特别地,考虑
1
minfx(=)xTQxbTxc,(7.1.2)
其中Rn,QRnn为正定矩阵,bRn,c,R.
设第k次迭代点为Xk,从点Xk出发沿」、f(xO作一维搜索,得
Xk4二Xk-“if(Xk),
其中“为最优步长.根据定理6.1.1,有Vf(Xkd八fX(k=).0而
Nf(x)=Qx+,bVXn,R
所以'f(Xk.J='f(xj-kQ'f(Xk),从而Cf(xj-■kQf(xJ八f(xj=0,而Q正
定,即if(Xk)TQf(Xk)0,故由上式解出
(7.1.3)
\f(Xk)Tlf(Xk)
'、f(Xk)TQf(Xk)
于是
这是最速下降法用于问题(7.1.2)的迭代公式.
例1用最速下降法求解问题
(7.1.5)
minf(x)二4x12x22,
其中x=(x,,x2)t•取初始点x(0)=(1,1)T,允许误差E=0.1.
解问题(7.1.5)中的f是正定二次函数,且
18Q=
<0
0)勺)
b=,c=0.
2丿<0.J
f在点x=(X|,X2)T处的梯度If(X)二(8X|,2X2)T.
第一次迭代:
令搜索方向d(0)-八f(x(0))=(-8,-2)丁,
|d(0)|=(64+4=2后a&,
从点x(0)出发沿d(0)作一维搜索,由(7.1.3)式和(7.1.4)式有
x⑴=(1,1)T0.130769(-8,-2)T=^0.046152,0.738462^.
第二次迭代:
令d⑴--if(x⑴)=(0.369216,-1.476924)丁,
|d⑴卜J2.18305=1.522375ae,
从点x⑴出发沿d⑴作一维搜索,按(7.1.4)式得
x
(2)=(0.101537,0.147682$.
第三次迭代:
令d⑵(x⑵)=(-0.812296,-0.295364)丁,
d⑵二.0.747056=0.864329;,
按(7.1.4)式求得
x⑶=(-0.009747,0.107217)丁.
第四次迭代:
令d⑶--'f(x⑶)=(0.077976,-0.214434「,
d⑶=x0.052062=0.228171;,
按(7.1.4)式求得
x(4)=(0.019126,0.027816^.
第五次迭代:
E(4)--'f(x⑷)=(-0.153008,-0.055632)丁,
d(4)=.0.026506丄0.162807;,
按(7.1.4)式求得
x⑸=(-0.001835,0.020195「.
此时,|^f(x⑸)||=".001847v名,已满足精度要求,故得问题(7.1.5)的近似
最优解
x⑸=(-0.001835,0.020195亍.
实际上问题(7.1.5)的最优解为x=(0,0)T.
定理7.1.1设f:
Rn>R具有一阶连续偏导数,冷•Rn,记:
一f(X。
),假定水平集S(f,:
J有界,令切是由最速下降法求解问题(7.1.1)产生的点列,则
(1)当「x"是有穷点列时,其最后一个点是f的平稳点;
(2)当:
Xk?
是无穷点列时,它必有极限点,并且任一极限点都是f的平稳占
八、、・
定理7.1.2设f:
Rn>R具有二阶连续偏导数,由最速下降法解问题(7.1.1)产生的点列{兀}收敛于x.若存在名>0和M,使得当||x-X||ce时,有
22myyT\2f(x)y—My,-yRn,(7.1.7)
则'人/线性收敛于x.
§7.2Newton法
f(x):
:
(x)=f(Xk)'、f(Xk)T(x-Xk);(x-Xk)T\2f(Xk)(X-Xk).
2
令灯申(x)=Q即Nf(xk)+N2f(兀心一兀)=0,解之得
Xk1二Xk-[\2f(Xk)]七f(Xk).
算法7-2(Newton法)
Step1选取初始数据.选取初始点Xq,给定允许误差;7,令k=0.
Step2检查是否满足终止准则.计算灯f(Xk),若|可f(兀)|£名,迭代终止,x<为问题(7.1.1)的近似最优解;否则,转Step3.
Step3构造Newton方向.计算['2f(兀)]‘,取d^-['2f(x<)]4yf(xj.
Step4求下一个迭代点.令XkXk-dk,k^k1,返回Step2.
例2用Newton法求解问题(7.1.5),仍取初始点x(0)=(1,1)T,允许误差
;一0.1.
z80、
<02」
解if(x(0)=(8「2八2f(x(0))=
(1)(0)_(0)TTT
x()=x+d=(1,1)-(1,1)=(0,0)・
由于|Vf(x
(1))=0c0.1,迭代结束,得x
(1)为问题(7.1.5)的最优解.
定理7.2.1设f:
Rn>R具有三阶连续偏导数,xRn,'f任)=0,若存在
名>0和m>0,使得当||x_刘兰g时,有
m||y「兰yF2f(x)y,PyERn,(7.2.2)
则当初始点x0充分接近x时,由Newton法解问题(7.1.1)产生的点列fxj收敛于x,并有二阶收敛速度.
算法7-3(阻尼Newton法)
Step1选取初始数据•选取初始点x0,给定允许误差;•0,令k=0・
Step2检查是否满足终止准则.计算'f(xj,若"(xj:
:
:
;,迭代终止,xk为问题(7.1.1)的近似最优解;否则,转Step3.
Step3构造Newton方向•计算八2仁兀)]‘,取dk二-['2f(兀)]七f(兀)・
Step4进行一维搜索•求k和Xk1,使得
f区kdQ二minf区■dQ,
Xk1=xk■'kdk・
令k-k1,返回Step2.
例3用阻尼Newton法求解下面问题:
minf(x)=(1-%)22(x2-皆)2,(7.2.6)
其中x=(xi,x2)T.取初始点x(0)=(0,0)T,允许误差;=0.1.
解第一次迭代:
于是,Newton方向d(0)2f(x(0))]七f(x(0))=(1,0)T,从x(0)出发沿d(0)作
x⑴=X(0)•'0d(0)=(1/2,0)t.
if(x
(1))=(0,-1)T,if(x
(1))■:
.
第二次迭代:
d⑴-f、2f(x
(1))]」if(x⑴)=(1/4,1/2)t.
从x⑴出发沿d⑴作一维搜索,即求
1
minf(x⑴■d⑴)=min[8(2-■)2(2-■)4]
.■-_00128
的最优解,得到1=2.令
x⑵=x
(1)计⑴=(1,1)T.
If(x⑴)=(0,-1)T,If(x⑴)=1;.
此时,\f(x
(2))=(0,0),fxf2))0,得问题(7.2.6)的最优解为
x⑵=(1,1)T,这是惟一的最优解.
定理722设f:
Rn>R具有二阶连续偏导数,x^Rn,记"f(X。
),假
定水平集S(f,〉)有界,并且对一切X,Rn」2f(x)正定.若:
是由阻尼Newton
法求解问题(7.1.1)产生的点列,则
(1)当「xj是有穷点列时,其最后一个点是f的唯一极小点;
(2)当:
Xk/是无穷点列时,它必收敛于f的唯一极小点.
§7.3共轭梯度法
最速下降法和Newton法是最基本的无约束最优化方法,它们的特性各异:
前者计算量较小而收敛速度慢;后者虽然收敛速度快,但需要计算目标函数的Hesse矩阵及其逆矩阵,故计算量大•本节介绍一类无需计算二阶导数并且收敛速度快的方法.
定义设QRnn为正定矩阵•若Rn中的向量组do,d!
,…,dm」满足
diTQdj=o,-i,j=0,1,,m-1,i=j,
则称d°,a,…,dm」是Q共轭的.
定理7.3.1设QRnn是正定矩阵,Rn中非零向量组d°,a,…,dm」是Q共轭的,则这m个向量线性无关.
定理7.3.2设p・Rn,d°,d1,…,dn」是Rn中线性无关的向量组,若p与每个di都正交,则p=0.
考虑正定二次函数的无约束最优化问题
1
minf(x)xTQxbTxc,(7.3.3)
2
其中QRnn为正定矩阵,bRn,c・R.
定理7.3.3设QRnn为正定矩阵,d°,a,…,dn:
是Rn中一组Q共轭的非零
向量.对于问题(7.3.3),若从任意点x^Rn出发依次沿d。
©,…,dnj进行一维搜索,则至多经过n次迭代可得问题(7.3.3)的最优解.
算法7-4(共轭方向法)
给定一个正定矩阵QRnn.
Stepl选取初始数据.选取初始点Xo,给定允许误差;.0.
Step2选取初始搜索方向.计算if(xo),求出do,使if(Xo)Td。
:
:
:
0,令k=0.
Step3检查是否满足终止准则.若'f(Xk):
:
:
;,迭代终止;否则,转Step4.
Step4进行一维搜索.求“和xkd,使得
f(Xkkdk)二minf(Xk,dk),
Xk-Xk''kdk.
Step5选取搜索方向.求dk1使
dk「Qdj=0,j=0,1,,k,
令k:
=k1,返回Step3.
如果用共轭方向法求解正定二次函数的无约束最优化问题
1
minf(x)xtQxbTXc,(7.3.3)
2
其中QRnn为正定矩阵,bRn,c・R(此时算法中的正定矩阵应与二次函数的
正定矩阵一致),那么容易推出迭代公式为
对于求解问题(7.1.1),我们还有如下一些方法.
、f(XkJUf(XkJ.dkT、f(Xk)'
Polak-Ribiere-Polyak(PRP)公式:
“皿
算法7-5(FR共轭梯度法)
Step1选取初始数据.选取初始点X0,给定允许误差;•0.
Step2检查是否满足终止准则.计算'f(x。
),若"(X0):
:
:
;,迭代终止,X)
为(7.1.1)
的近似最优解;否则,转Step3.
Step3
构造初始搜索方向.计算d。
-“f(X0),k=0.
Step4
进行一维搜索.求■k和Xk1,使得
f(XkMQ=minf(Xk,dQ,
■-
xk1=人…kdk.
Step5
检查是否满足终止准则.计算lf(xkd),若If(xk.J-,迭代终止,
xk1为(7.1.1)的近似最优解;否则,转Step6.
Step6
检查迭代次数.若k•1二n,令Xd>xn,返回Step3;否则,转Step7.
Step7
构造共轭方向.用FR公式取
f(Xk
dk1=-f(xk1)■'kdk,■'k2,
"(Xk)
令k>k1,返回Step4.
注意,如果算法7-4的Step7中〉k的形式改为DM公式或PRP公式,则分别得到DM共轭梯度法和PRP共轭梯度法.
定理7.3.5设f:
Rn>R具有一阶连续偏导数,Rn,记:
=f(X。
),并假设水平集S(f「)有界.若「xj是由共轭梯度法(包括任何一种仅仅与算法7-5中:
k的形式不同的共轭梯度法)解问题(7.1.1)所产生的点列,则
(1)当:
xkf是有穷点列时,其最后一个点是f的平稳点;
(2)当:
Xk/是无穷点列时,它必有极限点,并且任一极限点都是f的平稳
占
八、、・
可以证明:
共轭梯度法产生的点列Cxk!
是n步二阶收敛的,即
例4用FR共轭梯度法求解问题(7.2.6)minf(x)=(1-xj2•2(x2-xj)2,
仍取初始点x(o)=(0,0)T,允许误差;=0.1.minf(x)=(1一xj2•2区-%2)2
解因为
所以
Vf(x(0))=(—2,0)T』|Vf(x(0))|=2>名.
令d(0)-八f(x(0))=(2,0)t,从x(0)出发,沿d(0)进行一维搜索,得
■0=1/4,x
(1)=x(0)0d(0)=(1/2,0)T.
从而
W(x
(1))=(0,—1)T』Vf(x
(1))|=1“.
由FR公式有
"⑴)|2_1
2—
X(x(0))4
因此,新的搜索方向为
d⑴-f(X⑴):
0d(0)=(1/2,1)t.
从x⑴出发,沿d⑴进行一维搜索,得
>=1,X⑵二X⑴…”⑴=(1,1)T.
此时
可(x⑵)=(0,0)打pf(x⑵)||=0 得问题(7.2.6)的最优解为x (2)=(1,1)T. §7.4变度量法 前面介绍的最速下降法和阻尼Newton法,它们的迭代公式可以统一为 Xk1二xk」dk,dk「-G^f(Xk), 其中G「Rnn,*是从点Xk出发沿dk进行一维搜索的最优步长•当q“n(n阶 21单位矩阵)时,(7.4.1)式即为最速下降法的迭代公式;当q=pf(xJ]—时, (741)式就是阻尼Newton法的迭代公式.因此,如果能够使G的选取既不需要计算Hesse矩阵及其逆矩阵,又能很好地近似于V2f(X<)]J,则由(7.4.1)式确定的迭代算法将会保持Newton法收敛速度快的优点,同时又具有计算简单的特性. 设问题(7.1.1)中目标函数f具有二阶连续偏导数,且v2f(X<)正定•为使由(7.4.1)中第2式确定的搜索方向是f在点xk处的下降方向,根据定理1.2.3,应当要求'f(xQTdk: : : 0,或即'f(Xk)TG^f(Xk)0,所以我们应要求(7.4.1)式 中的Q是正定矩阵. 设在第k1次迭代后得到人1,将f在点x<・1处作Taylor展开,取二阶近似, T1t2 得f(xpf(Xk1)、f(Xk1)(X-Xk1)2(X-Xk1)'f(Xk1)(X-Xk1), 对上式两边求梯度,有\f(xp'f(Xk1)•'、'2f(Xk1)(x-Xk.1), 令x=Xk,得到'f(X<1)」f()0八2心.1)区.1-)0, 即r2f(X<1)]Tf(X<1)」f(X<)]X1-人• 易知,当f为正定二次函数时,上式成为等式,即 F2f(兀1)]Tf(兀1)」f(人)]二人1一X.(7.4.2) 因为具有正定Hesse矩阵的函数在极小点附近可用二次函数很好地近似,所以如果我们迫使G1满足类似于(7.4.2)式的关系式,即令 G<『f(Xk.1)」f(XJ]=Xk1一人,(7.4.3) 则q1就可以很好地近似于p2f(XkJ]'.因此称(7.4.3)式为拟Newton条件. 为方便起见,记 %=小我,q「f(Xk1)」f(x<),q=—q, 并称厶Gk为校正矩阵,则拟Newton条件可以写成 •>GkQk「X—GPQk.(7.4.4) 综上所述,我们得到如下的一类算法. 算法7-6(拟Newton法) Stepl选取初始数据.选取初始点Rn和初始矩阵Go,要求Go为正定矩阵(可取Go=In),给定允许误差>0,令k=0. Step2检查是否满足终止准则.计算f(xk),若岸f(xj|•;「,迭代终止,人为问题(7.1.1)的近似最优解;否则,转Step3. Step3构造搜索方向•令dk二-Gk'f(Xk). Step4进行一维搜索•求k和Xk1,使得 f(Xkkdk)二minf(Xk■dk), ■0 Xk1二兀•’kdk• Step5产生校正矩阵•求出满足(7.4.4)的校正矩阵Gk,令 Gkq=Gk二Gk,k: 二k1,返回Step2. 算法7-7(DFP法) Step1选取初始数据.选取初始点Xo和初始矩阵Go=In,给定允许误差 ;•0. Step2检查是否满足终止准则.计算\f(Xo),若|卜f(Xo)|「: : ;,迭代终止,Xo为(7.1.1)的近似最优解;否则,转Step3. Step3构造初始DFP方向.取do二」、f(X。 ),令k=0. Step4进行一维搜索.求出\和Xi,使得 f(Xk^miqf(Xk■dk), 0 Xk1二Xk'kdk. Step5检查是否满足终止准则.计算f(Xk1),若I卜f(Xk1)||: : : ;,迭代终止,xk1为(7.1.1)的近似最优解;否则,转Step6. Step6检查迭代次数.若k•仁n,令xo>Xn,返回Step3;否则,转Step7. Step7构造DFP方向.用DFP公式Gk1=: GkXk^X^_G^'gL_GL,算 AXk^gk^gjGQgk 出Gki,取dki-Gk八f(兀J,令kk1,返回Step4. 定理7.4.4设f: Rn>R具有一阶连续偏导数,X)•Rn,记: 一f(X。 ),并 假设水平集S(f“)有界.若g是由DFP法求解问题(7.1.1)产生的点列,则 (1)当Cxk? 是有穷点列时,其最后一个点是f的平稳点; (2)当: Xk/是无穷点列时,它必有极限点,并且其任一极限点都是f的平稳点. 可以证明DFP法具有超线性收敛性. 算法7-8(BFGS法) Step1选取初始数据.选取初始点X。 和初始矩阵G°=ln,给定允许误差 ;0. Step2检查是否满足终止准则.计算'f(Xo),若'f(Xo): : : ;,迭代终止,Xo 为(7.1.1)的近似最优解;否则,转Step3. Step3构造初始BFGS方向.取do=-Vf(x°),令k=0. Step4进行一维搜索.求出k和Xk1,使得 f(Xkgk)二miqf(Xk‘dj Xk・1=Xk■'kdk• Step5检查是否满足终止准则.计算f(Xk1),若、f(XkJ: : : ;,迭代终止,兀! 为(7.1.1)的近似最优解;否则,转Step6. Step6检查迭代次数.若k1n,令xoXn,返回Step3;否则,转Step7. Step7构造BFGS方向.用BFGS公式 算出Gk,,取dk1二-Gk八f区.J,令k^k1,返回Step4. 可以证明BFGS法具有超线性收敛性. §7.5最小二乘法 在实际应用中,我们经常遇到目标函数为若干个函数的平方和的最优化问 m 题: mins(x)八f,2(x),(7.5.1) 其中X•Rn,一般假设m_n,这类问题称为最小二乘问题.当每个fi(x)都是线 性函数时,问题(7.5.1)称为线性最小二乘问题,否则,称为非线性最小二乘 问题. 由于最小二乘问题相对于一般无约束最优化问题而言具有特殊形式,因此 除能运用本章前面介绍的一般求解方法外,还应有更为简便有效的方法. 一、线性最小二乘法 n 当fi(x)为线性函数时,即fi(x)=2: ajXj-b,i=1,2,…,m,问题(7.5.1)就 j# 成为线性最小二乘问题.如令 '刍11…3^' A= 9+9 b= , lbm丿 f(x)=(f1(X),f2(X),,fm(x))T, 则s(x)=fxT)fx(=)Ax(-bTAX"(b=AX『b|, 从而问题(7.5.1)可表示为 mins(x)二Ax-b? .(7.5.2) 因为s(x)二(Ax-b)T(Ax-b)二xTATAx-2bTAxbTb,所以s(x)为二次函数, 且's(x^2ATA^2Arb? 2s(x)=2ATA. 显然,对一切疙Rn,均有yTATAy=||Ay||>0,即知,AA是半正定矩阵,从而由定理2.3.7知,s(x)是Rn上的凸函数. 定理7.5.1x・Rn是问题(7.5.2)的最优解的充要条件是X满足方程组 ATAx=ATb.(7.5.3) 容易知道,矩阵AtA正定的充要条件是对于一切非零向量yRn,有 2 yTATAy=Ay0. 记y=(yi,y2,…,ynT’Ang,p? …,Pn),则上式等价于 n Ay八Pjyj-0.(7.5.4) jm 而(7.5.4)式成立的充要条件是向量组Pi,P2/,Pn线性无关,这又等价于 rankA二n.从而ATA为正定矩阵的充要条件是rankA=n,换句话说,s(x)为正定二次函数的充要条件是rankA=n. 定理7.5.2若rankA二n,贝U x=(ATA)」ATb(7.5.5) 为问题(7.5.2)的唯一最优解. 显然,方程组Ax二b有解的充分必要条件是问题(7.5.2)的最优值mins(x)=0. 2 例5求解线性最小二乘问题minAx-b,(7.5.6) S1、 其中A= 2-3 b= -3 <-14」 <_1」 由于问题(7.5.6)的最优值为(AX-b)T(A^-b)=11.45428571=0. S+X2=2,因此,方程组丿2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 无约束 优化 解析