第三章無(wú)約束非線(xiàn)性規(guī)劃課件

無(wú)約束非線(xiàn)性規(guī)劃第一節(jié)最優(yōu)性條件第二節(jié)一維搜索第三節(jié)最速下降法和共軛梯度法第四節(jié)牛頓法和擬牛頓法(變尺度法)第五節(jié)信賴(lài)域法無(wú)約束非線(xiàn)性規(guī)劃第一節(jié)最優(yōu)性條件第二節(jié)一維搜索第三節(jié)最引言本章討論如下的優(yōu)化模型其中是的實(shí)值連續(xù)函數(shù)，通常假定具有二階連續(xù)偏導(dǎo)數(shù)。引言本章討論如下的優(yōu)化模型其中是預(yù)備知識(shí)預(yù)備知識(shí)預(yù)備知識(shí)預(yù)備知識(shí)預(yù)備知識(shí)預(yù)備知識(shí)最優(yōu)性條件最優(yōu)性條件最優(yōu)性條件定理的逆不成立，即梯度為零的點(diǎn)不一定是局部解。最優(yōu)性條件定理的逆不成立，即梯度為零的點(diǎn)不一定是局部解。最優(yōu)性條件最優(yōu)性條件迭代法求解無(wú)約束優(yōu)化問(wèn)題的常用方法是數(shù)值解法，而數(shù)值解法中最為常見(jiàn)的是迭代法。迭代法思想：迭代法求解無(wú)約束優(yōu)化問(wèn)題的常用方法是數(shù)值解法，而數(shù)值解法中最迭代法迭代法最優(yōu)性條件最優(yōu)性條件迭代算法迭代的終止條件在不同的最優(yōu)化方法中也是不同的。理論上，根據(jù)最優(yōu)性的一階必要條件，以及算法的設(shè)計(jì)思想，可以用來(lái)終止迭代，其中是給定的精度要求。迭代算法迭代的終止條件在不同的最優(yōu)化方法中也是不同的。理論上一維搜索一維搜索一維搜索——二分法

