1.1問題定義

1.1.1優(yōu)化問題定義

最優(yōu)化問題數(shù)學(xué)上定義，最優(yōu)化問題的一般形式為

?????????????????????????????????? （1）

其中的是自變量，f(x)是目標(biāo)函數(shù)，為約束集或者說可行域。

可行域這個東西，有等式約束，也有不等式約束，或者沒有約束，這次的精力主要還是集中在無約束的優(yōu)化問題上，如果有精力，再討論有約束的。

1.1.2最優(yōu)化方法定義

優(yōu)化問題的解法叫最優(yōu)化方法。
最優(yōu)化方法通常采用迭代的方法求它的最優(yōu)解，其基本思想是：給定一個初始點(diǎn)。按照某一迭代規(guī)則產(chǎn)生一個點(diǎn)列，使得當(dāng)是有窮點(diǎn)列時，其最后一個點(diǎn)是最優(yōu)化模型問題的最優(yōu)解，當(dāng)是無窮點(diǎn)列時，它有極限點(diǎn)，且其極限點(diǎn)是最優(yōu)化模型問題的最優(yōu)解。一個好的算法應(yīng)具備的典型特征為：迭代點(diǎn)能穩(wěn)定地接近局部極小值點(diǎn)的鄰域，然后迅速收斂于。當(dāng)給定的某個收斂準(zhǔn)則滿足時，迭代即終止。

好吧，上面是一堆描述，來點(diǎn)定義，設(shè)為第k次迭代點(diǎn)，第k次搜索方向，為第k次步長因子，則第k次迭代為

??? ? ? ? ? ? ? （2）

然后后面的工作幾乎都在調(diào)整這個項(xiàng)了，不同的步長和不同的搜索方向分別構(gòu)成了不同的方法。

當(dāng)然步長和搜索方向是得滿足一些條件，畢竟是求最小值，不能越迭代越大了，下面是一些條件

?????????????????????????? （3）

???????????? （4）

式子（3）的意義是搜索方向必須跟梯度方向（梯度也就是）夾角大于90度，也就是基本保證是向梯度方向的另外一邊搜索，至于為什么要向梯度方向的另外一邊搜索，就是那樣才能保證是向目標(biāo)函數(shù)值更小的方向搜索的，因?yàn)樘荻确较蛞话闶鞘鼓繕?biāo)函數(shù)增大的（不增大的情況是目標(biāo)函數(shù)已經(jīng)到達(dá)極值）。

式子（4）的意義就很明顯了，迭代的下一步的目標(biāo)函數(shù)比上一步小。

最優(yōu)化方法的基本結(jié)構(gòu)為：

給定初始點(diǎn)，

（a）??????確定搜索方向，即按照一定規(guī)則，構(gòu)造目標(biāo)函數(shù)f在點(diǎn)處的下降方向作為搜索方向。

（b）??????確定步長因子，使目標(biāo)函數(shù)值有某種意義的下降。

（c）??????令

若滿足某種終止條件，則停止迭代，得到近似最優(yōu)解，否則，重復(fù)以上步驟。

能不能收斂到最優(yōu)解是衡量最優(yōu)化算法的有效性的一個重要方面。

?

1.1.3收斂速度簡介

收斂速度也是衡量最優(yōu)化方法有效性的一個重要方面。

設(shè)算法產(chǎn)生的迭代點(diǎn)列在某種范數(shù)意義下收斂，即

?? ? ? （5）

若存在實(shí)數(shù)（這個不是步長）以及一個與迭代次數(shù)k無關(guān)的常數(shù)，使得

?? （6）

則稱算法產(chǎn)生的迭代點(diǎn)列具有階收斂速度。特別地，常用的說法有以下幾種。

（a）????? 當(dāng)，時，迭代點(diǎn)列叫做具有Q-線性收斂速度；

（b）??????當(dāng)，q>0時或，q=0時，迭代點(diǎn)列叫做具有Q-超線性收斂速度；

（c）??????當(dāng)時，迭代點(diǎn)列叫做具有Q-二階收斂速度；

還有一種叫做R-收斂速度，不討論了，有興趣可以查閱相關(guān)資料。

一般認(rèn)為，具有超線性收斂速度和二階收斂速度的方法是比較快速的。但是對于一個算法，收斂性和收斂速度的理論結(jié)果并不保證算法在實(shí)際執(zhí)行時一定有好的實(shí)際計(jì)算特性。一方面是由于這些結(jié)果本身并不能保證方法一定有好的特性，另一方面是由于算法忽略了計(jì)算過程中十分重要的舍入誤差的影響。

?

1.2步長確定

