第八章數(shù)值優(yōu)化

第八章數(shù)值優(yōu)化第1頁，課件共65頁，創(chuàng)作于2023年2月8.1單變量函數(shù)的極小值8.2內(nèi)德-米德方法和鮑威爾方法8.3梯度和牛頓方法目錄第2頁，課件共65頁，創(chuàng)作于2023年2月8.1單變量函數(shù)的極小值定義8.1如果存在包含p的開區(qū)間I，使得對所有x∈I，有f(p)≤f(x)，則稱函數(shù)f在x=p處有局部極小值。類似地，如果對所有x∈I，有f(p)≥f(x)，則稱函數(shù)f在x=p處有局部極大值。如果f在點x=p處有局部極大值或極小值，則稱f在點x=p處有局部極值。第3頁，課件共65頁，創(chuàng)作于2023年2月單調(diào)性的定義和判定定義8.2設(shè)f(x)定義在區(qū)間I上。若對所有x1<x2，當(dāng)x1,x2∈I時有f(x1)<f(x2)，則稱f在區(qū)間I上遞增。若對所有x1<x2，當(dāng)x1,x2∈I時有f(x1)>f(x2)，則稱f在區(qū)間I上遞減。定理8.1設(shè)f(x)在區(qū)間I=[a,b]上連續(xù)，并在(a,b)上可微。若對所有x∈(a,b)有f’(x)>0，則f(x)在I上遞增。若對所有x∈(a,b)有f’(x)<0，則f(x)在I上遞減。第4頁，課件共65頁，創(chuàng)作于2023年2月駐點和一階導(dǎo)數(shù)測試定理8.2設(shè)f(x)定義在區(qū)間I=[a,b]上，并在內(nèi)點p∈(a,b)處有局部極值。若f(x)在x=p處可微，則f’(p)=0。定理8.3設(shè)f(x)在I=[a,b]上連續(xù)，并設(shè)除x=p處外，f’(x)對所有x∈(a,b)都有定義。若在(a,p)上f’(x)<0，而在(p,b)上f’(x)>0，則f(p)是局部極小值。若在(a,p)上f’(x)>0，而在(p,b)上f’(x)<0，則f(p)是局部極大值。第5頁，課件共65頁，創(chuàng)作于2023年2月二階導(dǎo)數(shù)測試定理8.4設(shè)f在區(qū)間[a,b]上連續(xù)，并且f’和f’’在區(qū)間(a,b)上有定義。又設(shè)p∈(a,b)是關(guān)鍵點，即f’(p)=0。若f’’(p)>0，則f(p)是f的一個局部極小值。若f’’(p)<0，則f(p)是f的一個局部極大值。若f’’(p)=0，則結(jié)果不確定。第6頁，課件共65頁，創(chuàng)作于2023年2月8.1.1分類搜索方法直接法是一種數(shù)值方法這種方法的基本思想是迭代，通過迭代產(chǎn)生一個點序列{X(k)}，使之逐步接近最優(yōu)點只用到目標(biāo)函數(shù)，通過對函數(shù)多次求值來求函數(shù)f(x)在給定區(qū)間上的一個局部極小值要盡量減少函數(shù)求值的次數(shù)，確定在哪里求f(x)值的好策略非常重要如黃金分割搜索法、Fibonacci搜索法、隨機搜索法第7頁，課件共65頁，創(chuàng)作于2023年2月搜索法必須滿足的條件使用這些方法來求f(x)的極小值必須滿足特定的條件，以保證在給定的區(qū)間內(nèi)有合適的極小值這個特定條件就是函數(shù)f(x)在給定區(qū)間中是單峰的定義8.3如果存在唯一的p∈I，使得（1）f(x)在[a,p]上遞減，（2）f(x)在[p,b]上遞增，則函數(shù)f(x)在I=[a,b]上是（下）單峰的。第8頁，課件共65頁，創(chuàng)作于2023年2月黃金分割搜索法（0.618法）如果已知f(x)在[a,b]上是（下）單峰的，則有可能找到該區(qū)間的一個子區(qū)間，f(x)在該子區(qū)間上取得極小值選擇兩個內(nèi)點c<d，這樣就有a<c<d<b。f(x)的單峰特性保證了函數(shù)值f(c)和f(d)小于max{f(a),f(b)}出現(xiàn)兩種情況：第9頁，課件共65頁，創(chuàng)作于2023年2月黃金分割搜索方法的決策過程acpdby=f(x)如果f(c)≤f(d)，則從右側(cè)壓縮，使用[a,d]cpdby=f(x)如果f(c)>f(d)，則從左側(cè)壓縮，使用[c,b]a第10頁，課件共65頁，創(chuàng)作于2023年2月黃金分割法原理

