004第四章無約束優(yōu)化計算方法ppt課件

1、本次課的主要內(nèi)容：本次課的主要內(nèi)容：一維尋優(yōu)最優(yōu)化的概念極值存在區(qū)間的確定壓縮區(qū)間計算原理黃金分割法的由來及其計算步驟0.618法的程序框圖第四章第四章 無約束優(yōu)化計算方法無約束優(yōu)化計算方法4.1 引言引言一、無約束優(yōu)化問題的一般形式: 求其最優(yōu)解 和 的方法,稱為無約束優(yōu)化計算方法分 類非梯度算法隨機搜索法、坐標(biāo)輪換法、Powell法、單純形法等梯度法、共軛梯度法、牛頓法、修正牛頓法、變尺度法等梯度算法)(minxfnRx)(xfx二、無約束優(yōu)化問題的一般步驟:1.從某一初始點 開始迭代計算；2.各種方法在 領(lǐng)域內(nèi)產(chǎn)生新點 ；3.檢驗點 是否滿足最優(yōu)性條件。函數(shù)構(gòu)造不同迭代終止準(zhǔn)則)0(x)

2、1( kx)(kx)1( kx4.2 單變量優(yōu)化計算方法單變量優(yōu)化計算方法即，求優(yōu)化步長因子 使 沿給定方向達到極小值。 則稱為一維搜索的最優(yōu)步長因子。求 值的方法稱為一維搜索優(yōu)化計算方法或單變量優(yōu)化計算方法。)(min)()()()1(kkkffsxx)(k)()()(kkfsx)(k)(k一、概念一維搜索示意圖)(xf)()(kf x)(ks)(min)()(kkfsx)(kx)(kks1x2x)(min)()()()1(kkkffsxx 當(dāng)目標(biāo)函數(shù)可以精確求導(dǎo)時,其最優(yōu)步長因子可以用解析法求得：)()()()()()()()(kkTkkTkkfsxHssx一維搜索方法包括: 分數(shù)法(Fi

3、bonacci法)、黃金分割法0.618法）、 牛頓法、二次插值法和三次插值法等。一維搜索最優(yōu)化方法步驟：1、在 方向上確定函數(shù)值最小點所在區(qū)間2、求出該區(qū)間內(nèi)的最優(yōu)步長因子)(ksk二、分類及一般步驟4.2.1 搜索區(qū)間的確定搜索區(qū)間的確定 所謂搜索區(qū)間就是沿所謂搜索區(qū)間就是沿 方向找出一個單峰區(qū)間方向找出一個單峰區(qū)間 ,即在該區(qū)間內(nèi)的函數(shù)變化只有一個峰值即在該區(qū)間內(nèi)的函數(shù)變化只有一個峰值,如下圖如下圖: 性質(zhì)：若在性質(zhì)：若在 區(qū)間內(nèi)另取一點區(qū)間內(nèi)另取一點 ，即，即 或或 )(ks31，2321321)()()(321fff31，單峰函數(shù)123)(f)()()(1kffx)(2f)(3f)(

4、f)(f 將初始迭代 和 定為搜索區(qū)間的左端點 ；用一試探步長 沿 方向移動一步 并計算其點的函數(shù)值 ，假設(shè) 則繼續(xù)增大步長 ，再計算其函數(shù)值 ，與前一點的函數(shù)值進行比較，直到相臨兩點的函數(shù)值滿足 時為止，即形成了高-低-高的一維函數(shù)曲線；最后一點就定為搜索區(qū)間的右端點 。 中間點 。)(f)()()(1kffx)(1kx2t)(3it)(21it 正向搜索)(kx)()(kf x0ts012tt)()()(2)(2kktftfsx)()(21tff002tt )(2tf)()(1iitftfit1311t112it321)()()(321fff前進極小點在右方 假設(shè) ，則步長值 改為 ，即取

5、步長 ，繼續(xù)計算，直到 為止，也可得到高-低-高的一維函數(shù)曲線。將左端點值定為終止點 ，而右端點定為起始點 ，中間點定為 。)()(21tff0t0t012tt)()(1iitftfit13)(f)(3it)(21it2t1 反向搜索1112it321)()()(321fff后退進退法極小點在左方2t)(f1t2t3t11t22t33t外推法確定搜索區(qū)間)()(23tftf11t22t33t)()(23tftf向右移動求新點想一想：想一想： 該方法的程序框圖該方法的程序框圖高-低-高32312ttttt，新點為為，為即以4.2.2 黃金分割法黃金分割法0.618法）法） 黃金分割法適用于黃金分

6、割法適用于 區(qū)間上的任何單峰函數(shù)求區(qū)間上的任何單峰函數(shù)求極小值問題。對函數(shù)除要求單峰外不作其它要求，甚至極小值問題。對函數(shù)除要求單峰外不作其它要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。可以不連續(xù)。因此，這種方法的適應(yīng)面相當(dāng)廣。一、區(qū)間壓縮原理一、區(qū)間壓縮原理 目標(biāo)函數(shù)目標(biāo)函數(shù) ， 所在搜索區(qū)所在搜索區(qū)間第一次搜索時定為間第一次搜索時定為 ，求給定方向，求給定方向 上上的最優(yōu)步長因子。的最優(yōu)步長因子。 首先在首先在 區(qū)間內(nèi)取兩個區(qū)間內(nèi)取兩個 值值 , , 且且滿足滿足 并按一個公比并按一個公比 (0 eps & kfu a=l; %改變區(qū)間左端點 l=u; u=a+0.382*

7、(b-a); else b=u; %改變區(qū)間右端點 u=l; l=a+0.382*(b-a); end k=k+1; tol=abs(b-a);endif k=100000 disp(找不到最小值); x=NaN; minf=NaN; return;endx=(a+b)/2;minf=subs(f,findsym(f),x);format short;書本的87頁，習(xí)題4-1一、基本思想： 利用三點的函數(shù)值來構(gòu)造一個二次插值多項式，以近似的表達原目標(biāo)函數(shù)，并求這個的多項式的極值點作為原函數(shù)極小點的近似值。二、原理： 在一維搜索中， 與 均為已知，因此目標(biāo)函數(shù)是 的一元函數(shù) 現(xiàn)在構(gòu)造一個二次多項

8、式 逼近目標(biāo)函數(shù)4.2.2 二次插值法近似拋物線法）二次插值法近似拋物線法）)()()()()()1(fffkkksxx2)(cbap)(kx)(ks二次插值法原理圖)(f12p431f2f3f)(f)(p)()()()()()1(fffkkksxx2)(cbap02)(cbddpcbp2，縮短搜索區(qū)間的關(guān)系，分析舍去區(qū)間和比較)()(24ff242fff13思索： 壓縮搜索區(qū)間時，有幾種情況，書上的程序框圖中是怎樣解決這個問題的？二次插值程序框圖課下作業(yè)課下作業(yè) 用黃金分割法求函數(shù) 的極小點，給定 要求： 1. 手工按黃金分割法計算 2. 至少用一種計算機語言以黃金分割法編程計算243)(3

9、xxxf2 . 0100，hx將一個多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列沿將一個多維的無約束最優(yōu)化問題轉(zhuǎn)化為一系列沿坐標(biāo)軸方向的一維易優(yōu)化問題的求解，因此也稱坐標(biāo)軸方向的一維易優(yōu)化問題的求解，因此也稱降維法。即，將一個降維法。即，將一個n維優(yōu)化問題轉(zhuǎn)化為依次沿維優(yōu)化問題轉(zhuǎn)化為依次沿n個坐標(biāo)方向反復(fù)進行一維搜索問題。每次一維搜個坐標(biāo)方向反復(fù)進行一維搜索問題。每次一維搜索時，只允許索時，只允許n個變量的一個改動，其他個變量的一個改動，其他(n-1)個個變量固定不變。變量固定不變?；驹砘驹?對于對于n個變量的函數(shù)，若在第個變量的函數(shù)，若在第k輪沿著第輪沿著第i個坐標(biāo)個坐標(biāo)方向進行搜索，其迭代公

10、式為：方向進行搜索，其迭代公式為：kikikikisxx12求最優(yōu)搜索步長求最優(yōu)搜索步長ki計算步驟：計算步驟：3本輪所有方向搜索完畢，判斷迭代終止條件：本輪所有方向搜索完畢，判斷迭代終止條件：kkn0 xxknxx 4滿足上式：滿足上式：否則，進行下一輪迭代。否則，進行下一輪迭代。搜索方向與步長的確定（1搜索方向的確定對于第k輪第i次的計算1kkkkiiiixxa d第k輪第I次的迭代方向，它輪流取n維坐標(biāo)的單位向量。0.1.0kiide 搜索步長的確定關(guān)于 值通常有以下幾種取法（1加速步長法（2最優(yōu)步長法 最優(yōu)步長法就是利用一維最優(yōu)搜索方法來完成每一次迭代，即此時可以采用0.618方法或二

11、次插值方法來計算 的值。)( ki圖4-12 加速步長法的搜索路線圖4-14 最優(yōu)步長法的搜索路線坐標(biāo)輪換法存在的問題圖4-14 坐標(biāo)輪換法在各種不同情況下的效能（a搜索有效；（b搜索低效；（c搜索無效 例例 求目標(biāo)函數(shù)求目標(biāo)函數(shù) 的極小點。的極小點。 取初始點取初始點02,2Tx2212( )25fxxx 220122010101010001sxx解：第一輪迭代：解：第一輪迭代：220101225)2()(xf20)(0101f 求最優(yōu)搜索步長求最優(yōu)搜索步長2001x020202020102201020sxx20202)2(25)(xf20)(0202f 求最優(yōu)搜索步長求最優(yōu)搜索步長0002

12、x沿著第二個坐標(biāo)方向搜索：沿著第二個坐標(biāo)方向搜索：00100010111111011sxx判斷終止條件，不滿足，進行第二輪迭代：判斷終止條件，不滿足，進行第二輪迭代：21111)()(xf00)(1111f 求最優(yōu)搜索步長求最優(yōu)搜索步長0011x12121212111201000sxx21212)(25)(xf00)(1212f 求最優(yōu)搜索步長求最優(yōu)搜索步長0012x沿著第二個坐標(biāo)方向搜索：沿著第二個坐標(biāo)方向搜索：01012xx00knxx例例3: 用坐標(biāo)輪換法求下面問題的最優(yōu)解，給定初用坐標(biāo)輪換法求下面問題的最優(yōu)解，給定初始點始點X0=0 0T,精度要求精度要求=0.160410)(2121

13、2221xxxxxxxf0010011)1(11)1(0)1(1)0()1(1SXXXX6010)(min121)1(1XF解解: 第一輪迭代第一輪迭代求最優(yōu)步長，即極小化：求最優(yōu)步長，即極小化： 05)( , 50102)()1(1)1(111)1(1XdXdF22)1(22)1(1)1(251005SXX以以X1(1)為新起點，沿為新起點，沿e2方向進行一維搜索：方向進行一維搜索： 5 . 45)( , 5 . 4092)()1(2)1(222)1(2XdXdF仍以最優(yōu)步長原則確定仍以最優(yōu)步長原則確定2： 繼續(xù)進行第二輪迭代計算，等等。繼續(xù)進行第二輪迭代計算，等等。從坐標(biāo)輪換法的迭代過程可以看出其搜索路線較長，計算從坐標(biāo)輪換法的迭代過程可以看出其搜索路線較長，計算效率低。效率低。因此，一般認為此法僅適宜因此，一般認為此法僅適宜n n1010的小型優(yōu)化問題的求解。的小型優(yōu)化問題的求解。另外，此法的效能在很大程度上取決于目標(biāo)函數(shù)的性質(zhì)。另外，此法的效能在很大程度上取決于目標(biāo)函數(shù)的性質(zhì)。7 . 65 . 4522)1 (0)1 (2XX按終止條件檢驗：按終止條件檢驗：（1