人教版六年級(jí)上冊(cè)語文主題學(xué)習(xí)《回顧·拓展四》課件模板

5.優(yōu)化設(shè)計(jì)5.3

一維搜索的優(yōu)化方法西南科技大學(xué)網(wǎng)絡(luò)教育系列課程5.優(yōu)化設(shè)計(jì)5.3一維搜索的優(yōu)化方法西南科技大學(xué)網(wǎng)15.3.1確定搜索區(qū)間的方法—進(jìn)退法實(shí)際問題數(shù)學(xué)模型數(shù)值計(jì)算方法程序設(shè)計(jì)上機(jī)計(jì)算求出結(jié)果

數(shù)值解法：利用計(jì)算機(jī)通過反復(fù)迭代計(jì)算，求得實(shí)際問題的近似值。5.3.1確定搜索區(qū)間的方法—進(jìn)退法實(shí)際問題數(shù)學(xué)模型數(shù)值25.3.1確定搜索區(qū)間的方法—進(jìn)退法

下降迭代算法中在搜索方向S(k)上尋求最優(yōu)步長(zhǎng)ak時(shí)通常采用一維搜索法。

一維搜索法就是一元函數(shù)極小化的數(shù)值迭代算法，其求解過程稱一維搜索。一維搜索問題指目標(biāo)函數(shù)為單變量的非線性規(guī)劃問題。又稱線性搜索問題。其模型為：t為實(shí)數(shù)或一般一維搜索問題有效一維搜索問題5.3.1確定搜索區(qū)間的方法—進(jìn)退法35.3.1確定搜索區(qū)間的方法—進(jìn)退法

一維搜索問題的算法分類：

1）精確一維搜索（最優(yōu)一維搜索）

2）非精確一維搜索（可接受一維搜索）1、進(jìn)退法確定搜索區(qū)間的方法在函數(shù)的任一單谷區(qū)間上必存在一個(gè)極小點(diǎn)，而且在極小點(diǎn)的左側(cè)，函數(shù)呈下降趨勢(shì)，在極小點(diǎn)的右側(cè)函數(shù)呈上升趨勢(shì)。若已知方向S(k)上的三點(diǎn)x1＜x2＜x3及其函數(shù)值f(x1)、f(x2)和f(x3)，便可通過比較三個(gè)函數(shù)值的大小估計(jì)出極小點(diǎn)所在的位置，如圖5.11所示。5.3.1確定搜索區(qū)間的方法—進(jìn)退法一維搜索問題45.3.1確定搜索區(qū)間的方法—進(jìn)退法圖5.11極小點(diǎn)的估計(jì)5.3.1確定搜索區(qū)間的方法—進(jìn)退法圖5.11極小點(diǎn)的55.3.1確定搜索區(qū)間的方法—進(jìn)退法2、進(jìn)退法的定義在某一方向上按一定方式逐次產(chǎn)生一些探測(cè)點(diǎn)，并比較這些探測(cè)點(diǎn)上函數(shù)值的大小，就可以找出函數(shù)值呈“大-小-大”變化的三個(gè)相鄰點(diǎn)，其中兩端點(diǎn)所確定的閉區(qū)間必定包含著極小點(diǎn)，這樣的區(qū)間稱為初始區(qū)間，記作[a,b]。這種尋找初始區(qū)間的方法稱為進(jìn)退法。

α

x*

x1x2

b5.3.1確定搜索區(qū)間的方法—進(jìn)退法2、進(jìn)退法的定義6若對(duì)任意x1,x2,α≤x1<x2

≤b滿足：

1)若x1

≤x*，則φ(x1)>φ(x*);

2)若x2

≥x*，則φ(x*)<φ(x2).則稱φ(x)在[α,b]

上強(qiáng)單峰。若只有當(dāng)x1≠x*，x2≠x*時(shí)，上述1),2)式才成立，則稱φ(x)在[α,b]

上單峰。

αx1x*x2

b

強(qiáng)單峰

α

x*b

