凸優化算法原理及講解？

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

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

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

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

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

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

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

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

其中的一種限制方案是：

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

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