非凸不可分離問題的廣義交替方向乘子法的收斂性

薛中會(huì)， 胡惠晴， 黨亞崢

（1.上海出版印刷高等?？茖W(xué)校，上海 200093；2.上海理工大學(xué) 管理學(xué)院，上海 200093）

1 問題的提出

考慮具有非凸不可分離的優(yōu)化問題

式中：f:Rn→R∪{+∞}是恰當(dāng)?shù)南掳脒B續(xù)函數(shù)；h:Rm→R是連續(xù)可微函數(shù)；g:Rn×Rm→R是光滑函數(shù)，且x和y是不可分離的。

問題（1）的一個(gè)特殊形式是沒有函數(shù)g，且目標(biāo)函數(shù)是可分離的，即

利用交替方向乘子法（ADMM）求解問題（2）的一種有效算法的迭代格式為

式中： λ為拉格朗日乘子； β為懲罰參數(shù)， β >0。

ADMM算法通過引入一個(gè)新的輔助變量，將原問題改寫為一個(gè)目標(biāo)函數(shù)可分離且輔助變量與原變量是線性約束的形式，通過交替更新原變量、輔助變量和對(duì)偶變量來(lái)迭代求解問題的最優(yōu)解。通過引入合適的輔助變量，每個(gè)迭代步驟可以變成非常簡(jiǎn)單的子問題，通?？梢允諗康椒€(wěn)定點(diǎn)或者被并行求解。這使得ADMM算法適用于求解大規(guī)模的優(yōu)化問題。

對(duì)于f和h都是凸函數(shù)的情況，ADMM（式（3））的收斂性得到了很好的證明，并且對(duì)其進(jìn)行了收斂率分析[1-3]。在沒有凸性的假設(shè)下，更難以證明ADMM的收斂性。在這方面的研究取得了一些進(jìn)展[4-8]。Guo等[4]利用經(jīng)典ADMM算法求解非凸多塊可分離最優(yōu)化問題，證明了其收斂性，并且提出了一些充分條件，保證了算法的超線性和線性收斂速率。Li等[5]提出了一種近似ADMM算法來(lái)解決非凸非光滑優(yōu)化問題，證明了當(dāng)罰參數(shù)足夠大且生成的序列有聚點(diǎn)時(shí)，算法所產(chǎn)生迭代點(diǎn)列收斂到穩(wěn)定點(diǎn)。

目前的研究大多數(shù)考慮如下的問題：

然而，由于函數(shù)g的存在，即使目標(biāo)函數(shù)是凸的情況，對(duì)ADMM（式（4））的收斂性分析的研究還處于初期，研究成果很少。并且由于約束條件中矩陣B的存在，使得收斂性分析變得更加困難。

Gao等[9]考慮了函數(shù)g是光滑函數(shù)以及函數(shù)f，h是凸函數(shù)的情況。通過假設(shè) ?g是利普希茨連續(xù)以及h強(qiáng)凸，證明了由ADMM算法生成的序列收斂到問題（4）的最優(yōu)解。Chen等[10]在耦合函數(shù)g是二次函數(shù)的情況下，分析了ADMM解決問題（4）的收斂性。Liu等[11]提出了線性化ADMM來(lái)解決非凸非光滑的目標(biāo)問題，通過將目標(biāo)中的可微項(xiàng)以及增廣項(xiàng)線性化，證明了算法的收斂性，然后將問題推廣到多塊并行的ADMM算法中。以上研究都是矩陣B為單位陣的情況。在耦合函數(shù)缺失的情況下，Wang等[12]研究了用Bregman距離修飾ADMM算法（BADMM算法），分別分析了矩陣B單射和非單射情況下算法的收斂性，證明了BADMM算法生成的序列收斂到穩(wěn)定點(diǎn)。Guo等[13]提出了一種廣義的ADMM算法來(lái)求解問題（4）。

本文研究廣義ADMM算法的收斂性，通過假設(shè)矩陣B列滿秩以及增廣拉格朗日函數(shù)滿足K-L不等式，當(dāng)罰參數(shù)足夠大時(shí)，證明了算法產(chǎn)生的序列收斂到其穩(wěn)定點(diǎn)，從而證明了算法的收斂性。

2 預(yù)備知識(shí)

現(xiàn)給出理論分析所需要的概念和性質(zhì)。

對(duì)于任意x∈Rn是函數(shù)f的極小值點(diǎn)的必要條件是 0 ∈?f(x)，滿足這個(gè)條件的點(diǎn)稱為穩(wěn)定點(diǎn)，函數(shù)f的穩(wěn)定點(diǎn)集記作 cr itf。