單峰若對(duì)任意x1,x2,α≤x1<x27其具體的程序見右圖：其具體的程序見右圖：85.3.1確定搜索區(qū)間的方法—進(jìn)退法

一維搜索法：就是一元函數(shù)極小化的數(shù)值迭代算法，其求解過程稱一維搜索。一維搜索法是構(gòu)成非線性優(yōu)化方法的基本算法，因?yàn)槎嘣瘮?shù)的迭代解法可歸結(jié)為在一系列逐步產(chǎn)生的下降方向上的一維搜索。一維搜索法一般分兩步：1）確定初始搜索區(qū)間，該區(qū)間應(yīng)是包括一維函數(shù)極小點(diǎn)在內(nèi)的單峰區(qū)間；2）在搜索區(qū)間內(nèi)尋找極小點(diǎn)。5.3.1確定搜索區(qū)間的方法—進(jìn)退法一維91、定義

黃金分割法：又稱0.618法，是一種通過不斷縮小區(qū)間得到極小點(diǎn)的一維搜索算法。問題：凸函數(shù)是不是單谷函數(shù)？嚴(yán)格凸函數(shù)是不是單谷函數(shù)？單谷函數(shù)是不是凸函數(shù)？單谷函數(shù)5.3.2

黃金分割法1、定義問題：凸函數(shù)是不是單谷函數(shù)？嚴(yán)格凸函數(shù)是不是單谷函10搜索法求解：或2、基本過程：

給出[a,b],使得x*在[a,b]中。[a,b]稱為搜索區(qū)間。

迭代縮短[a,b]的長(zhǎng)度。

當(dāng)[a,b]的長(zhǎng)度小于某個(gè)預(yù)設(shè)的值，或者導(dǎo)數(shù)的絕對(duì)值小于某個(gè)預(yù)設(shè)的正數(shù)，則迭代終止。搜索法求解：或2、基本過程：11假定：已經(jīng)確定了單谷區(qū)間[a,b]x1x2ababx1x2新搜索區(qū)間為[a,x2]新搜索區(qū)間為[x1,b]假定：已經(jīng)確定了單谷區(qū)間[a,b]x1x2ababx1x2新12區(qū)間縮小比例的確定：區(qū)間縮短比例為(x2-a)/(b-a)縮短比例為(b-x1)/(b-a)縮短比例滿足：

每次插入搜索點(diǎn)使得兩個(gè)區(qū)間[a,x2]和[x1,b]相等；

每次迭代都以相等的比例縮小區(qū)間。0.618法x1x2ababx1x2區(qū)間縮小比例的確定：區(qū)間縮短比例為(x2-a)/(b-a)縮13確定[a,b],計(jì)算探索點(diǎn)x1=a+0.382(b-a)x2=a+0.618(b-a)0.618法解題步驟：是否是停止，輸出x1否以[a,x2]為新的搜索區(qū)間是停止，輸出x2否以[x1,b]為新的搜索區(qū)間確定[a,b],計(jì)算探索點(diǎn)0.618法解題步驟：是否是停止，145.3.2黃金分割法例1：用黃金分割法求的初始區(qū)間，設(shè)初始點(diǎn)，初始步長(zhǎng)。解：用進(jìn)退法確定初始區(qū)間：

比較，因作前進(jìn)運(yùn)算：5.3.2黃金分割法例1：用黃金分割法求155.3.2黃金分割法因，再作前進(jìn)運(yùn)算：故初始搜索區(qū)間為：5.3.2黃金分割法16例2：解：x1x230x1)、第一輪：x1=1.146,x2=1.854x2-0>0.5例2：解：x1x230x1)、第一輪：x2-0>0.5171.4160xx2x12)、第二輪：x2=1.146,x1=0.708x2-0=1.146>0.53)、第三輪：x1=0.438,x2=0.708b-x1=1.146-0.438>0.51.8540xx2x11.4160xx2x12)、第二輪：x2-0=1.146>0184)、第四輪：x2=0.876,x1=0.708b-x1=1.146-0.708<0.5輸出：x*=x2=0.876為最優(yōu)解，最優(yōu)值為-0.079801.416xx1x24)、第四輪：b-x1=1.146-0.708<0.5輸出：195.3.3

