最優(yōu)化方法課件：第六講 無(wú)約束(多維)最優(yōu)化

第六講

無(wú)約束(多維)最優(yōu)化梯度法（最速下降法）牛頓法與擬牛頓法變尺度法(DFP法)共軛梯度法1序無(wú)約束最優(yōu)化問(wèn)題解析方法：利用函數(shù)的解析性質(zhì)——駐點(diǎn)，得到最優(yōu)解。數(shù)值方法：利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式使之收斂到最優(yōu)解。2無(wú)約束問(wèn)題的最優(yōu)性條件定理1定理2梯度為0的點(diǎn)稱為函數(shù)的駐點(diǎn)。駐點(diǎn)可能是極小點(diǎn)，也可能是極大點(diǎn)，也可能即不是極大也不是極小，這時(shí)稱為函數(shù)的鞍點(diǎn)。定理2說(shuō)明：UMP問(wèn)題的局部最優(yōu)解必是目標(biāo)函數(shù)的駐點(diǎn)。注：3定理3定理44迭代公式：如何選擇下降最快的方向？6.1梯度法（最速下降法）5一、梯度法（最速下降法）：二、梯度法算法步驟：6解：例１7三、最速下降法的特點(diǎn)1.性質(zhì).82.最速下降法的鋸齒現(xiàn)象9特點(diǎn)：線性收斂，易產(chǎn)生扭擺現(xiàn)象而造成早停。（當(dāng)x(k)距最優(yōu)點(diǎn)較遠(yuǎn)時(shí)，速度快，而接近最優(yōu)點(diǎn)時(shí)，速度下降）原因：

如果用f(x)的Taylor展開(kāi)近似計(jì)算？——牛頓法101.問(wèn)題6.2Newton法用f(x)

的Taylor展開(kāi)近似計(jì)算112.算法思想12133.算法步驟14算法框圖給定初始點(diǎn)x0和精度是是停止，輸出x0是否停止，解題失敗否停止，輸出x1否15例1：解：取x0=1,計(jì)算：迭代過(guò)程如下表：1.1370.11630.11692-0.00106131.3258-0.5178-0.570810.50000.78541016（ii）編寫(xiě)M文件nwfun.m如下：function[f,df,d2f]=nwfun(x);f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;df(1)=4*x(1)^3+2*x(1)*x(2)^2;df(2)=100*x(2)^3+2*x(1)^2*x(2);d2f(1,1)=12*x(1)^2+2*x(2)^2;d2f(1,2)=4*x(1)*x(2);d2f(2,1)=d2f(1,2);d2f(2,2)=300*x(2)^2+4*x(1)*x(2);編寫(xiě)M文件nwfun2.m：clcx=[2;2];[f0,g1,g2]=nwfun(x)whilenorm(g1)>0.00001i=1:3p=-inv(g2)*g1',p=p/norm(p)t=1.0,f=detaf(x+t*p)

whilef>f0t=t/2,f=detaf(x+t*p),%步長(zhǎng)減半

endx=x+t*p[f0,g1,g2]=nwfun(x)end17收斂速度快，為二階收斂。(2)初始點(diǎn)的選取困難，甚至無(wú)法實(shí)施。4.算法特點(diǎn)存在缺點(diǎn)及修正初始點(diǎn)要選在最優(yōu)點(diǎn)附近。18196.3擬牛頓法(變尺度法)一、擬牛頓法的思想202122分析23;)(.2kkkxfHdStep?-=計(jì)算搜索方向擬Newton條件或擬Newton方程:24Step4.判斷是否滿足終止準(zhǔn)則：

yes:計(jì)算stop,No:轉(zhuǎn)step5。256.4DFP算法一、DFP法的提出262728三、DFP算法的步驟改為:.2step,1:DFP.5Step轉(zhuǎn)，計(jì)算的校正公式：按照+=kkHk29

四、變尺度法算法框圖：yN30例解31324.6.33334六、變尺度法的主要特點(diǎn)⑴只需用到函數(shù)的一階梯度；（Newton法用到二階Hesse陣）⑵下降算法，故全局收斂；⑶不需求矩陣逆；（計(jì)算量小）⑷一般可達(dá)到超線性收斂；（速度快）⑸有二次終結(jié)性。35一、共軛方向和共軛方向法共軛是正交的推廣。1．定義6.5共軛梯度法362．共軛方向設(shè)直線

AB和CD過(guò)橢圓中心，且CD平行于橢圓在點(diǎn)A，B的切線，則稱AB與CD為共軛直徑，的方向?yàn)楣曹椃较颍駻,B的切線方向與稱為共軛方向）見(jiàn)下圖。的方向CDAB37定理1383.幾何意義3940414.共軛方向法425.共軛梯度法——

如何選取一組共軛方向？以下分析算法的具體步驟：基本思想

對(duì)于