設(shè)函數(shù)f(x)在閉區(qū)間[a,b]上是（下）單峰函數(shù)，即在(a,b)內(nèi)f(x)有唯一的極小點p，在p的左邊f(xié)(x)嚴(yán)格單調(diào)下降，在p的右邊f(xié)(x)嚴(yán)格單調(diào)上升。那么對于(a,b)內(nèi)任意兩點c＜d，如果f(c)＜f(d)，則p∈[a,d]；否則p∈[c,b]第11頁，課件共65頁，創(chuàng)作于2023年2月黃金分割法選擇內(nèi)點c和d，使得區(qū)間[a,c]與[d,b]對稱，即b-d=c-a，其中c=a+(1-r)(b-a)=ra+(1-r)bd=b-(1-r)(b-a)=(1-r)a+rb并且1/2<r<1（保證c<d）希望r在每個子區(qū)間上保持為常數(shù)，且舊的內(nèi)點中有一個成為新子區(qū)間的一個內(nèi)點，而另一個則成為新子區(qū)間的一個端點在每次迭代中只需要找一個新的點，則只需要一次新的函數(shù)求值計算第12頁，課件共65頁，創(chuàng)作于2023年2月比例因子的選擇設(shè)f(c0)≤f(d0)，則從右側(cè)壓縮，使用[a0,d0]，即取a1=a0，b1=d0和d1=c0，則需要再求一個新的點c1a1c1d1b1a0c0d0b001-rr1因為1/2<r<1（保證c<d），故取第13頁，課件共65頁，創(chuàng)作于2023年2月斐波那契（Fibonacci）搜索法黃金分割搜索法第一次迭代中進行了兩次函數(shù)求值，而在后續(xù)的每次迭代中則只進行一次函數(shù)求值r的值對每個子區(qū)間相同，當(dāng)|bk-ak|<ε或|f(bk)-f(ak)|<ε時，迭代結(jié)束，取[ak,bk]的中點為所求最小值點。其中ε是預(yù)定義的容差斐波那契（Fibonacci）搜索法中r的值不是常數(shù)，而且子區(qū)間數(shù)（迭代數(shù)）是由指定的容差決定的第14頁，課件共65頁，創(chuàng)作于2023年2月斐波那契（Fibonacci）搜索法斐波那契（Fibonacci）序列基于公式：F0=0,F1=1,Fn=Fn-1+Fn-2即{Fk}={0,1,1,2,3,5,8,13,21,…}設(shè)函數(shù)f(x)在閉區(qū)間[a0,b0]上是單峰函數(shù)，選擇1/2<r0<1，使內(nèi)點c0和d0可以在下一個子區(qū)間上使用，從而只需一次新的函數(shù)求值計算第15頁，課件共65頁，創(chuàng)作于2023年2月比例因子的確定設(shè)f(c0)≤f(d0)，則從右側(cè)壓縮，使用[a,d]，即取a1=a0，b1=d0和d1=c0，則需要再求一個新的點c1為子區(qū)間[a1,b1]選擇r1(1/2<r1<1)，使得a1c1d1b1a0c0d0b01-r0r02r0－11-r0r11-r1第16頁，課件共65頁，創(chuàng)作于2023年2月因為有Fn=Fn-1+Fn-2，F(xiàn)ibonacci搜索從r0=Fn-1/Fn開始，對k=1,2,…,n-3，用rk=Fn-1-k/Fn-k。注意rn-3=F2/F3=1/2，因此這一步無需增加新的點。整個過程總共需要(n-3)+1=n-2步。將第k個子區(qū)間的長度按因子rk=Fn-1-k/Fn-k縮減，得到第(k+1)個子區(qū)間。最后一個子區(qū)間的長度為由Fibonacci數(shù)列，將r0=Fn-1/Fn，n≥4代入r1，得第17頁，課件共65頁，創(chuàng)作于2023年2月如果極小值橫坐標(biāo)的容差為ε，則需要找到最小的n，使得按要求，由如下公式可找到第k個子區(qū)間[ak,bk]的內(nèi)點ck和dk其中的n由上面不等式求得第18頁，課件共65頁，創(chuàng)作于2023年2月區(qū)別常數(shù)的設(shè)置每次迭代需要確定兩個新的內(nèi)點，一個來自前一次的迭代，另一個重新計算。當(dāng)r0=F2/F3=1/2時，兩個內(nèi)點將在區(qū)間中點重合。為區(qū)分它們，引入一個小的區(qū)別常數(shù)e。當(dāng)求ck和dk的時候，rk=1/2+e，則(1-rk)=1/2-e例8.3第19頁，課件共65頁，創(chuàng)作于2023年2月分類搜索法黃金分割搜索法與斐波那契搜索法都可用于f(x)不可微的情況。搜索法存在的問題：函數(shù)在極小值附近可能比較平緩，從而限制了精度，而且速度也較慢對于小的n值，斐波那契搜索法比黃金分割搜索法更為有效；對于大的n值，兩者幾乎相同第20頁，課件共65頁，創(chuàng)作于2023年2月8.1.2利用導(dǎo)數(shù)求極小值設(shè)f(x)在區(qū)間[a,b]上是（下）單峰的，并在x=p處有唯一極小值。并設(shè)f’(x)在(a,b)上所有的點處有定義。令初始點p0在(a,b)內(nèi)。若f’(p0)<0，則極小值點p在p0右側(cè)；若f’(p0)>0，則極小值點p在p0左側(cè)。ap0pby=f(x)ap0pby=f(x)第21頁，課件共65頁，創(chuàng)作于2023年2月1.對極小值分類首先求出三個測試值p0,p1=p0+h,p2=p0+2h,使得f(p0)>f(p1),f(p1)<f(p2)成立若f’(p0)<0,則p0<p，且應(yīng)該選擇步長h>0若f’(p0)>0,則p0>p，且應(yīng)該選擇步長h<0容易找到h，使三點p0,p1=p0+h,p2=p0+2h滿足要求。如有a+1<b，則令h=(+/-)1，否則令h=(+/-)1/2，依此類推。第22頁，課件共65頁，創(chuàng)作于2023年2月尋找過程（設(shè)f’(p0)<(>)0）若滿足f(p0)>f(p1),f(p1)<f(p2)則結(jié)束若f(p0)>f(p1)且f(p1)>f(p2)，則說明p2<(>)p。則需檢測更靠右(左)的點。步長加倍，并重復(fù)檢測過程若f(p0)≤f(p1)，表明h太大，p1已經(jīng)跳過了p。則需檢測更靠近p0的點。步長減半，并重復(fù)檢測過程第23頁，課件共65頁，創(chuàng)作于2023年2月2.求極小值p的二次逼近方法由p0,p1=p0+h,p2=p0+2h，可用二次插值來求p的近似值pmin。基于三點的拉格朗日多項式為其中yi=f(pi),i=0,1,2.Q(x)的導(dǎo)數(shù)為以Q’(p0+hmin)的形式求解Q’(x)=0，得第24頁，課件共65頁，創(chuàng)作于2023年2月將上式中的各項乘以2h2，并合并包含hmin的項，得由上式解得值pmin=p0+hmin比p0更逼近p，因此可用pmin代替p0，并重復(fù)上述計算過程，求出新的h和新的hmin。重復(fù)這一迭代過程，直到得到所需的精度。第25頁，課件共65頁，創(chuàng)作于2023年2月8.1單變量函數(shù)的極小值8.2內(nèi)德-米德方法和鮑威爾方法8.3梯度和牛頓方法目錄第26頁，課件共65頁，創(chuàng)作于2023年2月多元函數(shù)求極值的問題設(shè)函數(shù)f(x1,x2,…,xN)定義在區(qū)域上。如果f(p1,p2,…,pN)≤f(x1,x2,…,xN)對所有的點(x1,x2,…,xN)∈R都成立，則函數(shù)f(x1,x2,…,xN)在點(p1,p2,…,pN)處有局部極小值；如果f(p1,p2,…,pN)≥

