直接搜尋法

基於啟發式方法的只利用目標函式值信息的無約束最佳化方法，如坐標輪換法、鮑威爾法，稱為直接搜尋法。因為直接搜尋法既不需要計算也不要逼近導數，他們常常被描述成“導數無關”。

而另一類利用目標函式的一階或二階導數信息的無約束最佳化方法，如梯度法、牛頓法、共軛梯度法、變尺度法，稱為間接搜尋法。

基本介紹

• 中文名：直接搜尋法
• 外文名：Direct search method
• 類別：數學術語
• 功能：無約束最佳化求解
• 作用對象：只利用目標函式值信息
• 特點：簡單，靈活和可靠

簡介

在歷史上，許多解決最佳化問題的方法都藉助於熟悉的“經典分析技術”，即目標函式的泰勒級數展開。實際上，我們可以根據所用的展開項數來分類數值最佳化的方法。採用一、二階導數的二階泰勒多項式構建 f 的局部二次逼近。牛頓方法是一個二階方法。採用一階導數的一階泰勒多項式構建 f 的局部線性逼近的最速下降方法是一個一階方法。在這種分類中，“零階方法”不需要求導信息和構造 f 的逼近。這些在工程最佳化界被稱為零階的方法就是直接搜尋法。直接搜尋法完全依賴於目標函式的值，但這並不能將直接搜尋法同其他最佳化方法完全區分。另外無約束最佳化的直接搜尋法僅僅依賴於通過可數集的函式值的相關階的目標函式。直接搜尋法可用新的疊代來減少目標。

經典分類

直接搜尋法一般被分為三類，許多在套用文獻中提到的新方法都是這三種方法的基本原理的改進版本。

模式搜尋法

模式搜尋法（Pattern search）用一系列的點模式考慮目標函式的行為的試探位移來刻劃。所有都依賴於有理格。試探位移由當前疊代鄰近格線的點訪問的系統策略組成。在戴維森的 ANL 5990延期的序言中，他描述了最基礎的一種模式搜尋算法，由於這么簡單而沒有歸類。

單純形法

單純形搜尋法（Simplex search）由指導搜尋的簡單策略刻劃。第一個單純形方法是在 1962 年由 Spendley et al.在論文中提出的。他們是由於早期的直接搜尋法在任何地方都需要 2n 到 2n 個目標估值完成疊代改進的搜尋的事實

而提出的。他們的結果是不需要 n+1個以上的目標函式的值來確定上升（或下降）方向。這意味著，只要n+1個 f(x)圖像中的點就可確定一個平面，利用 n+1 個 f(x)值的有限差分估計▽f (x)。同時， n+1 個點確定一個單純形。這引出了單純形搜尋的基本思想：在Rⁿ 空間中構造一個非退化單純形並用單純形驅動搜尋。單純形不只是簡化了空間的採樣，它同時還有其它特性，如果用某個點的相對於其象對面中心的對稱點代替該點後仍然是單純形，見圖1。這同樣簡化了操作，因為在搜尋最優解時一次可反射一個頂點，簡化了過程。

圖 1.原始單純形，關於相對面中心對稱的點，和鏡像單純形

一旦初始單純形構造好， Spendley et al 單純形算法的單個移動是鏡像的。這個移動首先在單純形中確定“最差”頂點（例如：最小期望目標值的），然後通過向對面映射最差單純形。如果映射後的點仍然是最差的，則選擇“次差”頂點繼續這個過程。（一個圖 1 的快速回顧應該確保鏡像點是否不比下一個最差點好，否則如果“最差”頂點又一次被選擇鏡像，就會被簡單的反射回原來的地方，開始了一個循環）。最終的目標是取代“最好”頂點（比如，有最期望目標值的）或者確定出最優頂點是一個最優解的候選。直到那時，算法一直在通過相對面的中心翻轉頂點來移動單純形（而不是最好頂點）。

搜尋方向集適應法

最後一個經典方法的家族包括 Rosenbrock 和 Powell 的方法，稱作搜尋方向集適應法（Methods with adaptive sets of search directions）。這些算法試圖利用在搜尋過程中獲得的函式曲率的信息構造方向來加速搜尋。

Rosenbrock 方法的初始階段用列向量做為搜尋方向。它沿著這些方向搜尋，每一輪循環一次，再轉到產生成功步的新的疊代（一個不成功的步是引起目標期望值變小的）。這持續到每個搜尋方向。一旦如此，當前階段就結束了。在下一階段，就不是像局部變數方法一樣重複搜尋同樣集的正交向量了， Rosenbrock 旋轉了方向集來獲得在早期移動過程中確定的目標的信息。

鮑威爾搜尋法描繪了一個不用計算導數尋找最小值的方法。我們定義它為求導無關算法，它不像直接搜尋法，建模是搜尋的核心。鮑威爾搜尋法第一次使直接搜尋法和求導無關方法有服務性的收斂分析。像鮑威爾搜尋法中線性搜尋使用的目標一樣的顯性建模的需要很清訴：它使得最佳化方法行為的嚴格陳述稱為可能。可以期望目標本質為二次的一個解的鄰域裡算法一次快速收斂到最小值。

優勢

直接搜尋法在實踐中工作的很好，實際上，許多直接搜尋法的基礎啟發性最近被分析家證明有和全局擬牛頓法技術類似的全局收斂性。直接搜尋法的成功是因為他們中的許多，包括胡克和吉夫斯的直接搜尋法是依賴於經典分析技術，方法上外觀不是顯然形成他們的初始規格。

擬牛頓法不能求解所有的非線性最佳化問題。直接搜尋法能夠解決許多其它精巧算法所解決不了的問題。直接搜尋法的獨特特性避免了許多其它方法的缺陷。

直接搜尋法即使對於要求很高的用戶也是首選。理由很簡單：直接搜尋法能夠直接、立即地被利用來求解許多非線性最佳化問題。對用戶的要求是最低的，算法幾乎不需要設定太多參數。