壓縮感知理論及應(yīng)用(附重建算法詳述)

壓縮感知理論與應(yīng)用Compressedsensing:theoremandApplications一.壓縮感知背景知識(shí)二.壓縮感知理論三.壓縮感知重建方法四.壓縮感知應(yīng)用內(nèi)容概覽一.壓縮感知背景知識(shí)Nyquist-Shannon采樣定理

1928年由美國(guó)電信工程師H.奈奎斯特首先提出 1933年由蘇聯(lián)工程師科捷利尼科夫首次用公式嚴(yán)

格地表述這一定理 1949年信息論的創(chuàng)始人香農(nóng)對(duì)該定理加以明確

地說(shuō)明并正式作為定理引用，因此在許多文

獻(xiàn)中又稱為香農(nóng)采樣定理HarryNyquist

ClaudeShannon

插值重建數(shù)字信號(hào)的獲取----Nyquist-Shannon采樣定理信號(hào)采樣非帶限信號(hào)香農(nóng)定理的數(shù)學(xué)表示香農(nóng)采樣定理后采樣理論的發(fā)展Nyquist-Shannon采樣定理局限性問(wèn)題1:真實(shí)信號(hào)沒(méi)有真正帶限的；問(wèn)題2:理想的低通濾波器不存在；獲取的大量數(shù)字信號(hào)為處理、存儲(chǔ)、傳輸?shù)能浻布黾恿撕芏嘭?fù)擔(dān)高分辨率大量的傳感器圖像數(shù)據(jù)庫(kù)，照相陣列，分布式無(wú)線傳感網(wǎng)越來(lái)越多的成像形式X-Ray，GammaRay,PET，MRI,紅外，超聲波，毫米波SAR成像海量的數(shù)據(jù)問(wèn)題3:當(dāng)信號(hào)的帶寬過(guò)寬時(shí)，采樣率過(guò)高難于實(shí)現(xiàn)

限制了超寬帶通信和超寬帶雷達(dá)的發(fā)展；限制醫(yī)學(xué)圖像成像的發(fā)展，比如MRI；等等。多種成像形式采樣壓縮傳輸/存儲(chǔ)NK小波系數(shù)局部放大大量采樣數(shù)據(jù)有無(wú)必要性？1M25K項(xiàng)系數(shù)近似原始圖像近似后的圖像2004~2006，

ECandes（加州理工大學(xué)）

D.Donoho(斯坦福大學(xué))

（Ridgelet和Curvelet的創(chuàng)始人）

一種新的采樣方法

以不確定準(zhǔn)則為基礎(chǔ)Romberg(佐治亞理工大學(xué))

Tao（加州大學(xué)洛杉磯分校）CS提出者用更一般的測(cè)量值代替信號(hào)樣本值壓縮感知或壓縮采樣直接獲取壓縮后的信號(hào)；壓縮采樣傳輸/存儲(chǔ)NM接收重建二.壓縮感知理論2.1壓縮感知問(wèn)題描述

三種線性方程組根據(jù)變量個(gè)數(shù)和方程個(gè)數(shù)來(lái)確定是欠定、適定還是超定方程組欠定方程組，無(wú)窮多解適定方程組，有唯一解超定方程組，無(wú)解良態(tài)問(wèn)題1923年Hadamard提出了良態(tài)問(wèn)題（Well-posedproblem）的概念，根據(jù)其定義，如果下述條件滿足，稱為良態(tài)問(wèn)題（1）方程的解是存在的；（2）解是唯一的；（3）解連續(xù)地依賴于數(shù)據(jù)（觀測(cè)矩陣或數(shù)據(jù)微小變化導(dǎo)致解很大變動(dòng)）病態(tài)問(wèn)題

如果良態(tài)問(wèn)題的三個(gè)條件任意一個(gè)不能滿足，就稱問(wèn)題是病態(tài)的（ill-posedproblem）

良態(tài)與病態(tài)問(wèn)題：病態(tài)問(wèn)題舉例系數(shù)矩陣A或者觀測(cè)項(xiàng)(常數(shù)項(xiàng))y的微小變化引起解的巨大變化,該問(wèn)題為病態(tài)問(wèn)題

