L1正則化問(wèn)題的對(duì)偶性理論*

吳焚供

(1. 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，廣州 廣東 510631；2. 廣東第二師范學(xué)院數(shù)學(xué)系，廣州 廣東 510303)

?

L1正則化問(wèn)題的對(duì)偶性理論*

吳焚供1,2

(1. 華南師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，廣州 廣東 510631；2. 廣東第二師范學(xué)院數(shù)學(xué)系，廣州 廣東 510303)

L1正則化問(wèn)題是一個(gè)非光滑的無(wú)約束最優(yōu)化問(wèn)題，在變量選擇，數(shù)據(jù)壓縮和圖像處理等領(lǐng)域有廣泛的應(yīng)用。給出了L1問(wèn)題最優(yōu)解存在的新的必要條件和充分條件，利用這些條件構(gòu)造出L1正則化問(wèn)題的一個(gè)Mond-Weir型對(duì)偶問(wèn)題，最后給出了相應(yīng)的弱對(duì)偶定理和強(qiáng)對(duì)偶定理。

L1正則化；最優(yōu)解；對(duì)偶問(wèn)題

正則化問(wèn)題近年來(lái)備受關(guān)注，許多研究者考慮如下的Lp最小化問(wèn)題

minF(x)=f(x)+ρ‖

其中f(x):Rn→R 為一光滑函數(shù)，ρ為一給定的非負(fù)正則化參數(shù)，p∈[0,1]，變量x∈Rn，‖x‖p為定義在Rn上的Lp擬范數(shù)，當(dāng)0

‖

Lp正則化問(wèn)題的一個(gè)重要的情況是如下的L2-

Lp最小化問(wèn)題

(1)

其中‖·‖為歐幾里得范數(shù)，A∈Rm×n，m

minF(x)=f(x)+ρ‖x‖1

(2)

該問(wèn)題在文[7]和文[1]中分別被稱為L(zhǎng)ASSO和BasisPursuit。他們證明了L1正則化問(wèn)題與L0正則化問(wèn)題在稀疏重建的意義下是等價(jià)的，從而L0正則化所要求的NP組合優(yōu)化問(wèn)題可以轉(zhuǎn)化為L(zhǎng)1罰優(yōu)化問(wèn)題。基于上述學(xué)者的工作，L1正則化成為當(dāng)今數(shù)據(jù)分析的主流工具之一。

(3)

其中▽if(x)=?f(x)/?xi，sign(t)為符號(hào)函數(shù)。條件(3)在文[9]中被敘述為如下的等價(jià)形式在這些理論的基礎(chǔ)上

x= sign (x-τ▽f(x))⊙

max{ |x-τ▽f(x)|-τρ,0} ,τ> 0

或

max{▽f(x)-ρ,min{x,▽f(x)+ρ}}=0

在這些理論的基礎(chǔ)上，一些有效求解L1問(wèn)題的算法得以建立，具體可參考文[9-11]等。

然而L1正則化問(wèn)題畢竟是非光滑優(yōu)化問(wèn)題，若能構(gòu)造出其光滑的對(duì)偶問(wèn)題，則更有效的求解該問(wèn)題便是有可能的。另一方面，早在1974年Mond[12]和1981年Mond和Weir[13]便考慮了一類特殊的不可微優(yōu)化問(wèn)題的對(duì)偶問(wèn)題， 受其工作的啟發(fā)，運(yùn)用類似的方法構(gòu)造出L1正則化問(wèn)題的一個(gè)光滑的對(duì)偶問(wèn)題，我們稱之為Mond-Weir型對(duì)偶。

1 最優(yōu)性條件

考慮原始問(wèn)題(P)

minF(x)=f(x)+ρ‖x‖1

證明 記S={y|y=▽f(x0)+ρw,wTx0=‖x0‖1,w∈Rn,|wi|≤1,i=1,2,…,n}，若不存在w∈Rn使命題成立，則0?S，由于S是閉凸集，根據(jù)凸集分離定理，存在z′∈Rn及α∈R，使得

z′Ty≤α<0,?y∈S

(4)

取w∈Rn，使得

這與假設(shè)Z0=?矛盾。

定理2(必要條件) 若x0是問(wèn)題(P)的解，則存在w∈Rn，使得

▽f(x0)+ρw=0

(5)

(6)

(7)

證明 若x0是問(wèn)題(P)的解，則對(duì)任意給定的z∈Rn，及任意的實(shí)數(shù)α>0，有

F(x0+αz)-F(x0) =

兩邊除以α并令α→0+，則對(duì)任意的z∈Rn，

即Z0=?，所以由引理，定理結(jié)論成立。

定理3(充分條件) 若f為凸函數(shù)，且存在x0,w∈Rn使(x0,w)滿足▽f(x0)+ρw=0及‖w‖1≤1，則x0是問(wèn)題(P)的解。

證明 對(duì)任意的x∈Rn，由f(x)是凸函數(shù)，所以

F(x)-F(x0)=f(x)+ρ‖x‖1-f(x0)-ρ‖x0‖1≥

(x-x0)T▽f(x0)+ρ‖x‖1-ρ‖x0‖1

