第三章無約束非線性規(guī)劃課件

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

對于區(qū)間[a,b]上連續(xù)不斷、且f(a)f(b)<0的函數(shù)y=f(x),通過不斷地把函數(shù)f(x)的零點所在的區(qū)間一分為二，使區(qū)間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫做二分法（bisection）例2借助計算器或計算機用二分法求方程2x+3x=7的近似解(精確到0.1).一維搜索——二分法對于區(qū)間[a,b]上連續(xù)不斷、且一維搜索——二分法那么我們一起來總結(jié)一下二分法的解題步驟給定精確度，用二分法求函數(shù)f(x)零點近似解的步驟如下：,給定精確度；⑴確定區(qū)間[a,b],驗證⑵求區(qū)間(a,b)的中點；⑶計算f()；若f()=0，則就是函數(shù)的零點；②若，則令b=()；此時零點③若，則令a=(此時零點)；⑷判斷是否達到精確度：即若|a-b|<,則得到零點近似值為a(或b);否則重復(fù)⑵~⑷一維搜索——二分法那么我們一起來總結(jié)一下二分法的解題步驟給定一維搜索——黃金分割法黃金分割法也叫0.618法，它是基于一種區(qū)間收縮的極小點搜索算法，當(dāng)確定搜索區(qū)間[a,b]后，我們只知道極小點包含于搜索區(qū)間內(nèi)，但是具體是哪個點，無法得知。1.算法原理黃金分割法的思想很直接，既然極小點包含于搜索區(qū)間內(nèi)，那么可以不斷的縮小搜索區(qū)間，就可以使搜索區(qū)間的端點逼近到極小點。一維搜索——黃金分割法黃金分割法也叫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,一維搜索——牛頓法一維搜索——牛頓法一維搜索——牛頓法一維搜索——牛頓法一維搜索——牛頓法對于正定二次函數(shù)，牛頓法一步即可達到最優(yōu)解。對于一般非二次函數(shù)，牛頓法并不能保證經(jīng)過有限次迭代法求得最優(yōu)解，但如果初始點充分靠近極小點，牛頓法的收斂速度一般是很快的。一維搜索——牛頓法對于正定二次函數(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最速下降法和共軛梯度法最速下降法和共軛梯度法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法最速下降法源程序運行結(jié)果最速下降法源程序運行結(jié)果共軛梯度法1.算法原理

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