病態(tài)問(wèn)題求解：用規(guī)整化（Regularization）理論處理病態(tài)問(wèn)題目的是修改一個(gè)病態(tài)問(wèn)題為一個(gè)良態(tài)問(wèn)題，使得問(wèn)題的解在物理上合理，并且解連續(xù)依賴于數(shù)據(jù)?；舅枷胧抢藐P(guān)于解的先驗(yàn)知識(shí)，構(gòu)造附加約束或改變求解策略，使得逆問(wèn)題的解變得確定且穩(wěn)定。即對(duì)解進(jìn)行約束J(x)約束信號(hào)x為平滑的應(yīng)用Lagrange乘子，將P2問(wèn)題約束轉(zhuǎn)換為無(wú)約束問(wèn)題

2.如何設(shè)計(jì)測(cè)量矩陣，讓其作用于信號(hào)后

能保持信號(hào)的所有信息不丟失？

（對(duì)應(yīng)于香農(nóng)采樣定理中對(duì)采樣率的要求）3.如何從測(cè)量中重建原信號(hào)？

（對(duì)應(yīng)依據(jù)香農(nóng)采樣定理采樣后內(nèi)插實(shí)現(xiàn)重建）信號(hào)應(yīng)滿足什么要求，方可重建？（對(duì)應(yīng)香農(nóng)采樣定理中對(duì)信號(hào)的帶寬要求）CS關(guān)注的問(wèn)題信號(hào)表示將信號(hào)表示為一組正交基的線性組合

如果合理選擇基底，處理系數(shù)序列比直接處理信號(hào)簡(jiǎn)單；如果系數(shù)序列具有稀疏結(jié)構(gòu)，可以從實(shí)質(zhì)上降低信號(hào)處理的成本，提高壓縮效率。二.壓縮采樣理論2.2信號(hào)的稀疏與可壓縮性信號(hào)的稀疏（Sparsity）與可壓縮性(Compressibility)光滑信號(hào)其Fourier變換,Wavelet變換系數(shù)呈現(xiàn)冪次衰減趨勢(shì)其全變差（TotalVariation）呈現(xiàn)冪次衰減趨勢(shì)有界變差函數(shù)

給定一個(gè)定義于有界開(kāi)集Ω上的可微函數(shù)f，其全變差（thetotalvariation）

為對(duì)于圖像x而言，其TV范數(shù)為Cameraman原圖4層小波分解傅里葉幅頻MRI圖像4層小波分解傅里葉幅頻原圖垂直水平全變差

根據(jù)信號(hào)x的先驗(yàn)知識(shí)，可以設(shè)計(jì)規(guī)整化項(xiàng)為

R2空間，一維子空間用lp范數(shù)進(jìn)行約束的解2.3.1不確定原理（測(cè)不準(zhǔn)原理

UncertaintyPrinciple,UP）物理學(xué)中經(jīng)典的測(cè)不準(zhǔn)原理兩個(gè)共軛的物理量，如微觀粒子的位置和動(dòng)量，不能同時(shí)測(cè)準(zhǔn)，其中一個(gè)量越確定，另一個(gè)量的不確定程度就越大

2.3測(cè)量離散時(shí)間不確定準(zhǔn)則（DiscreteTimeUncertaintyPrinciple）注：集的勢(shì)：集合元素的個(gè)數(shù)2.3.2部分Fourier變換已知的信號(hào)重建與RobustUncertaintyPrinciplesCS提出的最初研究：2004年，EmmanuelCandes,JustinRomberg和TerenceTao對(duì)以下問(wèn)題進(jìn)行了研究MRI圖像Fourier采樣，22線Fourier幅度M>=logN.S定理與UP的關(guān)系，以及RUP（RobustUncertaintyPrinciple）2.3.3隨機(jī)采樣與重建

定義2.1互相干

互

定理2.3

幾點(diǎn)說(shuō)明：2.信號(hào)表示越稀疏、兩組基之間的互相干性越小，所需

要的樣本數(shù)就越少3.常用的測(cè)量矩陣有高斯和伯努利分布，因?yàn)槠渑c

大多數(shù)的稀疏表示基相干性小。測(cè)量結(jié)果稀疏信號(hào)x隨機(jī)投影（測(cè)量）矩陣壓縮采樣的情況1:信號(hào)本身稀疏