f(x1,x2,…,xN)對所有的點(x1,x2,…,xN)∈R都成立，則函數(shù)f(x1,x2,…,xN)在點(p1,p2,…,pN)處有局部極大值。第27頁，課件共65頁，創(chuàng)作于2023年2月二元函數(shù)的極小值問題二元函數(shù)的圖形是一個幾何表面定理8.5（二階偏導(dǎo)數(shù)測試）設(shè)f(x,y)及其一階和二階偏導(dǎo)數(shù)在區(qū)域R上連續(xù)。設(shè)點(p,q)∈R是一個臨界點，即fx(p,q)=0且fy(p,q)=0?？捎酶唠A偏導(dǎo)數(shù)來確定臨界點的屬性。第28頁，課件共65頁，創(chuàng)作于2023年2月若且fxx(p,q)>0，則f(p,q)是f的局部極小值。若且fxx(p,q)<0，則f(p,q)是f的局部極大值。若，則f(x,y)在(p,q)沒有局部極值。若，則結(jié)果不確定。例8.5第29頁，課件共65頁，創(chuàng)作于2023年2月多元函數(shù)的直接搜索法多變量目標(biāo)函數(shù)f(x1,x2,…,xN)的極值直接搜索法對函數(shù)的可微性不作顯性或隱性的假設(shè)對非光滑（不可微）目標(biāo)函數(shù)而言，直接方法特別有用內(nèi)德－米德方法和鮑威爾方法第30頁，課件共65頁，創(chuàng)作于2023年2月單純形方法的基本思想內(nèi)德和米德提出了單純形法，可用于求解多變量函數(shù)的局部極小值從可行域中的一個基本可行解出發(fā)，判斷它是否已是最優(yōu)解，若不是，尋找下一個基本可行解，并使目標(biāo)函數(shù)得到改進，如此迭代下去，直到找出最優(yōu)解或判定問題無解為止。從另一個角度說，就是從可行域的某一個極點出發(fā)，迭代到另一個極點，并使目標(biāo)函數(shù)的值有所改善，直到找出有無最優(yōu)解時為止。第31頁，課件共65頁，創(chuàng)作于2023年2月單純形的概念單純形是指0維中的點，一維中的線段，二維中的三角形，三維中的四面體，n維空間中的有n+1個頂點的多面體。例如在三維空間中的四面體，其頂點分別為(0,0,0)，(1,0,0)，(0,1,0)，(0,0,1)。具有單位截距的單純形的方程是∑xi≤1，并且xi≥0，i=1,2,…,n第32頁，課件共65頁，創(chuàng)作于2023年2月二元函數(shù)的單純形方法在二維平面空間中，單純形就是三角形搜索過程：比較三角形3個頂點處的函數(shù)值，f(x,y)值最大的頂點為最差頂點(W)，用一個新的頂點代替最差頂點，形成新的三角形式繼續(xù)這一過程，生成一系列三角形（它們可能具有不同的形狀），函數(shù)在其頂點處的值越來越小隨著三角形的減小就可以找到極小值點的坐標(biāo)第33頁，課件共65頁，創(chuàng)作于2023年2月單純形的尋找過程初始三角形BGW良邊的中點反射點R開拓點E收縮點C向B方向收縮第34頁，課件共65頁，創(chuàng)作于2023年2月每一步的邏輯判斷①若f(B)<f(R)，則以R代替W否則計算E和f(E)若f(E)<f(B)，則以E代替W否則以R代替W②若f(R)<f(W)，則以R代替W否則計算C1=(M+R)/2和f(C1)計算C2=(W+M)/2和f(C2)取兩者中函數(shù)值較小者為C若f(C)<f(W)，則以C代替W否則計算S=(W+B)/2和f(S)以S代替W以M代替G若f(R)<f(G)，則轉(zhuǎn)①（反射點或開拓點）

