无约束优化方法
1.1問題定義
1.1.1優化問題定義
最優化問題數學上定義，最優化問題的一般形式為
?????????????????????????????????? （1）
其中的是自變量，f(x)是目標函數，為約束集或者說可行域。
可行域這個東西，有等式約束，也有不等式約束，或者沒有約束，這次的精力主要還是集中在無約束的優化問題上，如果有精力，再討論有約束的。
1.1.2最優化方法定義
優化問題的解法叫最優化方法。
最優化方法通常采用迭代的方法求它的最優解，其基本思想是：給定一個初始點。按照某一迭代規則產生一個點列，使得當是有窮點列時，其最后一個點是最優化模型問題的最優解，當是無窮點列時，它有極限點，且其極限點是最優化模型問題的最優解。一個好的算法應具備的典型特征為：迭代點能穩定地接近局部極小值點的鄰域，然后迅速收斂于。當給定的某個收斂準則滿足時，迭代即終止。
好吧，上面是一堆描述，來點定義，設為第k次迭代點，第k次搜索方向，為第k次步長因子，則第k次迭代為
??? ? ? ? ? ? ? （2）
然后后面的工作幾乎都在調整這個項了，不同的步長和不同的搜索方向分別構成了不同的方法。
當然步長和搜索方向是得滿足一些條件，畢竟是求最小值，不能越迭代越大了，下面是一些條件
?????????????????????????? （3）
???????????? （4）
式子（3）的意義是搜索方向必須跟梯度方向（梯度也就是）夾角大于90度，也就是基本保證是向梯度方向的另外一邊搜索，至于為什么要向梯度方向的另外一邊搜索，就是那樣才能保證是向目標函數值更小的方向搜索的，因為梯度方向一般是使目標函數增大的（不增大的情況是目標函數已經到達極值）。
式子（4）的意義就很明顯了，迭代的下一步的目標函數比上一步小。
最優化方法的基本結構為：
給定初始點，
（a）??????確定搜索方向，即按照一定規則，構造目標函數f在點處的下降方向作為搜索方向。
（b）??????確定步長因子，使目標函數值有某種意義的下降。
（c）??????令
若滿足某種終止條件，則停止迭代，得到近似最優解，否則，重復以上步驟。
能不能收斂到最優解是衡量最優化算法的有效性的一個重要方面。
?
1.1.3收斂速度簡介
收斂速度也是衡量最優化方法有效性的一個重要方面。
設算法產生的迭代點列在某種范數意義下收斂，即
?? ? ? （5）
若存在實數（這個不是步長）以及一個與迭代次數k無關的常數，使得
?? （6）
則稱算法產生的迭代點列具有階收斂速度。特別地，常用的說法有以下幾種。
（a）????? 當，時，迭代點列叫做具有Q-線性收斂速度；
（b）??????當，q>0時或，q=0時，迭代點列叫做具有Q-超線性收斂速度；
（c）??????當時，迭代點列叫做具有Q-二階收斂速度；
還有一種叫做R-收斂速度，不討論了，有興趣可以查閱相關資料。
一般認為，具有超線性收斂速度和二階收斂速度的方法是比較快速的。但是對于一個算法，收斂性和收斂速度的理論結果并不保證算法在實際執行時一定有好的實際計算特性。一方面是由于這些結果本身并不能保證方法一定有好的特性，另一方面是由于算法忽略了計算過程中十分重要的舍入誤差的影響。
?
1.2步長確定
1.2.1一維搜索
如前面的討論，優化方法的關鍵是構造搜索方向和步長因子，這一節就討論如何確定步長。
設
這樣，從x_k出發，沿搜索方向，確定步長因子，使得
的問題就是關于α的一維搜索問題。注意這里是假設其他的和都確定了的情況下做的搜索，要搜索的變量只有α。
如果求得的，使得目標函數沿搜索方向達到最小，即達到下面的情況
或者說
如果能求導這個最優的，那么這個就稱為最優步長因子，這樣的搜索方法就稱為最優一維搜索，或者精確一維搜索。
但是現實情況往往不是這樣，實際計算中精確的最優步長因子一般比較難求，工作量也大，所以往往會折中用不精確的一維搜索。
不精確的一維搜索，也叫近似一維搜索。方法是選擇，使得目標函數f得到可接受的下降量，即使得下降量是用戶可接受的。也就是，只要找到一個步長，使得目標函數下降了一個比較滿意的量就可以了。
為啥要選步長？看下圖，步長選不好，方向哪怕是對的，也是跑來跑去，不往下走，二維的情況簡單點，高維的可能會弄出一直原地不動的情況來。
?
一維搜索的主要結構如下：1）首先確定包含問題最優解的搜索區間，再采用某種分割技術或插值方法縮小這個區間，進行搜索求解。
當然這個搜索方法主要是適應單峰區間的，就是類似上面的那種，只有一個谷底的。
1.2.1.1確定搜索區間
確定搜索區間一般用進退法，思想是從某一點出發，按某步長，確定函數值呈現“高-低-高”的三個點，一個方向不成功，就退回來，沿相反方向尋找。
下面是步驟。
1.2.1.2搜索求解
搜索求解的話，0.618法簡單實用。雖然Fibonacci法，插值法等等雖然好，復雜，就不多說了。下面是0.618法的步驟。
普通的0.618法要求一維搜索的函數是單峰函數，實際上遇到的函數不一定是單峰函數，這時，可能產生搜索得到的函數值反而大于初始區間端點出函數值的情況。有人建議每次縮小區間是，不要只比較兩個內點處的函數值，而是比較兩內點和兩端點處的函數值。當左邊第一個或第二個點是這四個點中函數值最小的點是，丟棄右端點，構成新的搜索區間；否則，丟棄左端點，構成新的搜索區間，經過這樣的修改，算法會變得可靠些。步驟就不列了。
1.2.2不精確一維搜索方法
一維搜索過程是最優化方法的基本組成部分，精確的一維搜索方法往往需要花費很大的工作量。特別是迭代點遠離問題的解時，精確地求解一個一維子問題通常不是十分有效的。另外，在實際上，很多最優化方法，例如牛頓法和擬牛頓法，其收斂速度并不依賴于精確一維搜索過程。因此，只要保證目標函數f(x)在每一步都有滿意的下降，這樣就可以大大節省工作量。
有幾位科學家Armijo(1966)和Goldstein(1965)分別提出了不精確一維搜索過程。設
??????? （2.5.1）
是一個區間。看下圖
在圖中，區間J=(0,a)。為了保證目標函數單調下降，同時要求f的下降不是太小（如果f的下降太小，可能導致序列的極限值不是極小值），必須避免所選擇的α太靠近區間j的短短。一個合理的要求是
??????????????????????? （2.5.2）
????????????? （2.5.3）
其中0<ρ<1/2，。滿足(2.5.2)要求的α_k構成區間J_1=(0,c]，這就扔掉了區間J右端附件的點。但是為了避免α太小的情況，又加上了另一個要求(2.5.3)，這個要求扔掉了區間J的左端點附件的點。看圖中和兩條虛線夾出來的區間J_2=[b,c]就是滿足條件(2.5.2)和(2.5.3)的搜索區間，稱為可接受區間。條件(2.5.2)和(2.5.3)稱為Armijo-Goldstein準則。無論用什么辦法得到步長因子α，只要滿足條件(2.5.2)和(2.5.3)，就可以稱它為可接受步長因子。
其中這個要求是必須的，因為不用這個條件，可能會影響牛頓法和擬牛頓法的超線性收斂。
在圖中可以看到一種情況，極小值e也被扔掉了，為了解決這種情況，Wolfe-Powell準則給出了一個更簡單的條件代替
?????????????????????????????? （2.5.4）
其幾何解釋是在可接受點處切線的斜率大于或等于初始斜率的σ倍。準則(2.5.2)和(2.5.4)稱為Wolfe-Powell準則，其可接受區間為J_3=[e,c]。
要求ρ<σ<1是必要的，它保證了滿足不精確線性搜索準則的步長因子的存在，不這么弄，可能這個虛線會往下壓，沒有交點，就搞不出一個區間來了。
一般地，σ值越小，線性搜索越精確。取σ=0.1，就得到一個相當精確的線性搜索，而取σ=0.9，則得到一個相當弱的線性搜索。不過σ值越小，工作量越大。所以不精確線性搜索不要求過小的σ，通常可取ρ=0.1，σ=0.4。
下面就給出Armijo-Goldstein準則和Wolfe-Powell準則的框圖。
從算法框圖中可以看出，兩種方法是類似的，只是在準則不成立，需要計算新的時，一個利用了簡單的求區間中點的方法，另一個采用了二次插值方法。
算法步驟只給出Armijo-Goldstein不精確一維搜索方法的，下面就是
好了，說到這，確定步長的方法也說完了，其實方法不少，實際用到的肯定是最簡單的幾種，就把簡單的幾種提了一下，至于為什么這樣，收斂如何，證明的東西大家可以去書中慢慢看。
?
1.3方向確定
1.3.1最速下降法
最速下降法以負梯度方向作為最優化方法的下降方向，又稱為梯度下降法，是最簡單實用的方法。
1.3.1.1算法步驟
下面是步驟。
看個例子。
這個選步長的方法是對二次函數下的特殊情況，是比較快而且好的顯式形式，說明步長選得好，收斂很快。
1.3.1.2缺點
數值實驗表明，當目標函數的等值線接近一個圓（球）時，最速下降法下降較快，當目標函數的等值線是一個扁長的橢球是，最速下降法開始幾步下降較快，后來就出現鋸齒線性，下降就十分緩慢。原因是一維搜索滿足，即，這表明在相鄰兩個迭代點上函數f(x)的兩個梯度繁星是互相直交（正交）的。即，兩個搜索方向互相直交，就產生了鋸齒性質。當接近極小點時，步長越小，前進越慢。
下圖是鋸齒的一個圖。
1.3.2牛頓法
1.3.2.1算法思想和步驟
牛頓法的基本思想是利用目標函數的二次Taylor展開，并將其極小化。
設f(x)是二次可微實函數，，Hesse矩陣正定。在附件用二次Taylor展開近似f，
其中，，為f(x)的二次近似。將上式右邊極小化，便得
這就是牛頓迭代公式。在這個公式中，步長因子。令,，則上面的迭代式也可以寫成。
其中的Hesse矩陣的形式如下。
一個例子如下。
對于正定二次函數，牛頓法一步就可以得到最優解。
對于非二次函數，牛頓法并不能保證經過有限次迭代求得最優解，但由于目標函數在極小點附近近似于二次函數，所以當初始點靠近極小點時，牛頓法的收斂速度一般是快的。
當初始點遠離最優解，不一定正定，牛頓方向不一定是下降方向，其收斂性不能保證，這說明步長一直是1是不合適的，應該在牛頓法中采用某種一維搜索來確定步長因子。但是要強調一下，僅當步長因子收斂到1時，牛頓法才是二階收斂的。
這時的牛頓法稱為阻尼牛頓法，步驟如下。
下面看個例子。
這樣的牛頓法是總體收斂的。
1.3.2.2缺點
牛頓法面臨的主要困難是Hesse矩陣不正定。這時候二次模型不一定有極小點，甚至沒有平穩點。當不正定時，二次模型函數是無界的。
為了克服這種困難，有多種方法，常用的方法是使牛頓方向偏向最速下降方向。具體做法是將Hesse矩陣改變成，其中，使得正定。一般希望是比較小，最好是剛剛好能使正定。
1.3.3擬牛頓法
牛頓法在實際應用中需要存儲二階導數信息和計算一個矩陣的逆，這對計算機的時間和空間要求都比較高，也容易遇到不正定的Hesse矩陣和病態的Hesse矩陣，導致求出來的逆很古怪，從而算法會沿一個不理想的方向去迭代。
有人提出了介于最速下降法與牛頓法之間的方法。一類是共軛方向法，典型的是共軛梯度法，還有擬牛頓法。
其中擬牛頓法簡單實用，這里就特地介紹，其他方法感興趣的讀者可以去看相關資料。
1.3.3.1算法思想和步驟
牛頓法的成功的關鍵是利用了Hesse矩陣提供的曲率信息。但是計算Hesse矩陣工作量大，并且有些目標函數的Hesse矩陣很難計算，甚至不好求出，這就使得僅利用目標函數的一階導數的方法更受歡迎。擬牛頓法就是利用目標函數值f和一階導數g（梯度）的信息，構造出目標函數的曲率近似，而不需要明顯形成Hesse矩陣，同時具有收斂速度快的特點。
設在開集上二次可微，f在附近的二次近似為
兩邊求導，得
令，得
其中，是梯度。那么，只要構造出Hesse矩陣的逆近似滿足這種上式就可以，即滿足關系
這個關系就是擬牛頓條件或擬牛頓方程。
擬牛頓法的思想就是——用一個矩陣去近似Hesse矩陣的逆矩陣，這樣就避免了計算矩陣的逆。
當然需要滿足一些條件：
(a)????是一個正定的矩陣
(b)????如果存在，則。
(c)????初始正定矩陣取定后，應該由遞推給出，即；其中是修正矩陣，是修正公式。
常用而且有效的修正公式是BFGS公式，如下
下面給出BFGS公式下的擬牛頓法
在上述步驟中，初始正定矩陣通常取為單位矩陣，即。這樣，擬牛頓法的第一次迭代相當于一個最速下降迭代。
1.3.3.2優缺點
與牛頓法相比，有兩個優點：
(a)????僅需一階導數
(b)????校正保持正定性，因而下降性質成立
(c)????無需計算逆矩陣，但具有超線性收斂速度
(d)????每次迭代僅需要次乘法計算
缺點是初始點距離最優解遠時速度還是慢。
解決方法是，迭代前期用最速下降法進行迭代，得到一定解以后用擬牛頓法迭代。
?
?
致謝
Deep Learning高質量交流群里的多位同學@ ParadiseLost，@一路走來 等等，那個MathType太好用了。
?
參考文獻
【1】最優化理論與方法。袁亞湘，孫文瑜
總結
- 上一篇： 七种常用特征工程技术
- 下一篇： 用户特征工程详细解读