信號(hào)是時(shí)域稀疏的，頻域測(cè)量結(jié)果含有信號(hào)的所有信息；信號(hào)測(cè)量原信號(hào)M=50；S=19；N=100重建信號(hào)時(shí)域信號(hào)頻域1-維信號(hào)信號(hào)是頻域稀疏的，時(shí)域測(cè)量結(jié)果；壓縮采樣的情況2信號(hào)可以用一組基稀疏表示2-維圖像信號(hào)2.3.4一致不確定準(zhǔn)則（UniformUncertainty

Principle,UUP）

嚴(yán)格重建準(zhǔn)則（ExactReconstructionPrinciple,ERP）可壓縮信號(hào)（近似稀疏信號(hào)）的重建（P1）

定理2.4保證信號(hào)不在測(cè)量的零空間，信號(hào)的范數(shù)近似保持定義2.3

定理2.5定理2.62.3.6魯棒測(cè)量定理2.9測(cè)量A的零空間如果想從測(cè)量中重建所有的稀疏信號(hào)x，則對(duì)任意一對(duì)不同的信號(hào)x和x’，必然有Ax與Ax’。如果來(lái)觀測(cè)Ax=Ax’，則得到x-x’是2K稀疏的，因此，A能唯一表示所有，則中不能含有的向量。有許多方式可以表征這種性質(zhì)，其中之一為A的Spark定義Spark：一給定矩陣A的Spark是其最少的線性相關(guān)列的個(gè)數(shù)。

2.3.7最小化問(wèn)題的唯一解P0問(wèn)題的唯一解

P1問(wèn)題的唯一解

稱A有則A具有k階零空間性質(zhì)

MRI圖像Fourier采樣，22線令能量最小，未采樣的Fourier系數(shù)置0CS重建，令圖像的TV范數(shù)最小

利用計(jì)算機(jī)解決實(shí)際問(wèn)題，通常要按以下步驟進(jìn)行：（1）建立數(shù)學(xué)模型，即把實(shí)際問(wèn)題抽象為一個(gè)數(shù)學(xué)問(wèn)題，可以是一個(gè)方程組、一個(gè)函數(shù)、一個(gè)微分方程等。

（2）選擇數(shù)值方法，要考慮所能達(dá)到的精度，計(jì)算量，方法對(duì)數(shù)據(jù)微小擾動(dòng)的靈敏度。

（3）編寫(xiě)程序，上機(jī)計(jì)算。第二部分CS中的信號(hào)重建兩類主要方法：一、貪婪搜索（MatchedPursuit,匹配追蹤）二、基追蹤（BasisPursuit，基追蹤）

稱為基追蹤問(wèn)題，（BasisPursuit，BP）匹配追蹤（MatchedPursuit，MP）一、匹配追蹤（MatchedPursuit，簡(jiǎn)稱MP）MP算法的步驟正交匹配追蹤（OrthogonalMatchedPursuit，簡(jiǎn)稱OMP）

OMP算法步驟

t=t+1;5：如果

t>S,則停止迭代，否則重復(fù)步驟1體現(xiàn)正交思想由多元函數(shù)的微分學(xué)知，上式的解一定是駐點(diǎn)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式s.t.其中為M×N階矩陣

二、基追蹤問(wèn)題（BP）約束條件以及目標(biāo)函數(shù)都是決策變量的線性函數(shù)的規(guī)劃問(wèn)題稱為線性規(guī)劃(LinearProgramming)s.t.

線性規(guī)劃問(wèn)題解的概念：

(1)可行解。滿足約束條件的解

可行解集稱為線性規(guī)劃問(wèn)題的可行域。

(2)最優(yōu)解。使目標(biāo)函數(shù)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解，最優(yōu)解常用表示。

(3)基。若Ｂ是Ａ中M×M階非奇異矩陣，即|Ｂ|≠0，則稱Ｂ是線性規(guī)劃問(wèn)題的一個(gè)基。s.t.

基向量，基變量

若Ｂ是線性規(guī)劃問(wèn)題的一個(gè)基，那么Ｂ一定是由M個(gè)線性無(wú)關(guān)的列向量組成，不失一般性，可設(shè)

稱為基向量，

與基向量相對(duì)應(yīng)的變量稱為基變量。