1.2.1一維搜索

如前面的討論，優(yōu)化方法的關(guān)鍵是構(gòu)造搜索方向和步長因子，這一節(jié)就討論如何確定步長。

設(shè)

這樣，從x_k出發(fā)，沿搜索方向，確定步長因子，使得

的問題就是關(guān)于α的一維搜索問題。注意這里是假設(shè)其他的和都確定了的情況下做的搜索，要搜索的變量只有α。
如果求得的，使得目標(biāo)函數(shù)沿搜索方向達(dá)到最小，即達(dá)到下面的情況

或者說

如果能求導(dǎo)這個最優(yōu)的，那么這個就稱為最優(yōu)步長因子，這樣的搜索方法就稱為最優(yōu)一維搜索，或者精確一維搜索。
但是現(xiàn)實(shí)情況往往不是這樣，實(shí)際計(jì)算中精確的最優(yōu)步長因子一般比較難求，工作量也大，所以往往會折中用不精確的一維搜索。
不精確的一維搜索，也叫近似一維搜索。方法是選擇，使得目標(biāo)函數(shù)f得到可接受的下降量，即使得下降量是用戶可接受的。也就是，只要找到一個步長，使得目標(biāo)函數(shù)下降了一個比較滿意的量就可以了。
為啥要選步長？看下圖，步長選不好，方向哪怕是對的，也是跑來跑去，不往下走，二維的情況簡單點(diǎn)，高維的可能會弄出一直原地不動的情況來。
?

一維搜索的主要結(jié)構(gòu)如下：1）首先確定包含問題最優(yōu)解的搜索區(qū)間，再采用某種分割技術(shù)或插值方法縮小這個區(qū)間，進(jìn)行搜索求解。

當(dāng)然這個搜索方法主要是適應(yīng)單峰區(qū)間的，就是類似上面的那種，只有一個谷底的。

1.2.1.1確定搜索區(qū)間

確定搜索區(qū)間一般用進(jìn)退法，思想是從某一點(diǎn)出發(fā)，按某步長，確定函數(shù)值呈現(xiàn)“高-低-高”的三個點(diǎn)，一個方向不成功，就退回來，沿相反方向?qū)ふ摇?/p>

下面是步驟。

1.2.1.2搜索求解

搜索求解的話，0.618法簡單實(shí)用。雖然Fibonacci法，插值法等等雖然好，復(fù)雜，就不多說了。下面是0.618法的步驟。

普通的0.618法要求一維搜索的函數(shù)是單峰函數(shù)，實(shí)際上遇到的函數(shù)不一定是單峰函數(shù)，這時，可能產(chǎn)生搜索得到的函數(shù)值反而大于初始區(qū)間端點(diǎn)出函數(shù)值的情況。有人建議每次縮小區(qū)間是，不要只比較兩個內(nèi)點(diǎn)處的函數(shù)值，而是比較兩內(nèi)點(diǎn)和兩端點(diǎn)處的函數(shù)值。當(dāng)左邊第一個或第二個點(diǎn)是這四個點(diǎn)中函數(shù)值最小的點(diǎn)是，丟棄右端點(diǎn)，構(gòu)成新的搜索區(qū)間；否則，丟棄左端點(diǎn)，構(gòu)成新的搜索區(qū)間，經(jīng)過這樣的修改，算法會變得可靠些。步驟就不列了。

1.2.2不精確一維搜索方法

一維搜索過程是最優(yōu)化方法的基本組成部分，精確的一維搜索方法往往需要花費(fèi)很大的工作量。特別是迭代點(diǎn)遠(yuǎn)離問題的解時，精確地求解一個一維子問題通常不是十分有效的。另外，在實(shí)際上，很多最優(yōu)化方法，例如牛頓法和擬牛頓法，其收斂速度并不依賴于精確一維搜索過程。因此，只要保證目標(biāo)函數(shù)f(x)在每一步都有滿意的下降，這樣就可以大大節(jié)省工作量。

有幾位科學(xué)家Armijo(1966)和Goldstein(1965)分別提出了不精確一維搜索過程。設(shè)

??????? （2.5.1）

是一個區(qū)間。看下圖

在圖中，區(qū)間J=(0,a)。為了保證目標(biāo)函數(shù)單調(diào)下降，同時要求f的下降不是太小（如果f的下降太小，可能導(dǎo)致序列的極限值不是極小值），必須避免所選擇的α太靠近區(qū)間j的短短。一個合理的要求是

??????????????????????? （2.5.2）

????????????? （2.5.3）

