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

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

對于區(qū)間[a,b]上連續(xù)不斷、且f(a)f(b)<0的函數(shù)y=f(x),通過不斷地把函數(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).第15頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——二分法那么我們一起來總結(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ù)⑵~⑷第16頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——黃金分割法黃金分割法也叫0.618法，它是基于一種區(qū)間收縮的極小點(diǎn)搜索算法，當(dāng)確定搜索區(qū)間[a,b]后，我們只知道極小點(diǎn)包含于搜索區(qū)間內(nèi)，但是具體是哪個(gè)點(diǎn)，無法得知。1.算法原理黃金分割法的思想很直接，既然極小點(diǎn)包含于搜索區(qū)間內(nèi)，那么可以不斷的縮小搜索區(qū)間，就可以使搜索區(qū)間的端點(diǎn)逼近到極小點(diǎn)。第17頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——黃金分割法第18頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——黃金分割法2.算法步驟①②③④第19頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——黃金分割法③⑤②④第20頁，課件共84頁，創(chuàng)作于2023年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;黃金分割法源程序第21頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——牛頓法第22頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——牛頓法第23頁，課件共84頁，創(chuàng)作于2023年2月一維搜索——牛頓法對于正定二次函數(shù)，牛頓法一步即可達(dá)到最優(yōu)解。對于一般非二次函數(shù)，牛頓法并不能保證經(jīng)過有限次迭代法求得最優(yōu)解，但如果初始點(diǎn)充分靠近極小點(diǎn)，牛頓法的收斂速度一般是很快的。第24頁，課件共84頁，創(chuàng)作于2023年2月牛頓法程序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;第25頁，課件共84頁，創(chuàng)作于2023年2月最速下降法和共軛梯度法第26頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第27頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第28頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第29頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第30頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第31頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第32頁，課件共84頁，創(chuàng)作于2023年2月最速下降法第33頁，課件共84頁，創(chuàng)作于2023年2月最速下降法源程序運(yùn)行結(jié)果第34頁，課件共84頁，創(chuàng)作于2023年2月共軛梯度法1.算法原理

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