基的個(gè)數(shù)一個(gè)線性規(guī)劃的基通常不是唯一的，但是基的個(gè)數(shù)也不會(huì)超過(guò)個(gè)。一旦線性規(guī)劃的基確定了，那么相應(yīng)的基向量、基變量和非基變量也就確定了。(4)基本解。設(shè)B是線性規(guī)劃的一個(gè)基，若令n-m個(gè)非基變量等于0，則所得的方程組ＡＸ=b的解稱為線性規(guī)劃問(wèn)題的一個(gè)基本解（簡(jiǎn)稱基解）。有一個(gè)基就可以求得一個(gè)基本解。由基的有限性可知，基本解的個(gè)數(shù)也不會(huì)超過(guò)個(gè)。由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。(5)基本可行解。滿足非負(fù)條件的基本解稱為基本可行解（簡(jiǎn)稱基可行解）。與基本可行解對(duì)應(yīng)的基稱為可行基?；究尚薪獾姆橇阆蛄康膫€(gè)數(shù)小于等于m，并且都是非負(fù)的。由于基本可行解的數(shù)目一般少于基本解的數(shù)目，因此可行基的數(shù)目也要少于基的數(shù)目。

當(dāng)基本可行解中有一個(gè)或多個(gè)基變量是取零值時(shí)，稱此解為

退化的基本可行解。可行解

基本解求解線性規(guī)劃：圖解法單純形法內(nèi)點(diǎn)算法70單純形法的一般步驟如下：（1）尋找一個(gè)初始的基本可行解。（2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。（3）移至目標(biāo)函數(shù)值有所改善的另一個(gè)基本可行解，然后轉(zhuǎn)回到步驟（2）。

其基本思路是從一個(gè)初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。

1947年，Dantzig提出的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點(diǎn)）中。單純形法Lasso問(wèn)題

s.t.BPDN（BasisPursuitDenoising）BP（BasisPursuit）s.t.(1)約束問(wèn)題(2)約束問(wèn)題問(wèn)題(2)的解要么是x=0,要么是問(wèn)題(3)的解,因此說(shuō)BPDN問(wèn)題與LASSO等價(jià)(3)無(wú)約束問(wèn)題3.1無(wú)約束最優(yōu)化方法無(wú)約束問(wèn)題定義：設(shè)函數(shù)f(x)存在一階偏導(dǎo)數(shù)，x∈Rn