其中0<ρ<1/2，。滿足(2.5.2)要求的α_k構(gòu)成區(qū)間J_1=(0,c]，這就扔掉了區(qū)間J右端附件的點(diǎn)。但是為了避免α太小的情況，又加上了另一個要求(2.5.3)，這個要求扔掉了區(qū)間J的左端點(diǎn)附件的點(diǎn)。看圖中和兩條虛線夾出來的區(qū)間J_2=[b,c]就是滿足條件(2.5.2)和(2.5.3)的搜索區(qū)間，稱為可接受區(qū)間。條件(2.5.2)和(2.5.3)稱為Armijo-Goldstein準(zhǔn)則。無論用什么辦法得到步長因子α，只要滿足條件(2.5.2)和(2.5.3)，就可以稱它為可接受步長因子。

其中這個要求是必須的，因?yàn)椴挥眠@個條件，可能會影響牛頓法和擬牛頓法的超線性收斂。

在圖中可以看到一種情況，極小值e也被扔掉了，為了解決這種情況，Wolfe-Powell準(zhǔn)則給出了一個更簡單的條件代替

?????????????????????????????? （2.5.4）

其幾何解釋是在可接受點(diǎn)處切線的斜率大于或等于初始斜率的σ倍。準(zhǔn)則(2.5.2)和(2.5.4)稱為Wolfe-Powell準(zhǔn)則，其可接受區(qū)間為J_3=[e,c]。

要求ρ<σ<1是必要的，它保證了滿足不精確線性搜索準(zhǔn)則的步長因子的存在，不這么弄，可能這個虛線會往下壓，沒有交點(diǎn)，就搞不出一個區(qū)間來了。

一般地，σ值越小，線性搜索越精確。取σ=0.1，就得到一個相當(dāng)精確的線性搜索，而取σ=0.9，則得到一個相當(dāng)弱的線性搜索。不過σ值越小，工作量越大。所以不精確線性搜索不要求過小的σ，通常可取ρ=0.1，σ=0.4。

下面就給出Armijo-Goldstein準(zhǔn)則和Wolfe-Powell準(zhǔn)則的框圖。

從算法框圖中可以看出，兩種方法是類似的，只是在準(zhǔn)則不成立，需要計(jì)算新的時，一個利用了簡單的求區(qū)間中點(diǎn)的方法，另一個采用了二次插值方法。

算法步驟只給出Armijo-Goldstein不精確一維搜索方法的，下面就是

好了，說到這，確定步長的方法也說完了，其實(shí)方法不少，實(shí)際用到的肯定是最簡單的幾種，就把簡單的幾種提了一下，至于為什么這樣，收斂如何，證明的東西大家可以去書中慢慢看。

?

1.3方向確定

1.3.1最速下降法

最速下降法以負(fù)梯度方向作為最優(yōu)化方法的下降方向，又稱為梯度下降法，是最簡單實(shí)用的方法。

1.3.1.1算法步驟

下面是步驟。

看個例子。

這個選步長的方法是對二次函數(shù)下的特殊情況，是比較快而且好的顯式形式，說明步長選得好，收斂很快。

1.3.1.2缺點(diǎn)

數(shù)值實(shí)驗(yàn)表明，當(dāng)目標(biāo)函數(shù)的等值線接近一個圓（球）時，最速下降法下降較快，當(dāng)目標(biāo)函數(shù)的等值線是一個扁長的橢球是，最速下降法開始幾步下降較快，后來就出現(xiàn)鋸齒線性，下降就十分緩慢。原因是一維搜索滿足，即，這表明在相鄰兩個迭代點(diǎn)上函數(shù)f(x)的兩個梯度繁星是互相直交（正交）的。即，兩個搜索方向互相直交，就產(chǎn)生了鋸齒性質(zhì)。當(dāng)接近極小點(diǎn)時，步長越小，前進(jìn)越慢。
下圖是鋸齒的一個圖。

1.3.2牛頓法

1.3.2.1算法思想和步驟

牛頓法的基本思想是利用目標(biāo)函數(shù)的二次Taylor展開，并將其極小化。
設(shè)f(x)是二次可微實(shí)函數(shù)，，Hesse矩陣正定。在附件用二次Taylor展開近似f，

其中，，為f(x)的二次近似。將上式右邊極小化，便得

這就是牛頓迭代公式。在這個公式中，步長因子。令,，則上面的迭代式也可以寫成。

其中的Hesse矩陣的形式如下。

一個例子如下。

