非凸两分块问题乘子交替方向法的收敛性分析*

邓　钊,晁绵涛,简金宝

(1.广西大学数学与信息科学学院,广西南宁　530004；2.玉林师范学院数学与统计学院,广西玉林　537000)



非凸两分块问题乘子交替方向法的收敛性分析*

邓钊1,晁绵涛1,简金宝2**

(1.广西大学数学与信息科学学院,广西南宁530004；2.玉林师范学院数学与统计学院,广西玉林537000)

(College of Mathematics and Information Science,Guangxi University,Nanning,Guangxi 530004,China;School of Mathematics and Statistics,Yulin Normal University,Yulin,Guangxi,537000,China)

摘要:乘子交替方向法(ADMM)求解大规模问题十分有效.ADMM在凸情形下的收敛性已被清晰认识,但非凸问题ADMM的收敛性结果还很少.本文针对非凸两分块优化问题,在增广拉格朗日函数满足Kurdyka-Lojasiewicz不等式性质且罚参数大于某个常数的条件下,证明了ADMM的收敛性.

关键词：乘子交替方向法Kurdyka-Lojasiewicz不等式非凸优化收敛性

0　引言

【研究意义】乘子交替方向法(ADMM)求解大规模分布式计算问题十分有效.ADMM既能分散地收集和存储这些数据集,又能在并行和分布式的环境下求解这些问题.ADMM适合求解分布式凸优化问题,尤其适用于出现在统计学、机器学习和相关领域中的大规模问题,其重要性日益凸显.【前人研究进展】ADMM的思想最早起源于20世纪50年代,算法在20世纪70年代中期由Glowinski和Marrocco[1],以及Gabay和Mercier[2]首次提出.20世纪80年代,乘子交替方向法的研究和应用非常广泛,直到20世纪90年代中期,乘子交替方向法求解凸优化问题的很多理论结果,已经得到很好的证明.传统ADMM是求解凸两分块问题十分有效的方法[1-2],其直接应用到问题(0.5)的迭代框架如下

(0.1)

其中Lβ(x,y,λ)为问题(0.5)的增广拉格朗日函数,定义如下

(0.2)

在凸情形下,ADMM的收敛性已被充分认识[3].非凸问题ADMM的收敛性分析仅有初步的结果,其研究是当前的热点问题[4-6].文献[7]考虑如下非凸问题

minf(x)+g(y)

s.t.Ax=y,

(0.3)

并提出如下改进的ADMM

(0.4)

其中Δφ是关于强凸函数φ的Bregman距离.当φ=0时,算法(0.4)为传统ADMM.在罚参数充分大且目标函数二阶连续可微的条件下,文献[7]证明算法产生点列的聚点是问题(0.3)的稳定点.

文献[8]分析如下Bregman ADMM算法的收敛性

【本研究切入点】最近,文献[9]在矩阵A列满秩,增广拉格朗日函数满足KL性质(参见定义1.1)且罚参数大于某个常数的条件下,分析了传统ADMM算法(0.1)求解非凸问题(0.3)的全局收敛性.

我们考虑如下两分块极小化问题

minf(x) + g(y)

s.t.Ax+By=0,

(0.5)

其中函数f:Rn→Rn∪{+∞}是一个非凸正常下半连续函数,函数g:Rm→R L-Lipschitz可微,即存在L>0使得‖g(x)-g(y)‖≤L‖x-y‖,∀x,y∈Rn),矩阵A∈Rm×n,B∈Rm×n.这类问题广泛出现在实际应用中,如矩阵分解、图像处理、信号处理等[4-5].

【拟解决的关键问题】本文在不要求矩阵A列满秩,B不一定是单位阵,在Lβ(w)满足KL性质且罚参数β大于某个常数的条件下分析了ADMM算法(0.1)求解问题(0.5)的收敛性.

1　预备知识

下面,给出本文理论分析所需的一些概念与性质.

λ++(BTB)表示矩阵BTB最小正特征值.∂f(x)表示函数f在点x处的极限次微分[5],对于任意x∈Rn是函数f的极小值点的必要条件是:0∈∂f(x),满足这个条件的点称为关键点或稳定点,函数f关键点集记为crit f.

