求解可分離凸優(yōu)化問題的非精確混合分裂算法

曾玉華，楊 赟，彭 拯

(1．湖南大學(xué)數(shù)學(xué)與計量經(jīng)濟(jì)學(xué)院，湖南長沙 410082;2．湖南第一師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院，湖南長沙 410025;3．福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建福州 350116)

0 引言

形如的優(yōu)化問題被稱為線性約束結(jié)構(gòu)凸優(yōu)化問題，其中θi(xi)為閉凸集Xi上的凸函數(shù)．

當(dāng)m=1時，問題(1)就是一般線性約束凸優(yōu)化問題，增廣Lagrangian算法［1］和臨近點收縮算法［2］等經(jīng)典算法可用于求解此類問題．當(dāng)m≥2時，問題(1)有著許多實際應(yīng)用，如信號處理［3］，圖像恢復(fù)［4］，統(tǒng)計學(xué)習(xí)［5］，等等．正是由于這些應(yīng)用，國內(nèi)外學(xué)者研究了當(dāng)m=2，3時可分離結(jié)構(gòu)凸優(yōu)化問題的求解算法，算子分裂方法是求解這類問題最有效算法之一．算子分裂算法包括交替方向法和平行分裂算法．交替方向法最早可以追溯到Gabay［6］，當(dāng)m=2時，交替方向法能夠快速有效地求解問題(1);當(dāng)m ＞2時，交替方向法的收斂性無法得到保證，見He等［7］．為此，He［8］提出了一種平行分裂增廣Lagrangian算法，該方法是一種基于預(yù)測－校正的收縮算法，能夠很好地拓展到求解m＞2且具有可分離結(jié)構(gòu)的凸優(yōu)化問題．結(jié)合交替方向法和平行分裂算法，許多學(xué)者針對問題(1)提出了多種分裂算法，如He等［9］通過在子問題的增廣拉格朗日函數(shù)上增加臨近點項，并線性化增廣拉格朗日函數(shù)，提出了臨近點交替方向法及三種線性化臨近點交替方向法，該方法達(dá)到了簡化子問題的作用;Han等［10］給出了一種臨近點平行分裂算法;最近，He等［11］利用分塊性質(zhì)提出了一種Block－Wise交替方向法．

本文研究當(dāng)m=4時，問題(1)的求解算法．即

全文假設(shè):

① Xi為 Rni(i=1，2，3，4)的簡單閉凸集，且 n1+n2+n3+n4=n，Ai∈ Rm×ni;

