凸優化算法原理及講解

凸優化算法是最優化問題中非常重要的一類，也是被研究的很透徹的一類。

對於機器學習來說，如果要優化的問題被證明是凸優化問題，則說明此問題可以被比較好的解決。

求解一個一般性的最優化問題的全局極小值是非常困難的，至少要面臨的問題是：函數可能有多個局部極值點，另外還有鞍點問題。

對於第一個問題，我們找到了一個梯度爲0的點，它是極值點，但不是全局極值，如果一個問題有多個局部極值，則我們要把所有局部極值找出來，然後比較，得到全局極值，這非常困難，而且計算成本相當高。

第二個問題更嚴重，我們找到了梯度爲0的點，但它連局部極值都不是，典型的是這個函數，在0點處，它的導數等於0，但這根本不是極值點：

梯度下降法和牛頓法等基於導數作爲判據的優化算法，找到的都導數/梯度爲0的點，而梯度等於0只是取得極值的必要條件而不是充分條件。

如果我們將這個必要條件變成充分條件，即：問題將會得到簡化。

如果對問題加以限定，是可以保證上面這個條件成立的。

其中的一種限制方案是：

對於目標函數，我們限定是凸函數對於優化變量的可行域（注意，還要包括目標函數定義域的約束），我們限定它是凸集。

同時滿足這兩個限制條件的最優化問題稱爲凸優化問題，這類問題有一個非常好性質，那就是局部最優解一定是全局最優解。

凸優化算法原理及講解

凸優化方法是數學優化方法中具有代表性的一種，凸優化被廣泛運用在圖像處理，自動控制系統，估計和信號處理，通信網絡，數據挖掘，電路設計等很多方面，特別是在現在的人工智能時代，機器學習和深度學習具有很高的熱度和應用價值，從某種意義上講，凸優化也可看做是機器學習中的一部分。