[轉]關于凸優化的一些簡單概念

　　沒有系統學過數學優化，但是機器學習中又常用到這些工具和技巧，機器學習中最常見的優化當屬凸優化了，這些可以參考Ng的教學資料：http://cs229.stanford.edu/section/cs229-cvxopt.pdf，從中我們可以大致了解到一些凸優化的概念，比如凸集，凸函數，凸優化問題，線性規劃，二次規劃，二次約束二次規劃，半正定規劃等，從而對凸優化問題有個初步的認識。以下是幾個重要相關概念的筆記。

?

　　凸集的定義為：

　　

　　其幾何意義表示為：如果集合C中任意2個元素連線上的點也在集合C中，則C為凸集。其示意圖如下所示：

　　

　　常見的凸集有：

　　n維實數空間；一些范數約束形式的集合；仿射子空間；凸集的交集；n維半正定矩陣集；這些都可以通過凸集的定義去證明。

?

　　凸函數的定義為：

　　

　　其幾何意義表示為函數任意兩點連線上的值大于對應自變量處的函數值，示意圖如下：

　　

　　凸函數的一階充要條件為：

　　

　　其中要求f一階可微。

　　二階充要條件為：

　　

　　其中要求f二階可微，表示二階導數需大于0才是凸函數。

?　　常見的凸函數有：指數函數族；非負對數函數；仿射函數；二次函數；常見的范數函數；凸函數非負加權的和等。這些可以采用上面2個充要條件或者定義去證明。

?

　　凸優化問題（OPT）的定義為：

　　

　　即要求目標函數是凸函數，變量所屬集合是凸集合的優化問題。或者目標函數是凸函數，變量的約束函數是凸函數（不等式約束時），或者是仿射函數（等式約束時）。

　　對于凸優化問題來說，局部最優解就是全局最優解。

　　常見的凸優化問題包括：

　　線性規劃（LP）：該問題是優化下面的式子：

?　　

　　其中那個不常見的奇怪符號表示按元素小于等于，后面出現類似符號可以類似理解。

　　二次規劃（QP）：該問題是優化下面的式子：

?　　

　　二次約束的二次規劃（QCQP）：該問題是優化下面的式子：

?　　

　　半正定規劃（SDP）：該問題是優化下面的式子：

　　

　　按照文章說SDP在機器學習領域應用很廣，最近很流行，不過我好像沒太接觸到過。

?

　　參考資料：

? ? ?http://cs229.stanford.edu/section/cs229-cvxopt.pdf

?

?

?

?

作者：tornadomeet 出處：http://www.cnblogs.com/tornadomeet 歡迎轉載或分享，但請務必聲明文章出處。 （新浪微博：tornadomeet,歡迎交流！）