A. 最優化理論的方法
1、無約束最優化
2、帶約束最優化
即研究的是 函數最小化 問題。（舉例說明）
1、選定初始點
2、確定搜索方向 ,依照一定規則，構造 在 點處的下降方向作為搜索方向。
3、確定步長因子 ，使目標函數值有某種意義的下降
4、令 , 若 滿足某種終止條件，則停止迭代，得到最優解，否則重復（2）步驟。
1、考慮二次式
（問題：為什麼是二次式呢？）
2、二次式的可視化
令上式中
3、應用梯度方法找出下降方向
問題1：是不是沿梯度下降的方向去選擇方向就最好呢？——The Steepest Descent
問題 2：最優點有什麼性質？
4、對於二次型有
5、找出下降的步長
1）精確步長（精確一維線性搜索）
2）近似步長（不精確）
6、常見最優化方法
1）最速下降法
2）牛頓法
3）共軛梯度法
4）擬牛頓法
B. 幾種常用最優化方法
學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(optimization)有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。
1. 梯度下降法（Gradient Descent）
梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。 梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。
梯度下降 法的缺點：
（1）靠近極小值時收斂速度減慢;
（2）直線搜索時可能會產生一些問題；
（3）可能會「之字形」地下降。
在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。
比如對一個線性回歸（Linear Logistics）模型，假設下面的h(x)是要擬合的函數，J( )為損失函數， 是參數，要迭代求解的值，求解出來了那最終要擬合的函數h( )就出來了。其中m是訓練集的樣本個數，n是特徵的個數。
1）批量梯度下降法（Batch Gradient Descent，BGD）
（1）將J( )對 求偏導，得到每個theta對應的的梯度：
(2）由於是要最小化風險函數，所以按每個參數 的梯度負方向，來更新每個 ：
（3）從上面公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度會相當的慢。所以，這就引入了另外一種方法——隨機梯度下降。
對於批量梯度下降法，樣本個數m，x為n維向量，一次迭代需要把m個樣本全部帶入計算，迭代一次計算量為m*n2。
2）隨機梯度下降（Stochastic Gradient Descent，SGD）
（1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：
（2）每個樣本的損失函數，對 求偏導得到對應梯度，來更新 ：
（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能只用其中幾萬條或者幾千條的樣本，就已經將
迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。
隨機梯度下降每次迭代只使用一個樣本，迭代一次計算量為n2，當樣本個數m很大的時候，隨機梯度下降迭代一次的速度要遠高於批量梯度下降方法。 兩者的關系可以這樣理解：隨機梯度下降方法以損失很小的一部分精確度和增加一定數量的迭代次數為代價，換取了總體的優化效率的提升。增加的迭代次數遠遠小於樣本的數量。
對批量梯度下降法和隨機梯度下降法的總結：
批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小，但是對於大規模樣本問題效率低下。
隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近，適用於大規模訓練樣本情況。
2. 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）
1）牛頓法（Newton's method）
牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數 f ( x )的泰勒級數的前面幾項來尋找方程 f ( x ) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。
具體步驟：
首先，選擇一個接近函數 f ( x )零點的x0，計算相應的 f ( x 0)和切線斜率 f ' ( x 0)（這里 f ' 表示函數 f 的導數）。然後我們計算穿過點( x 0, f ( x 0))並且斜率為 f '( x 0)的直線和 x 軸的交點的 x 坐標，也就是求如下方程的解：
我們將新求得的點的 x 坐標命名為 x 1，通常 x 1會比 x 0更接近方程 f ( x ) = 0的解。因此我們現在可以利用 x 1開始下一輪迭代。迭代公式可化簡為如下所示：
已經證明，如果 f '是連續的，並且待求的零點 x 是孤立的，那麼在零點 x 周圍存在一個區域，只要初始值 x 0位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果 f ' ( x )不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。下圖為一個牛頓法執行過程的例子。
由於牛頓法是基於當前位置的切線來確定下一次的位置，所以牛頓法又被很形象地稱為是"切線法"。
關於牛頓法和梯度下降法的效率對比：
從本質上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優，沒有全局思想。）
根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。
註：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。
牛頓法的優缺點總結：
優點：二階收斂，收斂速度快；
缺點：牛頓法是一種迭代演算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較復雜。
2）擬牛頓法（Quasi-Newton Methods）
擬牛頓法是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。
擬牛頓法的本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。 擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。
具體步驟：
擬牛頓法的基本思想如下。首先構造目標函數在當前迭代xk的二次模型：
這里Bk是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點：
其中我們要求步長ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣Bk 代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣Bk的更新。現在假設得到一個新的迭代xk+1，並得到一個新的二次模型：
我們盡可能地利用上一步的信息來選取Bk。具體地，我們要求
從而得到
這個公式被稱為割線方程。常用的擬牛頓法有DFP演算法和BFGS演算法。
原文鏈接： [Math] 常見的幾種最優化方法 - Poll的筆記 - 博客園
C. 優化方法的理論體系 有哪些方面
1、一維優化方法
2、多維無約束優化方法
3、多維有約束優化方法
4、線性優化方法
5、多目標優化方法
6、離散變數優化方法
7、基於其他理論的優化方法
8、常見的優化算例
9、主要文獻
D. 一維搜索方法分幾類
一維搜索，又稱一維優化，是指求解一維目標函數 f(X) 最優解的過程。一維搜索的方法很多，常用的有試探法和插值法。試探法包括斐波那契法和黃金分割法等；插值法包括牛頓法等
E. 優化方法基礎系列-非精確的一維搜索技術
選擇最優步長的精確搜索方法往往計算量大，特別是當迭代點遠離最優解時，效率很低，而且很多最優化演算法的收斂速度並不依賴於精確的一維搜索過程。這促使一些研究者放寬了一維搜索的精確要求，而去保證目標函數在每次迭代有滿意的下降量，這類方法稱為非精確的一維搜索方法或可接受的一維搜索方法，它可以大大節省計算量。
不精確的一維搜索方法核心問題是選取可接受的步長 使得 得到一個滿意的水平，即足夠的下降且大范圍收斂。因此，研究者提出了一些准則，以滿足不精確搜索能也能收斂的條件。Armijo-Goldstein和Wolf-Powell准則為非精確一維搜索的兩大准則。
Armijo-Goldstein准則核心思想就兩點：
這兩點意圖是非常明顯，由於最優化問題就是尋找極小值，所以使得目標函數值下降，是我們努力的方向，此外如果搜索步長太小，可能原地打轉，影響收斂速度。具體方法如下：
假設 是一個下降方向，記 ，有：
則 的一個合理的下界（保證下降）：
再給其一個上界限制（ 不能太小）:
那麼Armijo-Goldstein准則可描述為：
可接受的 應該滿足：
註：如果 不在這個范圍內，將影響其超線性收斂性。
令 ，即固定 和方向 ，求解滿足條件的步長，則Armijo-Goldstein可寫為：
從上圖和公式中，可以看出 在 的下方， 在 的下方，所以 區間都是在滿足條件的步長。然而，Armijo-Goldstein准則可能會把極值點判斷在可接受的范圍之外，所以為了解決這一問題，Wolf-Powell准則應用而生。
Algorithm 9 Armijo-Goldstein准則
Wolf-Powell准則下界和Armijo-Goldstein准則是一樣的，即：
為了保證足夠的步長以及可接受的區間包含極小值點，上界被定義:
也就是：
其說明在點 處的斜率應該大於起始點斜率的 倍。 是負值，所以上界的含義就是可接受的范圍中斜率應該是接近零的負值或者正值。
此外，還有一種更為嚴苛的准則，稱為強Wolf調節，即：
強Wolf條件使得可接受的范圍的斜率的正值不至於過大，可以將遠離極小值點的步長排除在外。一般 越小，線性搜索越精確，不過 越小，工作量越大，一般取
Algorithm 10 Wolf-Powell 准則
後退法僅採用了Armijo-Goldstein准則的下界限制，即保證函數的下降，此外要求 不要太小即可。其基本思想是：
關於這些准則的有效性，比如步長的存在性，大范圍收斂性質可參閱劉紅英版本的數值規劃基礎或者Numerical Optimization。後來學者們又發展了Curry-Altman步長律、Danilin-Pshenichuyi步長律、De Leone-Grippo步長律等，這些步長律或者准則會在後文的具體優化演算法中有所涉及，使用的過程中可能會大大加速優化方法的收斂。
參考文獻：
[1] Numerical Optimization. Jorge Nocedal
F. 利用0.618法和二次插值法求解一維優化問題的基本思想各是什麼
審題——建模（建立二次函數模型）——解模（求解）——回答（用生活語言回答，即問什麼答什麼）
G. 第七章 一維搜索方法
本章討論的是一維問題的迭代求解方法，這些方法統稱為一維搜索法。
黃金分割法要求某單值一元函數 在閉區間 上是單峰的，即存在唯一的局部最小點。
該方法的思路為挑選 中的點，計算對應的函數值，通過不斷縮小極小點所在的求見，大刀片足夠的精度。
很顯然每次都要計算兩個目標函數值，以保證目標區間的壓縮。
在黃金分割法中， 始終不變，如果允許參數 中途改變，則產生斐波那契數列法。該方法選擇中間點的的原則如下：
高中學過的一階導求法，一階導大於0在左邊，一階導小於0在右邊。
壓縮比為
牛頓法假定函數連續二階可微，這樣可構建一個經過點 的二次函數，該函數在 的一階和二階導數分別為 和 ：
從迭代公式看出，牛頓法需要的是目標函數 的二階導數：
上述方法均需要提供目標函數極小點所在的初始區間。而這一初始區間的尋找需要劃界法確定。
本質就是不斷搜索，找三個點比一比，然後迭代。因為假定函數是單峰的，不需要考慮全局問題。
多維優化問題的迭代球閥，通常每次迭代都包括一維搜索。