現(xiàn)代設(shè)計方法-一維搜索

1現(xiàn)代設(shè)計方法

第二部分優(yōu)化設(shè)計

第三章非線性優(yōu)化設(shè)計2§3-1

非線性規(guī)劃特點及優(yōu)化設(shè)計方法簡述

只要目標函數(shù)或約束條件為非線性函數(shù)的規(guī)劃問題就稱為非線性規(guī)劃。一、非線性規(guī)劃的特點

(1)非線性規(guī)劃問題與線性規(guī)劃問題不同，其最優(yōu)值一般不是在約束集的一個頂點處，且可以甚至不在約束集的邊界上。

(2)非線性規(guī)劃問題可能有局部最優(yōu)值，它不同于全局最優(yōu)解。3二、非線性規(guī)劃的優(yōu)化設(shè)計方法概述1．間接尋優(yōu)方法(也稱解析法、求導法)

利用求導數(shù)尋求函數(shù)極值的優(yōu)化設(shè)計方法，即古典的微分法就屬于這一類。這類方法要求把一個非線性規(guī)劃問題用數(shù)學方程式描述出來，然后按照函數(shù)極值的必要條件用數(shù)學分析的方法求出其解析解，再按照充分條件或者問題的實際物理意義間接地確定最優(yōu)解。因此稱為間接法。這類間接尋優(yōu)方法適用于求解目標函數(shù)具有簡單而明確的數(shù)學形式的非線性規(guī)劃問題，否則間接法就無能為力了，往往籍助于下述的直接尋優(yōu)法。42．直接尋優(yōu)方法(搜索法、數(shù)值法)

這是一種數(shù)值方法，利用函數(shù)在某一局部區(qū)域的性質(zhì)或一些已知點的數(shù)值，來確定下一步計算的點，這樣一步步搜索、逼近，最后達到最優(yōu)點。直接尋優(yōu)方法又分為兩大類：

(1)

消去法：它是用不斷消去部分搜索區(qū)間，逐步縮小最優(yōu)點存在的范圍來尋求最優(yōu)點的。此法對處理單變量函數(shù)的優(yōu)化設(shè)計問題是十分有效的。

(2)

爬山法：它根據(jù)已經(jīng)求得的目標函數(shù)值，判斷前進的方向，逐步改善目標函數(shù)而達到最優(yōu)。這種優(yōu)化設(shè)計方法類似于爬山登高峰，故稱爬山法。爬山法主要用于解決多變量函數(shù)的優(yōu)化設(shè)計問題。5幾乎所有的非線性規(guī)劃的尋優(yōu)方法求解的結(jié)果往往都是局部最優(yōu)解。倘若非線性規(guī)劃中的目標函數(shù)是凸函數(shù)，則局部最優(yōu)解就是全局最優(yōu)解；若問題有多個局部極小值解，可認為其中最小者為全局極小值解。為了確定起見，我們總假設(shè)所研究的非線性規(guī)劃問題是尋求目標函數(shù)的最小值，且所討論的目標函數(shù)為嚴格的凸函數(shù)，即在所考慮的搜索區(qū)間內(nèi)函數(shù)有唯一的最小值。而在實際工作中，當我們處理一個具體的非線性規(guī)劃時，目標函數(shù)是否為凸函數(shù)問題，有時可以驗證，有時驗證也并不那么容易。非線性規(guī)劃的優(yōu)化設(shè)計方法是非常多的，但與線性規(guī)劃不同，似乎沒有一種方法甚至一類方法對非線性優(yōu)化設(shè)計問題是普遍有效的，而是各種計算方法適合于不同的情況且各有優(yōu)缺點。x0d0x1d1x2d2x3d3xkxk+1dk6§3-2

單變量函數(shù)的優(yōu)化設(shè)計方法

對于不少多變量函數(shù)的非線性規(guī)劃問題往往歸結(jié)為反復地求解一系列單變量函數(shù)的最優(yōu)值。因此，單變量函數(shù)的尋優(yōu)方法成為解非線性規(guī)劃最基本的方法。求解單變量函數(shù)極值的迭代方法稱為直線搜索或一維搜索。

單變量函數(shù)的尋優(yōu)方法，常用的主要有兩類：

(一)消去法

(二)近似法1、黃金分割法及其C語言程序