否則轉(zhuǎn)②（壓縮點或收縮點）例8.6第35頁，課件共65頁，創(chuàng)作于2023年2月坐標(biāo)輪換法設(shè)X0是函數(shù)z=f(x1,x2,…,xN)的極小值點的初始估計。假設(shè)函數(shù)的偏導(dǎo)數(shù)不可得。一種直觀的方法是通過連續(xù)地沿著每個標(biāo)準(zhǔn)基向量方向找極小值，來求下一個近似的X1。該方法生成一系列點X0=P0,P1,P2,…,PN=X1，沿著函數(shù)f的每個標(biāo)準(zhǔn)基向量是一個單變量函數(shù)，這樣就可以在一個函數(shù)為單峰的區(qū)間上用黃金分割搜索法或斐波那契搜索法來求f的極小值

重復(fù)該迭代過程，生成點序列第36頁，課件共65頁，創(chuàng)作于2023年2月鮑威爾方法通常由于多變量函數(shù)的幾何特點，沿著某個自變量的變化路線找到的極小值有可能并不是函數(shù)的極小值，所以坐標(biāo)輪換法的效率不高但從點X0到點X1這一步正是（原始）鮑威爾方法的第一步第37頁，課件共65頁，創(chuàng)作于2023年2月鮑威爾方法核心在坐標(biāo)輪換法過程中增加兩個步驟（1）在某種程度上，向量PN-P0代表著每次迭代過程移動的平均方向。因此確定點X1為沿向量PN-P0方向的函數(shù)f取得極小值的點。沿著PN-P0方向的f是單變量函數(shù)，因此可用黃金分割搜索法或斐波那契搜索法（2）用向量PN-P0代替下一迭代過程中的某個方向向量，對新的方向向量集開始迭代，并產(chǎn)生點序列第38頁，課件共65頁，創(chuàng)作于2023年2月鮑威爾基本算法要點在每一輪迭代中總有一個始點（第一輪的始點是任取的初始點）和n個線性獨立的搜索方向。從始點出發(fā)順次沿n個方向作一維搜索得一終點，由始點和終點決定了一個新的搜索方向用這個方向替換原來n個方向中的一個，于是形成新的搜索方向組。替換的原則是去掉原方向組的第一個方向而將新方向排在原方向的最后。此外規(guī)定，從這一輪的搜索終點出發(fā)沿新的搜索方向作一維搜索而得到的極小點，作為下一輪迭代的始點。這樣就形成算法的循環(huán)上述基本算法僅具有理論意義第39頁，課件共65頁，創(chuàng)作于2023年2月鮑威爾方法迭代步驟設(shè)X0是函數(shù)z=f(x1,x2,…,xN)的極小值點位置的初始估計，{Ek=[00...01k0...0]:k=1,2,…,N}為標(biāo)準(zhǔn)基向量，且i=0令P0=Xi對k=1,2,…,N，求值γk，使得f(Pk-1+γkUk)極小，并令Pk=Pk-1+γkUk令i=i+1對j=1,2,…,N-1，令Uj=Uj+1。令UN=PN-P0，若||UN||≤ε，則得到解PN，迭代停止求值γ，使得f(P0+γUN)極小。令Xi=P0+γUN重復(fù)第(I)步到第(V)步第40頁，課件共65頁，創(chuàng)作于2023年2月x1x2P0P1X1X2X3鮑威爾基本方法示意圖P2（二維情形）第41頁，課件共65頁，創(chuàng)作于2023年2月鮑威爾方法舉例例8.7：用鮑威爾方法對二元函數(shù)f(x,y)=cos(x)+sin(y)求局部極小值。初始點為X0=(5.5,2)，求迭代前兩步X1和X2。準(zhǔn)確值是P=(π,3π/2)用MATLAB自帶的求局部極小值函數(shù)（線性搜索）fminunc求得的結(jié)果是P=(3.141592403193604,4.712389175014903)第42頁，課件共65頁，創(chuàng)作于2023年2月鮑威爾方法的討論在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點和終點所產(chǎn)生出的搜索方向PN

