(5.3.8)-2.4 一維非線性規(guī)劃

腳本——一維非線性規(guī)劃(ppt1,ppt2)同學(xué)，你好，這節(jié)課我們來學(xué)習(xí)一維非線性規(guī)劃。(ppt3)對于今天我們要講的內(nèi)容，先來了解這些問題實(shí)際背景。(ppt4)（動(dòng)畫1,2）首先，我們觀看下面兩幅圖，左邊是汽車的流線圖，我們設(shè)計(jì)的原則需要汽車受空氣阻力盡量小，同時(shí)人坐車?yán)镄枰孢m，外觀需要漂亮等，設(shè)計(jì)出來的汽車流線就是一典型的一維非線性規(guī)劃。（動(dòng)畫3）右邊是平常所見到的橋梁道路曲線。這些都與一維非線性規(guī)劃有著密切的聯(lián)系，隨著社會的發(fā)展，一維非線性規(guī)劃也受到普遍的關(guān)注，廣泛應(yīng)用于科學(xué)工程等領(lǐng)域。(ppt5)今天我們講一維非線性規(guī)劃的求解。在此之前，我們先看一維極值問題具體模型。(ppt6)（動(dòng)畫1）無約束一維極值問題的一般表達(dá)式為：（動(dòng)畫2）??????f(??)，??屬于R，或者??????f(??)，??屬于[??_1，??_2]，（動(dòng)畫3）其中，??為一維變量，f(??)為一維變量??的函數(shù)。（動(dòng)畫4）針對一維極值問題的求解方法非常多，下面將主要介紹幾類經(jīng)典的搜索方法，如：黃金分割法、斐波那契法以及二分法。(ppt7)（動(dòng)畫1）先來看黃金分割法，黃金分割法是用于求解一元單值函數(shù)f:R映到R，在閉區(qū)間[??_0，b_0]上是單峰的，即存在局部極小值點(diǎn)，且唯一。（動(dòng)畫2）對于極小值問題，單峰函數(shù)的圖形如圖所示。(ppt8)黃金分割法的主要思想是：（動(dòng)畫1）首先，在區(qū)間[??_0，b_0]中挑選兩點(diǎn)，由此把區(qū)間分為三段，然后再通過比較這兩點(diǎn)的函數(shù)值大小，就可以確定是刪去最左端還是最右端。如此進(jìn)行下去不斷縮短極小點(diǎn)所在的區(qū)間，直到達(dá)到足夠的精度水平。（動(dòng)畫2）特別地，可以按照對稱壓縮方式來縮小極小點(diǎn)所在區(qū)間，即（動(dòng)畫3）??_1-??_2=b_1-b_2=rho(b_0-??_0)，（rho<1/2），（動(dòng)畫4）（見背板）具體的分段如下圖所示，區(qū)間分3段，兩邊的長度相等，最好保證中間的長度小于兩邊的長度。(ppt9)（動(dòng)畫1）在上述基礎(chǔ)上，再計(jì)算目標(biāo)函數(shù)值在中間點(diǎn)處的值，如果f(??_1)<f(b_1)，那么極小點(diǎn)應(yīng)該位于區(qū)間[??_0，b_1]中，若f(??_1)≥f(b_1)，極小點(diǎn)應(yīng)該位于區(qū)間[??_1，b_0]中。（動(dòng)畫2）我們看示意圖，為什么如果f(??_1)<f(b_1)，那么極小點(diǎn)應(yīng)該位于區(qū)間[??_0，b_1]中呢？因?yàn)樵趨^(qū)間[??_0，b_1]中，至少有a1比區(qū)間的端點(diǎn)值小，說明在這個(gè)區(qū)間內(nèi)，函數(shù)圖形有下降的過程，極小值落在這個(gè)區(qū)間。(ppt10)（動(dòng)畫1）通過上面分析，目標(biāo)函數(shù)的極小點(diǎn)已經(jīng)被壓縮到[??_0，b_1]中。由于??_1已經(jīng)位于區(qū)間[??_0，b_1]中，且f(??_1)已知，因此為了減少計(jì)算工作量，可令??_1作為b_2。這樣我們還需要找一點(diǎn)??_2，找的原則是保證這一步的壓縮比與前面的壓縮比相同，并計(jì)算出函數(shù)在??_2的值。（動(dòng)畫2）具體的過程如圖所示。第二次還是把區(qū)間分三部分，兩邊區(qū)間長度相等。剖分的原則是壓縮比與第一次相同。(ppt11)下面確定壓縮比，即參數(shù)rho的確定：（動(dòng)畫1）不失一般性，假定初始區(qū)間[??_0，b_0]的長度為1，下一次壓縮比仍是rho，（動(dòng)畫2）如圖所示，經(jīng)過一次壓縮后區(qū)間長度變?yōu)閇??_0，b_1]，把區(qū)間分三部分，[b_2，b_1]已經(jīng)確定了。（動(dòng)畫3）左邊區(qū)別取多長呢，即??_2位置如何選取，需要保證[??_0，a_2]等于[b_2，b_1]，且壓縮比還是rho。因此我們可以得到（動(dòng)畫4）rho（b_1-??_0）=b_1-b_2。（動(dòng)畫5）整個(gè)區(qū)間的長度假設(shè)為1后，b_1-??_0就等于1-rho，同時(shí)，由于第一次壓縮兩邊的長度都是rho，因此夾在中間的部分為b_1-b_2=1-2rho，把他們代入上面方程中，（見背板）得到rho（1-rho）=1-2rho（動(dòng)畫6）整理后可得一元二次方程：rho^2-3rho+1=0，（動(dòng)畫7）解之可得rho_1=(3+5^(1/2))/2，rho_2=(3-5^(1/2))/2，要求rho<1/2，從而可知rho=(3-5^(1/2))/2約等于0.382。(ppt12)結(jié)合以上，我們對黃金分割法做一下總結(jié)：（動(dòng)畫1）由1-rho=(5^(1/2)-1)/2，故有rho/(1-rho)=(3-5^(1/2))/(5^(1/2)-1)=(1-rho)/1，即以rho/(1-rho)的比例劃分區(qū)間，能夠使的短區(qū)間與長區(qū)間長度之間的比值等于長區(qū)間與整個(gè)區(qū)間長度的比值。（動(dòng)畫2）如右上角圖所示，第一次的壓縮比為(1-rho)/1，（動(dòng)畫3）第二次的壓縮比為rho/(1-rho)，這兩個(gè)壓縮比是相等的。（動(dòng)畫4）因此，按照1-rho的比例逐步壓縮經(jīng)過N步壓縮之后，極小點(diǎn)所在區(qū)間長度將壓縮到初始區(qū)間長度的(1-rho)^N約等于(0.61803)^N，稱為總壓縮比。（動(dòng)畫5）重復(fù)以上過程，如此往復(fù)，通過多次計(jì)算，即可獲得精度水平足夠的區(qū)間。(ppt13)黃金分割法算法步驟：（動(dòng)畫1）1、給定初始區(qū)間[??_0，b_0]，給定精度要求epsina>0。令??_1=??_0+rho(b_0-??_0)，b_1=??_0+(1-rho)(b_0-??_0)，并計(jì)算f(??_1)與f(b_1)。（動(dòng)畫2）2、若b_1-??_1<epsina，算法停止；否則，當(dāng)f(??_1)≥f(b_1)時(shí)，轉(zhuǎn)3；當(dāng)f(??_1)<f(b_1)時(shí)，轉(zhuǎn)4。（動(dòng)畫3）3、當(dāng)f(??_1)≥f(b_1)時(shí),則??*屬于[??_1，b_0]，令??_2=b_1，b_2=??_1+(1-rho)(b_0-??_1)，計(jì)算f(b_2)。（動(dòng)畫4）4、當(dāng)f(??_1)<f(b_1)時(shí)，則??*屬于[??_0，b_1]，令b_2=??_1，??_2=??_0+rho(b_1-??_0)，計(jì)算f(??_2)。（動(dòng)畫5）5、重復(fù)上述計(jì)算過程，直到精度達(dá)到要求。(ppt14)（動(dòng)畫1）接下來介紹斐波那契法，它也是一種區(qū)間收縮算法，它與黃金分割法的區(qū)別：在區(qū)間壓縮過程中，允許壓縮比參數(shù)不斷調(diào)整。其次，該方法與黃金分割法的理念類似，需要確定一個(gè)參數(shù)序列，即使得每次迭代中只需要計(jì)算一次目標(biāo)函數(shù)值即可。兩次迭代的中間點(diǎn)選擇方式如下圖所示。（動(dòng)畫2）從圖可以看出來，我們還是把區(qū)間分3部分，兩端區(qū)間長度相同。與黃金分割法的區(qū)別是壓縮比每一筆都變了，比如由第K次壓縮后，到第K+1次壓縮，壓縮比為rho_k+1(ppt15)（動(dòng)畫1）接著，兩次迭代中的參數(shù)滿足rho_(k+1)(1-rho_k)=1-2rou_k，整理后可得rho(k+1)=1-rho_k/(1-rou_k)，rho_k屬于[0，1/2]，N次迭代后的總壓縮比：(1-rho_1)(1-rho_2)...(1-rho_N)很多序列都能滿足上式，我們最終的目標(biāo)就是要收斂快，即要使得多次迭代后的總壓縮比達(dá)到最小，因此我們可建立一個(gè)有約束優(yōu)化問題:（動(dòng)畫2）（見背板）minmize(1-rho_1)(1-rho_2)...(1-rho_N),subjecttorho_(k+1)=1-rho_k/(1-rho_k)，k=1，...N-1，rho_k屬于[0，1/2]，k=1，...N。(ppt16)（動(dòng)畫1）下面要求這個(gè)優(yōu)化問題的最優(yōu)解，我們引入斐波那契數(shù)列F_1，F(xiàn)_2，F(xiàn)_3，...，令F_(0)=0，F(xiàn)_(1)=1；對于k大于等于1，有（動(dòng)畫2）F_(k+1)=F_(k)+F_(k-1)，（動(dòng)畫3）比如F3=3,F4=5,F5=8,也稱這個(gè)序列為兔子序列。（動(dòng)畫4）（見背板）可以證明上述優(yōu)化問題的最優(yōu)解采用斐波那契數(shù)列表示，即：rho_1=1-F_(N)/F_(N+1)，rho_2=1-F_(N-1)/F_(N)，...，rho_k=1-F_(N-k+1)/F_(N-k+2)，...，rho_N=1-F_(1)/F_(2)。（動(dòng)畫5）斐波那契數(shù)列法的總壓縮比為：(1-rho_1)(1-rho_2)...(1-rho_N)=[F_(N)/F_(N+1)][F_(N-1)/F_(N)]...[F_(1)/F_(2)]=1/F_(N+1)。(ppt17)（動(dòng)畫1）（見背板）斐波那契法算法步驟如下：①給定初始區(qū)間[??_0，b_1]和精度要求，求迭代次數(shù)N,確定壓縮比1-rho_1=1-F_(N)/F_(N+1)，計(jì)算中間點(diǎn)??_1和b_1，并計(jì)算f(??_1)與f(b_1)，其中，??_1=??_0+rho*(b_0-??_0)，b_1=??_0+(1-rho)(b_0-??_0)。（動(dòng)畫2）②當(dāng)f(??_1)>f(b_1)時(shí)，轉(zhuǎn)3；當(dāng)f(??_1)<f(b_1)時(shí)，轉(zhuǎn)④。（動(dòng)畫3）③則??*屬于[??_1，b_0]，令??_2=b_1，b_2=??_1+(1-rho)*(b_0-??_1)，計(jì)算f(b_2)。（動(dòng)畫4）④則??*屬于[??_0，b_1]，令b_2=??_1，??_2=??_0+rho*(b_1-??_0)，計(jì)算f(??_2)。(ppt18)下面來看二分法：（動(dòng)畫1）設(shè)f(??)是定義在區(qū)間[??_0，b_0]上的連續(xù)可微函數(shù)，求解函數(shù)f(??)在區(qū)間的極小點(diǎn)，該方法的思路是以0.5的比率逐步縮小搜索區(qū)間，并在區(qū)間壓縮過程中利用函數(shù)的一階導(dǎo)數(shù)。（動(dòng)畫2）算法步驟如下：（動(dòng)畫3）1、區(qū)間[??_0，b_0]上，驗(yàn)證f(??_0)*f(b_0)<0，給定精度epsina。（動(dòng)畫4）2、求解區(qū)間[??_0，b_0]的中點(diǎn)??(0)=(??_0+b_0)/2，計(jì)算??(0)處的一階導(dǎo)數(shù)。（動(dòng)畫5）3、若??(0)處的一階導(dǎo)數(shù)>0，則極小值點(diǎn)??*屬于[??_0，??(0)]。（動(dòng)畫6）4、若??(0)處的一階導(dǎo)數(shù)>0，則極小值點(diǎn)??*屬于[??(0)，b_0]。（動(dòng)畫7）5、若??(0)處的一階導(dǎo)數(shù)=0，則??(0)為函數(shù)的極小值點(diǎn)。（動(dòng)畫8）6、判斷是否達(dá)到精度epsina，否則，在區(qū)間[??_0，??_1]或[??_1，b_0]重復(fù)步驟2-5。(ppt19)下面我們總結(jié)本節(jié)課所學(xué)習(xí)的內(nèi)容(ppt20)三種方法比較：（動(dòng)畫1）1、黃金分割法的壓縮比rho約等于0.618固定；斐波那契法壓縮比每步可變,總的壓縮比1/F_(N+1)；二分法的壓縮比rho等于二分之一。后面的方法比前面方法收斂快。（動(dòng)畫2）2、黃金分割法和斐波那契法只用到用到了f(??)的值，但二分法用到了f(??)的導(dǎo)數(shù)值，對函數(shù)的條件要求更強(qiáng)。（動(dòng)畫3）給大家留