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

第四章

單變量函數(shù)的優(yōu)化方法第一節(jié)優(yōu)化方法的基本思想第二節(jié)搜索區(qū)間的確定第三節(jié)黃金分割法第四節(jié)拋物線插值法12024/4/3第四章單變量函數(shù)的優(yōu)化方法第一節(jié)優(yōu)化方法的基本思想第一節(jié)優(yōu)化方法的基本思想

求目標函數(shù)

的極小點，從理論上說需要求解方程：

其中

那么如何來求的極小點呢？22024/4/3第一節(jié)優(yōu)化方法的基本思想

求目標函數(shù)的極小基本思想:這種方法是逐次迭代的方法，在電子計算機上很容易實現(xiàn)，因此它在優(yōu)化設計中被廣泛地采用。32024/4/3基本思想:這種方法是逐次迭代的方法，在電子計算pk方向上的任何一點可以表示為

其中t為步長因子，為實系數(shù)，此時pk方向上任何一點的目標函數(shù)值為

，它是參數(shù)t的一元函數(shù)。那么在沿pk方向求

的極小點，這就是求一元函數(shù)

的極小問題，它可表示為：這個過程稱為一維搜索過程。42024/4/3pk方向上的任何一點可以表示為這個過程稱為一維搜索過程。42

故：

優(yōu)化方法的基本思想是將優(yōu)化問題轉化為一系列的一維搜索問題，所以，一維搜索方法就成為優(yōu)化設計中最基本的方法。

注意：采用一維搜索法求出極小點，必須考慮三個因素。初始點X0的選取，應盡量選擇靠近極值點X*，這佯就能較快地找到極值點X*。

搜索方向pk的確定。從Xk出發(fā)沿什么方向可以很快找到F（X）的極小點X*？以不同的原則選取pk就構成了優(yōu)化方法中各種不同的方法。在確定了搜索方向pk以后，關鍵的問題是如何進行沿pk方向的一維搜索。52024/4/3故：注意：采用一維搜索法求出極小點，必須考慮三個因素。初第二節(jié)搜索區(qū)間的確定欲求一元函數(shù)

的極小點

必須先確定極小點所在的區(qū)間〔a，b〕。圖3-1具有單谷性的函數(shù)62024/4/3第二節(jié)搜索區(qū)間的確定欲求一元函數(shù)的極小點－、確定搜索區(qū)間〔a，b〕的外推法先假設

具有圖示的單谷性。〔a，b〕區(qū)間形成“高—低—高”趨勢。從a=0開始，以h0為步長向前試探：函數(shù)值上升→步長變號；函數(shù)值下降→步長加倍→區(qū)間的始點、中間點依次沿試探方向移動一步；重復步驟2直至函數(shù)值上升為止。最后得到的三點即為搜索區(qū)間的是始點、中間點和終點。圖3-1具有單谷性的函數(shù)72024/4/3－、確定搜索區(qū)間〔a，b〕的外推法先假設圖3-2圖3-2表示a沿正向試探，每走一步區(qū)間的始點、中間點依次沿試探方向移動一步（進行換名），3步后確定搜索區(qū)間為

，且區(qū)間內：82024/4/3圖3-2圖3-2表示a沿正向試探，每走一步區(qū)圖3-3圖3-3表示a沿正向試探，確定搜索區(qū)間為

，且區(qū)間內

：92024/4/3圖3-3圖3-3表示a沿正向試探，確定搜索區(qū)間圖3—4外推法的程序框圖MATLAB程序實現(xiàn)OPT4t2waituifa.m102024/4/3圖3—MATLAB102024/4/1二、區(qū)間消去方法搜索區(qū)間確定之后，采用區(qū)間消去法逐步縮短搜索區(qū)間，從而找到極小點的數(shù)值近似解。假定在搜索區(qū)間內[a,b]任取兩點a1，b1，對應函數(shù)值為，

；112024/4/3二、區(qū)間消去方法搜索區(qū)間確定之后，采用區(qū)間消存在三種可能情況：122024/4/3存在三種可能情況：122024/4/1綜合為兩種情況：1、若

則取

為縮短后的搜索區(qū)間。

2、若

則取

為縮短后的搜索區(qū)間。

思考：2、3兩中情況為何寫在一起？132024/4/3綜合為兩種情況：1、若第三節(jié)黃金分割法黃金分割法也是建立在區(qū)間消去法原理基礎上的試探方法。基本思想是：

在搜索區(qū)間內[a,b]適當插入兩點a1、a2

，將區(qū)間分成三段，然后利用區(qū)間消去法，使搜索區(qū)間縮小，通過迭代計算，使搜索區(qū)間無限縮小，從而得到極小點處函數(shù)值近似解。

它適用于[a,b]區(qū)間上的任何單谷函數(shù)求極小值問題。對函數(shù)除要求“單谷”外不作其他要求，甚至可以不連續(xù)。因此，這種方法的適應面相當廣。142024/4/3第三節(jié)黃金分割法黃金分割法也是建立在黃金分割法對插入點的要求：1、插入點

、

的位置相對于區(qū)間

兩端具有對稱性，即：為待定常數(shù)；152024/4/3黃金分割法對插入點的要求：1、插入點、2、在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，

與原來區(qū)間的三段具有相同的比例分布。設：

區(qū)間長度為1，保留下來區(qū)間為，其長度為

，區(qū)間縮短率為

。為了保持相同比例分布，新插入點應在

位置上，

在原區(qū)間的

位置相當于在保留區(qū)間的

位置。故:162024/4/32、在保留下來的區(qū)間內再插入一點所形成的區(qū)間新三段，設：區(qū)172024/4/3172024/4/1黃金分割法的搜索過程：1）給出初始搜索區(qū)間及收斂精度

ε，將

λ賦以0.618；2）按坐標點計算公式計算

，

；并計算其對應的函數(shù)值

，

；182024/4/3黃金分割法的搜索過程：1）給出初始搜索區(qū)間及收斂精度ε，將3）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來的坐標點計算公式，需進行區(qū)間名稱的代換，并在保留區(qū)間中計算一個新的試驗點及其函數(shù)值。如果：如果：記N0=0；記N0=1；192024/4/33）根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。如果：如果：記N0=04）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度：

如果收斂條件滿足，則取最后兩試驗點的平均值作為極小點的數(shù)值近似解。如果條件不滿足則轉向步驟5）；5）產(chǎn)生新的插入點：如N0=0，則取如N0=1，則取轉向3）進行新的區(qū)間縮小。202024/4/34）檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠精度：5）產(chǎn)生MATLAB程序實現(xiàn)