第三章無約束最優化方法

2021-03-04 08:12:09 字數 1829 閱讀 7869

把乙個多維問題轉化為一系列較少維數的問題稱為降維。降維方法有幾種,座標輪換法是用得較多的一種,這是一種不需要求函式導數的直接探索目標函式最優解的方法。

直接法、降維法

一、座標輪換法的基本思想

其基本思想就是通過每次僅對多元函式的乙個變數沿其座標軸進行一維探索,其餘各變數均固定不動,並依次輪換進行一維探索的座標軸,完成第一輪探索後再重新進行第二輪探索,直到找到目標函式在全域上的最小點為止,以達到將乙個多維的無約束最優化問題,轉化為一系列的一維問題來求解的目的。為簡明起見,現以二元函式來說明

基本步驟:

1.從初始點出發,依次沿各座標軸方向搜尋最優點,保持其餘n-1個變數不變。

例:如果,如果沿x1軸方向搜尋,則搜尋過後改變的僅僅是x1的值3,其餘座標的值均保持不變。假設搜尋到的值是8,則下乙個點的值為。

迭代點的序列為:

上標表示搜尋的輪次,下標表示對應的座標,亦即該輪次的第幾次迭代。

經過一輪(n次)迭代後,得到乙個新點,然後進行下一輪迭代。只到滿足精度。

二、步長可以有以下幾種取法

1.隨機選擇值的方法

2. 加速步長法

為方向的初始試驗了加快探索過程,可以採用加速步長法。

用此法時,先規定沿方向的初始試驗步長,並用它探測跨步輪沿第的前、後方向。若第k輪沿第i個座標方向進行探索時所獲得的探索點

滿足,則取正向,否則取負向。若探索均未成功則需要減小值。當步長的正負確定以後,再取步長為初始步長的若干()倍,即,若,則繼續取進行探索,直到目標函式值不再下降才改換座標軸為軸進行探索,當進行多輪探索後發現整個過程停滯不前,再並仍未達到計算精度要求時,則可縮小,取,再進行探索,直到得到滿意結果或已縮小到預定精度時為止。

3. 最優步長法

利用以前所介紹過的一維探索方法,求最優步長。

三、座標輪換法的效能

從座標輪換法的迭代過程可以看出其探索路線較長,而且顯然是問題的維數愈多求最優解的效率愈低。因此,這種方法對設計變數少的最優化問題雖然有效,但對設計變數較多的問題則不太適用,當維數n>10時,則不應採用此法。

另外,此法的效能在很大程度上還取決於目標函式的性質,如圖

直接法(不需要對函式求導)、共軛方向法(利用目標函式值資訊構造共軛方向)。

一、鮑威爾方法的基本思想

從乙個初始點出發,通過一組線性無關向量組搜尋,並構造n個共軛方向,不需要對函式求一階導數、二階導數,只需利用目標函式值資訊構造共軛方向。

powell方法搜尋方向(共軛方向)的形成:

1.首先按座標輪換法進行一輪搜尋

從初始點出發,沿n個座標軸方向進行一維搜尋,即,得到點。

利用和構造第乙個共軛方向

從沿方向進行一維搜尋,求得乙個新點

2.第二輪搜尋

從先沿和方向進行n次一維搜尋,(即用作為本輪的最後乙個搜尋方向,而將原來的第乙個方向擠掉),可得到點

利用和構造第二個共軛方向

從沿方向進行一維搜尋,求得乙個新點

如此反覆,每輪迭代將新前一輪的共軛方向加在最後,而將第乙個方向擠掉不用。

經過n輪迭代,即可構造出n個共軛方向,,,

迭代步驟

二、改進的鮑威爾方法

按上述方法構造的共軛方向會出現線性相關的情況,即在某一次一維搜尋中會出現或,特別的,當時,那麼在構造共軛方向時,由於其中的,下一輪迭代由於擠掉了,故僅由n-1個向量組合。這樣在下一輪的各次搜尋中,都是在下降了的空間中進行的,導致搜尋僅限於n維空間的乙個子空間的極小點而失敗。

以三維空間搜尋為例

假設第一維優化步長或非常接近於0,即表示沿座標軸方向的搜尋沒有前進或前進很少,則共軛方向為

下一輪迭代方向是,,,它們是線性相關的,故搜尋是在下降了的空間中進行的,無法搜尋函式的極小值。

powell對此進行了改進。

第十八章無約束最優化的梯度方法

目的是在找一點稱為此無約束最優化問題的全域性最優點。然而在實際中,大多數最優化方法只能求到區域性最優點,即在中可找到一點使得在的某個鄰域中有。但在實際中,可以根據問題的意義來判斷求得的區域性極小點是否為全域性最優點,無約束最優化可以分為兩大類 一類是使用導數的方法,也就是根據目標函式的梯度 一階導數...

關於無約束最優化問題的信賴域解法

一 引言 無約束優化問題是實際工程中最常見的問題之一。這類問題雖然形式比較簡單,但是對於某些大規模的或者非線性很強的問題,求解它們仍然是有相當難度的。無約束問題的演算法大致分成兩類 一類在計算過程中要用到目標函式的導數,另一類則只要求目標函式值。本文中所講述的信賴域法,與牛頓法 最速下降法 共軛梯度...

第三章計畫

t 4 c類工作特徵是不迫切,後果影響小。f 5 既然時間客觀存在,時間就可以儲存。四 填空題 1 按計畫的約束程度劃分,計畫可分為 2 目標管理分為制定目標體系和三個階段。3 時間的特徵包括客觀性 和 4 計畫工作的核心問題是 5是管理職能中最基本的職能。五 名詞解釋題 1 計畫 2 目標管理 六...