定义1.1[10](Kurdyka-Lojasiewicz性质)设函数f:Rn→Rn∪{+∞}是正常下半连续函数,对于任意实数η1,η2(η1<η2),令[η1

(i)φ(0)=0;

(ii)φ在0处连续,在区间(0,η)上一阶连续可微;

(iii)φ′(s)>0,∀s∈(0,η);

(iv)对于任意的x∈U∩[f(x*)

f(x*)+η],有如下Kurdyka-Lojasiewicz不等式成立

φ ′(f(x)-f(x*))d(0,∂ f(x))≥1.

则称函数f在点x*处满足Kurdyka-Lojasiewicz性质(简称KL性质).

满足上述性质(i)、(ii)、(iii)的函数全体记为Φη.

引理1.1[11](uniformized KL property)设Ω是一个紧集,函数f:Rn→Rn∪{+∞}是正常下半连续函数.设函数f在集合Ω上取常数,并在Ω中任一点处满足KL性质,则存在>0,η>0,φ ∈Φη,对于任意的和x∈{x∈Rn:d(x,ω)<},有

引理1.2[12]若h:Rn→R为L-Lipschitz可微函

数,则对任意的x,y∈Rn,有

2　收敛性分析

由算法(0.1)中每个子问题的最优性条件,有

(2.1)

进一步,可得

(2.2)

本文的收敛性建立在如下假设条件下.

假设2.1假设以下条件成立

(i)Im(A)⊆Im(B);

首先，证明{Lβ(wk)}k∈N是递减序列.

证明由增广拉格朗日函数的定义,可得

(2.3)

利用yk+1的最优性可得

(2.4)

由引理1.2和式(2.2)中第二式可得

把上式代入式(2.4)可得

(2.5)

由λk+1=λk-β(Axk+1+Byk+1)可得

故

把上式代入式(2.5)右端可得

(2.6)

由λk+1=λk-β(Axk+1+Byk+1)可得

λk+1-λk=-β(Axk+1+Byk+1)∈Im(B).

‖λk+1-λk‖≤μ‖B(λk+1-λk)‖=μ‖g(yk+1)-g(yk)‖≤μL‖yk+1-yk‖.

(2.7)

由H的性质可得yk=H(Byk),从而

‖yk+1-yk‖=‖H(Byk+1)-H(Byk)‖≤M‖B(yk+1-yk)‖.

(2.8)

结合式(2.6)和引理2.1可得

Lβ(xk+1,yk+1,λk+1)≤Lβ(xk+1,yk,λk)+

结合式(2.7)、式(2.8)有

利用xk+1的最优性可得

故序列{Lβ(wkj)}有下界,又序列{Lβ(wk)}k∈N单调递减,所以Lβ(wkj)收敛并且Lβ(wk)≥Lβ(w*).由引理2.1可得

由δ>0及n的任意性可得

上式结合式(2.7)可得

两式相减,可得

λk+1-λk=(λk-λk-1)+β(Axk-Axk+1)+β(Byk-Byk+1).

利用不等式(a+b+c)2≤3(a2+b2+c2)可得

‖β(Axk-Axk+1)‖2≤3(‖λk+1-λk‖2+‖λk-λk-1‖2+β2‖B(yk+1-yk)‖2).

(2.9)

由F的性质可得xk=F(Axk),进而

(2.10)

由式(2.9)和式(2.10)可得

引理2.3存在ζ>0,对于任意k有

d(0,∂Lβ(wk+1))≤ζ‖yk+1-yk‖.

证明由增广拉格朗日函数定义,可得

(2.11)

进一步结合式(2.2)可得

(2.12)

令ζ:=ζ1+μLζ2,结合式(2.7)可得

d(0,∂Lβ(wk+1))≤ζ‖yk+1-yk‖.

引理2.4设序列{wk}的全体极限点记为S(w0),则

(i)S(w0)是一个非空紧集,并且

d(wk,S(w0))→0,k→+∞;

(ii)S(w0)⊂critLβ;

(iii)Lβ(·)在S(w0)上取有限值且为常数,且

证明(i)式由S(w0)的定义直接可得.

(ii)设(x*,y*,λ*)∈S(w0),则存在子列{(xkj,ykj,λkj)}使得(xkj,ykj,λkj)→(x*,y*,λ*),(kj→+∞).由xk+1的最优性有

Lβ(xk+1,yk,λk)≤Lβ(x*,yk,λk).

由引理2.2可知‖wk+1-wk‖→0,从而(xkj+1,ykj+1,λkj+1)→(x*,y*,λ*).又Lβ(·)关于y,λ连续,

则有

由函数Lβ(·)的下半连续性,有

即w*⊂critLβ.

(iii)对于任意点(x*,y*,λ*)∈S(w0),存在子列(xkj,ykj,λkj)→(x*,y*,λ*).结合Lβ(xkj+1)收敛,以及{Lβ(wk)}k∈N单调递减,可得

最后,给出非凸问题(0.5)的ADMM算法(0.1)的收敛性分析.

定理2.1若Lβ(w)满足KL性质,则

(ii)序列{wk}收敛到函数Lβ(·)的一个关键点.

Lβ(w*)(∀w*∈S(w0))成立.考虑如下两种情形:

(i)存在整数k0使得Lβ(wk0)=Lβ(w*)成立,由引理2.1可知,对于任意的k>k0,有

‖yk+1-yk‖2≤Lβ(wk)-Lβ(wk+1)≤

Lβ(wk0)-Lβ(w*)=0,

因此,对于任意的k>k0,有yk+1=yk.结合式(2.7)、式(2.9)、式(2.10)可知,对于任意的k>k0+1,有wk+1=wk成立,结论成立.

d(wk,S(w0))<ε,

Lβ(w*)

由于S(w0)是非空紧集,函数Lβ(·)在集合

S(w0)上是常数,由引理1.1得

φ′(Lβ(wk)-Lβ(w*))d(0,∂Lβ(wk))≥

由函数φ的凹性,可得

φ(Lβ(wk)-Lβ(w*))-φ(Lβ(wk+1)-

Lβ(w*))≥φ′(Lβ(wk)-Lβ(w*))(Lβ(wk)-Lβ(wk+1)).

由引理2.3及φ′(Lβ(wk)-Lβ(w*))>0,可得

Lβ(wk)-Lβ(wk+1)≤

ζ‖yk-yk-1‖[φ(Lβ(wk)-Lβ(w*))-

φ(Lβ(wk+1)-Lβ(w*))].

δ‖yk+1-yk‖2≤ζ‖yk-yk-1‖Δk,k+1,

即

由上式可得

注意到φ(Lβ(wm+1)-Lβ(w*))>0,移项并且令m→+∞,可得

所以

由式(2.7)可得

另一方面,由式(2.9)、式(2.10)可得

‖yk+1-yk‖+‖λk+1-λk‖,

所以

进一步可知序列wk是Cauchy序列(参见文献[11]),所以序列{wk}收敛,定理得证.

3　结论

本文针对非凸两分块优化问题,在不要求矩阵A列满秩,B不一定是单位阵,在Lβ(w)满足Kurdyka-Lojasiewicz性质且罚参数大于某个常数的条件下,证明了非凸问题ADMM的收敛性.

参考文献：

[1]GLOWINSKI R,MARROCO A.Sur l’approximation,par elements finis d’ordre un,et la resolution,par penalisation-dualité,d’une classe de problèms de Dirichlet nonlineares[J].Revue Francaise d’Automatique,Informatique et Recherche Opérationelle,Series R,1975,31(5/6):41-76.

[2]GABAY D,MERCIER B.A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J].Computers &Mathematics with Applications,1976,2(1):17-40.

