無(wú)約束優(yōu)化計(jì)算方法ppt課件

1、本次課的主要內(nèi)容：本次課的主要內(nèi)容：一維尋優(yōu)最優(yōu)化的概念極值存在區(qū)間確實(shí)定緊縮區(qū)間計(jì)算原理黃金分割法的由來(lái)及其計(jì)算步驟0.618法的程序框圖第四章第四章 無(wú)約束優(yōu)化計(jì)算方法無(wú)約束優(yōu)化計(jì)算方法4.1 引言引言一、無(wú)約束優(yōu)化問(wèn)題的普通方式: 求其最優(yōu)解 和 的方法,稱為無(wú)約束優(yōu)化計(jì)算方法分 類非梯度算法隨機(jī)搜索法、坐標(biāo)輪換法、Powell法、單純形法等梯度法、共軛梯度法、牛頓法、修正牛頓法、變尺度法等梯度算法)(minxfnRx)(xfx二、無(wú)約束優(yōu)化問(wèn)題的普通步驟:1.從某一初始點(diǎn) 開(kāi)場(chǎng)迭代計(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)目的函數(shù)可以準(zhǔn)確求導(dǎo)時(shí),其最優(yōu)步長(zhǎng)因子可以用解析法求得：)()()()()()()()(kkTkkTkkfsxHssx一維搜索方法包括: 分?jǐn)?shù)法(

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

4、f)(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í)為止，即構(gòu)成了高-低-高的一維函數(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ù)求極小值問(wèn)題。對(duì)函數(shù)除要求單峰外不作其它要求，甚至極小值問(wèn)題。對(duì)函數(shù)除要求單峰外不作其它要求，甚至可以不延續(xù)。因此，這種方法的順應(yīng)面相當(dāng)廣?？梢圆谎永m(xù)。因此，這種方法的順應(yīng)面相當(dāng)廣。一、區(qū)間緊縮原理一、區(qū)間緊縮原理 目的函數(shù)目的函數(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; %改動(dòng)區(qū)間左端點(diǎn) l=u; u=a+0.3

7、82*(b-a); else b=u; %改動(dòng)區(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頁(yè)，習(xí)題4-1一、根本思想： 利用三點(diǎn)的函數(shù)值來(lái)構(gòu)造一個(gè)二次插值多項(xiàng)式，以近似的表達(dá)原目的函數(shù)，并求這個(gè)的多項(xiàng)式的極值點(diǎn)作為原函數(shù)極小點(diǎn)的近似值。二、原理： 在一維搜索中， 與 均為知，因此目的函數(shù)是 的一元函數(shù) 如今構(gòu)造一個(gè)二次

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

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

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

11、二次插值方法來(lái)計(jì)算 的值。)( ki圖4-12 加速步長(zhǎng)法的搜索道路圖4-14 最優(yōu)步長(zhǎng)法的搜索道路坐標(biāo)輪換法存在的問(wèn)題圖4-14 坐標(biāo)輪換法在各種不同情況下的效能a搜索有效；b搜索低效；c搜索無(wú)效 例例 求目的函數(shù)求目的函數(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)0002x沿

12、著第二個(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)輪換法求下面問(wèn)題的最優(yōu)解，給定初用坐標(biāo)輪換法求下面問(wèn)題的最優(yōu)解，給定初始點(diǎn)始點(diǎn)X0=0 0T,精度要求精度要求=0.160410)(212122

13、21xxxxxxxf0010011)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)輪換法的迭代過(guò)程可以看出其搜索道路較長(zhǎng)，計(jì)算從坐標(biāo)輪換法的迭代過(guò)程可以看出其搜索道路較長(zhǎng)，計(jì)算效率低。效率低。因此，普通以為此法僅適宜因此，普通以為此法僅適宜n n1010的小型優(yōu)化問(wèn)題的求解。的小型優(yōu)化問(wèn)題的求解。另外，此法的效能在很大程度上取決于目的函數(shù)的性質(zhì)。另外，此法的效能在很大程度上取決于目的函數(shù)的性質(zhì)。7 . 65 . 4522)1 (0)1 (2XX按終止條件檢驗(yàn)：按終止條件檢驗(yàn)：1計(jì)