-P0去替換原來向量組中的第一個向量U1，而不管它的“好壞”。上述步驟中假設(shè)了平均方向是繼續(xù)搜索的良好方向，但實際情況有可能并不是這樣隨著迭代次數(shù)的增加，方向向量集的n個搜索方向有時會趨向于變成線性相關(guān)，它將會丟掉一個或多個方向，從而不能組成n維空間，因此可能出現(xiàn)點集并不收斂于局部極小值點的情況基本鮑威爾算法有待改進第43頁，課件共65頁，創(chuàng)作于2023年2月有關(guān)線性相關(guān)的說明在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點和終點所產(chǎn)生出的搜索方向UN+1=PN

-P0去替換原來向量組中的第一個向量U1，即下一輪的搜索方向組為{U2,U3,…,UN+1}這種自然的替換方式忽略了向量組{U2,U3,…,UN+1}可能出現(xiàn)線性相關(guān)的情況當(dāng)上述向量組線性相關(guān)時，算法產(chǎn)生的點列可能不收斂于問題的解如果拋棄f減小最快的方向向量Ur，結(jié)果將更好。Ur可能是平均向量UN=PN

-P0的主要分量第44頁，課件共65頁，創(chuàng)作于2023年2月改進的鮑威爾方法改進的算法是：首先判斷原向量組是否需要替換。如需要替換，還要進一步判斷原向量組中哪個向量最壞，然后再用新產(chǎn)生的向量替換這個最壞的向量，以保證逐次生成共軛方向。要替換的兩種情況：沿著平均方向f繼續(xù)減小f沿最大下降方向Ur的減小是f整體減小量的主要部分第45頁，課件共65頁，創(chuàng)作于2023年2月改進的鮑威爾方法概要①令P0=Xi②對k=1,2,…,N，求γk的值，使得f(Pk-1+γkUk)最小，并令Pk=Pk-1+γkUk③令r和Ur分別為第②步的所有向量中使得f減小的最大量及其方向④令i=i+1⑤如果f(2PN-P0)≥f(P0)或2(f(P0)-2f(PN)+f(2PN-P0))(f(P0)-f(PN)-r)2≥r(f(P0)-f(2PN-P0))2，則令Xi=PN，并返回第①步；否則，執(zhí)行第⑥步⑥令Ur=PN