434445464748k=k+1k=1Stop.x(k)—解k=n?yNYN重新開(kāi)始FR算法流程圖49FR算法特點(diǎn)：1、全局收斂（下降算法）；線性收斂；2、每步迭代只需存儲(chǔ)若干向量（適用于大規(guī)模問(wèn)題）；3、有二次終結(jié)性（對(duì)于正定二次函數(shù)，至多n次迭代可達(dá)最優(yōu).）

注：對(duì)不同的βk公式，對(duì)于正定二次函數(shù)是相等的，對(duì)非正定二次函數(shù)，有不同的效果，經(jīng)驗(yàn)上PRP效果較好。50例解：5152536.用于一般函數(shù)的共軛梯度法54552.牛頓法3.擬牛頓法(變尺度法)1、梯度法（最速下降法）：多變量無(wú)約束優(yōu)化搜索方法56多變量無(wú)約束優(yōu)化搜索方法4.特殊擬牛頓法1——DFP算法：5.特殊擬牛頓法2——BFGS算法：576.共軛梯度法1——

7.共軛梯度法2——

多變量無(wú)約束優(yōu)化搜索方法58命令格式為:

[x，fval，exitflag，output]=

fminunc(fun,x0

，options)；或[x，fval，exitflag，output]=

fminsearch(fun,x0,options)；標(biāo)準(zhǔn)型為：minF(X)matlab解多元函數(shù)無(wú)約束優(yōu)化問(wèn)題fminsearch是用單純形法尋優(yōu).fminunc的算法見(jiàn)以下幾點(diǎn)說(shuō)明：使用fminunc和fminsearch可能會(huì)得到局部最優(yōu)解.59[3]fminunc為中型優(yōu)化算法的步長(zhǎng)一維搜索提供了兩種算法，由options中參數(shù)LineSearchType控制：

LineSearchType=’quadcubic’(缺省值)，混合的二次和三次多項(xiàng)式插值；LineSearchType=’cubicpoly’，三次多項(xiàng)式插值說(shuō)明:[1]fminunc為無(wú)約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法。由options中的參數(shù)LargeScale控制：LargeScale=’on’(默認(rèn)值),使用大型算法LargeScale=’off’(默認(rèn)值),使用中型算法[2]fminunc為中型優(yōu)化算法的搜索方向提供了3種算法，由options中的參數(shù)HessUpdate控制：

HessUpdate=’bfgs’（默認(rèn)值），擬牛頓法的BFGS公式；

HessUpdate=’dfp’，擬牛頓法的DFP公式；

HessUpdate=’steepdesc’，最速下降法60例1minf(x)=(4x12+2x22+4x1x2+2x2+1)*ex1

1、編寫(xiě)M-文件fun.m:functionf=fun(x)f=exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

2、輸入M文件wliti.m如下:x0=[-1,1];x=fminunc(‘fun’,x0);y=fun(x)

3、運(yùn)行結(jié)果:x=0.5000-1.0000y=1.3029e-106162用fminsearch函數(shù)求解輸入命令:

f='100*(x(2)-x(1)^2)^2+(1-x(1))^2';[x,fval,exitflag,output]=fminsearch(f,[-1.22])運(yùn)行結(jié)果:x=1.00001.0000fval=1.9151e-010exitflag=1output=iterations:108

funcCount:202algorithm:'Nelder-Meadsimplexdirectsearch'634.

用fminunc

函數(shù)(1)建立M-文件fun2.m

functionf=fun2(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2(2)簡(jiǎn)單計(jì)算[x,fval,exitflag,output]=fminunc('fun2',[-1.22])(3)比較各種算法主程序compare.m64

options11=optimset('HessUpdate','dfp')[x11,fval11,exitflag11,output11]=fminunc('fun2',[-1.22],options11)pauseoptions12=optimset('HessUpdate','dfp','LineSearchType','cubicpoly')[x12,fval12,exitflag12,output12]=fminunc('fun2',[-1.22],options12)pauseoptions21=optimset('HessUpdate','bfgs')[x21,fval21,exitflag21,output21]=fminunc('fun2',[-1.22],options21)pauseoptions22=optimset('HessUpdate','bfgs','LineSearchType','cubicpoly')[x22,fval22,exitflag22,output22]=fminunc('fun2',[-1.22],options22)pauseoptions31=optimset('HessUpdate','steepdesc')[x31,fval31,exitflag31,output31]=fminunc('fun2',[-1.22],options31)pauseoptions32=optimset(,'HessUpdate','steepdesc','MaxIter',8000,'MaxFunEvals',8000)[x32,fval32,exitflag32,output32]=fminunc('fun2',[-1.22],options32)pauseoptions33=optimset('HessUpdate','steepdesc','MaxIter',9000,'MaxFunEvals',9000)[x33,fval33,exitflag33,output33]=fminunc('fun2',[-1.22],options33)65各種方法比較66（ii）編寫(xiě)M文件zuisu.mx=[2;2];[f0,g]=detaf(x