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

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

2、1( kx)(kx)1( kx4.2 單變量?jī)?yōu)化計(jì)算方法單變量?jī)?yōu)化計(jì)算方法即，求優(yōu)化步長(zhǎng)因子 使 沿給定方向達(dá)到極小值。 則稱為一維搜索的最優(yōu)步長(zhǎng)因子。求 值的方法稱為一維搜索優(yōu)化計(jì)算方法或單變量?jī)?yōu)化計(jì)算方法。)(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)時(shí),其最優(yōu)步長(zhǎng)因子可以用解析法求得：)()()()()()()()(kkTkkTkkfsxHssx一維搜索方法包括: 分?jǐn)?shù)法(Fi

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

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

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

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

7、(b-a); else b=u; %改變區(qū)間右端點(diǎn) 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一、基本思想： 利用三點(diǎn)的函數(shù)值來構(gòu)造一個(gè)二次插值多項(xiàng)式，以近似的表達(dá)原目標(biāo)函數(shù)，并求這個(gè)的多項(xiàng)式的極值點(diǎn)作為原函數(shù)極小點(diǎn)的近似值。二、原理： 在一維搜索中， 與 均為已知，因此目標(biāo)函數(shù)是 的一元函數(shù) 現(xiàn)在構(gòu)造一個(gè)二次多項(xiàng)

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ū)間時(shí)，有幾種情況，書上的程序框圖中是怎樣解決這個(gè)問題的？二次插值程序框圖課下作業(yè)課下作業(yè) 用黃金分割法求函數(shù) 的極小點(diǎn)，給定 要求： 1. 手工按黃金分割法計(jì)算 2. 至少用一種計(jì)算機(jī)語言以黃金分割法編程計(jì)算243)(3

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

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

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

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

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