求解三块变量约束凸优化问题的邻近部分平行分裂算法

申 远, 李俊峄

(南京财经大学 应用数学学院, 南京 210023)

0 引 言

去模糊去噪[1]、主成分分析[2]、高维统计[3]和隐变量高斯图形模型选择[4]的许多应用均可归结为目标函数是三块可分离的凸最小化模型.交替方向乘子法(ADMM)近年来在许多领域应用广泛[5], 该算法的收敛性与计算复杂性已得到广泛关注[6-8].因此将ADMM直接推广到目标函数为两个以上可分离凸函数的最小化问题, 有较强的实用价值.但研究表明, ADMM的直接扩展不一定收敛[9].

考虑如下三块线性等式约束凸极小化问题：

(1)

其中θi:Rni→(-∞,+∞]是闭的凸函数(不一定光滑),Ai∈Rl×ni是列满秩矩阵,b∈Rl是一个向量,χi⊂Rni是非空的凸集, 并且n1+n2+n3=n.问题(1)的增广Lagrange函数为

其中β>0是罚参数.假设问题(1)的解集非空.

若将ADMM由两块推广至多块以求解模型(1), 一种解决方法是增加严格的假设条件, 即目标函数中部分函数是强凸的且罚参数在一定范围内, 文献[10-12]在不同假设条件下证明了算法的收敛性.另一种方法是对算法进行改进, 如广义对称ADMM(generalized symmetric ADMM, GS-ADMM)[13]和MSC-PRSM(modified strictly contractive Peaceman-Rachford splitting method)[14]算法；或加校正步骤, 如部分平行分裂算法，简称APCM(ADMM based prediction-correction method)[15].

APCM算法的迭代格式如下：

校正步骤为

本文在部分平行分裂算法的基础上，提出一种邻近部分平行分裂方法(PAPCM)，并证明其收敛性.该算法可用于求解三块变量的线性约束凸优化问题.一方面，它的子问题像ADMM一样易求解；另一方面，它在x3子问题的目标函数中加入了正则项，且校正步长的条件比APCM更放松.

1 预备知识

函数F:Rn⟹Rn即∀x∈Rn,F(x)是Rn中的一个函数.若

(x-y)T(F(x)-F(y))≥0, ∀x,y∈Rn,

则称F是单调的.设Ω⊂Rn是非空集合, 若

‖xk+1-x‖≤‖xk-x‖, ∀x∈Ω,k≥1,

则序列{xk}⊆Rn在Ω中被称为Fejér单调的.

引理1[16]假设序列{xk}是关于ΩFejér单调的, 则序列{xk}是有界的, 并且序列{‖xk-x‖}对∀x∈Ω收敛.

θ(x)-θ(x*)+(u-u*)TF(u*)≥0, ∀u∈U,

(2)

其中

(3)

2 算法框架和全局收敛性

算法1PAPCM: 对问题(1)提出的一种邻近部分平行分裂算法.

步骤2)(预测步骤) 利用

(4)

步骤3)(校正步骤) 利用

(5)

产生新的迭代点;

步骤4)(终止) 若

图1 参数(γ,α)的取值范围Fig.1 Value ranges of parameter (γ,α)

则停止；否则, 令k=k+1, 转步骤2).

(6)

其中

(7)

(8)

所有θi是闭凸函数,Ai是列满秩矩阵.因此, 式(2)的解集(用U*表示)是非空的.

为便于表示, 设

(9)

(10)

GD=αM.

(11)

定义

Q=α(M+MT+N+NT)-DGD,

(12)

可得

因此Q是一个正定矩阵当且仅当矩阵

引理3设序列{uk}由算法1生成, 若

(13)

成立, 则序列{vk}相对于集合V*是Fejér单调的.

由F(u)在U上的单调性和矩阵M,N的定义, 得

(15)

另一方面, 由式(5)可知

其中D由式(10)定义.再由式(12)中Q的定义, 可得

式(16)中不等式由式(15)得到, 由式(16)可知式(13)成立, 从而序列{vk}相对于集合V*是Fejér单调的.

下面建立算法1的全局收敛性.

证明: 由引理3可知, {vk}相对于V*是Fejér单调的, 因此, {vk}是有界的.此外, ∀k有

(17)

对不等式(17)关于k=0,1,…求和, 得

(18)

(19)

由于式(4)中第四个恒等式、式(5)中第一个的恒等式和假设A1是满秩的, 因此有

(20)

(21)

结合式(19),(21), 可推导出

表明u∞∈U*(v∞∈V*).

3 数值实验

考虑求解如下三块变量线性等式约束的二次凸优化问题:

(22)

下面用算法1求解问题(22), 并将算法1与APCM算法、MSC-PRSM算法进行比较, 验证其计算效率.所有程序均利用MATLAB编制, 测试平台配置为Intel Core i5-8250U CPU, 8 GB内存, Windows10操作系统和MATLAB R2017a.

2) 随机生成系数矩阵A,B,C:A,B,C的元素取值按i.i.d.N(0,1)分布随机生成;

3) 随机生成向量x*,y*,z*,λ*:x*,y*,z*,λ*的元素取值按i.i.d.N(0,1)分布随机生成;

4) 通过满足的KKT(Karush-Kuhn-Tucker)条件

Mx+q-ATλ=0,Ly+p-BTλ=0,Nz+v-CTλ=0,

可得向量q,p,v;

5) 通过Ax+By+Cz=b得到右端项b.

在算法开始时对3个系数矩阵做一次分解, 以后每次子问题只需求解系数矩阵为上(下)三角矩阵的线性方程组两次, 从而降低了子问题的计算量.取

作为停机准则.测试几组不同(m,n1,n2,n3)设置下, 随机生成10个问题, 并对计算结果取平均值.最后, 将3种算法的数值结果进行比较, 不同算法的数值结果列于表1.

表1 MSC-PRSM算法、APCM算法和算法1的数值实验比较结果

由表1可见, 算法1平均每次计算迭代步数比MSC-PRSM算法约少49.67%, 计算时间约少45.85%；算法1平均每步计算迭代次数比APCM算法约少36.86%, 计算时间约少33.30%.可见带随机步长的算法1比MSC-PRSM算法和APCM算法更高效, 并且随着问题规模的增长, 算法1的计算时间增长相对较慢, 表明算法1的计算效率有更好的尺度适应性.例如, 设置的问题(300,200,200,200)与(2 000,1 000,1 000,1 000)结果相比, APCM算法的计算时间约增长了148倍, 而算法1只增长了约97倍, 说明算法1更适合处理大规模问题.实验结果表明, 与MSC-PRSM算法、APCM算法相比, 算法1的计算效率更高且具有更好的尺度适应性.

综上所述, 本文在线性约束三块变量凸优化问题部分平行分裂算法的校正步骤中选取不同步长参数的基础上, 提出了一种邻近部分平行分裂算法(PAPCM).该算法在预测步骤上一个原始子问题的目标函数中加入正则项, 校正步长的条件比APCM算法更放松, 并给出了相应的收敛性证明.数值实验结果表明, 在求解带有三块变量的结构型凸优化问题时, 算法1的计算效率明显优于MSC-PRSM算法和APCM算法.