對于正定二次函數(shù)，牛頓法一步就可以得到最優(yōu)解。
對于非二次函數(shù)，牛頓法并不能保證經(jīng)過有限次迭代求得最優(yōu)解，但由于目標(biāo)函數(shù)在極小點(diǎn)附近近似于二次函數(shù)，所以當(dāng)初始點(diǎn)靠近極小點(diǎn)時，牛頓法的收斂速度一般是快的。
當(dāng)初始點(diǎn)遠(yuǎn)離最優(yōu)解，不一定正定，牛頓方向不一定是下降方向，其收斂性不能保證，這說明步長一直是1是不合適的，應(yīng)該在牛頓法中采用某種一維搜索來確定步長因子。但是要強(qiáng)調(diào)一下，僅當(dāng)步長因子收斂到1時，牛頓法才是二階收斂的。
這時的牛頓法稱為阻尼牛頓法，步驟如下。

下面看個例子。

這樣的牛頓法是總體收斂的。

1.3.2.2缺點(diǎn)

牛頓法面臨的主要困難是Hesse矩陣不正定。這時候二次模型不一定有極小點(diǎn)，甚至沒有平穩(wěn)點(diǎn)。當(dāng)不正定時，二次模型函數(shù)是無界的。
為了克服這種困難，有多種方法，常用的方法是使牛頓方向偏向最速下降方向。具體做法是將Hesse矩陣改變成，其中，使得正定。一般希望是比較小，最好是剛剛好能使正定。

1.3.3擬牛頓法

牛頓法在實(shí)際應(yīng)用中需要存儲二階導(dǎo)數(shù)信息和計(jì)算一個矩陣的逆，這對計(jì)算機(jī)的時間和空間要求都比較高，也容易遇到不正定的Hesse矩陣和病態(tài)的Hesse矩陣，導(dǎo)致求出來的逆很古怪，從而算法會沿一個不理想的方向去迭代。

有人提出了介于最速下降法與牛頓法之間的方法。一類是共軛方向法，典型的是共軛梯度法，還有擬牛頓法。

其中擬牛頓法簡單實(shí)用，這里就特地介紹，其他方法感興趣的讀者可以去看相關(guān)資料。

1.3.3.1算法思想和步驟

牛頓法的成功的關(guān)鍵是利用了Hesse矩陣提供的曲率信息。但是計(jì)算Hesse矩陣工作量大，并且有些目標(biāo)函數(shù)的Hesse矩陣很難計(jì)算，甚至不好求出，這就使得僅利用目標(biāo)函數(shù)的一階導(dǎo)數(shù)的方法更受歡迎。擬牛頓法就是利用目標(biāo)函數(shù)值f和一階導(dǎo)數(shù)g（梯度）的信息，構(gòu)造出目標(biāo)函數(shù)的曲率近似，而不需要明顯形成Hesse矩陣，同時具有收斂速度快的特點(diǎn)。
設(shè)在開集上二次可微，f在附近的二次近似為

兩邊求導(dǎo)，得

令，得

其中，是梯度。那么，只要構(gòu)造出Hesse矩陣的逆近似滿足這種上式就可以，即滿足關(guān)系

這個關(guān)系就是擬牛頓條件或擬牛頓方程。
擬牛頓法的思想就是——用一個矩陣去近似Hesse矩陣的逆矩陣，這樣就避免了計(jì)算矩陣的逆。
當(dāng)然需要滿足一些條件：

(a)????是一個正定的矩陣

(b)????如果存在，則。

(c)????初始正定矩陣取定后，應(yīng)該由遞推給出，即；其中是修正矩陣，是修正公式。

常用而且有效的修正公式是BFGS公式，如下

下面給出BFGS公式下的擬牛頓法

在上述步驟中，初始正定矩陣通常取為單位矩陣，即。這樣，擬牛頓法的第一次迭代相當(dāng)于一個最速下降迭代。

1.3.3.2優(yōu)缺點(diǎn)

與牛頓法相比，有兩個優(yōu)點(diǎn)：

(a)????僅需一階導(dǎo)數(shù)

(b)????校正保持正定性，因而下降性質(zhì)成立

(c)????無需計(jì)算逆矩陣，但具有超線性收斂速度

(d)????每次迭代僅需要次乘法計(jì)算

缺點(diǎn)是初始點(diǎn)距離最優(yōu)解遠(yuǎn)時速度還是慢。

解決方法是，迭代前期用最速下降法進(jìn)行迭代，得到一定解以后用擬牛頓法迭代。

?

?

致謝

Deep Learning高質(zhì)量交流群里的多位同學(xué)@ ParadiseLost，@一路走來 等等，那個MathType太好用了。

?

參考文獻(xiàn)

【1】最優(yōu)化理論與方法。袁亞湘，孫文瑜

總結(jié)

以上是生活随笔為你收集整理的无约束优化方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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