黃金分割法即是消去法的一種。該方法適用于[a,b]區(qū)間上的任何單谷函數(shù)，函數(shù)甚至可以不連續(xù)。7單谷區(qū)間內(nèi)函數(shù)可以不連續(xù)，也可以有不可微點消去法的基本思路：逐步縮小搜索的區(qū)間，直至最小點存在的范圍達到允許的誤差范圍為止。

設(shè)函數(shù)f(x)如圖3-1中所示；起始的搜索區(qū)間為(a0，b0)，x*為所要尋求的函數(shù)的最小點。在搜索區(qū)間(a0，b0)內(nèi)任取兩點x1與x2，且x1<x2，計算函數(shù)值f(x1)與f(x2)，當將f(x1)的值與f(x2)的值進行比較時，可能的情況有下列三種：8(1)如圖(a)所示，若x1、x2在x*的右側(cè)，則必然f(x1)<f(x2)，這種情況下，可丟掉(x2,b0)部分，而最小點x*必在區(qū)間(a0,x2)內(nèi)(2)如圖(b)所示，若x1、x2在x*的左側(cè)；則必然f(x1)>f(x2)，這種情況下，可丟掉(a0,x1)部分，而最小點x*必在區(qū)間(x1,b0)

內(nèi)(3)如圖(c)所示，若x1、x2在x*的兩側(cè)，f(x1)=f(x2)，則不論丟掉(a0,x1)

，還是(x2,b0)，最小點x*

必在留下部分內(nèi)。圖3-1搜索區(qū)間的縮短消去法的基本原理：只要在搜索區(qū)間內(nèi)任取兩點，計算它們的函數(shù)值并加以比較以后，總可把搜索區(qū)間縮小。

平分法：適于目標函數(shù)易求一階或二階導數(shù)。取具有極小點的單谷函數(shù)的探索區(qū)間[s,e]的中點m作為計算點，并根據(jù)函數(shù)在m處的一階導數(shù)(>0或<0)來判斷應該消去m點左右哪一半搜索區(qū)間(如f(

m(k))>0

，遞增，則取新區(qū)間為[s(k),m(k)]（左邊）)。收縮率約為0.5。

Fibonacci法（分數(shù)法）F(1)=F(2)=1,F(n)=F(n-1)+F(n-2)(n≥2)按照上式產(chǎn)生的Fibonacci數(shù)F(n)，縮短率為(n)=F(n-1)/F(n)

n0123456789101112Fn01123581321345589144黃金分割法(0.618法)：計算次數(shù)較少，計算過程較簡單設(shè)有一線段為L，將它分割為兩部分，長的一段為x，短的一段為L－x，如果分割的比例滿足以下的關(guān)系：

則這種分割稱為黃金分割。其中，λ為比例系數(shù)。即分割后長的一段與整個線段的長度之比，等于短的一段與長的一段的長度之比。a1(0)a2(0)as(0)ae(0)如f(2(0))>f(1(0))，則探索區(qū)間[s(0),e(0)]縮短為[s(0),2(0)]如f(2(0))≤f(1(0))，則探索區(qū)間[s(0),e(0)]縮短為[1(0),e(0)]11斐波納契數(shù)列是1、1、2、3、5、8、13、21、34、55、89、144、233┅┅。上述神秘數(shù)字的任何兩個連續(xù)的比率，譬如55/89≈

0.618，89/144≈0.618。相鄰兩個斐波那契數(shù)的比值是隨序號的增加而逐漸趨于黃金分割比的。

這組數(shù)字十分有趣。0.618的倒數(shù)是1.618。譬如233/144≈

1.168。有人研究過向日葵，發(fā)現(xiàn)向日葵花有89個花辮，55個朝一方，34個朝向另一方。五角星非常美麗，這是因為在五角星中可以找到的所有線段之間的長度關(guān)系都是符合黃金分割比的。人們認為按0.618的比率分割線段是最協(xié)調(diào)的，勝似黃金，故稱黃金分割。因此把上述縮短搜索區(qū)間的迭代方法稱為黃金分割法或優(yōu)選法。黃金分割法消去的區(qū)間是哪一段事先不能預測，如圖所示，x1和x2哪個點好事先是不知道的，因此丟掉[0，x1]或丟掉[x2，L]都是可能的，所以最有利的方案應是要求它們一樣長：x2=L－x1即x2，應該是x1的對稱點。而且希望經(jīng)過舍去之后，其保留點，仍處于留下區(qū)間的相應位置上。1213

