三分块凸优化问题的改进Peaceman-Rachford分裂法

刘学念,黄 甜

(1.湖北师范大学 数学与统计学院,湖北 黄石 43500;2.山东外事职业大学 教育学院,山东 威海 264500)

0 引言

考虑如下带有线性约束的两分块可分凸优化问题的数学模型:

(1)

其中θi∶ni→∪(+∞)(i=1,2)是闭正常函数(不一定光滑),Ai∈m×ni(i=1,2),b∈m是给定的矩阵和向量,χi∈ni(i=1,2)是非空闭凸集。假设此问题的解集非空,则问题(1)的增广拉格朗日函数为:

(2)

其中λ∈m是拉格朗日乘子,β>0是罚参数。

(3)

Gabay在文献[6]中指出,较ADMM相比,PR分裂法的鲁棒性较差,即需要在更严格的条件下才能收敛。但在确保收敛前提下,它的收敛速度更快。很多学者对此加以研究,He等人[7]于2014年提出对两个乘子迭代中加入相同的松弛因子以保证其迭代序列的严格收缩。于2016年,He等[8]又采取不同的步长来更新拉格朗日乘数,减少了算法中的迭代次数。Gu等[9]在子问题中加入半邻近项,提出半邻近PR分裂法,使该方法更加灵活。Du等人[10]于2020年通过变分不等式研究证明了带有Bregman距离的对称ADMM的全局收敛性,该算法的迭代形式为:

(4)

本文主要考虑三分块凸优化问题:

(5)

其中θi∶ni→∪(+∞)(i=1,2,3)是闭正常函数(不一定光滑),Ai∈m×ni(i=1,2,3),b∈m是列满秩的矩阵和向量,Xi∈ni(i=1,2,3)是非空闭凸集。假设此问题的解集非空。提出带有Bregman距离的PR分裂法的改进迭代形式为:

(6)

其中β>0,α和γ是松弛因子且α∈(0,1),γ∈(0,1-α),引入的Bregman距离函数为δ-强凸。本文从变分不等式的角度去研究算法(6)的全局收敛性,以及该算法在遍历意义O(1/t)下的最坏收敛速率。

1 预备知识

w*∈Ω,θ(u)-θ(u*)+(w-w*)TF(w*)≥0,∀w∈Ω

(7)

根据上述定义,很容易得知映射F是单调的,也就是F满足:

所以公式(7)可以改写为:

w*∈Ω,θ(u)-θ(u*)+(w-w*)TF(w)≥0,∀w∈Ω

(8)

设定义变分不等式(7)的解集是Ω*,并且在问题(5)的解集非空的情况下Ω*非空。

为了后面的分析更加方便,在此说明几个用到的理论。

引理1[12]设集合X∈n是一个闭凸集,θ(x)为凸函数,f(x)为可微凸函数,假设min{θ(x)+f(x)|x∈X}的解集非空,则:

x*∈arg min{θ(x)+f(x)|x∈X}

成立当且仅当

命题1[11]设ρ(x)是可微凸函数,Bρ(x,y)是Bregman距离,对任意x,y∈dom(ρ)有:

1) 一般情况下,Bρ(x,y)=Bρ(y,x)是不成立的;

2)Bρ(x,y)≥0,Bρ(x,x)=0;

3)y固定时,Bρ(x,y)关于x时凸的;

命题2[10]如果ρA,对于任意x,y∈dom(ρ),则有

引理2[14]对于可微凸函数σ,给定向量a,b,c,d,有:

命题3[10]对于可微凸函数ρ,ψ,φ,以下式子成立:

2 收敛性检验

(9)

并定义下列矩阵:

(10)

(11)

则能得到以下结论。

(12)

(13)

(14)

(15)

(16)

联立(13)至(16)可得引理(3)成立。

引理4 设{wk}是由算法(6)产生的序列,则有:

(17)

接着,我们定义如下矩阵:

(18)