②θi(xi)為Xi上的可微凸函數(shù)，記fi(xi)=▽θi(xi)，且fi(xi)在Xi上Lipschitz連續(xù)，即存在常數(shù)Lfi＞0，使得 fi(xi)－fi(x'i)≤Lfixi－x'i，?xi，x'i∈Xi;

③問題(2)的解集非空．

本文提出一種非精確混合分裂算法求解問題(2)，該算法在每一輪迭代中求解四個子問題．依據(jù)計算工作量均衡的原則，算法將四個子問題平均分為兩組，在每組內(nèi)部執(zhí)行平行分裂算法，兩組之間執(zhí)行交替方向算法．

1 預(yù)備知識及若干記號

其中

定義1 f:W→Rn是單調(diào)算子當(dāng)且僅當(dāng)

引理1 設(shè)W?Rn是閉凸集，PW(v)表示v在凸集W上的投影，則為了方便算法描述與收斂性分析，下列記號將被用到:H∈Sn++為對稱正定矩陣，

2 算法描述

先給出求解問題(2)的非精確平行－交替混合算法，非精確混合分裂算法(HSM)．

S0:給定ε ＞ 0，r0＞ 0，ν∈(0，1)，γ∈(0，2)和矩陣H，迭代起始點w0=(x01，x02，x03，x04，λ0)∈Rn+m，令k=0．

且

S2:產(chǎn)生迭代點，wk+1=(x1k+1，x2k+1，x3k+1，x4k+1，λk+1)，其中校正1

或者，校正2

這里

注 在式(10)中，rk可通過自適應(yīng)線搜索方法得到(參見文獻(xiàn)［12］)，即定義

當(dāng)νk＞ν時，rk:=rk×νk×1．25;當(dāng)νk＜ν時，即為所要預(yù)測點．

由文獻(xiàn)［12］可知，{rk}是非單調(diào)遞減且有上界，即存在r0，使得

引理2 滿足條件(10)的參數(shù)rk能在有限次循環(huán)得到．

證明 由式(4)的ξ(vk，)定義可知:

其中:Lf=max{Li:i=1，2，3，4}，因此，只要rk≥(Lf+N)ν，式(10)就成立，即有限次循環(huán)能使參數(shù)rk滿足條件(10)．

引理3 若wk=，則為變分不等式VI(W，F(xiàn))的解．

當(dāng) wk=時，d2(wk，)=F()，d1(wk，)=0．因此

3 收斂性分析

其中:

證明 由d1(wk，)的定義，結(jié)合條件(15)與Cauchy－Schwarz不等式，可得到 d1(wk，)的上界，具體計算過程從略．

定理1 存在一個α0＞0，使得α*k≥α0對于所有的迭代指標(biāo)k成立，其中:α0=

其中:c=min{(1 － v)r0，0．5 H－1} ＞ 0．

證明 直接計算，并結(jié)合矩陣H的正定性，可得出結(jié)果。具體證明從略。

證明 由式(14)，(17)和(18)，結(jié)論顯然成立．

引理6 對于任意的w*∈W*，由混合分裂算法(HSM)產(chǎn)生的序列{wk}滿足

證明 由假設(shè)②可知，fi為單調(diào)函數(shù)(參見文獻(xiàn)［13］)，因此F(w)為單調(diào)，所以

引理7 對于任意的w*∈W*，由混合分裂算法(HSM)產(chǎn)生的序列{w^k}，{wk}滿足

證明 由于w*，wk∈W，令w'=w*，w'=wk，(16)可轉(zhuǎn)化為

以上兩式分別加上式(19)，可得

定理2 序列{wk}由混合分裂算法(HSM)的校正1產(chǎn)生，w*∈W*，那么

證明 由式(12)可知:

上式中第一個不等式由式(14)和(20)可得，第二個不等式由式(17)和定理1可得．定理得證．

定理3 序列{wk}由混合分裂算法(HSM)的校正2產(chǎn)生，w*∈W*，那么

證明 由式(3)和(20)的第二個式子可知

因為

結(jié)合式(14)，(17)和(19)，可得

定理4 設(shè)w∞為VI(W，F(xiàn))的一個解．由混合分裂算法(HSM)產(chǎn)生的迭代序列{wk}收斂于VI(W，F(xiàn))的一個解．

證明 該定理證明類似于文獻(xiàn)［10］．

4 結(jié)論

針對一類帶有四個可分離塊變量的凸優(yōu)化問題，提出一種基于分組的非精確混合分裂算法，即非精確兩兩平行－交替混合分裂算法(HSM)．該算法依據(jù)子問題計算工作量將子問題分為兩組．每一組包含兩個子問題，按照平行分裂算法的迭代格式來求解．兩組之間按照交替方向算法的迭代格式求解．該算法在一定條件下可以看作分塊乘子交替方向算法［11］的一種特例．算法允許子問題非精確求解，本文證明了非精確混合分裂算法的全局收斂性．與已有的分裂方法相比較，本文所提出算法由于允許非精確求解子問題，從而更具有實用性．同時，組間的交替方向法能夠有效地提高實際收斂速度．

［1］Nocedal J，Wright SJ．Numerical optimization［M］．2nd．［s．l．］:Springer，1999．

［2］He Bingsheng，Yuan Xiaoming．A contraction method with implementable proximal regularization for linearly constrained convex programming［EB/OL］．［2011 －02 －21］．http://www．optimization － online．org/DB_HTML//2010/11/2817．html．

［3］Chen SS，Donoho D L，Saunders M A．Atomic decomposition by basis pursuit［J］．SIAM Journal on Scientific Computing，1998，20(1):33－61．

［4］Ng M，Weiss X M，Yuan Xiaoming．Solving constrained total－variation image restoration and reconstruct－ion problems via alternating direction methods［J］．SIAM Journal on Scientific Computing，2010，32(5):2 710 －2 736．

［5］Stephen B，Parikh N，Chu E，et al．Distributed optimization and statistical learning via the alternating direction method of multipliers［J］．Foundations and Trends in Machine Learning，2011，3(1):1 －122．

［6］Gabay D，Mercier B．A dual algorithm for the solution of nonlinear variational problems via finite element approxim －ation［J］．Computers＆ Mathematics with Applications，1976，2(1):17－40．

［7］Chen Caihua，He Bingsheng，Ye Yinyu，et al．The direct extension of ADMM for multi－ block convex minimization problems is not necessarily convergent［EB/OL］．［2013 －12 －01］．http://www．optimization － online．org/DB_FILE/2013/09/4059．pdf．

［8］He Bingsheng．Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities［J］．Computation Optimization and Applications，2009，42(2):195－212．

［9］He Bongsheng，Peng Zheng，Wang Xiangfeng．Proximal alternating direction －based contraction methods for separable linearly constrained convex optimization［J］．Frontiers of Mathematics in China，2011，6(1):79－114．

［10］Han Deren，He Hongjing，Xu Lingling．A proximal parallel splitting method for minimizing sum of convex functions with linear constraints［J］．Journal of Computational and Applied Mathematics，2014，256(1):36 －51．

［11］He Bingsheng，Yuan Xiaoming．Block－wise alternating direction method of multipliers for multiple－block convex programming and beyond［EB/OL］．［2014－08－24］．http://www．math．hkbu．edu．hk/～xmyuan/Paper/Two－Group－ADMM －HY － Aug12．pdf．

［12］He Bingsheng，Liao Lizhi，Qian Maijian．Alternating projection based prediction －correction methods for structured variational inequalities［J］．Journal of Computational Mathematics，2006，24(6):693 －710．

［13］Fletcher R．Practical methods of optimization［M］．2nd．［s．l．］:John Wiley ＆ Sons，2013．