Newton法Newton法基本思想：用探索點(diǎn)xk處的二階Taylor展開式近似代替目標(biāo)函數(shù)，以展開式的最小點(diǎn)為新的探索點(diǎn)。5.3.3Newton法Newton法基本思想：用探索點(diǎn)20解題步驟：給定初始點(diǎn)x1和精度是是停止，輸出x1是否停止，解題失敗否停止，輸出x2否解題步驟：給定初始點(diǎn)x1和精度是是停止，輸出x1是否停止，解21

5.3.4

二次插值法5.3.4二次插值法22

1、定義：

二次插值法又稱拋物線法，它是以目標(biāo)函數(shù)的二次插值函數(shù)的極小點(diǎn)作為新的中間插入點(diǎn)，進(jìn)行區(qū)間縮小的一維搜索算法。

用f(x)在2或3個(gè)點(diǎn)的函數(shù)值或?qū)?shù)值，構(gòu)造2次或3次多項(xiàng)式作為f(x)的近似值，以這多項(xiàng)式的極小點(diǎn)為新的迭代點(diǎn)。

3點(diǎn)2次，2點(diǎn)2次，4點(diǎn)3次，3點(diǎn)3次，2點(diǎn)3次等以3點(diǎn)2次為例：取x1，x

2，x3，求出f(x1)，f(x2)，f(x3)

5.3.4

二次插值法1、定義：5.3.4二次插值法235.3.4二次插值法設(shè)二次插值多項(xiàng)式：f(x)

=a0+a1x+a2x2f(x1)=

a0+a1x1+a2x12f(x2

)=a0+a1x2+a2x22

f(x3)

=

a0

+a1x3+a2x32解得a1a25.3.4二次插值法設(shè)二次插值多項(xiàng)式：f(x)245.3.4二次插值法5.3.4二次插值法255.3.4二次插值法f2<fp的新搜索區(qū)間f2>fp的新搜索區(qū)間5.3.4二次插值法f2<fp的新搜索區(qū)間f2>fp的新搜265.3.4二次插值法2、特點(diǎn)：1）二次插值法的中間插入點(diǎn)包含了函數(shù)在三個(gè)點(diǎn)上的函數(shù)值信息，因此這樣的插入點(diǎn)比較接近函數(shù)的極小值。2）二次插值法以兩個(gè)中間插入點(diǎn)的距離充分小作為收斂準(zhǔn)則，即當(dāng)成立時(shí)，把

作為此次一維搜索的極小點(diǎn)。二次插值法的計(jì)算程序如下圖:5.3.4二次插值法2、特點(diǎn)：27人教版六年級(jí)上冊(cè)語文主題學(xué)習(xí)《回顧·拓展四》課件模板285.3.4二次插值法

例2.用二次插值法求函數(shù)的極小點(diǎn)，給定解：1）確定初始區(qū)間：由于，應(yīng)加大步長(zhǎng)繼續(xù)向前探測(cè)，

由于，可知初始區(qū)間已經(jīng)找到，即5.3.4二次插值法例2.用二次插值法求函數(shù)295.3.4二次插值法2）用二次插值法逼近極小點(diǎn)記此初始區(qū)間內(nèi)的相鄰三點(diǎn)及其函數(shù)值依次為：將它們代入式，得插值函數(shù)的極小點(diǎn)，即新的插入點(diǎn)及其函數(shù)值：

由于，故新區(qū)間5.3.4二次插值法2）用二次插值法逼近極小點(diǎn)305.3.4二次插值法由于，故應(yīng)繼續(xù)作第二次插值計(jì)算。在新的區(qū)間內(nèi)，相鄰三點(diǎn)及其函數(shù)值依次為：將它們代入式，得由于，新區(qū)間5.3.4二次插值法由于，315.3.4二次插值法由于，故一維搜索到此結(jié)束，極小點(diǎn)和極小值為：5.3.4二次插值法由于，325.優(yōu)化設(shè)計(jì)5.4