根据式(10)和式(11)中Q,M的定义可以得到H=QM-1.因为α∈(0,1),γ∈(0,1-α),对称矩阵H的所有顺序主子式均大于零,所以H为正定矩阵。

接着定义G=QT+Q-MTHM,其中:

在松弛因子α∈(0,1)范围下,矩阵QT+Q为对称正定阵。

则:

(19)

由简单分析可得上述对称矩阵G是不定的,所以此时算法(6)的收敛结果不能由文献[14]中的结果来保证,需要对矩阵G进一步计算,矩阵G可改写为:

当α∈(0,1),γ∈(0,1-α),把矩阵G分成两部分G=G1+G2,其中

其中A2,A3是列满秩的矩阵,则矩阵G20.再假设ψ,φ是δ-强凸的,并满足δI+G1≻ 0,则有

(20)

定理1 设{wk}是由算法(6)产生的序列,由(9)定义,则:

(21)

(22)

(23)

联立(22)(23)两式,定理(1)得证。

证明 对(20)式按k=0,1,…,n累加可得:

(24)

将上式代入式(24)就可以得到

(25)

θ(u)-θ(u∞)+(w-w∞)TF(w∞)≥0,∀w∈Ω

(26)

对于{wk}的其他任意聚点wρ,则

所以wρ=w∞,即w∞是唯一的聚点。

3 数值实验

本节所有的测试代码都在MATLAB-R2020a进行编写,运行环境为惠普笔记本电脑(Intel(R) Core(TM) i5-1135G7,16.0 GB)。在数值实验中,我们把记迭代次数记为“Ite.”,把运行时间记为“CPU(s)”。

我们针对以下模型进行数值实验:

(27)

很明显,上述最小化问题是问题(5)的标准表述,其中

把我们的算法应用于(27)时,产生的子问题求解如下:

上述问题可等价于

其中软阈值shrink、算子D由下式定义

shrink(N,c)∶=sign(N)max{|N|-c,0},N∈s×n

Dc(N)∶=Udiag(shrink(∑,c))VT,N∈s×n

并且U∑VT是矩阵N的奇异值分解。

我们用所提出的改进带有Bregman距离的PR分裂法,即算法(6)与He等人在文献[17]中提出的分裂增广拉格朗日算法(以下简称SPALM)和文献[18]中针对多块的广义Peaceman-Rachford(以下简称GPRSM)m取3时进行比较,且终止条件为

其中fk表示问题(27)第k步目标函数的函数值。

能得到以下结果,如表1所示。

表1 算法SPALM和GPRSM的数值结果比较

从表1中可以看出,本文提出的算法在迭代步数和时间上优于 SPALM 和GPRSM.我们在图1中绘制了目标函数值、X的秩、Y的稀疏度和误差相对于迭代次数的演变。与带有近端项的PRSM相比有更好的恢复效果:目标函数值较低,X秩较低,Y稀疏度较高。这些现象可能表明,在追求更好的结果质量时,本文的算法比GPRSM更为可靠。此外算法和SPALM相比,目标函数值较低,Y稀疏度偏低,X秩和误差结果相近,但不难看出在迭代次数和时间方面,本文的算法更具有竞争力。总体来说,本文提出的算法效果较好,因此是有意义的。

图1 m=1 000,n=800时目标函数值、X的低秩、Y的稀疏度和误差与迭代步数的关系图

4 结论

本文针对带有线性约束的三块可分凸优化问题,提出了带有Bregman距离的Peaceman-Rachford分裂法的改进算法,在对称Bregman ADMM的基础上选择不同的松弛因子更新拉格朗日乘子。当Bregman距离函数为δ-强凸时,从变分不等式的角度证明了该算法的全局收敛性和在遍历情形下O(1/t)的最坏收敛速率。最后用数值实验初步验证了本文所提的算法在迭代步数和迭代时间上具有一定的优势。

5 致谢

感谢编辑和审稿人提供的意见以提高论文的质量,特别感谢湖北师范大学数学与统计学院的王阳老师在后期工作中提供的帮助。