因此，只要第二個點取在原始區(qū)間的0.618處，第一點在它對稱的位置：x2=L－x1就能保證無論經(jīng)過多少次舍去，保留的點始終在新區(qū)間的0.618處。要進一步縮短區(qū)間，在其保留點的對稱位置再作一次計算就可以了。而且每次消去時，區(qū)間的縮短率E不變，E=λ=0.618。因此計算n個點以后，總的縮短率為：也就是說，如果丟掉的是[x2，L]留下了[0，x2]，則其中保留的點x1在[0，x2]

中的位置和x2在[0，L]中的位置相仿，即比值相同，為：

此式與(3-1)式相同，即為黃金分割，

。14圖3-2黃金分割法的取點圖

若給定區(qū)間縮短的精度δ，黃金分割法的計算方法及步驟如下：

(1)設(shè)初始區(qū)間為[a0

，b0]，第一次區(qū)間縮短要取兩個點，如3-2(b)所示，分別為：計算f(x1)與f(x2)，并進行比較．若f(x1)≤f(x2)

，則如圖3-2(c)

若f(x1)>f(x2)

，則如圖3-2(d)15

再計算函數(shù)值，進行比較，縮短區(qū)間如前。(2)每縮短一次區(qū)間，判斷一下是否滿足：式中b–

a

——現(xiàn)時求得的區(qū)間，

b0

–a0——初始區(qū)間，

δ

——給定的區(qū)間縮短的精度。若不滿足式(3-12)，則再進行縮短區(qū)間，直至滿意為止

(3)比較最后求得的兩函數(shù)值，確定最后的區(qū)間、最小點及函數(shù)的最小值。也可以兩函數(shù)值平均值作為最小值。用計算機進行黃金割法的計算時，其程序如圖3-3所示圖3-3黃金分割法程序框圖給定否否是是止也可采用迭代次數(shù)是否大于或等于k作終止準則。例1用黃金分割法求函數(shù)f(x)=3x3-4x+2的極小點，給定[a,b]=[0,2],ε=0.2。解：第一次縮小區(qū)間：

x1=0+0.382·(2-0)=0.764,f1=0.282x2=0+0.618·(2-0)=1.236,f2=2.72

f1<f2,新區(qū)間[a,b]=[a,x2]=[0,1.236],b-a>0.2第二次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0+0.382·(1.236-0)=0.472,f1=0.317由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.472,1.236]因為b-a=1.236-0.472=0.764>0.2,應繼續(xù)縮小區(qū)間第三次縮小區(qū)間：令x1=x2=0.764,f1=f2=0.282

x2=0.472+0.618·(1.236-0.472)=0.944,f2=0.747由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.944]因為b-a=0.944-0.472=0.472>0.2,應繼續(xù)縮小區(qū)間×××第四次縮小區(qū)間：令x2=x1=0.764,f2=f1=0.282

x1=0.472+0.382·(0.944-0.472)=0.652,f1=0.223由于f1<f2,故新區(qū)間[a,b]=[a,x2]=[0.472,0.764]因為b-a=0.764-0.472=0.292>0.2,應繼續(xù)縮小區(qū)間第五次縮小區(qū)間：令x2=x1=0.652,f2=f1=0.223

x1=0.472+0.382·(0.764-0.472)=0.584,f1=0.262由于f1>f2,故新區(qū)間[a,b]=[x1,b]=[0.584,0.764]因為b-a=0.764-0.584=0.18<0.2,停止迭代極小點與極小值：x*=0.5×(0.584+0.764)=0.674f(x*)=0.222××例2對函數(shù)，當給定搜索區(qū)間時，試用黃金分割法求極小點黃金分割法的搜索過程