多維優(yōu)化方法西南科技大學(xué)網(wǎng)絡(luò)教育系列課程5.優(yōu)化設(shè)計(jì)5.4多維優(yōu)化方法西南科技大學(xué)網(wǎng)絡(luò)教335.4

多維優(yōu)化方法多維優(yōu)化方法是進(jìn)行多變量?jī)?yōu)化設(shè)計(jì)的數(shù)值迭代法。它包括了無約束優(yōu)化方法和約束優(yōu)化方法兩種。1、無約束優(yōu)化問題的一般形式：求解設(shè)計(jì)變量：X=[x1,x2,…,xn]T,X∈Rn滿足目標(biāo)函數(shù)minf(X)的無約束最優(yōu)化解X*和最優(yōu)化函數(shù)minf(X

*)。2、無約束優(yōu)化的分類根據(jù)搜索方向的不同構(gòu)成形式，可分類以下兩類：5.4多維優(yōu)化方法多維優(yōu)化方法是進(jìn)行多345.4

多維優(yōu)化方法1）導(dǎo)數(shù)法：利用目標(biāo)函數(shù)的一階和二階導(dǎo)數(shù)信息構(gòu)成搜索方向的算法，稱為導(dǎo)數(shù)法，如梯度法和共軛梯度法。

注：其收斂性和收斂速度都是比較好的。

2）模式法：通過幾個(gè)已知點(diǎn)上函數(shù)值的比較構(gòu)造搜索方向的算法。如鮑威爾法。對(duì)于較復(fù)雜的目標(biāo)函數(shù)優(yōu)化是有利的。3、約束優(yōu)化方法

minf(X)s.t.gu(X)≤0(u=1,2,…,m)

hv(X)=0(v=1,2,…,p<n)5.4多維優(yōu)化方法1）導(dǎo)數(shù)法：利用目標(biāo)函355.4

多維優(yōu)化方法根據(jù)處理?xiàng)l件的不同，約束優(yōu)化方法分為直接法和間接法兩類。直接法是指在迭代過程中逐點(diǎn)考察約束，并使迭代點(diǎn)始終局限于可行域之內(nèi)的算法。如可行方向法和復(fù)合法。間接法是指把約束條件引入目標(biāo)函，將約束優(yōu)化問題轉(zhuǎn)化為無約束問題求解的算法。如懲罰函數(shù)法。5.4多維優(yōu)化方法根據(jù)處理?xiàng)l件的不同，約365.4.1梯度法1定義什么方向是函數(shù)下降最快的方向呢？答案是負(fù)梯度方向。

梯度法又稱最速下降法，是無約束優(yōu)化方法中間接法的一種。其基本原理：是將一個(gè)多維無約束優(yōu)化問題轉(zhuǎn)化為一系列沿目標(biāo)函數(shù)負(fù)梯度方向進(jìn)行一維搜索尋優(yōu)的一種方法，即是在每一迭代點(diǎn)，選取搜索方向?yàn)樨?fù)梯度方向：

5.4.1梯度法1定義375.4.1梯度法再沿進(jìn)行一維搜索，以確定步長(zhǎng)因子，找到新的設(shè)計(jì)點(diǎn)按照上述迭代公式進(jìn)行若干次一維搜索，每次迭代的初始點(diǎn)取上次迭代的終點(diǎn)，即可使迭代點(diǎn)逐漸逼近目標(biāo)函數(shù)的極小點(diǎn)。5.4.1梯度法再沿進(jìn)行一維38梯度法程序框圖梯度法程序框圖395.4.1梯度法2梯度法的特點(diǎn)

1）梯度法理論明確，程序簡(jiǎn)單，計(jì)算量和存儲(chǔ)量較少，對(duì)初始點(diǎn)的要求不嚴(yán)格。2）負(fù)梯度方向不是理想的搜索方向，梯度法也不是一種理想的方法，梯度法的收斂速度并不快。這是因?yàn)樽钏傧陆捣较騼H僅是指某點(diǎn)的一個(gè)局部性質(zhì)，一旦離開這點(diǎn)，就不能保證仍是最速下降方向了。