，向量?)(xf=Tnxfxfxf????è???????,,,21為f(x)在點(diǎn)x處的梯度?！x設(shè)函數(shù)存在二階偏導(dǎo)數(shù)，x∈R，則稱矩陣)(xfnúúúúúúúú?ùêêêêêêêê?é????????????????????????2222122222212212212212nnnnnxfxxfxxfxxfxfxxfxxfxxfxfLLL為在點(diǎn)x處的Hesse矩陣。)(xf)(2xf?=………三、BPDN問(wèn)題定理:(一階必要條件）

凸集和凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面給出凸集和凸函數(shù)的一些基本知識(shí)。設(shè)，若對(duì)D中任意兩點(diǎn)，連接的線段仍屬于D；換言之，對(duì),

則稱D為凸集。稱為的凸組合。定義:凸集對(duì)凸的一元函數(shù)的幾何意義為：在曲線上任取兩點(diǎn)P1(x1,),P2(x2,)弦位于弧之上（見(jiàn)圖）。)(xf)(1xf(x2)f21PP21PPx1x2x(x,y)p1p2)(xf設(shè)D為RN

中非空凸集，若對(duì),

恒有則稱f(x)為D上的凸函數(shù)；進(jìn)一步，若時(shí)，上式僅〝<〞成立,則稱f(x)為D上嚴(yán)格凸函數(shù)。定義:凸函數(shù)定義:凸規(guī)劃設(shè)D為RN

中非空凸集，f(x)是定義在D上的凸函數(shù)，則稱規(guī)劃問(wèn)題為凸規(guī)劃。若規(guī)劃???íì===ljhmigtsfji,,2,1,0)(,,2,1,0)(..)(minxxx……中,和

為凸函數(shù),是線性函數(shù),則上述問(wèn)題為凸規(guī)劃。)(xf)(xig)(xih

凸規(guī)劃是非線性規(guī)劃中的一種重要特殊情形，它具有很好的性質(zhì)。定理:(1)凸規(guī)劃的任意局部極小點(diǎn)就是整體極小點(diǎn)，且極小點(diǎn)集合是凸集。

(2)如果凸規(guī)劃的目標(biāo)函數(shù)是嚴(yán)格凸函數(shù)，又存在極小點(diǎn)，則它的極小點(diǎn)還是唯一的。多數(shù)問(wèn)題由條件得到的是一個(gè)非線性方程組，求解非常困難，甚至無(wú)法得到解析解，因此求解非線性規(guī)劃問(wèn)題一般都采用數(shù)值計(jì)算的迭代方法。即從已知點(diǎn)出發(fā)，按照某種算法產(chǎn)生后繼點(diǎn)，形成點(diǎn)列非線性規(guī)劃迭代方法的基本思想是：要求迭代所采用的算法，使得當(dāng)是有窮點(diǎn)列時(shí)，其最后一點(diǎn)是該問(wèn)題的最優(yōu)解；當(dāng)為無(wú)窮點(diǎn)列時(shí)，有極限點(diǎn)，并且該極限點(diǎn)是問(wèn)題的最優(yōu)解。

定理：設(shè)f：具有二階連續(xù)偏導(dǎo)數(shù)。則：

Taylor展開(kāi)式還可寫(xiě)成如下形式：

多元函數(shù)的Taylor展開(kāi)公式其中算法的收斂性

如果算法構(gòu)造出的點(diǎn)列{xk}在有限步之內(nèi)得到問(wèn)題的最優(yōu)解x*

，或者點(diǎn)列{xk}有極限點(diǎn)，并且其極限點(diǎn)是最優(yōu)解

x*

，則稱這種算法是收斂的。

如果只有當(dāng)

x0充分接近最優(yōu)解

x*時(shí)，由算法產(chǎn)生的點(diǎn)列才收斂于

x*

，則該算法稱為局部收斂。

如果對(duì)于任意初始點(diǎn)

x0

，由算法產(chǎn)生的點(diǎn)列都收斂于最優(yōu)解

，則這個(gè)算法稱為全局收斂?？紤]問(wèn)題式中函數(shù)具有一階連續(xù)偏導(dǎo)數(shù)，具有極小點(diǎn)若現(xiàn)在已求得的第k次近似值，為求得第k+1次近似值，需要選定方向p將f(x)在xk處進(jìn)行一階泰勒展開(kāi)，得到如果忽略高階無(wú)窮小項(xiàng)，因?yàn)?.1.1最速下降法有說(shuō)明搜索方向應(yīng)該與梯度的點(diǎn)積小于0,因?yàn)檎f(shuō)明夾角為180o時(shí)目標(biāo)函數(shù)下降最快，稱為負(fù)梯度方向

負(fù)梯度方向使目標(biāo)函數(shù)

下降最快，又稱之為最速下降方向。算法：最速下降法

在相繼兩次迭代中，搜索方向是相互正交的。可見(jiàn)，最速下降法逼近極小點(diǎn)的路線是鋸齒形的，而且越靠近極小點(diǎn)步長(zhǎng)越小，即越走越慢。

最速下降法具有整體收斂性，但由于其收斂速度慢，所以它不是好的實(shí)用算法。然而一些有效算法是通過(guò)對(duì)它進(jìn)行改進(jìn)或利用它與其他收斂快的算法相結(jié)合而得到的。是基本算法之一。3.1.2牛頓法(Newton)算法：牛頓法

牛頓法的優(yōu)缺點(diǎn)3.1.3共軛梯度法(ConjugateGradient)1.共軛方向及其性質(zhì)定理：設(shè)矩陣A為對(duì)稱正定，求解方程組

的解等價(jià)于求二次泛函

f(x)

的極小點(diǎn)共軛梯度法的基本思想是

在共軛方向法和最速下降法之間建立某種聯(lián)系，為了節(jié)省存儲(chǔ)單元和計(jì)算量，在迭代過(guò)程中逐步形成共軛方向。即用迭代點(diǎn)處的負(fù)梯度向量為基礎(chǔ)產(chǎn)生一組共軛方向的方法，叫做共軛梯度法。下面具體介紹對(duì)于正定二次函數(shù)規(guī)劃問(wèn)題的共軛梯度法

共軛梯度法特點(diǎn)是介于最速下降法與牛頓法之間的一個(gè)方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì)算Hesse矩陣并求逆的缺點(diǎn)，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。

CG是一個(gè)典型的共軛方向法，它的每一個(gè)搜索方向是互相共軛的，而這些搜索方向僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合，因此，存儲(chǔ)量少，計(jì)算方便所需存儲(chǔ)量小，穩(wěn)定性高，而且不需要任何外來(lái)參數(shù)。用共軛梯度法求得的

