一維搜索方法總結

一維搜索

首先說下一維搜索。一維搜索是針對以下場景而生。

其目的就是找這樣的最優步長因子。

其一般包含以下結構：

1. 確定包含問題最優解的搜索區間；
2. 利用某種分割技術或者插值方法縮小這個區間，進行搜索求解。

搜索區間——進退法

從一點出發，試圖確定出函數值呈現「高-低-高」的三點。一個方向不成功，就退回來，再沿相反方向尋找。

一般步驟如下：

1. 選取初始值和，加倍係數(一般)，;
2. 如果，則，繼續進行2，否則繼續進行3;
3. 若k==0，轉換搜索方向（即,轉2）；否則停止迭代，輸出，即為得出的區間。

分割方法

1. 黃金分割法。類似於二分查找的策略，只是每次縮小區間的時候選用的是黃金比例0.618。
2. Fibonacci。類似黃金分割法，但是在縮減區間時採用的是Fibonacci數。

此類方法及其適用於針對導數表達式複雜或未知的情況。

插值方法

針對具備較好解析性質的函數求解時，插值要比分割法好不少。

1. 一點二次插值（牛頓法）。需要利用一點處的函數值、一階和二階導數值構造二次插值函數。該方法收斂速度快，具備局部二階收斂速度。假設已知一個點和其對應的一階導和二階導數，那麼可推出近似的一維搜索極小點為。每次更新該點，然後再去迭代查找即可。
2. 二點二次插值法。給出兩點的函數值和其中一點的導數值，構造二次插值函數。其求取極小點式子為：。
3. 三點二次法（拋物線法）。類似，極小點求解公式為：。其中。迭代時，從，，和中挑選最小的點和其左右兩點，進行下一步的迭代。
4. 二點三次插值法。用三次多項式來逼近。比二次插值法有較好的收斂效果， 但通常要求計算導數值，且計算量較大。一般當導數易求時，用三次插值法較好，其收斂速度為2階，一般優於拋物線法。用函數在,兩點的函數值,和導數值,來構造三次函數，初值條件,,。推導後公式如下:

一般而言，上面插值和分割方法都要結合進退法一起使用，屬於精確一維搜索方法。下面講下不精確一維搜索方法。

不精確一維搜索

• 精確一維搜索往往需要花費很大的時間。
• 當迭代點遠離問題的解時，精確求解通常不十分有效。
• 很多最優化方法，如牛頓法和擬牛頓法，其收斂速度並不依賴於精確一維搜索過程。
• 只要保證目標函數有滿意的下降，可大大節省計算量

一般而言主要有以下兩種準則。

Armijo-Goldstein準則

Wolfe-Powell準則

Armijo-Goldstein準則有可能把最優步長因子排除在可接受

區間外，更改其下界約束後，得到以下約束：

這裡重點說下這個，畢竟相較於Armijo，本方法為改進型。

Wolfe-Powell方法相較於精確一維搜索，不再採用進退法去尋找搜索區間。在進退法裡面，是通過慢慢擴展生成區間，然後在在區間中查找合適的，而在Wolfe-Powell中我們可以直接定義步長區間的界限，比如[0,10000]，那麼其會根據其準則去每次剔除不符合的區間，逐步縮小區間，其能夠較為快速的跳過無用的計算，速度要快很多。

Wolfe-Powell方法計算過程中，也用到了插值方法，用以區間切割剔除。自己在L-BFGS方法上對該準則方法進行了實現，發現這個實現要比其他複雜很多，主要分為區間裁剪和查找求解倆個過程，大致流程如下：

實現代碼見https://github.com/sloth2012/scalaML/blob/master/src/main/scala/com/lx/algos/ml/optim/newton/LBFGS.scala，主要是調用fit_Wolfe_Powell函數，zoom即為定義的該函數中的一個函數zoomfunc，測試可見相關的測試代碼。

參考文獻

1. 最優化方法
2. 用「人話」解釋不精確線搜索中的Armijo-Goldstein準則及Wolfe-Powell準則
3. 無約束優化方法讀書筆記—入門篇

推薦閱讀：