淺談壓縮感知：凸優(yōu)化

我們知道壓縮感知主要有三個(gè)東西：信號(hào)的稀疏性，測(cè)量矩陣的設(shè)計(jì)，重建算法的設(shè)計(jì)。那么，在重建算法中，如何對(duì)問(wèn)題建立數(shù)學(xué)模型并求解，這就涉及到了最優(yōu)化或凸優(yōu)化的相關(guān)知識(shí)。

在壓縮感知中，大部分情況下都轉(zhuǎn)換為凸優(yōu)化問(wèn)題，并通過(guò)最優(yōu)化方法來(lái)求解，因此了解相關(guān)知識(shí)就顯得尤為重要了。

1、問(wèn)題引出

在n維空間中，對(duì)于任意兩個(gè)點(diǎn)，對(duì)于0<=μ<=1，則表達(dá)式μx+(1-μ)y表示x和y連線之間的所有點(diǎn)。

證明略。

2、凸集

定義：

對(duì)于某集合中的任意x, y兩個(gè)點(diǎn)，若x和y連線之間的所有點(diǎn)（0<=μ<=1，μx+(1-μ)y）仍屬于這個(gè)集合，則稱此集合為凸集。

直觀的幾何表示：

左邊的是凸集，右邊的不是凸集，因?yàn)橛疫叺募现腥我鈨牲c(diǎn)x和y連線之間的所有點(diǎn)有時(shí)不屬于這個(gè)集合（右圖中的連線）。

3、凸函數(shù)

定義：

對(duì)于f(x)是定義在某凸集（非空的，空集也被規(guī)定為凸集）上的函數(shù)，對(duì)于凸集中的任意兩點(diǎn)x1和x2，若

f[μx1+(1-μ)x2]<=μf(x1)+(1-μ)f(x2)

則稱函數(shù)f(x)為凸函數(shù)。

直觀的幾何表示：

也就是說(shuō)兩點(diǎn)對(duì)應(yīng)的函數(shù)值f(x1)和f(x2)的之間的連線（μf(x1)+(1-μ)f(x2)）大于等于相應(yīng)的（即同一個(gè)μ值）兩點(diǎn)之間連線（μx1+(1-μ)x2）所對(duì)應(yīng)的函數(shù)值f[μx1+(1-μ)x2]。

這其實(shí)應(yīng)叫下凸。

如果把上面不等式中的等號(hào)去掉，即

f[μx1+(1-μ)x2]<μf(x1)+(1-μ)f(x2)?，其中0<μ<1

則稱f(x)為嚴(yán)格凸函數(shù)。

凸函數(shù)的判定方法：

求導(dǎo)計(jì)算判斷：

一階充要條件：

其中要求f一階可微。

二階充要條件：

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

常用函數(shù)分析法：

　　指數(shù)函數(shù)是凸函數(shù)；

　　對(duì)數(shù)函數(shù)是凹函數(shù)，然后負(fù)對(duì)數(shù)函數(shù)就是凸函數(shù)；

　　對(duì)于一個(gè)凸函數(shù)進(jìn)行仿射變換，可以理解為線性變換，結(jié)果還是凸函數(shù)；

　　二次函數(shù)是凸函數(shù)（二次項(xiàng)系數(shù)為正）；

　　高斯分布函數(shù)是凹函數(shù)；

　　常見(jiàn)的范數(shù)函數(shù)是凸函數(shù)；

?多個(gè)凸函數(shù)的線性加權(quán)，如果權(quán)值是大于等于零的，那么整個(gè)加權(quán)結(jié)果函數(shù)是凸函數(shù)。

4、凸優(yōu)化

定義：

同時(shí)滿足如下兩個(gè)條件的優(yōu)化問(wèn)題稱為凸優(yōu)化：

1）目標(biāo)函數(shù)(objective function)是凸函數(shù)；

2）可行集合(feasible set)必須是凸集；

即在凸集上尋找凸函數(shù)的全局最值的過(guò)程稱為凸優(yōu)化。

對(duì)于一下的優(yōu)化問(wèn)題：

若目標(biāo)函數(shù)f(x)是凸函數(shù)且可行集R是凸集，則稱這樣的問(wèn)題為凸優(yōu)化問(wèn)題。

或者：

如果目標(biāo)函數(shù)f(x)和共l個(gè)約束函數(shù)gi(x)都是凸函數(shù)，則稱這樣的問(wèn)題為凸優(yōu)化問(wèn)題。

實(shí)際上，可以證明，約束函數(shù)gi(x)都是凸函數(shù)，則它的可行集是凸集。

凸優(yōu)化的特點(diǎn)：

1）如果一個(gè)實(shí)際的問(wèn)題可以被表示成凸優(yōu)化問(wèn)題，那么我們就可以認(rèn)為其能夠得到很好的解決。

2）還有的問(wèn)題不是凸優(yōu)化問(wèn)題，但是凸優(yōu)化問(wèn)題同樣可以在求解該問(wèn)題中發(fā)揮重要的左右。比如松弛算法和拉格朗日松弛算法，將非凸的限制條件松弛為凸限制條件。

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

4）若f(x)在非空可行集R上是嚴(yán)格凸函數(shù)，則全局極值點(diǎn)是唯一的。

也就是說(shuō)如果把一個(gè)非凸優(yōu)化問(wèn)題轉(zhuǎn)化為凸優(yōu)化問(wèn)題（松弛算法），則若求得一個(gè)局部最優(yōu)解即為得到了全局最優(yōu)解（若目標(biāo)函數(shù)在可行集上是嚴(yán)格凸函數(shù)，則此解還是唯一的），并且凸優(yōu)化問(wèn)題能夠比較好的得解決，因此在看壓縮感知的文獻(xiàn)時(shí)經(jīng)常會(huì)看到如何如之何修改一下約束條件使之變?yōu)橐粋€(gè)凸優(yōu)化問(wèn)題。

非凸優(yōu)化問(wèn)題如何轉(zhuǎn)化為凸優(yōu)化問(wèn)題：

1）修改目標(biāo)函數(shù)，使之轉(zhuǎn)化為凸函數(shù)

2）拋棄一些約束條件，使新的可行域?yàn)橥辜⑶野尚杏?/p>

實(shí)際建模中判斷一個(gè)最優(yōu)化問(wèn)題是不是凸優(yōu)化問(wèn)題的方法：

1）目標(biāo)函數(shù)f如果不是凸函數(shù)，則不是凸優(yōu)化問(wèn)題

2）決策變量x中包含離散變量（0-1變量或整數(shù)變量），則不是凸優(yōu)化問(wèn)題

3）約束條件寫成g(x)<=0時(shí)，g如果不是凸函數(shù)，則不是凸優(yōu)化問(wèn)題

5、最優(yōu)化

最優(yōu)化問(wèn)題：

線性規(guī)劃

二次規(guī)劃

二次約束的二次規(guī)劃

半正定規(guī)劃

最優(yōu)化手段：

　　梯度上升（下降）法

　　牛頓法 / 擬牛頓法

　　坐標(biāo)下降法：