文章编号：1007 − 6735(2020)05 − 0460 − 07DOI: 10.13255/jki.jusst.20191125001
一种改进的乘子交替方向法在ℓ1-正则化
分裂可行问题中的应用
党亚峥，    唐崇伟
（上海理工大学 管理学院，上海 200093）
摘要：提出了一种改进的乘子交替方向法（ADMM ）算法，基于松弛技术和预测−校正框架，将松弛算子引入子问题x 和对偶变量λ，使得每次迭代的步长大于1，从而提高了算法的收敛性，并在变分不等式的框架下证明了该算法的收敛性。此外，数值实验中通过图像去模糊问题验证了算法的有效性，并基于多组对照实验，综合考虑收敛效率和图像质量，选取适当的收敛准则。关键词：ℓ1范数；改进的乘子交替方向法；松弛因子；图像模糊
中图分类号：O 221            文献标志码：A
An improved alternating direction method of multipliers for
ℓ1-norm regularization splitting feasibility problem
DANG Yazheng ，      TANG Chongwei
(Business School, University of Shanghai for Science and Technology, Shanghai 200093, China )
Abstract: we  proposes  an  improved  alternating  direction  method  of  multipliers  (ADMM) algorithm
based on the relaxation technique and the prediction-correction framework, which introduces the new parameters in the subproblem x  and the dual problem λ , so that the step size of each iteration is greater than 1, thereby improving the convergence of the algorithm. The convergence of the algorithm is proved in  the  framework  of  variational  inequality. Moreover, the  image  deblurring  problem  in  numerical experiments verifies that the algorithm is effective. Based on multiple sets of convergence criteria, the appropriate value is selected by comprehensively considering the rate of convergence and the quality of images.
Keywords: ℓ1-norm ; improved  alternating  direction  method  of  multipliers ; relaxated  parameter ;image deblurring
1    研究现状
分裂可行性问题（SFP ）由Censor 和Elfving
[1]
x ∗首次提出，其数学模型实际上是一个可行性问题，即一个具有以下属性的点：
上  海  理  工  大  学  学  报
第 42 卷    第 5 期
J. University of Shanghai for Science and Technology Vol. 42    No. 5    2020
收稿日期：2019−11−25
第一作者：党亚峥（1973−），女，副教授．研究方向：优化、图像重建、金融优化．E-mail ：*************
C Q C ∈R n Q ∈R m A :R n ⇒R m 其中，和属于非空的闭凸集，且，，
为线性运算符。
Q =b x ∗众所周知，问题（1）包含现实中各种特殊情况下的逆问题。例如，当是单元素集合时，问题（1）简化为经典的凸约束线性逆问题，即到一个点，使得
问题（2）在文献[2-5]及其参考文献中有着广泛的研究。由于约束集Q 结构的不确定性，有关问题（1）的研究比其特殊情况问题（2）要少得多，同时某些适用于问题（2）的算法并不能直接运用于问题（1）。例如，目前尚不清楚是否可以将文献[4]中针对问题（2）提出的算法扩展应用到问题（1）中。
事实上，问题（1）等价于如下约束优化问题：
P Q Q 式中，为上的投影。
ℓ1ℓ1受矩阵A 的影响，问题（1）和问题（2）时常是不适定的，因此，需要对其进行正则化处理，所以，在过去的几十年中，利用正则化技术解决问题（2）已经非常成熟了
[5-8]
。于是，针对问题（1）的
正则化方法成为了新的研究话题[9-12]
，由于范数
会导致解的稀疏性，故其正则化问题引起了很多
学者的关注
[13-17]
。因此，考虑如下范数形式，即
σ>0其中，是正则化参数。显然，lasso 问题、BP 问题、BPDN 问题
[13, 16-19]
皆属于问题（4）的特殊情
况，相较而言，问题（4）则很少被提及。
ℓ1在变分不等式（VI ）的框架下，通过乘子交替方向法（ADMM ）
[20]
引入一种可实现的分裂算法来解决
范数正则化的SFP 问题。为此，变量拆分后得到
f (x )其中，为问题（3）中所定义的形式。如今ADMM 已广泛应用于变分不等式、压缩感知、图像处理及统计学习等领域
[13-14, 21-26]
。
He 等
[27]
针对问题（5）的可分离结构，通过结
合线性化思想和邻近点算法，提出了一种新的可实现ADMM 算法，并设计了预测和校正两个步骤。文献[28]中引入一组松弛算子，在取值恰当的情况下具有良好的收敛效果。本文受文献[27-28]启发，提出了一种改进的ADMM 算法，通过在预
测步中引入松弛因子对算法进行改进，提高ADMM 算法的收敛性。并在一定条件下证明了算法的收敛性，最后通过图像恢复数值实验验证了算法的有效性。
2    预备知识
现给出一些常用的预备知识。
R n n x ,y ∈R n ,
⟨x ,y ⟩∥x ∥M =√
⟨x ,Mx ⟩x M ∥A ∥令为一个维的欧式空间，给定为内积。此外，定义为的范数，对于任意的A ，定义为2范数。
R n M 定义1　由
投影到范数下的非空闭凸集上的投影算子
正交投影算子可以通过以下关系式来表示：
证明过程参考文献[29]。
T ∈(R n ,2R n )
定义2　若集值算子 是单调的，则
必有
如果单调算子的图形没有正确包含在任何其他单调算子的曲线图中，则称其为最大单调。
g :R n →R ∇g
L >0定义3　令为一个可微的凸函数，那么，它的梯度是Lipschitz 连续的，常数，有
f ∇f =A T (I −
P Ω)A ∇f 注意到式（
3）中定义的函数的梯度为，显然是单调且Lipschitz 连续的，可知：3    改进的ADMM 算法
k w k
:=(x k ,z k ,λk
)∈
C ×R n ×R n k +1w k +1:=(x k +1,z k +1,λk +1)在问题（5）中，给定第次迭代，则第 次迭代表示为，由此可以得到以下的子问题：
λγ>0式中，为拉格朗日算子，为罚因子。
第 5 期党亚峥，等：一种改进的乘子交替方向法在ℓ1-正则化分裂可行问题中的应用
461
˜z k
ADMM 算法的优势在于充分利用了问题（5）[27]
ρ⩾∥A ∥2ρ2
z −z k  2z 其中，为正常数，通过近似项使子问题  正则化。
x f f (x k ,˜z k ,λk )˜x k 对于子问题，由于函数 的非线性，使得最小化子问题（10）无法获得封闭解。He 等[27]
利用线
性化思想处理 的非线性，给定生成如下
ω˜z k +(1−ω)x k ˜x k ˜z k ˜x k 本文算法引入来对子问题中的
˜k
ω∈[1,2)˜w k =(
˜x
k ,˜z k ,˜λk )其中，详见文献[28]。于是，得到了一组
完整的预测序列。(x ,˜x ):=∇f (x )−∇f (˜x )为方便起见，定义，则有最后，对以上给出的预测序列进行校正，即可得到改进的ADMM （IADMM ）算法。
IADMM 算法：
l1正则化的作用ρ⩾∥A ∥2t ∈(0,2)w 0:=(
x 0,y 0,λ0)∈
C ×R n
×R n a . 令，，并设;
k =0,1,2,···,k ;
b . 取˜w k =(˜x k ,˜y k ,˜λ
k )c . 根据式（12）～（14）得到预测序列;w k +1=(
x k +1,y
k +1,λk +1)d . 根据式（16）迭代;
e . 终止准则
f . 结束。
4    收敛性
现证明算法的全局收敛性。
w ∗∈
Ω问题（5）的解集可以看成到对应变分不等式（VI ）的解集，即
其中，
w ∗引理1　令为变分不等式（20）的解，必有
证明　首先将式（13）改写为对应的变分不等式（VI ）形式，即
由式（14）和式（15）对式（21）进行简单的整理，可
得
同理，对式（
12）和式（14）作同样的变换，有
ζ∈∂(σ∥·∥1)(z )其中，。
综合式（22）～（24），可得如下紧凑形式：462上  海  理  工  大  学  学  报2020 年 第 42 卷
I n n 式中，为维单位矩阵。
w :=w ∗x ∗=y ∗令，显然，，同时结合式（14），则有
对上式进行恒等变换
σ∥·∥1f F 由于和皆属于凸函数，故易知是单调的，即
于是，有
因此，
即
令
证毕。
˜w k α为将生成的预测序列进行校正，定义一组关于步长的新方程，将式（19），（25），（27）代入式（26）中，有
g (α)=2αΓ(w k ,˜w k )−α2  d w k ,˜w
k  2H
显然，方程αg (α)是一个关于的二次函数，易知取最大值时的
的值为
t >0事实证明，对于任意松弛因子，有
t ∈[1,2)为确
保每次迭代都能得到改进，建议选择
以便得到更好的收敛结果。
ρ⩾∥A ∥2αmin >0引理2　假设，则有式（28）定义的步长。
同理，可得
同样地，将式（17）代入式（19），有
Γw k ,˜w k ⩾C min  w k −˜w k  2C min :=min {ρ+γ−12γ,ρ,1γ−γ
2
}
显然，，其中，。
另一方面，再次运用柯西不等式  d w k ,˜w k  2H ⩽C max  w k −˜w k  2C max :=max {ρ+γ+∥A ∥2
ρ+γ,ρ,1γ
}
αk ⩾
C min C max =:αmin >0显然，，其中，。因此，有 。
证毕。
第 5 期党亚峥，等：一种改进的乘子交替方向法在ℓ1-正则化分裂可行问题中的应用
463
w ∗{w k }
定理1　令为式（20）的任意一个可行解，算
法产生的序列必须满足以下属性：
证明　综合式（27）～（29）可得
证毕。
定理2　算法产生的序列必须全局收敛于变分不等式（20）的解。
w ∗证明　令为式（20）的任意一个可行解，根据式（31）
可以得出结论：
w k −w ∗ 2H 也就是说，是单调减的有界序列，即
变换式（31）可得，
可得结论
w k {w ∞}这证明了序列全局收敛于。
5    数值实验
通过图像恢复问题验证算法的效果，所有代码均由Matlab 2017a 编写，处理器为 Intel Core i52.3 GHz ，内存8 GB ，并且在macOS 10.15上运行。
由于图像恢复为问题（4）的特殊情况，此问题的模型可以表示为
b A =BW B W 其中，为观测到的图像，其经过高斯噪声模糊化处理。包含模糊算子和余弦离散变换算子。实例中描述的所有原始图像的所有像素首先被缩放到0～1之间。现采用4种不同的图片来展示算法。图1分别为house, pepper, camera 和bridge 的原图与模糊图像。
(a) house (b) pepper
(c) camera
(d) bridge
图 1    原图和模糊图像
随后采用一种常用的信噪比（SNR ）概念来观测恢复图像的质量。
x ˜x 式中：表示原本的图像；表示恢复后的图像。
464上  海  理  工  大  学  学  报2020 年 第 42 卷

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。