定義1令f:Rn→R∪{+∞}為正常的下半連續(xù)函數(shù)。

a.Fréchet次微分。

函數(shù)f在x∈domf的Fréchet次微分，定義為滿足下列關(guān)系x?∈ Rn的集合：

b.極限次微分。

函數(shù)f在x∈domf的極限次微分，定義為

?f(x):={x?∈Rn:?xn→x,f(xn)→f(x),x?n∈??f(xn),x?n→x?}，記作?f(x)。

c.若在函數(shù)f的定義域中滿足 0 ∈ ?f(x?)，則稱x?為f的穩(wěn)定解。

d.對(duì) ?x,y∈domf，若滿足∥f(x)?f(y)∥≤L∥x?y∥，則稱f滿足Lipschitz連續(xù)條件，L為L(zhǎng)ipschitz常數(shù)。

引理1h:Rm→R是連續(xù)可微函數(shù)，且 ?h是關(guān)于常數(shù)L利普希茨連續(xù)的，那么，對(duì)于任意的x,y∈Rn，有

引理2（K?L不等式）設(shè)函數(shù)f:Rn→R∪{+∞}是恰當(dāng)下半連續(xù)函數(shù)，對(duì)于 ? ∞<η1<η2<+∞，令

若存在 η ∈(0,+∞]，x?的領(lǐng)域U以及一個(gè)連續(xù)的凹函數(shù) φ : [0,η)→R+，滿足如下條件：

a.φ( 0 )=0；

b.φ在 (0 ,η)連續(xù)可微且在0處連續(xù)；

c.φ′(s)>0,?s∈ (0,η)；[]

d.對(duì) 所 有 的x∈U∩f(x?)

成立，則稱函數(shù)f在x?∈dom?f上滿足K?L性質(zhì)。

引理3（一致K?L性質(zhì)） ? 是緊集，設(shè)函數(shù)f:Rn→R∪{+∞}是恰當(dāng)下半連續(xù)函數(shù)。假設(shè)f在?上是常數(shù)并且在? 上的每個(gè)點(diǎn)滿足K?L性質(zhì)，那么，存在 ε >0,η>0以及 φ ∈ Φη，使得對(duì)于任意的x?∈ ?以及x∈{x∈Rn:d(x,?)<ε}∩{f(x?)

3 算法及收斂性分析

針對(duì)問題（1），本文提出了一種廣義交替方向乘子法（GADMM），即

其中， α ∈(0,2)是一個(gè)松弛因子，顯然，當(dāng)α=1時(shí)，GADMM即退化成經(jīng)典的ADMM算法，并且當(dāng)g≡0時(shí)退化成經(jīng)典的GADMM算法。

在證明收斂性之前，先給出式（5）的變形，由最優(yōu)性條件得到

利用式（6）的最后一個(gè)等式，得到

假設(shè)：令f:Rn→R∪{+∞}是弱凸函數(shù)，常數(shù)ω>0；h:Rm→R是連續(xù)可微函數(shù)，它的梯度 ?h是利普希茨連續(xù)的，其利普希茨常數(shù)L1>0；g:Rn×Rm→R是光滑函數(shù)。問題（1）滿足下列條件：

a.矩陣B是列滿秩的，且 Im (A)?Im(B)；

c.?g在Rn×Rm的有界子集上是利普希茨連續(xù)的，即對(duì)于每個(gè)有界子集B1×B2?Rn×Rm，存在M>0，使得對(duì)于所有的(xi,yi)∈B1×B2,i=1,2，∥?xH(x1,y1)??xH(x2,y2)，?yH(x1,y1)??yH(x2,y2)∥≤M∥(x1?y1，x2?y2)∥

e.存在L2,L3>0,使得

式中： α ∈(0,2)為松弛因子。()()

在收斂分析中，記ωk:=xk,yk,zk及vk:=xk,yk。問題（1）的增廣拉格朗日函數(shù)為

式中： γ是與線性約束相關(guān)的拉格朗日乘子； β是懲罰參數(shù)， β >0。

此外，設(shè)

引理4在上述假設(shè)條件下，對(duì)于任意的l>k，有

式中， λBTB是BTB的最小的特征值。

證明由式（4）的第3項(xiàng)，以及假設(shè)的a，對(duì)于2個(gè)整數(shù)l>k，有 γl?γk∈ Im(B)。

由于B∈ Rn×q是列滿秩的，因此，存在P∈ Rq×q，Q∈Rq×n，且(矩陣)P可逆，QQT=In×(n，)BT=PQ。由Im(B)=ImQT，可得γl?γk∈ ImQT，∥γl?γk∥2=由此得到

式中， λPTP是PTP的最小的特征值。

由矩陣P和Q的 定義，有 λBTB=λPPT，又因?yàn)榫€性代數(shù)的常見結(jié)論 λPTP=λPPT，因此，λPTP=λBTB。{()}