有如下的誤差估計(jì)其中PCG（PreconditionedConjugateGradient）

當(dāng)矩陣A僅有少數(shù)幾個(gè)互不相同的特征值或者非常良態(tài)時(shí)，共軛梯度法就會(huì)收斂的非常之快。當(dāng)矩陣A是病態(tài)的，想辦法將其轉(zhuǎn)化為一個(gè)良態(tài)的等價(jià)方程組，然后再應(yīng)用共軛梯度法于轉(zhuǎn)化后的方程組其中，這里的C對(duì)陣正定，目的是通過(guò)選擇C，使得是良態(tài)的，然后再應(yīng)用CG算法考慮約束非線性規(guī)劃問(wèn)題

其中

，可行域記為，

，，是上的連續(xù)函數(shù)。

基本思想有，構(gòu)造廣義拉格朗日函數(shù)，懲罰范數(shù)使得約束問(wèn)題轉(zhuǎn)換為無(wú)約束問(wèn)題；將非線性問(wèn)題線性化，然后通過(guò)解線性規(guī)劃問(wèn)題求原問(wèn)題的解等；3.2約束問(wèn)題求解定義（1）式的廣義拉格朗日函數(shù)為則存在向量，（此條件叫Kuhn-Tucker約束規(guī)范）3.2.1外點(diǎn)法構(gòu)造一個(gè)由目標(biāo)函數(shù)與約束函數(shù)組成的懲罰函數(shù)，對(duì)懲罰函數(shù)實(shí)行極小化。先考慮只含有不等式約束的問(wèn)題：

s.t

構(gòu)造一個(gè)函數(shù)：

將

作為t，顯然當(dāng)

時(shí)，

，

當(dāng)

時(shí)，

構(gòu)造函數(shù)：

求解無(wú)約束問(wèn)題

若(5)式問(wèn)題有解，設(shè)其最優(yōu)解為，則由(3)式和(4)式應(yīng)有：

這就是說(shuō)

因此不僅是問(wèn)題(5)式的極小解，也是問(wèn)題(2)式的極小解。因此將問(wèn)題(2)式的求解化為無(wú)約束問(wèn)題(5)式的求解。

上述函數(shù)的函數(shù)性態(tài)不好，它在t=0點(diǎn)不連續(xù)，也沒(méi)有導(dǎo)數(shù)。希望構(gòu)造出一個(gè)在任意點(diǎn)t處函數(shù)及其導(dǎo)數(shù)都連續(xù)的輔助函數(shù)?？蛇x擇如下的函數(shù)：

函數(shù)(6)式在t為任意值時(shí)，與都連續(xù)，且當(dāng)時(shí)仍有

當(dāng)時(shí)為了使輔助函數(shù)能更快地滿足要求，將引入一個(gè)充分大的正數(shù)M(>0)，修改為

求解問(wèn)題(5)式就變?yōu)榍蠼鉄o(wú)約束問(wèn)題(8)式稱函數(shù)為懲罰函數(shù)（或罰函數(shù)），其中第二項(xiàng)為懲罰項(xiàng)。稱M為罰因子。懲罰函數(shù)只對(duì)不滿足約束條件的點(diǎn)實(shí)行懲罰。當(dāng)

時(shí)，滿足各個(gè)，故罰項(xiàng)等于0，不受懲罰；當(dāng)時(shí)，必有，故罰項(xiàng)>0，對(duì)極小化罰函數(shù)的問(wèn)題，就要受懲罰。在實(shí)際計(jì)算中，罰因子M的值選得過(guò)小或過(guò)大都不好。如果選得過(guò)小，則罰函數(shù)的極小點(diǎn)遠(yuǎn)離約束問(wèn)題的最優(yōu)解，計(jì)算效率很差；如果M過(guò)大，則給罰函數(shù)的極小化增加計(jì)算上的困難。因此，一般策略是取一個(gè)趨向無(wú)窮大的嚴(yán)格遞增正數(shù)列，從某個(gè)

開(kāi)始，對(duì)每個(gè)求解：當(dāng)趨向于正無(wú)窮大時(shí)，點(diǎn)列就從可行域外部趨于原問(wèn)題的極小點(diǎn)，“外點(diǎn)法”正是因此而得名第1步：給定初始點(diǎn)，初始罰因子（例如），放大系數(shù)（如取或10），允許誤差。令。