……-0.665-0.940-1.111-1.3865-0.987>-0.851-0.665-1.111-1.386-1.8324-0.888<-0.9870.056-0.665-1.111-1.8323-0.987>-0.3060.056-1.111-1.832-320.115<-0.9871.9440.056-1.111-317.667<0.11551.9440.056-30f2比較f1bx2x1a迭代序號………………2、二次多項式近似法及外推內(nèi)插法單變量函數(shù)的尋優(yōu)方法，除了消去法外，另一種常用的方法為近似法，特別是多項式近似法。方法：用一個多項式來擬合目標函數(shù)，即在尋求目標函數(shù)極小點的區(qū)間上，我們可以利用在若干點處的函數(shù)值來構(gòu)成低次插值多項式；用它作為求極小點的函數(shù)的近似表達式，并用這個多項式的極小點作為目標函數(shù)極小點的近似如圖，多項式P(x)的極值點就是的根。我們只要求出這個方程的根并加以判斷，就可以得到函數(shù)f(x)極小點的近似位置。重復使用此法，直到得出符合要求的結(jié)果為止。21常用的插值多項式P(x)為二次或三次多項式，而由于用二次多項式來逼近，其計算較簡單且又具有一定的精度，所以應用較廣。我們只介紹二次多項式近似法。插值法與區(qū)間消去法都是不斷縮短初始搜索區(qū)間，從而求得極小點的數(shù)值近似解，其不同點在于試驗點位置的確定方法，在區(qū)間消去法中試驗點位置是由某種給定的規(guī)律確定的，它不考慮函數(shù)值的分布情況，如黃金分割法是按等比例0.618的縮短率確定的。區(qū)間消去法僅僅利用了試驗點函數(shù)值的大小進行比較，而插值法還利用了函數(shù)值本身或者其導數(shù)的信息。這樣，對于簡單的函數(shù)在極值點附近的尋優(yōu)問題，插值法具有較快的收斂速度。22二次多項式近似法

1．拋物線插值法

假定目標函數(shù)f(x)在搜索區(qū)間[x1，x3]內(nèi)連續(xù)，記x1、x2、x3三點的函數(shù)值分別為f1、f2、f3。如果x1<x2<x3與

f1≥f2<f3同時成立，可以利用這三點及相應的函數(shù)值作拋物線插值公式，即令這是f(x)在[x1，x3]上的一種近似。在這里，我們對P(x)的具體表達式并不感興趣，而只是關(guān)心它的極小點x4，x4就是f(x)在[x1，x3]上的極小點x*的一個近似。再利用x4所提供的信息可使搜索區(qū)間進一步縮短，在縮短的區(qū)間內(nèi)再作二次插值，依次循環(huán)下去，就可以求到x*

。231)

插值拋物線極小點的求法所需要的插值多項式，它應滿足條件對多項式(3-13)求導數(shù)并令其為零，得式(3-15)就是計算近似極小點的公式。只需算出a1和a2即可確定極小點。在方程組(3-14)中利用相鄰兩個方程消去a0，得24解方程組(3-16)就得到所需要的系數(shù)a1和a2將式(3-17)，(3-18)代入式(3-15)便得極值點x4的公式：

x4即為近似的最優(yōu)點。一般來說，x4處的函數(shù)值f4會比f1、f2、f3都好。為便于計算。可把(3-19)式改寫為：252)

終止準則由于二次多項式僅是目標函數(shù)的近似描述，不能指望一次近似就能得到函數(shù)的最優(yōu)值，必須在x4附近重復以上的步驟，直至滿足某個給定的精度要求時為止。如果x4是滿足給定精度的極小點，那么|x4－x2|一般應該會很小，|f4－f2|也應該很小。計算經(jīng)驗指出，當滿足時，取x4和x2中函數(shù)值較小的點作為極小點。3)

搜索區(qū)間的縮短當終止準則沒有得到滿足時，需要利用x4所提供的信息將原來的搜索區(qū)間[x1，x2

，x3]縮短，其過程如下：①比較x4和x2的大小，若x4>x2則轉(zhuǎn)②；若x4≤x2則轉(zhuǎn)③。②若f2≥f4成立，則x1=x2，x2=x4，f1=f2，f2=f4，區(qū)間縮短為[x2，x4

，x3]，轉(zhuǎn)④；否則x3=x4，f3=f4，區(qū)間縮短為[x1，x2

，x4]，轉(zhuǎn)④?！痢?7③若f4≤f2成立，則x3=x2，x2=x4，f3=f2，f2=f4，區(qū)間縮短為[x1，x4

，x2]，轉(zhuǎn)④；否則x1=x4，f1=f4，區(qū)間縮短為[x4，x2

，x3]，轉(zhuǎn)④。④區(qū)間搜索完畢。然后轉(zhuǎn)向計算新的搜索區(qū)間[x1，x2

，x3]上插值拋物線的極小點x4?！痢?8拋物線插值法的計算流程圖例：用二次插值法求函數(shù)f(x)=3x3-4x+2的極小點，給定[a,b]=[0,2],

ε=0.2。解1）初始區(qū)間[a,b]=[0,2],中間點x2=1。2）用二次插值法逼近極小點相鄰三點的函數(shù)值:x1=0,x2=1,x3=2;

