機(jī)器學(xué)習(xí)中為什么要強(qiáng)調(diào)凸優(yōu)化逮京？

? ? ? ? 凸優(yōu)化在數(shù)學(xué)規(guī)劃領(lǐng)域具有非常重要的地位卿堂。工程中大量的問(wèn)題最終都可以歸結(jié)為一個(gè)優(yōu)化問(wèn)題，包括且不限于雷達(dá)懒棉、通信草描、信息處理、機(jī)器學(xué)習(xí)策严、模式識(shí)別穗慕、圖像處理、自動(dòng)控制妻导、金融等學(xué)科揍诽。

在一些數(shù)學(xué)問(wèn)題中很可能遇到復(fù)雜的函數(shù)诀蓉、高階函數(shù)等一些不易求解的目標(biāo)函數(shù)。如圖1所示的函數(shù)暑脆，其可能有多個(gè)局部極值點(diǎn)渠啤，而我們想找到全局最優(yōu)點(diǎn)。

圖1

對(duì)于一個(gè)復(fù)雜函數(shù)或一個(gè)上圖所示的函數(shù)添吗，找其全局最優(yōu)點(diǎn)無(wú)疑比較困難或者說(shuō)比較復(fù)雜沥曹，在實(shí)際工程中可能很難求解，這時(shí)我們想將一個(gè)復(fù)雜的目標(biāo)函數(shù)轉(zhuǎn)化為一個(gè)如圖2所示的函數(shù)碟联。這樣其局部最優(yōu)便是全局最優(yōu)的解妓美。

圖2

? ? ? ? 而圖2所示的函數(shù)圖像便是一個(gè)典型的凸函數(shù)圖像，對(duì)應(yīng)的優(yōu)化稱(chēng)為凸優(yōu)化鲤孵。

所以凸優(yōu)化問(wèn)題便是便是機(jī)器學(xué)習(xí)的一個(gè)根本性問(wèn)題壶栋。在工程中的很多問(wèn)題可以抽象化為一個(gè)凸問(wèn)題，很多非凸問(wèn)題可以通過(guò)一定的手段或方法轉(zhuǎn)化為一個(gè)凸問(wèn)題普监，一旦轉(zhuǎn)化為一個(gè)凸問(wèn)題贵试，那么理論上來(lái)說(shuō)，這個(gè)問(wèn)題便得到了解決凯正。所以如何將工程中的問(wèn)題或一個(gè)非凸問(wèn)題轉(zhuǎn)化為一個(gè)凸優(yōu)化問(wèn)題才是真正的考驗(yàn)一個(gè)人的能力毙玻。

一些基本概念

1、凸集

凸集的定義（直接上圖片了廊散，簡(jiǎn)書(shū)上不好寫(xiě)公式）

? ? ? ? 簡(jiǎn)單的來(lái)說(shuō)桑滩，凸集的定義就是在凸集內(nèi)部任意選取兩個(gè)點(diǎn)，則這兩個(gè)點(diǎn)的連線上的任意一點(diǎn)也還在這個(gè)集合內(nèi)允睹，如圖3.? ?直觀上來(lái)說(shuō)运准，凸集的圖像外觀就是外形往外凸不能有內(nèi)凹的 部分。

圖3.

2缭受、常見(jiàn)的凸集：

（1）超平面（Hyperplane）：

圖4

（2）半空間（Halfspace）

圖5

（3）多面體（Polyhedron）

圖6

此外還有歐式球胁澳、橢球等凸集。

歐式球（Euclidean ball）

橢球（Ellipsoid）

? ? ? ? 特別注意的是：一個(gè)凸優(yōu)化的問(wèn)題他的可行域必須是一個(gè)凸集贯涎，這也是凸集在優(yōu)化問(wèn)題中的重要性听哭。

3、凸函數(shù)

? ? ? ? 其幾何解釋?zhuān)鐖D7所示凸函數(shù)的圖上任取兩個(gè)點(diǎn)連成一條直線塘雳，在這條直線的范圍內(nèi)陆盘，凹函數(shù)圖上的值小于這個(gè)直線上的值。

圖7

關(guān)于凸函數(shù)败明，它有兩個(gè)充要條件隘马。

（1）凸函數(shù)的一階充要條件

幾何解釋?zhuān)?/p>

圖8

? ? ? ? 運(yùn)用幾何可以很直觀的解釋上式的關(guān)系，總結(jié)起來(lái)就是凸函數(shù)總是在其任意一點(diǎn)的切線的上方妻顶，對(duì)于函數(shù)在定義域的任意取值酸员，函數(shù)的值都大于或者等于對(duì)函數(shù)在這點(diǎn)的一階近似蜒车。但是，具體在應(yīng)用中幔嗦，這個(gè)條件并不好用酿愧，我們不可能對(duì)每一個(gè)點(diǎn)都去計(jì)算函數(shù)的一階導(dǎo)數(shù)，因此后面會(huì)說(shuō)道利用凸函數(shù)的二階特征來(lái)進(jìn)行判斷一個(gè)函數(shù)是否是一個(gè)凸函數(shù)邀泉。

（2）凸函數(shù)的二階充要條件

? ? ? ? 其中要求函數(shù)f二階可微嬉挡，則函數(shù)f在定義域上是凸函數(shù)的充要條件是：函數(shù)的二階導(dǎo)數(shù)（即Hessian矩陣）是半正定的，也就是所有的特征值都是大于等于0的汇恤。特殊的庞钢，對(duì)于一元函數(shù)，可以退化為f′′(x)≥0因谎。

4基括、凸函數(shù)的重要定理

? ? ? ? （1）f(x)在區(qū)間[a,b]上連續(xù)，在(a,b)內(nèi)二階可導(dǎo)财岔，那么：

? ? ? ? ? ? ? ? ? ? ? ? ?若f′′(x)>0风皿，則f(x)是凸函數(shù)；

? ? ? ? ? ? ? ? ? ? ? ? ?若f′′(x)<0使鹅，則f(x)是凹函數(shù)揪阶。

? ? ? ? 即：當(dāng)且僅當(dāng)f(x)的二階導(dǎo)數(shù)是非負(fù)的昌抠，一元二階可微的函數(shù)在區(qū)間上是凸的患朱。

? ? ? ? （2）凸函數(shù)的表述

? ? ? ? f(x)為凸函數(shù)，則有：

其中0<=θi<=1炊苫，θ1+θ2+? ...+θn=1

? ? ? ? 在確定函數(shù)的凸凹性之后裁厅，可根據(jù)上式對(duì)函數(shù)進(jìn)行不等式替換。

? ? ? ? 對(duì)于復(fù)雜函數(shù)和約束函數(shù)的優(yōu)化一般采用拉格朗日乘子法和KKT條件侨艾，這個(gè)將在下一篇進(jìn)行介紹执虹。