前言
大部分機器學習模型的
引數估計
問題都可以寫成最佳化問題。機器學習模型不同，損失函式不同，對應的最佳化問題也各不相同。瞭解最佳化問題的形式和特點，能幫助我們更有效地求解問題，得到模型引數，從而達到學習的目的。
問題1
機器學習中的最佳化問題，哪些是凸最佳化問題，哪些是非凸最佳化問題？請各舉幾個例子。
答：
要回答這個問題，需要先弄明白什麼是凸函式。
一個常用的機器學習模型——
邏輯迴歸
對應的最佳化問題就是凸最佳化問題（
SVM、線性迴歸也是！
）。具體來說，對於二分類問題，Y＝｛1，-1｝，假設模型引數為θ，則邏輯迴歸的最佳化問題為
可以透過驗證目標函式二階 Hessian矩陣的（半）正定性來驗證凸性。
對於凸最佳化問題，所有的區域性極小值都是全域性極小值，因此這類問題一般認為是比較容易求解的問題。
另一方面，
主成分分析對應的最佳化問題是非凸最佳化問題（低秩模型如矩陣分解、深度神經網路模型也是！）
。令X＝［x1，x2，。。。，xn］為資料中心化後構成的矩陣，則主成分分析的最佳化問題為
透過凸函式的定義可以驗證該最佳化問題的目標函式為非凸函式：
令V* 為最佳化問題的全域性極小值，則-V*也是該問題的全域性極小值，且有
這不滿足凸函式的定義，因此主成分分析的最佳化問題為非凸最佳化問題題。一般來說，非凸最佳化問題被認為是比較難求解的問題，
但主成分分析是一個特例，我們可以藉助SVD直接得到主成分分析的全域性極小值。
問題2
經典最佳化演算法有哪些？/假設有一道無約束最佳化問題擺在你面前: #FormatImgID_9# ，其中目標函式L（·）是光滑的。請問求解該問題的最佳化演算法有哪些？它的適用場景是什麼？
答：
分析與解答經典的最佳化演算法可以分為
直接法和迭代法
兩大類。
①直接法
，顧名思義，就是能夠直接給出最佳化問題最優解的方法。這個方法聽起來非常厲害的樣子，但它不是萬能的。
直接法要求目標函式需要滿足兩個條件
。第一個條件是，
L（·）是凸函式。
若L（·）是凸函式，那麼是最優解的
充分必要條件是L（·）在處的梯度為0。
因此，為了能夠直接求解出θ，
第二個條件是，上式有閉式解
。同時滿足這兩個條件的經典例子是嶺迴歸（ Ridge Regression），其目標函式為
稍加推導就能得到最優解
直接法要滿足的這兩個條件限制了它的應用範圍
。
因此，在很多實際問題中，會採用迭代法。迭代法就是迭代地修正對最優解的估計
。假設當前對最優解的估計值為
，希望求解最佳化問題
來得到更好的估計值
迭代法又可以分為一階法和二階法兩類。
1)一階法
對函式L（
）做一階泰勒展開，得到近似式
由於該近似式僅在δ較小時才比較準確，因此在求解δ時一般加上L2正則項：
由此，一階法的迭代公式表示為
其中α稱為學習率。
一階法也稱梯度下降法
，梯度就是目標函式的一階資訊。
2）二階法
對函式L（
）做二階泰勒展開，得到近似式
其中
是函式L在處的 Hessian矩陣。透過求解近似最佳化問題
可以得到二階法的迭代公式
二階法也稱為牛頓法
， Hessian矩陣就是目標函式的二階資訊。
二階法的收斂速度一般要遠快於一階法
，但是在
高維情況下， Hessian矩陣求逆的計算複雜度很大，而且當目標函式非凸時，二階法有可能會收斂到鞍點
（ Saddle Point）。
拓展延伸
①俄羅斯著名數學家Yurii Nesteriv在1983年提出了一階法的加速演算法，該演算法的收斂速率能夠達到一階法收斂速率的理論界。針對二階法矩陣求逆的計算複雜度過高的問題 Charles George Broyden， Roger Fletcher， Donald Goldfarb和 David Shanno於1970年獨立提出了後來被稱為BFGS的演算法114，1989年擴充套件為低儲存的L-bfgs演算法。
②平方根倒數速演算法
參考自：百面機器學習：演算法工程師帶你去面試 - 知乎書店
