凸優化和非凸優化

機器學習（37） 

其中，是 凸集是指對集合中的任意兩點，有，即任意兩點的連線段都在集合內，直觀上就是集合不會像下圖那樣有“凹下去”的部分。至于閉合的凸集，則涉及到閉集的定義，而閉集的定義又基于開集，比較抽象，不贅述，這里可以簡單地認為閉合的凸集是指包含有所有邊界點的凸集。

非凸優化問題如何轉化為凸優化問題的方法：1）修改目標函數，使之轉化為凸函數2）拋棄一些約束條件，使新的可行域為凸集并且包含原可行域

----------------------------------------------------------------------------------------------------------------------------------------------------------

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

機器學習（39） 

http://www.cnblogs.com/tornadomeet/p/3300132.html

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

　　凸集的定義為：

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

　　常見的凸集有：

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

　　凸函數的定義為：

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

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

　　其中要求f一階可微。

　　二階充要條件為：

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

     按照上面的兩個定義，如果f(x)=x^2肯定是凸函數，而g(x) = -x^2是非凸函數。也就是說開口向下的函數是非凸函數，但是對于這種情況可以通過添加負號變成凸函數，從而求解。

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

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

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

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

　　常見的凸優化問題包括：

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

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

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

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

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

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

　　參考資料：

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

為什么凸優化這么重要？

11 個回答

我就按著問題一個個的回答吧： 首先，在現實生活中，如果對實際問題進行建模，直接符合凸優化條件的問題很少很少，少的可憐，我們在機器學習中、深度學習中所謂的模型正好符合凸優化模型的情況是經過無數先輩幾十年的沉淀轉化而來的，現今的機器學習、深度學習，所謂的智能，其實也只是數據進行建模，kNN、貝葉斯、決策樹、SVM做超平面分隔、k聚簇等等只是在使用統計學的方法來做決策，其實只是概率(對已發生事件的頻率統計)選擇來進行決策而已，而解決這些問題的過程當中，存在著無數約束條件:等式+不等式。求解?(x),使得等式+不等式符合條件，經過先輩們的改善、切合，發現轉化為凸優化可以解決這類問題。但是還有著大量的問題沒法解決，例如NP問題，目前是無解的，因為它涉及的約束條件、可能性太多，計算過于復雜。我們沒法直接將它轉化為凸優化。 其次，凸優化的重要在于它是一個相對而言被嚼爛的數據模型，對凸優化的問題我們在基礎數學上面已經有了很多解決方法，例如可以將凸優化問題Lagerange做對偶化，然后用Newton、梯度下降算法求解等等。

再次，現有的優化方法不是都解決了的，還是有很多問題是沒有解決的，例如NP問題，如果轉化為可解問題，如何對這些問題做近似優化處理，這就需要遇到具體問題的時候具體去分析，而且建立一個近似可解的優化模型需要我們對優化本身理解透徹。一個對水墨、顏料都不懂的畫家如何能夠創造出新穎的畫風？

最后，回答末尾一個問題，凸優化的作用在于思維方式的轉變，跟計算機思維方式一樣，計算機從業人員在遇到問題的時候習慣了通過電腦去協助解決問題，而他們的價值不在于知道聽得懂別人告訴他如何解決問題，而是遇到現實問題的時候都會將問題拆分成機器可以實現的方式去解決：例如遇到購物，阿里巴巴建立了網站、app、c/s系統、b/s系統，用互聯網建立信息流，建立帝國。遇到查詢問題，百度建立了搜索引擎。這種思維方式才是最重要的。。同樣，凸優化的價值也在于思維轉變，遇到現實生活問題的時候，我們必然要對問題進行建模，然后抽象問題，利用機器去幫助我們解決問題，那么，當問題的計算量接近無窮大的時候我們如何去解決？這就需要我們抽離問題抽象結構，想辦法將轉換成“凸優化問題”，因為凸優化已經被嚼爛，所以只要問題轉化成凸優化，我們就可以分布迭代去運算，于是才有了機器學習、深度學習這一門門的交叉科學。凸優化是數學領域的重要分支，而計算機科學僅僅是數學這門基礎科學的延伸而已，基礎科學才是王道！！！ C#、java固然是被封裝成了便于人類使用的高級語言，但是總有些功能是“已有實現”沒有封裝好的，這時就需要我們回歸更加原始語言C、匯編去編程。。深究底層、精通基礎科學才是從容面對所有問題的解決王道，學會別人解決過的問題只能讓你解決相同的問題，現實是無限可能的，總有未解決過的問題等著你，凸優化，你值得擁有