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

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

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