-P0（替換）⑦求γ，使得f(P0

+γUr)最小。令Xi

=P0–γUr⑧重復(fù)第①步到第⑦步第46頁，課件共65頁，創(chuàng)作于2023年2月8.1單變量函數(shù)的極小值8.2內(nèi)德-米德方法和鮑威爾方法8.3梯度和牛頓方法目錄第47頁，課件共65頁，創(chuàng)作于2023年2月梯度方法和牛頓方法8.2節(jié)介紹的內(nèi)德－米德方法和鮑威爾方法是針對多元函數(shù)偏導(dǎo)數(shù)不可求的方法，是直接搜索法8.3節(jié)介紹的梯度方法和牛頓方法是針對函數(shù)f(X)的偏導(dǎo)數(shù)可得的求極小值的方法，其中，X=(x1,x2,…,xN)T第48頁，課件共65頁，創(chuàng)作于2023年2月梯度的定義定義8.4設(shè)z=f(X)是X的函數(shù)，對k=1,2,…,N,存在。f的梯度，記為▽f(X)，是向量梯度向量在局部指向f(X)增加得最快的方向。因此-▽f(X)在局部指向下降得最快的方向。例8.8第49頁，課件共65頁，創(chuàng)作于2023年2月

梯度是一個向量。N元函數(shù)f(x1,x2,…xN)在某點x處的梯度為：

梯度的方向與函數(shù)f的等值線的一個法線方向相同，從較低的等值線指向較高的等值線。

