凸優(yōu)化算法原理及講解？

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

對(duì)于機(jī)器學(xué)習(xí)來說，如果要優(yōu)化的問題被證明是凸優(yōu)化問題，則說明此問題可以被比較好的解決。

求解一個(gè)一般性的最優(yōu)化問題的全局極小值是非常困難的，至少要面臨的問題是：函數(shù)可能有多個(gè)局部極值點(diǎn)，另外還有鞍點(diǎn)問題。

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

第二個(gè)問題更嚴(yán)重，我們找到了梯度為0的點(diǎn)，但它連局部極值都不是，典型的是這個(gè)函數(shù)，在0點(diǎn)處，它的導(dǎo)數(shù)等于0，但這根本不是極值點(diǎn)：

梯度下降法和牛頓法等基于導(dǎo)數(shù)作為判據(jù)的優(yōu)化算法，找到的都導(dǎo)數(shù)/梯度為0的點(diǎn)，而梯度等于0只是取得極值的必要條件而不是充分條件。

如果我們將這個(gè)必要條件變成充分條件，即：?jiǎn)栴}將會(huì)得到簡(jiǎn)化。

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

其中的一種限制方案是：

對(duì)于目標(biāo)函數(shù)，我們限定是凸函數(shù)；對(duì)于優(yōu)化變量的可行域（注意，還要包括目標(biāo)函數(shù)定義域的約束），我們限定它是凸集。

同時(shí)滿足這兩個(gè)限制條件的最優(yōu)化問題稱為凸優(yōu)化問題，這類問題有一個(gè)非常好性質(zhì)，那就是局部最優(yōu)解一定是全局最優(yōu)解。