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

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

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

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

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

ClaudeShannon

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

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

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

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

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

一種新的采樣方法

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

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

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

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

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

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

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

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

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

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

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

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

為對于圖像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不確定原理（測不準(zhǔn)原理

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

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

定義2.1互相干

互

定理2.3

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

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

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

信號(hào)是時(shí)域稀疏的，頻域測量結(jié)果含有信號(hào)的所有信息；信號(hào)測量原信號(hào)M=50；S=19；N=100重建信號(hào)時(shí)域信號(hào)頻域1-維信號(hào)信號(hào)是頻域稀疏的，時(shí)域測量結(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)不在測量的零空間，信號(hào)的范數(shù)近似保持定義2.3

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

2.3.7最小化問題的唯一解P0問題的唯一解

P1問題的唯一解

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

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

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

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

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

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

OMP算法步驟

t=t+1;5：如果

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

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

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

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

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

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

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

基向量，基變量

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

稱為基向量，

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

基的個(gè)數(shù)一個(gè)線性規(guī)劃的基通常不是唯一的，但是基的個(gè)數(shù)也不會(huì)超過個(gè)。一旦線性規(guī)劃的基確定了，那么相應(yīng)的基向量、基變量和非基變量也就確定了。(4)基本解。設(shè)B是線性規(guī)劃的一個(gè)基，若令n-m個(gè)非基變量等于0，則所得的方程組ＡＸ=b的解稱為線性規(guī)劃問題的一個(gè)基本解（簡稱基解）。有一個(gè)基就可以求得一個(gè)基本解。由基的有限性可知，基本解的個(gè)數(shù)也不會(huì)超過個(gè)。由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。(5)基本可行解。滿足非負(fù)條件的基本解稱為基本可行解（簡稱基可行解）。與基本可行解對應(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問題

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

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

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

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

中非空凸集，若對,

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

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

為凸函數(shù),是線性函數(shù),則上述問題為凸規(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ù)問題由條件得到的是一個(gè)非線性方程組，求解非常困難，甚至無法得到解析解，因此求解非線性規(guī)劃問題一般都采用數(shù)值計(jì)算的迭代方法。即從已知點(diǎn)出發(fā)，按照某種算法產(chǎn)生后繼點(diǎn)，形成點(diǎn)列非線性規(guī)劃迭代方法的基本思想是：要求迭代所采用的算法，使得當(dāng)是有窮點(diǎn)列時(shí)，其最后一點(diǎn)是該問題的最優(yōu)解；當(dāng)為無窮點(diǎn)列時(shí)，有極限點(diǎn)，并且該極限點(diǎn)是問題的最優(yōu)解。

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

Taylor展開式還可寫成如下形式：

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

如果算法構(gòu)造出的點(diǎn)列{xk}在有限步之內(nèi)得到問題的最優(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*

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

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

x0

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

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

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

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

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

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

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

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

f(x)

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

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

共軛梯度法特點(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)定性高，而且不需要任何外來參數(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對陣正定，目的是通過選擇C，使得是良態(tài)的，然后再應(yīng)用CG算法考慮約束非線性規(guī)劃問題

其中

，可行域記為，

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

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

s.t

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

將

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

時(shí)，

，

當(dāng)

時(shí)，

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

求解無約束問題

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

這就是說

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

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

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

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

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

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

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

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

以為初始點(diǎn)，選擇適當(dāng)?shù)姆椒ㄇ蠼猓闷錁O小點(diǎn)。

第3步：判斷精度。

在點(diǎn)，若罰項(xiàng)，則停止計(jì)算，得到原問題的近似極小點(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è)迭代過程始終在可行域內(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ù)的無約束極小化問題。以為初始點(diǎn)，求解

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

若收斂準(zhǔ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ī)劃問題。3.3其他算法

3.3.1

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

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

2.一般問題的近似模型

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