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