3）梯度法的迭代全過程的搜索路線呈鋸齒狀。由于梯度法的相鄰兩次搜索方向的正交性決定的，如圖5.14所示，故前幾次迭代函數(shù)值下降較快，但以后的迭代下降越來越慢。5.4.1梯度法2梯度法的特點(diǎn)405.4.1梯度法圖5.14二維目標(biāo)函數(shù)的梯度法搜索過程5.4.1梯度法圖5.14二維目標(biāo)函數(shù)的梯度法搜索過程415.4.1梯度法所以，梯度法常與其它方法聯(lián)合使用，即在迭代的第一步或前幾步使用，當(dāng)接近極小點(diǎn)時(shí)，改為用其它算法，以此加快收斂速度。特點(diǎn)：全局收斂，線性收斂，易產(chǎn)生扭擺現(xiàn)象而造成早停。5.4.1梯度法所以，梯度法常與其它方法聯(lián)425.4.1梯度法例1用梯度法求下列無約束優(yōu)化問題，已知函數(shù)X(0)=[1

1]T，ε＝0.1。min

解：1）第一次迭代求

令則

5.4.1梯度法例1用梯度法求下列無約束優(yōu)化問題，已知函435.4.1梯度法對(duì)這種簡(jiǎn)單的一元函數(shù)，可以直接用解析法對(duì)求極小。令解得因還應(yīng)繼續(xù)迭代計(jì)算。5.4.1梯度法445.4.1梯度法

2)第二次迭代因

解得5.4.1梯度法2)第二次迭代455.4.1梯度法因可知X(2)不是極小點(diǎn)，還應(yīng)繼續(xù)進(jìn)行迭代。最后得此問題的最優(yōu)解為：

5.4.1梯度法因465.4.2共軛梯度法共軛方向的概念：設(shè)H為一正定對(duì)稱矩陣，若有一組非零向量S1,S2,…,Sn滿足則稱這組向量關(guān)于矩陣H共軛。以正定二元二次函數(shù)為例。5.4.2共軛梯度法共軛方向的概念：475.4.2共軛梯度法任選初始點(diǎn)X(0)并沿某一下降方向S(0)作一維搜索，得由于梯度的迭代過程中，相鄰的搜索方向相互垂直。可知

對(duì)函數(shù)f(X)求點(diǎn)X(1)的梯度從點(diǎn)X(1)開始沿另一下降方向S(1)作一維搜索，得5.4.2共軛梯度法任選初始點(diǎn)X(0)并485.4.2共軛梯度法

欲使X(2)成為極小點(diǎn)，則必有將式代入得

展開得化簡(jiǎn)為左乘[S(0)]T，且得5.4.2共軛梯度法欲使X(2)成為極小點(diǎn)，則495.4.2共軛梯度法這就是說，若要使第二個(gè)迭代點(diǎn)X(2)成為該正定二元二次函數(shù)的極小點(diǎn)，只要使兩次一維搜索的搜索方向S(0)和S(1)關(guān)于函數(shù)的二階導(dǎo)數(shù)矩陣H為共軛就可以了。換句話說，如果能夠找到以H為共軛的兩個(gè)向量，則無論從哪個(gè)初始點(diǎn)出發(fā)，依次沿這兩個(gè)共軛方向作一維搜索，經(jīng)兩次迭代即可達(dá)到此正定二元二次函數(shù)的極小點(diǎn)。5.4.2共軛梯度法這就是說，若要使505.4.2共軛梯度法對(duì)于一般函數(shù)，共軛方向具有以下性質(zhì)：（1）若是以H共軛的n個(gè)向量，則對(duì)于正定二次函數(shù)從任意初始點(diǎn)出發(fā)，依次沿這n個(gè)方向進(jìn)行一維搜索，最多n次即可達(dá)到極小點(diǎn)。（2）從任意兩個(gè)點(diǎn)和出發(fā)，分別沿同一方向進(jìn)行一維搜索，得到兩個(gè)一維極小