第2步：求解罰函數(shù)的無(wú)約束極小化問(wèn)題。

以為初始點(diǎn)，選擇適當(dāng)?shù)姆椒ㄇ蠼?，得其極小點(diǎn)。

第3步：判斷精度。

在點(diǎn)，若罰項(xiàng)，則停止計(jì)算，得到原問(wèn)題的近似極小點(diǎn)；否則令，置

，返回第2步。外點(diǎn)法考慮非線性規(guī)劃

s.t

記為可行域內(nèi)部。即是可行域中所有嚴(yán)格內(nèi)點(diǎn)（即不包括可行域邊界上的點(diǎn)）的集合。

3.2.2內(nèi)點(diǎn)法

與外點(diǎn)法不同，內(nèi)點(diǎn)法要求整個(gè)迭代過(guò)程始終在可行域內(nèi)部進(jìn)行，初始點(diǎn)是一個(gè)嚴(yán)格的內(nèi)點(diǎn)，再在可行域邊界上設(shè)置一道“障礙”，以阻止搜索點(diǎn)到可行域邊界上去。構(gòu)造障礙函數(shù)（取倒數(shù)或?qū)?shù)函數(shù)）：

或

其中是很小的正數(shù)，通常稱為障礙因子，稱或?yàn)檎系K項(xiàng)。

障礙函數(shù)應(yīng)具備的功能：可行域內(nèi)部或離邊界較遠(yuǎn)處，障礙函數(shù)與原目標(biāo)函數(shù)盡可能接近，而在邊界上時(shí)，應(yīng)變成很大的值，因此滿足該要求的障礙函數(shù)其極小值不會(huì)在可行域的邊界上達(dá)到。內(nèi)點(diǎn)法計(jì)算步驟第1步：給定嚴(yán)格內(nèi)點(diǎn)為初始點(diǎn)，初始障礙因子（如取），縮小系數(shù)（如取或0.2），允許誤差，置。第2步：構(gòu)造障礙函數(shù)，障礙函數(shù)可取(14)式形式，也可取(15)式形式。第3步：求解障礙函數(shù)的無(wú)約束極小化問(wèn)題。以為初始點(diǎn)，求解

得其極小點(diǎn)。是可行域中所有嚴(yán)格內(nèi)點(diǎn)的集合。第4步：判斷精度。

若收斂準(zhǔn)則得到滿足，則迭代停止，取作為原問(wèn)題極小點(diǎn)的近似值。否則取，置，轉(zhuǎn)第3步。內(nèi)點(diǎn)法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：由于迭代總是在可行域內(nèi)進(jìn)行，每一個(gè)中間結(jié)果都是可行解，可以作為近似解。缺點(diǎn)：選取初始可行點(diǎn)較困難，且只適用于含有不等式約束的非線性規(guī)劃問(wèn)題。3.3其他算法

3.3.1

ISTA(IterativeShrinkage-ThresholdingAlgorithm）1.考慮無(wú)約束的最小化連續(xù)可微函數(shù)f(x),解決這個(gè)問(wèn)題的最簡(jiǎn)單方法就是用梯度算法產(chǎn)生x序列這個(gè)公式可以等價(jià)為如下二次形式把這種梯度算法應(yīng)用到非光滑l1正則化問(wèn)題中那么x的迭代序列為將公式(5)的第二項(xiàng)和第三項(xiàng)結(jié)合，并去掉常數(shù)項(xiàng)，則公式(5)可表示為

L1范數(shù)是可分離的那么(5)式的計(jì)算就簡(jiǎn)化為求解一維最小化問(wèn)題，通過(guò)CHAMBOLLE,R.A.DEVORE等人的證明x迭代步驟可以寫(xiě)成如下形式收縮算子定義為如下形式確保x收斂的關(guān)鍵條件是步長(zhǎng)的設(shè)置

2.一般問(wèn)題的近似模型

對(duì)于任何L>0,F(x)=f(x)+g(x)在y點(diǎn)的二次近似模型為它的唯一最小解為與(5)式同理，忽略掉常數(shù)項(xiàng)的影響，可以表示為前面講的g(x)為l1范數(shù)是這個(gè)一般問(wèn)題的特例那么基本的ISTA步驟即為3.3.2