[3]BOYD S,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.

[4]YANG L,PONG T K,CHEN X J.Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction[J].Mathematics,2016.

[5]HONG M Y,LUO Z Q,RAZAVIYAYN M.Convergen- ce analysis of alternating direction method of multipliers for a family of nonconvex problems[J].SIAM Journal on Optimization,2014,26(1):337-364.

[6]WANG Y,YIN W T,ZENG J S.Global Convergence of ADMM in Nonconvex Nonsmooth Optimization[R].UCLA CAM Report 15-62,2015.

[7]LI G Y,PONG T K.Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems[J].Mathematical Programming,2016,159(1/2):374-401.

[8]WANG F H,XU Z B,XU H K.Convergence of multi-block Bregman ADMM for nonconvex composite problems[J].Mathematics,2015,arXiv:1505.03063vl:1-25.

[9]GUO K,HAND R,WUT T.Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints[J].International Journal of Computer Mathematics,2016:1-17.

[10]BOLTE J,DANIILIDIS A,LEY O,et al.Characterizations of Lojasiewicz inequalities and applications[J].arXiv:0802.0826vl,2008:1-48.

[11]ATTOUCH H,BOLTE J,REDONT P,et al.A Proximal alternating minimization and projection methods for nonconvex problems:An approach based on the Kurdyka-Lojasiewicz inequality[J].Mathematics of Operations Research,2010,35(2):438-457.

[12]BOLTE J,SABACH S,TEBOULLE M.Proximal alternating linearized minimization for nonconvex and nonsmooth problem[J].Mathematical Programming,2013,146(1/2):459-494.

(责任编辑：米慧芝)

Convergence Analysis of Alternating Direction Method of Multipliers for Two Block Nonconvex Problems

DENG Zhao1,CHAO Miantao1,JIAN Jinbao2

Key words：Alternating Direction Method of Multipliers,Kurdyka-Lojasiewicz inequality,nonconvex optimization,convergence

Abstract：The Alternating Direction Method of Multipliers(ADMM) is an effective method for large scale optimization problems.While the convergence of ADMM has been clearly recognized in the case of convex,the convergence result of ADMM in the case of nonconvex is still an open problem.In this paper,under the assumption that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz inequality and the penalty parameter is greater than a constant,we analyze the convergence of ADMM for a class of nonconvex optimization problems whose objective function is the sum of two block nonconvex functions.

收稿日期：2016-07-01

作者简介：邓钊(1991-),男,硕士研究生,主要从事最优化理论与方法研究。

中图分类号:O221.2

文献标识码：A

文章编号：1005-9164(2016)05-0422-06

修回日期：2016-10-27

*国家自然科学基金项目(11601095),广西自然科学基金项目(2014GXNSFFA118001，2016GXNSFDA380019)和广西高校科研项目(ZD201407)资助。

**通信作者：简金宝(1964-),男,教授,博士,博士生导师,主要从事最优化理论与算法及应用研究，E-mail:jianjb@gxu.edu.cn。

广西科学Guangxi Sciences 2016,23(5):422～427

网络优先数字出版时间：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.005

网络优先数字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1520.010.html