再由式(5)-(6)及xTw≤‖x‖1·‖w‖1，有

2 對(duì)偶性定理

以下我們均假設(shè)f是凸函數(shù)，我們將建立起原問(wèn)題(P)與如下問(wèn)題(D)的對(duì)偶關(guān)系。

(D) maxG(u)=f(u)-uT▽f(u)

s.t.▽f(u)+ρw=0

(8)

‖w‖1≤1

(9)

記問(wèn)題(P)的可行域?yàn)棣窹，問(wèn)題(D)的可行域?yàn)棣窪。

定理4(弱對(duì)偶定理) 問(wèn)題(P)的下確界大于或等于問(wèn)題(D)的上確界。

證明 對(duì)任意x∈ΩP，(u,w)∈ΩD，

F(x)-G(u)=f(x)+ρ‖x‖1-f(u)+

uT▽f(u)≥(x-u)T▽f(u)+ρ‖x‖1+uT▽f(u)

根據(jù)式(8)-(9)，有

F(x)-G(u)≥ρ(‖x‖1-xTw)≥0

所以結(jié)論成立。

定理5(強(qiáng)對(duì)偶定理) 若x0∈Rn是原問(wèn)題(P)的一個(gè)最優(yōu)解，則若存在w∈Rn，使(x0,w)∈ΩD，則(x0,w)必是問(wèn)題(D)的解，且兩問(wèn)題的最值相等。

證明 若x0是問(wèn)題(P)的解，則由定理2存在w使式(5)-(7)成立，而且有

▽f(x0)=

再由定理4，只要(x0,w)∈ΩD，則(x0,w)∈ΩD必是(D)的解。

[1]CHENSS,DONOHODL,SAUNDERSMA.Atomicdecompositionbybasispursuit[J].SIAMJournalonScientificComputing, 1998, 20(1): 33-61.

[2]CHARTRANDR.Exactreconstructionofsparsesignalsvianonconvexminimization[J].SignalProcessingLetters,IEEE, 2007, 14(10): 707-710.

[3]CHARTRANDR,STANEVAV.Restrictedisometrypropertiesandnonconvexcompressivesensing[J].InverseProblems, 2008, 24(3): 035020.

[4]CHENX,ZHOUW.Smoothingnonlinearconjugategradientmethodforimagerestorationusingnonsmoothnonconvexminimization[J].SIAMJournalonImagingSciences, 2010, 3(4): 765-790.

[5]DONOHODL.Compressedsensing[J].InformationTheory,IEEETransactionson, 2006, 52(4): 1289-1306.

[6]FANJ,LIR.Variableselectionvianonconcavepenalizedlikelihoodanditsoracleproperties[J].JournaloftheAmericanStatisticalAssociation, 2001, 96(456): 1348-1360.

[7]TIBSHIRANIR.Regressionshrinkageandselectionviathelasso[J].JournaloftheRoyalStatisticalSociety:SeriesB(Methodological), 1996: 267-288.

[8]CLARKEFH.Optimizationandnonsmoothanalysis[M].SIAM, 1990.

[9]HALEET,YINW,ZHANGY.Fixed-pointcontinuationforl1-minimization:Methodologyandconvergence[J].SIAMJournalonOptimization, 2008, 19(3): 1107-1130.

[10]SHEVADESK,KEERTHISS.Asimpleandefficientalgorithmforgeneselectionusingsparselogisticregression[J].Bioinformatics, 2003, 19(17): 2246-2253.

[11]FUWJ.Penalizedregressions:thebridgeversusthelasso[J].JournalofComputationalandGraphicalStatistics, 1998, 7(3): 397-416.

[12]BERTRAMM.Aclassofnondifferentiablemathematicalprogrammingproblems[J].JournalofMathematicalAnalysisandApplications,1974, 46:169-174.

[13]MONDB,WEIRT.Generalizedconcavityandduality[C].GeneralizedConcavityinOptimizationandEconomics, 1981: 263-279.

Duality Theorem forL1-Regularization Problem

WUFengong1,2

(1. Department of Mathematics, South China Normal University, Guangzhou 510631, China; 2. Department of Mathematics, Guangdong University of Education, Guangzhou 510303, China)

L1-regularizationproblemisanon-smoothunconstrainedoptimizationproblem,whichiswidelyusedinthefieldssuchasvariableselection,datacompressionandimageprocessing.OptimalityconditionsforthesolutionofL1-regularizationproblemisgiven.AndaMond-WeirtypedualproblemforL1-regularizationproblemisformulated,byusingtheseoptimalconditions.Finallyaweakdualitytheoremandastrongdualitytheoremareproved.

L1-regularization;optimalitycondition;dualproblem

2014-03-07

廣東省教育廳科研項(xiàng)目“育苗工程”(自然科學(xué))資助項(xiàng)目(2013LYM_0061)

吳焚供(1980年生)，男；研究方向：最優(yōu)化算法理論；E-mail:wufengong@gdei.edu.cn

10.1347/j.cnki.acta.snus.2015.01.003

O

A

0529-6579(2015)01-0010-03