對(duì)于區(qū)間[a,b]上連續(xù)不斷、且f(a)f(b)<0的函數(shù)y=f(x),通過(guò)不斷地把函數(shù)f(x)的零點(diǎn)所在的區(qū)間一分為二，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法叫做二分法（bisection）例2借助計(jì)算器或計(jì)算機(jī)用二分法求方程2x+3x=7的近似解(精確到0.1).一維搜索——二分法對(duì)于區(qū)間[a,b]上連續(xù)不斷、且一維搜索——二分法那么我們一起來(lái)總結(jié)一下二分法的解題步驟給定精確度，用二分法求函數(shù)f(x)零點(diǎn)近似解的步驟如下：,給定精確度；⑴確定區(qū)間[a,b],驗(yàn)證⑵求區(qū)間(a,b)的中點(diǎn)；⑶計(jì)算f()；若f()=0，則就是函數(shù)的零點(diǎn)；②若，則令b=()；此時(shí)零點(diǎn)③若，則令a=(此時(shí)零點(diǎn))；⑷判斷是否達(dá)到精確度：即若|a-b|<,則得到零點(diǎn)近似值為a(或b);否則重復(fù)⑵~⑷一維搜索——二分法那么我們一起來(lái)總結(jié)一下二分法的解題步驟給定一維搜索——黃金分割法黃金分割法也叫0.618法，它是基于一種區(qū)間收縮的極小點(diǎn)搜索算法，當(dāng)確定搜索區(qū)間[a,b]后，我們只知道極小點(diǎn)包含于搜索區(qū)間內(nèi)，但是具體是哪個(gè)點(diǎn)，無(wú)法得知。1.算法原理黃金分割法的思想很直接，既然極小點(diǎn)包含于搜索區(qū)間內(nèi)，那么可以不斷的縮小搜索區(qū)間，就可以使搜索區(qū)間的端點(diǎn)逼近到極小點(diǎn)。一維搜索——黃金分割法黃金分割法也叫0.618法，它是基于一一維搜索——黃金分割法一維搜索——黃金分割法一維搜索——黃金分割法2.算法步驟①②③④一維搜索——黃金分割法2.算法步驟①②③④一維搜索——黃金分割法③⑤②④一維搜索——黃金分割法③⑤②④function[x,minf]=minHJ(f,a,b,eps)formatlong;ifnargin==3eps=1.0e-6;endl=a+0.382*(b-a);u=a+0.618*(b-a);k=1;tol=b-a;whiletol>eps&&k<100000fl=subs(f,findsym(f),l);fu=subs(f,findsym(f),u);iffl>fua=l;l=u;u=a+0.618*(b-a);elseb=u;u=l;l=a+0.382*(b-a);endk=k+1;tol=abs(b-a);endifk==100000disp('找不到最小值！');x=NaN;minf=NaN;return;endx=(a+b)/2;minf=subs(f,findsym(f),x);formatshort;黃金分割法源程序function[x,minf]=minHJ(f,a,一維搜索——牛頓法一維搜索——牛頓法一維搜索——牛頓法一維搜索——牛頓法一維搜索——牛頓法對(duì)于正定二次函數(shù)，牛頓法一步即可達(dá)到最優(yōu)解。對(duì)于一般非二次函數(shù)，牛頓法并不能保證經(jīng)過(guò)有限次迭代法求得最優(yōu)解，但如果初始點(diǎn)充分靠近極小點(diǎn)，牛頓法的收斂速度一般是很快的。一維搜索——牛頓法對(duì)于正定二次函數(shù)，牛頓法一步即牛頓法程序function[x,minf]=minNewton(f,x0,eps)formatlong;ifnargin==2eps=1.0e-6;enddf=diff(f);d2f=diff(df);k=0;tol=1;whiletol>epsdfx=subs(df,findsym(df),x0);ifdiff(d2f)==0d2fx=double(d2f);elsed2fx=subs(d2f,findsym(d2f),x0);endx1=x0-dfx/d2fx;k=k+1;tol=abs(dfx);x0=x1;endx=x1;minf=subs(f,findsym(f),x);formatshort;牛頓法程序function[x,minf]=minNe最速下降法和共軛梯度法最速下降法和共軛梯度法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法源程序運(yùn)行結(jié)果最速下降法源程序運(yùn)行結(jié)果共軛梯度法1.算法原理

共軛梯度法是利用目標(biāo)函數(shù)梯度逐步產(chǎn)生共軛方向作為線(xiàn)搜索方向的方法，每次搜索方向都是在目標(biāo)函數(shù)梯度的共軛方向，搜索步長(zhǎng)通過(guò)一維極值算法確定。共軛梯度法是介于最速下降法與牛頓法之間的一個(gè)方法。它僅需利用一階導(dǎo)數(shù)的信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì)算Hesse矩陣并求逆的缺點(diǎn)。共軛梯度法不僅是解大型線(xiàn)性方程組最有用的方法之一，也是解大型非線(xiàn)性最優(yōu)化問(wèn)題最有效的算法之一。共軛梯度法1.算法原理共軛梯度法是介于最速下降法與牛共軛梯度法共軛梯度法最早是由Hestenes和Stiefel(1952)提出來(lái)的，用于解正定系數(shù)矩陣的線(xiàn)性方程組。在這個(gè)基礎(chǔ)上，F(xiàn)letcher和Reeves(1964)首先提出了解非線(xiàn)性最優(yōu)化問(wèn)題的共軛梯度法。由于共軛梯度法不需要矩陣存儲(chǔ)，且有較快的收斂速度和二次終止性等優(yōu)點(diǎn)，現(xiàn)在共軛梯度法已經(jīng)廣泛地應(yīng)用于實(shí)際問(wèn)題中。共軛梯度法共軛梯度法最早是由Hestenes和Sti共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法是一個(gè)典型的共軛方向法，它的每一個(gè)搜索方向是互相共軛的。而這些搜索方向僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合。因此存儲(chǔ)量小，計(jì)算方便。共軛梯度法共軛梯度法是一個(gè)典型的共軛方向法，它的每一個(gè)搜共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法這說(shuō)明我們?cè)诿恳粋€(gè)迭代點(diǎn)處產(chǎn)生的下降方向都是互相共軛的，這滿(mǎn)足算法的要求。共軛梯度法這說(shuō)明我們?cè)诿恳粋€(gè)迭代點(diǎn)處產(chǎn)生的下降方向都共軛梯度法共軛梯度法共軛梯度法綜合以上，我們可以得到各個(gè)迭代點(diǎn)處下降方向都是Q共軛的共軛梯度算法。共軛梯度法綜合以上，我們可以得到各個(gè)迭代點(diǎn)處下降方向共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法共軛梯度法源程序共軛梯度法源程序共軛梯度法小結(jié)共軛梯度法小結(jié)共軛梯度法小結(jié)共軛梯度法小結(jié)共軛梯度法小結(jié)共軛梯度法小結(jié)共軛梯度法小結(jié)共軛梯度法小結(jié)牛頓法牛頓法牛頓法牛頓法牛頓法牛頓法牛頓法源程序運(yùn)行結(jié)果牛頓法源程序運(yùn)行結(jié)果擬牛頓法(變尺度法)牛頓法成功的關(guān)鍵是利用了Hesse矩陣提供的曲率信息，但計(jì)算Hesse矩陣工作量大，并且有的目標(biāo)函數(shù)的Hesse矩陣很難計(jì)算，甚至不好求出，這就導(dǎo)致了一個(gè)想法:能否僅利用目標(biāo)函數(shù)值和一階導(dǎo)數(shù)的信息，構(gòu)造出目標(biāo)函數(shù)的曲率近似，使方法具有類(lèi)似牛頓法的收斂速度快的優(yōu)點(diǎn)。擬牛頓法就是這樣的一類(lèi)算法。由于它不需要二階導(dǎo)數(shù)，擬牛頓法往往比牛頓法更有效。擬牛頓條件和牛頓法的推導(dǎo)一樣，考慮目標(biāo)函數(shù)在當(dāng)前點(diǎn)處的二次模型。擬牛頓法(變尺度法)牛頓法成功的關(guān)鍵是利用了He擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓算法擬牛頓法(變尺度法)擬牛頓算法擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺度法)DFP校正是第一個(gè)擬牛頓校正，是1959年由Davidon提出的，后來(lái)由Fletcher和Powell(1963)解釋和發(fā)展的.BFGS校正是目前最流行的也是最有效的擬牛頓校正，它是由Broyden,Fletcher,Goldfarb和Schanno在1970年各自獨(dú)立提出的擬牛頓法。擬牛頓法(變尺度法)DFP校正是第一個(gè)擬牛頓校正，是1959擬牛頓法(變尺度法)擬牛頓法(變尺度法)擬牛頓法(變尺