轉(zhuǎn)載請(qǐng)注明出處：http://www.codelast.com/

line search（一維搜索，或線搜索）是最優(yōu)化（Optimization）算法中的一個(gè)基礎(chǔ)步驟/算法。它可以分為精確的一維搜索以及不精確的一維搜索兩大類。
在本文中，我想用“人話”解釋一下不精確的一維搜索的兩大準(zhǔn)則：Armijo-Goldstein準(zhǔn)則 ＆ Wolfe-Powell準(zhǔn)則。
之所以這樣說，是因?yàn)槲易x到的所有最優(yōu)化的書或資料，從來沒有一個(gè)可以用初學(xué)者都能理解的方式來解釋這兩個(gè)準(zhǔn)則，它們要么是長(zhǎng)篇大論、把一堆數(shù)學(xué)公式丟給你去琢磨；要么是簡(jiǎn)短省略、直接略過了解釋的步驟就一句話跨越千山萬水得出了結(jié)論。
每當(dāng)看到這些書的時(shí)候，我腦子里就一個(gè)反應(yīng)：你們就不能寫人話嗎？

我下面就嘗試用通俗的語言來描述一下這兩個(gè)準(zhǔn)則。

【1】為什么要遵循這些準(zhǔn)則

由于采用了不精確的一維搜索，所以，為了能讓算法收斂（即：求得極小值），人們逐漸發(fā)現(xiàn)、證明了一些規(guī)律，當(dāng)你遵循這些規(guī)律的時(shí)候，算法就很有可能收斂。因此，為了達(dá)到讓算法收斂的目的，我們就要遵循這些準(zhǔn)則。如果你不愿意遵循這些已經(jīng)公認(rèn)有效的準(zhǔn)則，而是要按自己的準(zhǔn)則來設(shè)計(jì)算法，那么恭喜你，如果你能證明你的做法是有效的，未來若干年后，書本里可能也會(huì)出現(xiàn)你的名字。

文章來源：http://www.codelast.com/

【2】Armijo-Goldstein準(zhǔn)則

此準(zhǔn)則是在196X年的時(shí)候由Armijo和Goldstein提出的，當(dāng)然我沒有具體去搜過這倆人是誰。在有的資料里，你可能會(huì)看到“Armijo rule”（Armijo準(zhǔn)則）的說法，可能是同一回事，不過，任何一個(gè)對(duì)此作出重要貢獻(xiàn)的人都是不可抹殺的，不是么？

Armijo-Goldstein準(zhǔn)則的核心思想有兩個(gè)：①目標(biāo)函數(shù)值應(yīng)該有足夠的下降；②一維搜索的步長(zhǎng)α不應(yīng)該太小。

這兩個(gè)思想的意圖非常明顯。由于最優(yōu)化問題的目的就是尋找極小值，因此，讓目標(biāo)函數(shù)函數(shù)值“下降”是我們努力的方向，所以①正是想要保證這一點(diǎn)。

同理，②也類似：如果一維搜索的步長(zhǎng)α太小了，那么我們的搜索類似于在原地打轉(zhuǎn)，可能也是在浪費(fèi)時(shí)間和精力。

文章來源：http://www.codelast.com/
有了這兩個(gè)指導(dǎo)思想，我們來看看Armijo-Goldstein準(zhǔn)則的數(shù)學(xué)表達(dá)式：

其中，?0<ρ<12?
文章來源：http://www.codelast.com/
(1)為什么要規(guī)定?ρ∈(0,12)?這個(gè)條件？其實(shí)可以證明：如果沒有這個(gè)條件的話，將影響算法的超線性收斂性（定義看這個(gè)鏈接，第4條）。在這個(gè)速度至關(guān)重要的時(shí)代，沒有超線性收斂怎么活啊！(開個(gè)玩笑)
具體的證明過程，大家可以參考袁亞湘寫的《最優(yōu)化理論與方法》一書，我沒有仔細(xì)看，我覺得對(duì)初學(xué)者，不用去管它。
(2)第1個(gè)不等式的左邊式子的泰勒展開式為：
f(xk+αkdk)=f(xk)+αkgkTdk+o(αk)?
去掉高階無窮小，剩下的部分為：?f(xk)+αkgkTdk?
而第一個(gè)不等式右邊與之只差一個(gè)系數(shù)?ρ?
我們已知了?gkTdk<0?（這是?dk?為下降方向的充要條件），并且?ρ∈(0,12)?，因此，1式右邊仍然是一個(gè)比?f(xk)?小的數(shù)，即：
f(xk)+αkρgkTdk<f(xk)?
也就是說函數(shù)值是下降的（下降是最優(yōu)化的目標(biāo)）。
文章來源：http://www.codelast.com/
(3)由于?ρ∈(0,12)?且?gkTdk<0?（?dk?是一個(gè)下降方向的充要條件），故第2個(gè)式子右邊比第1個(gè)式子右邊要小，即：
αk(1?ρ)gkTdk<αkρgkTdk<0?
如果步長(zhǎng)?α?太小的話，會(huì)導(dǎo)致這個(gè)不等式接近于不成立的邊緣。因此，式2就保證了?α?不能太小。
(4)我還要把很多書中都用來描述Armijo-Goldstein準(zhǔn)則的一幅圖搬出來說明一下（親自手繪）：

