凸優(yōu)化和非凸優(yōu)化

機(jī)器學(xué)習(xí)（37） 

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

非凸優(yōu)化問(wèn)題如何轉(zhuǎn)化為凸優(yōu)化問(wèn)題的方法：1）修改目標(biāo)函數(shù)，使之轉(zhuǎn)化為凸函數(shù)2）拋棄一些約束條件，使新的可行域?yàn)橥辜⑶野尚杏?/p>

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

關(guān)于凸優(yōu)化的一些簡(jiǎn)單概念

機(jī)器學(xué)習(xí)（39） 

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

沒(méi)有系統(tǒng)學(xué)過(guò)數(shù)學(xué)優(yōu)化，但是機(jī)器學(xué)習(xí)中又常用到這些工具和技巧，機(jī)器學(xué)習(xí)中最常見(jiàn)的優(yōu)化當(dāng)屬凸優(yōu)化了，這些可以參考Ng的教學(xué)資料：http://cs229.stanford.edu/section/cs229-cvxopt.pdf，從中我們可以大致了解到一些凸優(yōu)化的概念，比如凸集，凸函數(shù)，凸優(yōu)化問(wèn)題，線性規(guī)劃，二次規(guī)劃，二次約束二次規(guī)劃，半正定規(guī)劃等，從而對(duì)凸優(yōu)化問(wèn)題有個(gè)初步的認(rèn)識(shí)。以下是幾個(gè)重要相關(guān)概念的筆記。

　　凸集的定義為：

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

　　常見(jiàn)的凸集有：

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

　　凸函數(shù)的定義為：

　　其幾何意義表示為函數(shù)任意兩點(diǎn)連線上的值大于對(duì)應(yīng)自變量處的函數(shù)值，示意圖如下：

　　凸函數(shù)的一階充要條件為：

　　其中要求f一階可微。

　　二階充要條件為：

　　其中要求f二階可微，表示二階導(dǎo)數(shù)需大于0才是凸函數(shù)。

     按照上面的兩個(gè)定義，如果f(x)=x^2肯定是凸函數(shù)，而g(x) = -x^2是非凸函數(shù)。也就是說(shuō)開(kāi)口向下的函數(shù)是非凸函數(shù)，但是對(duì)于這種情況可以通過(guò)添加負(fù)號(hào)變成凸函數(shù)，從而求解。

 　　常見(jiàn)的凸函數(shù)有：指數(shù)函數(shù)族；非負(fù)對(duì)數(shù)函數(shù)；仿射函數(shù)；二次函數(shù)；常見(jiàn)的范數(shù)函數(shù)；凸函數(shù)非負(fù)加權(quán)的和等。這些可以采用上面2個(gè)充要條件或者定義去證明。

　　凸優(yōu)化問(wèn)題（OPT）的定義為：

　　即要求目標(biāo)函數(shù)是凸函數(shù)，變量所屬集合是凸集合的優(yōu)化問(wèn)題。或者目標(biāo)函數(shù)是凸函數(shù)，變量的約束函數(shù)是凸函數(shù)（不等式約束時(shí)），或者是仿射函數(shù)（等式約束時(shí)）。

　　對(duì)于凸優(yōu)化問(wèn)題來(lái)說(shuō)，局部最優(yōu)解就是全局最優(yōu)解。

　　常見(jiàn)的凸優(yōu)化問(wèn)題包括：

　　線性規(guī)劃（LP）：該問(wèn)題是優(yōu)化下面的式子：

　　其中那個(gè)不常見(jiàn)的奇怪符號(hào)表示按元素小于等于，后面出現(xiàn)類(lèi)似符號(hào)可以類(lèi)似理解。

　　二次規(guī)劃（QP）：該問(wèn)題是優(yōu)化下面的式子：

　　二次約束的二次規(guī)劃（QCQP）：該問(wèn)題是優(yōu)化下面的式子：

　　半正定規(guī)劃（SDP）：該問(wèn)題是優(yōu)化下面的式子：

　　按照文章說(shuō)SDP在機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用很廣，最近很流行，不過(guò)我好像沒(méi)太接觸到過(guò)。

　　參考資料：

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

為什么凸優(yōu)化這么重要？

11 個(gè)回答

我就按著問(wèn)題一個(gè)個(gè)的回答吧： 首先，在現(xiàn)實(shí)生活中，如果對(duì)實(shí)際問(wèn)題進(jìn)行建模，直接符合凸優(yōu)化條件的問(wèn)題很少很少，少的可憐，我們?cè)跈C(jī)器學(xué)習(xí)中、深度學(xué)習(xí)中所謂的模型正好符合凸優(yōu)化模型的情況是經(jīng)過(guò)無(wú)數(shù)先輩幾十年的沉淀轉(zhuǎn)化而來(lái)的，現(xiàn)今的機(jī)器學(xué)習(xí)、深度學(xué)習(xí)，所謂的智能，其實(shí)也只是數(shù)據(jù)進(jìn)行建模，kNN、貝葉斯、決策樹(shù)、SVM做超平面分隔、k聚簇等等只是在使用統(tǒng)計(jì)學(xué)的方法來(lái)做決策，其實(shí)只是概率(對(duì)已發(fā)生事件的頻率統(tǒng)計(jì))選擇來(lái)進(jìn)行決策而已，而解決這些問(wèn)題的過(guò)程當(dāng)中，存在著無(wú)數(shù)約束條件:等式+不等式。求解?(x),使得等式+不等式符合條件，經(jīng)過(guò)先輩們的改善、切合，發(fā)現(xiàn)轉(zhuǎn)化為凸優(yōu)化可以解決這類(lèi)問(wèn)題。但是還有著大量的問(wèn)題沒(méi)法解決，例如NP問(wèn)題，目前是無(wú)解的，因?yàn)樗婕暗募s束條件、可能性太多，計(jì)算過(guò)于復(fù)雜。我們沒(méi)法直接將它轉(zhuǎn)化為凸優(yōu)化。 其次，凸優(yōu)化的重要在于它是一個(gè)相對(duì)而言被嚼爛的數(shù)據(jù)模型，對(duì)凸優(yōu)化的問(wèn)題我們?cè)诨A(chǔ)數(shù)學(xué)上面已經(jīng)有了很多解決方法，例如可以將凸優(yōu)化問(wèn)題Lagerange做對(duì)偶化，然后用Newton、梯度下降算法求解等等。

再次，現(xiàn)有的優(yōu)化方法不是都解決了的，還是有很多問(wèn)題是沒(méi)有解決的，例如NP問(wèn)題，如果轉(zhuǎn)化為可解問(wèn)題，如何對(duì)這些問(wèn)題做近似優(yōu)化處理，這就需要遇到具體問(wèn)題的時(shí)候具體去分析，而且建立一個(gè)近似可解的優(yōu)化模型需要我們對(duì)優(yōu)化本身理解透徹。一個(gè)對(duì)水墨、顏料都不懂的畫(huà)家如何能夠創(chuàng)造出新穎的畫(huà)風(fēng)？

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