梯度的方向就是函數(shù)f的值增加最快的方向，其相反方向就是函數(shù)值降低最快的方向。關(guān)于函數(shù)梯度的說明第50頁，課件共65頁，創(chuàng)作于2023年2月梯度法的定義梯度法又稱最速下降法（steepestdescentmethod）由法國數(shù)學(xué)家Cauchy于1847年首先提出。在每次迭代中，沿最速下降方向（負(fù)梯度方向）進行搜索，每步沿負(fù)梯度方向取最優(yōu)步長，因此這種方法稱為最優(yōu)梯度法。第51頁，課件共65頁，創(chuàng)作于2023年2月梯度方法描述從迭代初始點P0開始，沿著過P0，方向為S0=-▽f(P0)/||-▽f(P0)||的直線搜索，到達點P1.當(dāng)點X滿足約束X=P0+γS0時，在該點取得局部極小值由于偏導(dǎo)數(shù)可得，因此極小化過程可以使用二次或三次近似方法然后計算-▽f(P1)，并沿方向S1=-▽f(P1)/||-▽f(P1)||搜索，到達點P2.當(dāng)X滿足約束X=P1+γS1時，在該點取得局部極小值迭代該計算過程，得到點序列，滿足f(P0)>f(P1)>...>f(Pk)>....如果limk→∞Pk=P，則f(P)是f(X)的一個局部極小值第52頁，課件共65頁，創(chuàng)作于2023年2月梯度法搜索過程示意圖第53頁，課件共65頁，創(chuàng)作于2023年2月梯度方法概要設(shè)Pk已知求梯度向量▽f(Pk)計算搜索方向Sk=-▽f(Pk)/||-▽f(Pk)||在區(qū)間[0,b]上對Φ(γ)=f(Pk+γSk)進行單參數(shù)極小化，b為一個較大值。這一過程將產(chǎn)生值γ=hmin，它是Φ(γ)的一個局部極小值點。關(guān)系式Φ(hmin)=f(Pk+hminSk)表明，它是f(X)沿搜索線X=Pk+hminSk的一個極小值構(gòu)造下一個點Pk+1=Pk+hminSk進行極小化過程的終止判斷，若函數(shù)值滿足|f(Pk+1)-f(Pk)|<ε或兩點距離滿足||Pk+1-Pk||<ε，則迭代終止，否則轉(zhuǎn)第①步第54頁，課件共65頁，創(chuàng)作于2023年2月例8.9用梯度法求函數(shù)的P1和P2。初始點采用P0=(-3,-2)P0P1P2P第55頁，課件共65頁，創(chuàng)作于2023年2月梯度法小結(jié)梯度法是從梯度的幾何含義自然延伸得到的，所以幾何上比較直觀梯度法的基本思想是從當(dāng)前點xk出發(fā)尋找使得目標(biāo)函數(shù)下降最快的方向，即負(fù)梯度方向。優(yōu)點：迭代點列總是收斂的，而且計算過程簡單第56頁，課件共65頁，創(chuàng)作于2023年2月梯度法的缺點梯度法相鄰的兩個搜索方向是相互垂直的，迭代點越靠近極小值點則函數(shù)下降的速度越慢對于N變量函數(shù)f(x1,x2,…,xN)而言，收斂到一個極小值的速度可能很慢一般地，函數(shù)f的極小值在幾何上使得值hmin很小，這導(dǎo)致需要大量的極小化過程梯度法一般用于最優(yōu)化過程開始的幾步搜索第57頁，課件共65頁，創(chuàng)作于2023年2月例求目標(biāo)函數(shù)的極小點。第58頁，課件共65頁，創(chuàng)作于2023年2月牛頓方法原理由單變量函數(shù)的二次逼近求極小值的方法推廣而得，以有N個獨立變量的二次多項式的極小值來近似代替目標(biāo)函數(shù)f的極小值對有N個獨立變量的函數(shù)z=f(x1,x2,…,xN)而言，從初始點P0開始，遞歸構(gòu)造出一個含N個變量的二次多項式序列如果目標(biāo)函數(shù)是良態(tài)的，并且初始點在實際極小值附近，則該二次多項式的極小值序列將收斂到目標(biāo)函數(shù)f的極小值第59頁，課件共65頁，創(chuàng)作于2023年2月黑森（Hessian）矩陣定義8