文章來源：http://www.codelast.com/
橫坐標(biāo)是?α?，縱坐標(biāo)是?f?，表示在?xk,dk?均為常量、?α?為自變量變化的情況下，目標(biāo)函數(shù)值隨之變化的情況。
之所以說?xk,dk?均為常量，是因?yàn)樵谝痪S搜索中，在某一個(gè)確定的點(diǎn)?xk?上，搜索方向?dk?確定后，我們只需要找到一個(gè)合適的步長(zhǎng)?α?就可以了。
當(dāng)?x?為常量，?α?為自變量時(shí)，?f(x+αd)?可能是非線性函數(shù)（例如目標(biāo)函數(shù)為?y=x2?時(shí)）。因此圖中是一條曲線。
右上角的?f(xk+αdk)?并不是表示一個(gè)特定點(diǎn)的值，而是表示這條曲線是以?α?為自變量、?xk,dk?為常量的函數(shù)圖形。
當(dāng)?α=0?時(shí)，函數(shù)值為?f(xk)?，如圖中左上方所示。水平的那條虛線是函數(shù)值為?f(xk)?的基線，用于與其他函數(shù)值對(duì)比。
f(xk)+αkρgkTdk?那條線在?f(xk)?下方（前面已經(jīng)分析過了，因?yàn)?gkTdk<0?），?f(xk)+αk(1?ρ)gkTdk?又在?f(xk)+αkρgkTdk?的下方（前面也已經(jīng)分析過了），所以Armijo-Goldstein準(zhǔn)則可能會(huì)把極小值點(diǎn)（可接受的區(qū)間）判斷在區(qū)間bc內(nèi)。顯而易見，區(qū)間bc是有可能把極小值排除在外的（極小值在區(qū)間ed內(nèi)）。
所以，為了解決這個(gè)問題，Wolfe-Powell準(zhǔn)則應(yīng)運(yùn)而生。
文章來源：http://www.codelast.com/
【3】Wolfe-Powell準(zhǔn)則
在某些書中，你會(huì)看到“Wolfe conditions”的說法，應(yīng)該和Wolfe-Powell準(zhǔn)則是一回事——可憐的Powell大神又被無情地忽略了...
Wolfe-Powell準(zhǔn)則也有兩個(gè)數(shù)學(xué)表達(dá)式，其中，第一個(gè)表達(dá)式與Armijo-Goldstein準(zhǔn)則的第1個(gè)式子相同，第二個(gè)表達(dá)式為：

這個(gè)式子已經(jīng)不是關(guān)于函數(shù)值的了，而是關(guān)于梯度的。
此式的幾何解釋為：可接受點(diǎn)處的切線斜率≥初始斜率的?σ?倍。
上面的圖已經(jīng)標(biāo)出了?σgTkdk?那條線（即?e?點(diǎn)處的切線），而初始點(diǎn)（?α=0?的點(diǎn)）處的切線是比?e?點(diǎn)處的切線要“斜”的，由于?σ∈(ρ,1)?，使得?e?點(diǎn)處的切線變得“不那么斜”了——不知道這種極為通俗而不夠嚴(yán)謹(jǐn)?shù)恼f法，是否有助于你理解。
這樣做的結(jié)果就是，我們將極小值包含在了可接受的區(qū)間內(nèi)（?e?點(diǎn)右邊的區(qū)間）。
文章來源：http://www.codelast.com/
Wolfe-Powell準(zhǔn)則到這里還沒有結(jié)束！在某些書中，你會(huì)看到用另一個(gè)所謂的“更強(qiáng)的條件”來代替(3)式，即：

這個(gè)式子和(3)式相比，就是左邊加了一個(gè)絕對(duì)值符號(hào)，右邊換了一下正負(fù)號(hào)（因?yàn)?gTkdk<0?，所以??σgTkdk>0?）。
這樣做的結(jié)果就是：可接受的區(qū)間被限制在了?[b,d]?內(nèi)，如圖：

圖中紅線即為極小值被“夾擊”的生動(dòng)演示。

總結(jié)

以上是生活随笔為你收集整理的线搜索中的Armijo-Goldstein准则及Wolfe-Powell准则的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。