引理5令xk,yk,γk由算法GADMM式（式（5））產(chǎn)生，則有

證明首先將增廣拉格朗日函數(shù)的差分拆分，得到

根據(jù)定義，有

因?yàn)?，f是關(guān)于常數(shù) ω的弱凸函數(shù)，因此，由式（7）的第1個(gè)關(guān)系式得到

根據(jù)假設(shè)的d，有

將上述3個(gè)不等式代入式（10），可得

類似地，

其中，最后1個(gè)等式由

得到。通過 ?h的利普希茨連續(xù)性，由引理1及式（7）的第2個(gè)不等式，可得

又由于B是列滿秩的，可得

將上述3個(gè)等式相加并代入式（12），可得

現(xiàn)計(jì)算式（9）剩余的項(xiàng)。

事實(shí)上，

且

將式（14）和式（15）相加，可得

根據(jù)引理4可得

其中，第2個(gè)不等式是由 ?h的利普希茨連續(xù)性和假設(shè)的c得到。因此，

將式（17）代入式（16），得到

因此，將式（11），（13），（18）代入式（9），得到

其中，第2個(gè)不等式由假設(shè)的e得到，在最后1個(gè)等式中，令

由假設(shè)的c可知， δ >0。

引理6令序列由算法GADMM生成，且假設(shè)有界，因此，有

證明由于序列是有界的，則存在收斂子列且。由h和g的 連續(xù)性和f的下半連續(xù)性可知是下半連續(xù)的，從而可得

由 δ >0可得

因此，

此外，由式（17）和式（20）可得

因此，

引理7存在 ξ >0，使得

證明根據(jù)增廣拉格朗日函數(shù)的定義，可得

進(jìn)一步結(jié)合式式（7），可得

令

又由假設(shè)的c可得

根據(jù)式（17）可得

因此，由式（24）～（26）可得

令

由上式可以得到式（21）。

引理8假設(shè)序列為算法生成的有界序列，其所(有)極限點(diǎn)記為Sω0，則(())

a.Sω0是一個(gè)非空緊集，并且dωk,Sω0→ 0,k→+∞；

證明a.由Sω0的定義可直接得到。

b.對(duì)于任意點(diǎn) (x?,y?,γ?)∈S(ω0)，存在子列

根據(jù)增廣拉格朗日函數(shù)的定義，式（5）的x子問題等價(jià)于

即xk+1是關(guān)于變量x的全局最小點(diǎn)，由此可得

又因?yàn)長(zhǎng)β(·)關(guān)于y和 γ連續(xù)，則有

由函數(shù)Lβ(·)的下半連續(xù)性可得

因此，結(jié)合式（27）和式（28），可得

由此可以推斷

定理1若Lβ(·)滿足K?L性質(zhì)，則+∞，且序列收斂到Lβ(·)的一個(gè)穩(wěn)定點(diǎn)。

證明由引理8可知，因此，考慮以下2種情況：

a.存在整數(shù)k0使得由引理5可知，

因此，對(duì)任意的k>k0，有vk+1=vk，結(jié)合式（16）可知，對(duì)于任意的k>k0+1，有 ωk+1=ωk成立。

b.假設(shè)對(duì)于任意的k都有成立，存在使得對(duì)于所有的，有

其中，

由于

結(jié)合引理5，可得式（30）成立，且由式（30）可得

進(jìn)一步，將上式從k? +1到m求和，得到

進(jìn)一步由式（17）可得

此外，由于

因此，

4 結(jié) 論

研究了非凸不可分離的線性約束優(yōu)化問題，以及求解該問題的廣義交替方向乘子法（GADMM），在矩陣B不是單位陣的情況下，要求其列滿秩，通過假設(shè)增廣拉格朗日函數(shù)滿足K-L不等式，證明了當(dāng)懲罰參數(shù)大于一定的閾值時(shí)，算法生成的序列收斂到增廣拉格朗日函數(shù)的穩(wěn)定點(diǎn)。