f1=2,f2=1,f3=18.代入公式：由于f4<f2,x4<x2,新區(qū)間[a,b]=[a,x2]=[0,1]|x2-x4

|=1-0.555=0.445>0.2,應繼續(xù)迭代。在新區(qū)間，相鄰三點的函數(shù)值:

x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1x4=0.607,f4=0.243

由于f4<f2,x4>x2,新區(qū)間[a,b]=[x2,b]=[0.555,1]|x2-x4

|=|0.555-0.607|=0.052<0.2,迭代終止。

x*=x4

=0.607,f*=0.243例：用二次插值法求的極值點。初始搜索區(qū)間，。解：取x2點為區(qū)間[x1,x3]的中點，,計算3點處的函數(shù)值f1=19，f2=－96.9375，f3=124?？梢姾瘮?shù)值滿足“高－低－高”形態(tài)。 以x1,x2,x3為插值點構(gòu)造二次曲線，求第一次近似的二次曲線P(x)，其極小值點x4=1.9545，f4=－65.4648>f2。比較函數(shù)值可知應去掉區(qū)間[x1,x4]，以[x4,x2,x3]作為[x1,x2,x3]構(gòu)建新的P(x)x1x2x3x4f41-1.02.561.9545-65.464821.95452.563.1932-134.539432.53.193263.4952-146.776143.19323.495263.7268-154.977153.49523.726863.9123-155.685063.72683.840263.9123-155.685073.84033.912363.9501-155.896931

2．二次插值法與外推內(nèi)插法

拋物線插值法是二次插值法的一種特殊情況，其中所取的三個近似計算點所對應的函數(shù)值必為兩頭大，中間小，即三個近似計算點xa，xb，xc

(xa<xb<xc)滿足：f(xb)<f(xa)，f(xb)<f(xc)，因此保證能收斂。如果不滿足“高－低－高”的原則，則有的迭代方式不能保證一定收斂，有時甚至可能無解，此外，有不少問題其最優(yōu)點存在的范圍事先沒有給出，這時，無論用消去法或近似法，首先要尋找極值點存在的區(qū)間。外推內(nèi)插法，就是一種能自尋極值點范圍的二次多項式近似法。它先用外推法求出最優(yōu)點存在的區(qū)間，然后用內(nèi)插法求出二次多項式的極值點，以此為新的起點，逐次迭代直至達到給定的精度。由于在每次迭代中，它滿足“高－低－高”的原則，則一定能保證收斂，其具體步驟如下：32(a)外推法求極值點存在的區(qū)間

為了加速尋找區(qū)間的速度，這里采取了成倍地加大步長h的措施。設(shè)從某點x1開始，原始步長為h0(充分小的正數(shù))計算f(x1)與x2=x2＋h0處的函數(shù)值f(x2)。比較f(x1)與f(x2)有兩種情況：(圖3-4)若f(x1)≥f(x2)

，則將步長加倍,在x3=x2+2h0,x4=x3+4h0…,xK=xK-1+2K-2h0等點處求f(xK)，直至函數(shù)值增加為止(圖a)。若f(x1)<f(x2)，則求x3=x1－h(huán)0，x4=x3－2h0，…，xK=xK-1－2K-3h0等點處的f(xK)，直至函數(shù)值增加為止(圖(b)33對于凸函數(shù)來說，最小點必落在xK-2~xK之間，即xK-2<x*<xK，而且有此時若在xK-1與xK之間的中點處進行第K+1個點的計算，即取共得四個等間距的點xK-2

、xK-1

、xK+1

、xK，它們之間的間距為d。當f(x1)≥f(x2)時為d=2k-2h0，當f(x1)<f(x2)時為d=2k-3h0。比較這四個點的函數(shù)值，將其中函數(shù)值最小的點命名為xb，則取xa=xb－d，xc=xb+d，拋去余下的另一端點(見圖3-4)。至此，用加大步長的外推法，得到了區(qū)間[xa，xc]。要求的最小點必然落在這區(qū)間之中。應當指出，當沒有給出最小點存在的區(qū)間時，若要用直接消去法求最優(yōu)值，也可以利用以上尋找區(qū)間的外推法首先確定搜索區(qū)間，然后再用消去法求極值點。34(b)二次多項式內(nèi)插法求近似極值點利用式(3-19)或式(3-21)求出近似的最優(yōu)點xml(即x4)

，一般來說f(xml)要比f(xa)