7无约束最优化的解析法Word文档下载推荐.docx
《7无约束最优化的解析法Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《7无约束最优化的解析法Word文档下载推荐.docx（20页珍藏版）》请在冰点文库上搜索。
其中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）勺）
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；
x（4）=（0.019126,0.027816^.
第五次迭代：
E（4）--'
f（x⑷）=（-0.153008,-0.055632）丁,
d（4）=.0.026506丄0.162807；
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:
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构造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:
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・
f（xj，若"
（xj：
迭代终止，xk为问题（7.1.1）的近似最优解；
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⑴作一维搜索，即求
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:
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.
考虑正定二次函数的无约束最优化问题
minf（x）xTQxbTxc，（7.3.3）
其中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.
如果用共轭方向法求解正定二次函数的无约束最优化问题
minf（x）xtQxbTXc，（7.3.3）
其中QRnn为正定矩阵，bRn,c・R（此时算法中的正定矩阵应与二次函数的
正定矩阵一致），那么容易推出迭代公式为
对于求解问题（7.1.1），我们还有如下一些方法.
、f（XkJUf（XkJ.dkT、f（Xk）'
Polak-Ribiere-Polyak（PRP）公式：
“皿
算法7-5（FR共轭梯度法）
Step1选取初始数据.选取初始点X0，给定允许误差；
•0.
f（x。
），若"
（X0）：
迭代终止，X）
为（7.1.1）
的近似最优解；
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:
R具有一阶连续偏导数，Rn，记:
=f（X。
），并假设水平集S（f「）有界.若「xj是由共轭梯度法（包括任何一种仅仅与算法7-5中:
k的形式不同的共轭梯度法）解问题（7.1.1）所产生的点列，则
（1）当：
xkf是有穷点列时，其最后一个点是f的平稳点；
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<
z.
得问题（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构造搜索方向•令dk二-Gk'
f（Xk）.
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构造初始DFP方向.取do二」、f（X。
），令k=0.
Step4进行一维搜索.求出\和Xi，使得
f（Xk^miqf（Xk■dk）,
Xk1二Xk'
kdk.
Step5检查是否满足终止准则.计算f（Xk1），若I卜f（Xk1）||:
，迭代终止，xk1为（7.1.1）的近似最优解；
Step6检查迭代次数.若k•仁n，令xo>
Xn，返回Step3;
Step7构造DFP方向.用DFP公式Gk1=：
GkXk^X^_G^'
gL_GL，算
AXk^gk^gjGQgk
出Gki，取dki-Gk八f（兀J，令kk1，返回Step4.
定理7.4.4设f:
R具有一阶连续偏导数，X）•Rn，记:
），并
假设水平集S（f“）有界.若g是由DFP法求解问题（7.1.1）产生的点列，则
（1）当Cxk?
Xk/是无穷点列时，它必有极限点，并且其任一极限点都是f的平稳点.
可以证明DFP法具有超线性收敛性.
算法7-8（BFGS法）
Step1选取初始数据.选取初始点X。
和初始矩阵G°
=ln，给定允许误差
0.
f（Xo），若'
f（Xo）：
迭代终止，Xo
为（7.1.1）的近似最优解；
Step3构造初始BFGS方向.取do=-Vf（x°
），令k=0.
Step4进行一维搜索.求出k和Xk1，使得
f（Xkgk）二miqf（Xk‘dj
Xk・1=Xk■'
kdk•
Step5检查是否满足终止准则.计算f（Xk1），若、f（XkJ：
，迭代终止，兀！
Step6检查迭代次数.若k1n，令xoXn，返回Step3;
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=
am1amn」
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，有
yTATAy=Ay0.
记y=（yi,y2,…，ynT’Ang,p?
…,Pn），则上式等价于
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.
例5求解线性最小二乘问题minAx-b，（7.5.6）
S1、
其中A=
2-3
-3
-14」
_1」
由于问题（7.5.6）的最优值为（AX-b）T（A^-b）=11.45428571=0.
S+X2=2,因此，方程组丿2
升级会员 