直接搜索法

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

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

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

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

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

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

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

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

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

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

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

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