上海理工大学学报  2020, Vol. 42 Issue (5): 460-466   PDF    
一种改进的乘子交替方向法在1-正则化分裂可行问题中的应用
党亚峥, 唐崇伟     
上海理工大学 管理学院,上海 200093
摘要: 提出了一种改进的乘子交替方向法(ADMM)算法,基于松弛技术和预测−校正框架,将松弛算子引入子问题x和对偶变量λ,使得每次迭代的步长大于1,从而提高了算法的收敛性,并在变分不等式的框架下证明了该算法的收敛性。此外,数值实验中通过图像去模糊问题验证了算法的有效性,并基于多组对照实验,综合考虑收敛效率和图像质量,选取适当的收敛准则。
关键词: 1范数     改进的乘子交替方向法     松弛因子     图像模糊    
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.
Key words: 1-norm     improved alternating direction method of multipliers     relaxated parameter     image deblurring    
1 研究现状

分裂可行性问题(SFP)由Censor和Elfving[1]首次提出,其数学模型实际上是一个可行性问题,即找一个具有以下属性的点 $ {x}^{*} $

$ {x}^{*}\in C ,\qquad {{A}}{x}^{*}\in Q $ (1)

其中, $ C $ $ Q $ 属于非空的闭凸集,且 $ C\in {\mathbb{R}}^{n} $ $ Q\in \;{\mathbb{R}}^{m} $ $ A:{\mathbb{R}}^{n}\Rightarrow {\mathbb{R}}^{m} $ 为线性运算符。

众所周知,问题(1)包含现实中各种特殊情况下的逆问题。例如,当 $ Q = b $ 是单元素集合时,问题(1)简化为经典的凸约束线性逆问题,即找到一个点 $ {x}^{*} $ ,使得

$ {x}^{*}\in C,\qquad {{A}}{x}^{*}=b $ (2)

问题(2)在文献[2-5]及其参考文献中有着广泛的研究。由于约束集Q结构的不确定性,有关问题(1)的研究比其特殊情况问题(2)要少得多,同时某些适用于问题(2)的算法并不能直接运用于问题(1)。例如,目前尚不清楚是否可以将文献[4]中针对问题(2)提出的算法扩展应用到问题(1)中。

事实上,问题(1)等价于如下约束优化问题:

$ \mathop {\min }\limits_{x \in C} \;f\left( x \right): = \dfrac{1}{2}{\left\| {{{A}}x - {P_Q}{{A}}x} \right\|^2} $ (3)

式中, $ {P}_{Q} $ $ Q $ 上的投影。

受矩阵A的影响,问题(1)和问题(2)时常是不适定的,因此,需要对其进行正则化处理,所以,在过去的几十年中,利用正则化技术解决问题(2)已经非常成熟了[5-8]。于是,针对问题(1)的正则化方法成为了新的研究话题[9-12],由于 $ \ell _{1} $ 范数会导致解的稀疏性,故其正则化问题引起了很多学者的关注[13-17]。因此,考虑如下 $ \ell _{1} $ 范数形式,即

$ \mathop {\min }\limits_{x \in C} \;\frac{1}{2}{\left\| {{{A}}x - {P_Q}\left( {{{A}}x} \right)} \right\|^2} + \sigma {\left\| x \right\|_1} $ (4)

其中, $ \sigma >0 $ 是正则化参数。显然,lasso问题、BP问题、BPDN问题[13, 16-19]皆属于问题(4)的特殊情况,相较而言,问题(4)则很少被提及。

在变分不等式(VI)的框架下,通过乘子交替方向法(ADMM)[20]引入一种可实现的分裂算法来解决 $ \ell _{1} $ 范数正则化的SFP问题。为此,变量拆分后得到

$ \begin{array}{*{20}{c}} {\mathop {\min }\limits_{x,z} \;f\left( x \right) + \sigma {{\left\| z \right\|}_1}}\\ {{\rm{s}}.{\rm{t}}.\;x = z,\;\;x \in C,\;\;z \in {{\mathbb{R}}^n}} \end{array} $ (5)

其中, $ f\left(x\right) $ 为问题(3)中所定义的形式。如今ADMM已广泛应用于变分不等式、压缩感知、图像处理及统计学习等领域[13-14, 21-26]

He等[27]针对问题(5)的可分离结构,通过结合线性化思想和邻近点算法,提出了一种新的可实现ADMM算法,并设计了预测和校正两个步骤。文献[28]中引入一组松弛算子,在取值恰当的情况下具有良好的收敛效果。本文受文献[27-28]启发,提出了一种改进的ADMM算法,通过在预测步中引入松弛因子对算法进行改进,提高ADMM算法的收敛性。并在一定条件下证明了算法的收敛性,最后通过图像恢复数值实验验证了算法的有效性。

2 预备知识

现给出一些常用的预备知识。

$ {\mathbb{R}}^{n} $ 为一个 $ n $ 维的欧式空间,给定 $ { x},{ y}\in {\mathbb{R}}^{n}, $ $ \left\langle {x,y} \right\rangle $ 为内积。此外,定义 ${\left\| {x} \right\|}_{M}= \sqrt{\left\langle {x,Mx} \right\rangle }$ $ { x} $ $ M $ 范数,对于任意的A,定义 $ \left\| { A} \right\| $ 为2范数。

定义1  由 ${\mathbb {R}}^{n} $ 投影到 $ M $ 范数下的非空闭凸集上的投影算子

$ {P_{{{\varOmega }},M}}\left[ x \right] \sim = {\rm{argmin}}\;\left\{ {{{\left\| {y - x} \right\|}_M}\left| {y \in {{\varOmega }}} \right.} \right\},\quad x \in {{\mathbb{R}}^n} $ (6)

正交投影算子可以通过以下关系式来表示:

$ \left\langle {u\!-\!{P}_{{{\varOmega }},M}\left[u\right],M\left(v\!-\!{P}_{{{\varOmega }},M}\left[u\right]\right)} \right\rangle \!\leqslant \!0, \;\;\;u\!\in\! {\mathbb{R}}^{n},v\!\in\! {{\varOmega }} $ (7)

证明过程参考文献[29]。

定义2  若集值算子 ${{T}}\in \left({\mathbb{R}}^{n},{2}^{{\mathbb{R}}^{n}}\right)$ 是单调的,则必有

$ \left\langle {{x}_{1}-{x}_{2},{x}_{1}^{*}-{x}_{2}^{*}} \right\rangle \geqslant 0,\;{x}_{1},{x}_{2}\in {\mathbb{R}}^{n},\;{x}_{1}^{*}\in T\left({x}_{1}\right),\;{x}_{2}^{*}\in T\left({x}_{2}\right) $

如果单调算子的图形没有正确包含在任何其他单调算子的曲线图中,则称其为最大单调。

定义3  令 $ {{g}}:{\mathbb{R}}^{n}\to \mathbb{R} $ 为一个可微的凸函数,那么,它的梯度 $ \nabla {{g}} $ 是Lipschitz连续的,常数 $ L>0 $ ,有

$ \left\| {\nabla {{g}}\left({x}_{1}\right)-\nabla {{g}}\left({x}_{2}\right)} \right\|\leqslant L\left\| {{x}_{1}-{x}_{2}} \right\|,\;\;\;\;\;{x}_{1},{x}_{2}\in {\mathbb{R}}^{n} $

注意到式(3)中定义的函数 $ f $ 的梯度为 $\nabla f= {{{A}}}^{\rm T}(I- {P}_{{{\varOmega }}}){{A}}$ ,显然 $ \nabla f $ 是单调且Lipschitz连续的,可知:

$ \left\| {\nabla f\left({x}_{1}\right)-\nabla f\left({x}_{2}\right)} \right\|\leqslant {\left\| { A} \right\|}^{2}\left\| {{x}_{1}-{x}_{2}} \right\|,\;\;\;{x}_{1},{x}_{2}\in {\mathbb{R}}^{n} $ (8)
3 改进的ADMM算法

在问题(5)中,给定第 $ k $ 次迭代 ${w}^{k}:= \left({x}^{k},{z}^{k},{\rm{\lambda }}^{k}\right) \in C\times {\mathbb{R}}^{n}\times {\mathbb{R}}^{n}$ ,则第 $ k+1 $ 次迭代表示为 ${w}^{k+1}:= ({x}^{k+1},\; {z}^{k+1},\;{\rm{\lambda }}^{k+1})$ ,由此可以得到以下的子问题:

$ {z}^{k+1}=\underset{z\in {\mathbb{R}}^{n}}{{\rm{arg}}{\rm{min}}}\;\left\{{\left\| {z} \right\|}_{1}+\frac{\gamma }{2}{\left\| {{x}^{k}-z-\frac{{\lambda }^{k}}{\gamma }} \right\|}^{2}\right\} $ (9)
$ {x}^{k+1}=\underset{{{x}}\in \;{{C}}}{{\rm{arg}}{\rm{min}}}\;\left\{f\left(x\right)+\frac{\gamma }{2}{\left\| {x-{z}^{k+1}-\frac{{\lambda }^{k}}{\gamma }} \right\|}^{2}\right\} $ (10)
$ {\rm{\lambda }}^{k+1}={\rm{\lambda }}^{k}-{\rm{\gamma }}\left({x}^{k+1}-{z}^{k+1}\right) $ (11)

式中, $ \lambda $ 为拉格朗日算子, $ \gamma >0 $ 为罚因子。

ADMM算法的优势在于充分利用了问题(5)的可分离结构,He等[27]通过下式生成预测变量 $ {\tilde z}^{k} $

$ {\tilde z}^{k}\!=\!\underset{z\in \;{\mathbb{R}}^{n}}{{\rm{arg}}{\rm{min}}}\left\{{\left\| {z} \right\|}_{1}\!+\!\frac{\gamma }{2}{\left\| {{x}^{k}\!-\!z\!-\!\frac{{\lambda }^{k}}{\gamma }} \right\|}^{2}\!+\!\frac{\rho }{2}{\left\| {z\!-\!{z}^{k}} \right\|}^{2}\right\} $ (12)

其中, $ \rho \geqslant {\left\| { A} \right\|}^{2} $ 为正常数,通过近似项 $\dfrac{\rho }{2}{\left\| {z-{z}^{k}} \right\|}^{2}$ 使子问题 $ z $ 正则化。

对于子问题 $ x $ ,由于函数 $ f $ 的非线性,使得最小化子问题(10)无法获得封闭解。He等[27]利用线性化思想处理 $ f $ 的非线性,给定 $ \left({x}^{k},{\tilde z}^{k},{\rm{\lambda }}^{k}\right) $ 生成如下预测变量 $ {\tilde x}^{k} $

$ \begin{split} {\tilde x}^{k}\!\!=&\underset{{{x}}\in \;{{C}}}{{\rm{arg}}{\rm{min}}}\left\{\!\left\langle {\nabla\! f\!\left(\!{x}^{k}\!\right),x\!-\!{x}^{k}}\! \right\rangle \!+\!\dfrac{\gamma }{2}{\left\| \!{x\!-\!{\tilde z}^{k}\!-\!\dfrac{{\lambda }^{k}}{\gamma }}\! \right\|}^{2}\!\!+\!\dfrac{\rho }{2}{\left\| {x\!-\!{x}^{k}} \right\|}^{2}\right\}=\\[-2pt] &{P}_{C}\left[\frac{1}{\rho +{\rm{\gamma }}}\left(\rho {x}^{k}+{\rm{\gamma }}{\tilde z}^{k}+{\rm{\lambda }}^{k}-\nabla f\left({x}^{k}\right)\right)\right] \end{split} $

本文算法引入 $ {\rm{\omega }}{\tilde z}^{k}+\left(1-{\rm{\omega }}\right){x}^{k} $ 来对 $ {\tilde x}^{k} $ 子问题中的 $ {\tilde z}^{k} $ 进行改进,生成新的预测变量 $ {\tilde x}^{k} $ ,即

$\begin{split} {\tilde x}^{k}=&{P}_{C}\Biggr[\frac{1}{\rho +{\rm{\gamma }}}\Bigr[{\rm{\rho }}_{1}{x}^{k}+\\[-2pt] &{\rm{\gamma }}\left[{\rm{\omega }}{\tilde z}^{k}+\left(1-{\rm{\omega }}\right){x}^{k}\right]+{\rm{\lambda }}^{k}-\nabla f\left({x}^{k}\right)\Bigr]\Biggr] \end{split} $ (13)

采用如下形式的预测变量 $ {\tilde \lambda }^{k} $

$ {\tilde \lambda }^{k}={\rm{\lambda }}^{k}-{\rm{\gamma }}\left\{{\tilde x}^{k}-\left[{\rm{\omega }}{\tilde z}^{k}+\left(1-{\rm{\omega }}\right){x}^{k}\right]\right\} $ (14)

其中, $ {\rm{\omega }}\in \left[{1,2}\right) $ 详见文献[28]。于是,得到了一组完整的预测序列 $ {\tilde w }^{k}=\left({\tilde x}^{k},{\tilde z}^{k},{\tilde \lambda }^{k}\right) $

为方便起见,定义 $ {\eta }_{1}(x,{\tilde x}):=\nabla f\left(x\right)-\nabla f\left({\tilde x}\right) $ ,则有

$ {\rm{\eta }}\left({\rm{w}},{\tilde w}\right):=\left(\begin{array}{c}{\eta }_{1}\left(x,{\tilde x}\right)\\ 0\\ 0\end{array}\right) $ (15)

最后,对以上给出的预测序列进行校正,即可得到改进的ADMM(IADMM)算法。

IADMM算法:

a. 令 $\; \rho \geqslant {\left\| { A} \right\|}^{2}$ $ t\in \left({0,2}\right) $ ,并设 ${w}^{0}:=\left({x}^{0},{y}^{0},{\lambda }^{0}\right)\in C\times {\mathbb{R}}^{n}\times {\mathbb{R}}^{n}$ ;

b. 取 $k={0,1},2, \cdots , k;$

c. 根据式(12)~(14)得到预测序列 $ {\tilde w }^{k}= ({\tilde x}^{k}, {\tilde y}^{k},{\tilde \lambda }^{k}) $ ;

d. 根据式(16)迭代 $ {w}^{k+1}=\left({x}^{k+1},{y}^{k+1},{\lambda }^{k+1}\right) $ ;

$ {w}^{k+1}={w}^{k}-{t\alpha }_{k}d\left({w}^{k},{\tilde w }^{k}\right) $ (16)

其中,

$ d\left({w}^{k},{\tilde w }^{k}\right)=\left({w}^{k}-{\tilde w }^{k}\right)-{{H}}^{-1}{\rm{\eta }}\left({{\rm{w}}}^{k},{\tilde w }^{k}\right) $ (17)
$ {\alpha }_{k}:=\frac{{\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right)}{{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{H}^{2}} $ (18)
$\begin{split} {\rm{\Gamma }}({w}^{k},{\tilde w }^{k})=&\left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle -\\ &\left\langle {{\tilde w }^{k}-{w}^{k},{{H}}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \end{split} $ (19)

e. 终止准则

$ \frac{\left\| {{x}^{k+1}-{x}^{k}} \right\|}{\left\| {{x}^{k}} \right\|}\leqslant {10}^{-4} $

f. 结束。

4 收敛性

现证明算法的全局收敛性。

问题(5)的解集可以看成找到对应变分不等式(VI)的解集 ${w}^{*}\in {{\varOmega }}$ ,即

$ \left\langle {w-{w}^{*},F\left({w}^{*}\right)} \right\rangle \geqslant 0, \;w\in {{\varOmega }} $ (20)

其中,

$ { w}:=\left(\begin{array}{c}x\\ z\\ \lambda \end{array}\right),F\left(w\right):=\left(\begin{array}{c}\nabla f\left(x\right)-\lambda \\ \zeta +\lambda \\ x-z\end{array}\right),{{\varOmega }}\in {{C}}\times {\mathbb{R}}^{n}\times {\mathbb{R}}^{n} $

引理1  令 $ {w}^{*} $ 为变分不等式(20)的解,必有

$ \left\langle {{w}^{k}-{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \geqslant {\rm{\Gamma }}({w}^{k},{\tilde w }^{k}) $

证明  首先将式(13)改写为对应的变分不等式(VI)形式,即

$\begin{split} \left\langle x - {{\tilde x}^k},\nabla f\left( {{x^k}} \right) + \left( {\rho + \gamma } \right)\left( {{{\tilde x}^k} - {x^k}} \right) + \gamma {x^k} - \right.\\ \left.\gamma \left[ {{\rm{\omega }}{{\tilde z}^k} - \left( {1 - {\rm{\omega }}} \right){x^k}} \right] - {\gamma ^k} \right\rangle \geqslant 0,x \in C \end{split} $ (21)

由式(14)和式(15)对式(21)进行简单的整理,可得

$ \begin{split} &\left\langle x-{\tilde x}^{k},\nabla f\left({\tilde x}^{k}\right)-{\tilde \lambda }^{k}+\left(\rho +\gamma \right)\left({\tilde x}^{k}-{x}^{k}\right)+\right.\\ &\qquad\quad \left.{\eta }_{1}\left({x}^{k},{\tilde x}^{k}\right) \right\rangle \geqslant \gamma \left\langle {x-{\tilde x}^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle ,\quad x\in C \end{split} $ (22)

同理,对式(12)和式(14)作同样的变换,有

$\begin{split} &\left\langle {z-{\tilde z}^{k},\;{\zeta }^{k}+{\tilde \lambda }^{k}+\rho \left({\tilde z}^{k}-{z}^{k}\right)} \right\rangle \geqslant \\ &\quad\qquad\gamma \left\langle {{\tilde z}^{k}-z,{\tilde x}^{k}-{x}^{k}} \right\rangle ,\quad z\in {\mathbb{R}}^{n} \end{split} $ (23)
$\begin{split} &\left\langle {\lambda -{\tilde \lambda }^{k},{\tilde x}^{k}-{\tilde z}^{k}+\frac{1}{\lambda }\left({\tilde \lambda }^{k}-{\lambda }^{k}\right)} \right\rangle\geqslant \\ &\quad\qquad \gamma \left(1-\omega \right)\left\langle {{x}^{k}-{\tilde z}^{k},{\tilde \lambda }^{k}-\lambda } \right\rangle ,\quad {\rm{\lambda }}\in {\mathbb{R}}^{n} \end{split}$ (24)

其中, $ {\rm{\zeta }}\in \partial \left({\rm{\sigma }}{\left\| {\cdot } \right\|}_{1}\right)\left(z\right) $

综合式(22)~(24),可得如下紧凑形式:

$ \begin{split} & \left\langle {w-{\tilde w }^{k},{{F}}\left({\tilde w }^{k}\right)-{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \geqslant\\ &\quad\qquad \gamma \left\langle {x-{\tilde x}^{k}+{\tilde z}^{k}-z,{\tilde x}^{k}-{x}^{k}} \right\rangle +\\ &\quad\qquad\left\langle {\gamma \left(1-\omega \right)\left({x}^{k}-{\tilde z}^{k}\right),{\tilde \lambda }^{k}-\lambda } \right\rangle ,\quad w\in {{\varOmega }} \end{split} $
$ {{H}} \sim = \left( {\begin{array}{*{20}{c}} {\left( {\rho + \gamma } \right){{{I}}_n}}&0&0\\ 0&{\rho {{ I}_n}}&0\\ 0&0&{\dfrac{1}{\gamma }{{ I}_n}} \end{array}} \right) $

式中, $ {{I}}_{n} $ $ n $ 维单位矩阵。

$ w:={w}^* $ ,显然, $ {x}^*={y}^* $ ,同时结合式(14),则有

$ \begin{split} &\left\langle {{w}^{*}-{\tilde w }^{k},F\left({\tilde w }^{k}\right)-{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \geqslant\\ &\qquad \left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle +\gamma \left(1-\omega \right)\left\langle {{\tilde z}^{k}-{x}^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle +\\ &\qquad\gamma \left(1-\omega \right)\left\langle {{x}^{k}-{\tilde z}^{k},{\tilde \lambda }^{k}-\lambda } \right\rangle\geqslant \\ & \qquad \left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle ,w\in {\rm{\Omega }} \end{split} $

对上式进行恒等变换

$ \left\langle {{\tilde w }^{k}\!-\!{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \geqslant \left\langle {{\tilde \lambda }^{k}\!-\!{\lambda }^{k},{\tilde x}^{k}\!-\!{x}^{k}} \right\rangle \!+\!\left\langle {{\tilde w }^{k}\!-\!{w}^{*},F\left({\tilde w }^{k}\right)} \right\rangle $

由于 $ {{\sigma }}{\left\| \cdot \right\|}_{1} $ $ f $ 皆属于凸函数,故易知 $ F $ 是单调的,即

$ \left\langle {{\tilde w }^{k}-{w}^{*},F\left({\tilde w }^{k}\right)} \right\rangle \geqslant \left\langle {{\tilde w }^{k}-{w}^{*},F\left({\tilde w }^{*}\right)} \right\rangle \geqslant 0 $

于是,有

$ \left\langle {{\tilde w }^{k}-{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \geqslant \left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle $

因此,

$ \begin{array}{l} \left\langle {{\tilde w }^{k}-{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle =\\ \qquad\quad \left\langle {{\tilde w }^{k}-{w}^{k},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle +\left\langle {{w}^{k}-{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \end{array} $

$ \begin{split} &\left\langle {{w}^{k}-{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle\geqslant \\ &\qquad\quad \left\langle {{\tilde \lambda }^{k}\!-\!{\lambda }^{k},{\tilde x}^{k}\!-\!{x}^{k}} \right\rangle \!-\!\left\langle {{\tilde w }^{k}\!-\!{w}^{k},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle \end{split} $ (25)

$ {\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right)=\left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle -\left\langle {{\tilde w }^{k}-{w}^{k},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle $

证毕。

为将生成的预测序列 $ {\tilde w }^{k} $ 进行校正,定义一组关于步长 $ \alpha $ 的新方程,

$ G\left(\alpha \right)={ \left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-{ \left\| {{w}^{k+1}\left(\alpha \right)-{w}^{*}} \right\|}_{ H}^{2} $ (26)
$ {w}^{k+1}\left(\alpha \right)={w}^{k}-\alpha d\left({w}^{k},{\tilde w }^{k}\right) $ (27)

将式(19),(25),(27)代入式(26)中,有

$ \begin{split} G\left(\alpha \right)=&{\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-{\left\| {{w}^{k}-\alpha d\left({w}^{k},{\tilde w }^{k}\right)-{w}^{*}} \right\|}_{ H}^{2} =\\ &2\alpha \left\langle {{w}^{k}-{w}^{*},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle -{\alpha }^{2}{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}\geqslant\\ & 2\alpha {\rm{\Gamma }}({w}^{k},{\tilde w }^{k})-{\alpha }^{2}{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}=g\left(\alpha \right) \end{split} $

显然,方程 $g\left(\alpha \right)=2\alpha {\rm{\Gamma }}({w}^{k},{\tilde w }^{k})-{\alpha }^{2}{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}$ 是一个关于 $ \alpha $ 的二次函数,易知 $ g\left(\alpha \right) $ 取最大值时的 $ \alpha $ 的值为

$ {\alpha }_{k}:=\frac{{\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right)}{{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}} $ (28)

事实证明,对于任意松弛因子 $ t>0 $ ,有

$\begin{split} G\left(t{\alpha }_{k}\right)\geqslant &2t{\alpha }_{k}{\rm{\Gamma }}({w}^{k},{\tilde w }^{k})-{t}^{2}{\alpha }_{k}^{2}{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}=\\ &t(2-t){\alpha }_{k}{\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right) \end{split}$

为确保每次迭代都能得到改进,建议选择 $ t\in \left[{1,2}\right) $ 以便得到更好的收敛结果。

引理2  假设 $ \rho \geqslant {\left\| { A} \right\|}^{2} $ ,则有式(28)定义的步长 $ {\alpha }_{\min}>0 $

证明  引用柯西不等式的形式如下:

$ 2\left\langle {a,{\rm{b}}} \right\rangle \leqslant \varepsilon {\left\| {a} \right\|}^{2}+\frac{1}{\varepsilon }{\left\| {b} \right\|}^{2},\quad a,{{b}}\in {\mathbb{R}}^{{n}},\quad\varepsilon >0 $

同理,可得

$ \left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle \leqslant {\frac{\gamma }{2}\left\| {{\tilde \lambda }^{k}-{\lambda }^{k}} \right\|}^{2}+{\frac{1}{2\gamma }\left\| {{\tilde x}^{k}-{x}^{k}} \right\|}^{2} $

同样地,将式(17)代入式(19),有

$ \begin{split} {\rm{\Gamma }}({w}^{k},&{\tilde w }^{k})=\left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle -\left\langle {{\tilde w }^{k}-{w}^{k},{ H}d\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle =\\ &{\left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle +\left\| {{w}^{k}-{\tilde w }^{k}} \right\|}_{ H}^{2}-\left\langle {{x}^{k}-{\tilde x}^{k},{\eta }_{1}\left(x,{\tilde x}\right)} \right\rangle =\\ &\left\langle {{\tilde \lambda }^{k}-{\lambda }^{k},{\tilde x}^{k}-{x}^{k}} \right\rangle +{\left(\rho +\gamma \right)\left\| {{\tilde x}^{k}-{x}^{k}} \right\|}^{2}+\rho {\left\| {{\tilde z}^{k}-{z}^{k}} \right\|}^{2}+\\ &{\dfrac{1}{\gamma }\left\| {{\tilde \lambda }^{k}-{\lambda }^{k}} \right\|}^{2}-\left\langle {{x}^{k}-{\tilde x}^{k},{\eta }_{1}\left(x,{\tilde x}\right)} \right\rangle \geqslant\\ &{\left(\rho +\gamma -\dfrac{1}{2\gamma }\right)\left\| {{\tilde x}^{k}-{x}^{k}} \right\|}^{2}+\rho {\left\| {{\tilde z}^{k}-{z}^{k}} \right\|}^{2}+\\ &{\left(\dfrac{1}{\gamma }-\dfrac{\gamma }{2}\right)\left\| {{\tilde \lambda }^{k}-{\lambda }^{k}} \right\|}^{2}\\[-15pt] \end{split} $ (29)

显然, $ {\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right)\geqslant {C}_{\min}{\left\| {{w}^{k}-{\tilde w }^{k}} \right\|}^{2} $ ,其中, ${C}_{\min}:= \min\left\{\rho +\gamma -\dfrac{1}{2\gamma },\rho ,\dfrac{1}{\gamma }-\dfrac{\gamma }{2}\right\}$

另一方面,再次运用柯西不等式

$ \begin{split} &\left\| {d\left( {{w^k},{{\tilde w}^k}} \right)} \right\|_{ H}^2 = \left\| {{w^k} - {{\tilde w}^k}} \right\|_{ H}^2 - 2\left\langle {{x^k} - {{\tilde x}^k},{\eta _1}\left( {x,\tilde x} \right)} \right\rangle +\\ &\qquad\quad \dfrac{1}{{\rho \!+\! \gamma }}{\left\| {{\eta _1}\left( {x,\tilde x} \right)} \right\|^2} \!\leqslant\! \left( {\rho \!+ \!\gamma \!+\! \dfrac{{{{\left\| A \right\|}^2}}}{{\rho \!+\! \gamma }}} \right){\left\| {{{\tilde x}^k} \!-\! {x^k}} \right\|^2} + \\ &\qquad \quad\rho {\left\| {{{\tilde z}^k} - {z^k}} \right\|^2} + \dfrac{1}{\gamma }{\left\| {{{\tilde \lambda }^k} - {\lambda ^k}} \right\|^2}\\[-15pt] \end{split} $ (30)

显然, ${\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}\leqslant {C}_{\max}{\left\| {{w}^{k}-{\tilde w }^{k}} \right\|}^{2}$ ,其中, ${C}_{\max}:= \max\left\{\rho +\gamma +\dfrac{{\left\| {A} \right\|}^{2}}{\rho +\gamma },\rho ,\dfrac{1}{\gamma }\right\}$ 。因此,有 ${\alpha }_{k}\geqslant \dfrac{{C}_{\min}}{{C}_{\max}}=: {\alpha }_{\min} > 0$

证毕。

定理1  令 $ {w}^{*} $ 为式(20)的任意一个可行解,算法产生的序列 $ \left\{{w}^{k}\right\} $ 必须满足以下属性:

$\begin{split} &\left\| {{w}^{k+1}-{w}^{*}} \right\|_{H}^{2}\leqslant {\left\| {{w}^{k}-{w}^{*}} \right\|}_{H}^{2}-\\ &\qquad \quad\;\; t(2-t){\alpha }_{\min}{C}_{\min}{\left\| {{w}^{k}-{\tilde w }^{k}} \right\|}^{2} \end{split} $ (31)

证明  综合式(27)~(29)可得

$ \begin{split} &\left\| {{w}^{k+1}-{w}^{*}} \right\|_{M}^{2}={\left\| {{w}^{k}-{t\alpha }_{k}d\left({w}^{k},{\tilde w }^{k}\right)-{w}^{*}} \right\|}_{ H}^{2}=\\ &\qquad\quad {\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-2t{\alpha }_{k}\left\langle {{w}^{k}-{w}^{*},Md\left({w}^{k},{\tilde w }^{k}\right)} \right\rangle +\\ &\qquad\quad{{{t}^{2}\alpha }_{k}}^{2}{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}\leqslant {\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-\\ &\qquad\quad 2{t\alpha }_{k}{\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right)+{{{t}^{2}\alpha }_{k}}^{2}{\left\| {d\left({w}^{k},{\tilde w }^{k}\right)} \right\|}_{ H}^{2}=\\ &\qquad\quad{\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-t(2-t){\alpha }_{k}{\rm{\Gamma }}\left({w}^{k},{\tilde w }^{k}\right)\leqslant\\ &\qquad\quad{\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-{t(2-t)\alpha }_{\min}{C}_{\min}{\left\| {{w}^{k}-{\tilde w }^{k}} \right\|}^{2} \end{split} $

证毕。

定理2 算法产生的序列必须全局收敛于变分不等式(20)的解。

证明  令 $ {w}^{*} $ 为式(20)的任意一个可行解,根据式(31)可以得出结论:

$ {\left\| {{w}^{k+1}-{w}^{*}} \right\|}_{ H}^{2}\leqslant {\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}\leqslant \cdots \leqslant {\left\| {{w}^{0}-{w}^{*}} \right\|}_{ H}^{2} $ (32)

也就是说, ${\left\| {{w}^{k}-{w}^*} \right\|}_{ H}^{2}$ 是单调减的有界序列,即

$ \underset{k\to \infty }{\rm{lim}}\;{\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}{\text{存在}}。$ (33)

变换式(31)可得,

$\begin{split} (2-t)&{\alpha }_{\min}{C}_{\min}{\left\| {{w}^{k}-{\tilde w }^{k}} \right\|}^{2}\leqslant \\ &{\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}-{\left\| {{w}^{k+1}-{w}^{*}} \right\|}_{ H}^{2} \end{split} $

可得结论

$ \underset{k\to \infty }{\rm{lim}}\;{\left\| {{w}^{k}-{w}^{*}} \right\|}_{ H}^{2}=0 $ (34)

这证明了序列 $ \left\{{w}^{k}\right\} $ 全局收敛于 $ \left\{{w}^{{\infty }}\right\} $

5 数值实验

通过图像恢复问题验证算法的效果,所有代码均由Matlab 2017a 编写,处理器为 Intel Core i5 2.3 GHz,内存8 GB,并且在macOS 10.15上运行。

由于图像恢复为问题(4)的特殊情况,此问题的模型可以表示为

$ \mathop {{\rm{min}}}\limits_x \left\{ {\sigma {{\left\| {Wx} \right\|}_1} + \frac{1}{2}{{\left\| {{{A}}x - b} \right\|}^2},x \in C} \right\} $ (35)

其中, $ b $ 为观测到的图像,其经过高斯噪声模糊化处理。 ${ A}=BW$ 包含 $ B $ 模糊算子和 $ W $ 余弦离散变换算子。实例中描述的所有原始图像的所有像素首先被缩放到0~1之间。现采用4种不同的图片来展示算法。图1分别为house, pepper, camera和bridge的原图与模糊图像。


图 1 原图和模糊图像 Fig. 1 Original images and blurred images

随后采用一种常用的信噪比(SNR)概念来观测恢复图像的质量。

$ {{SNR}} : = 20\;{\lg }\;\frac{{\left\| x \right\|}}{{\left\| {\tilde x - x} \right\|}} $ (36)

式中: $ x $ 表示原本的图像; $ {\tilde x} $ 表示恢复后的图像。

SNR的数值越大,图像恢复的效果越好。一般使用式

$ \frac{\left\| {{x}^{k+1}-{x}^{k}} \right\|}{\left\| {{x}^{k}} \right\|}\leqslant {10}^{-4} $ (37)

来终止实验。

实验中设置 $\gamma \!\!=\!\!0.1$ $\rho \!\!=\!\!1.05{\left\| {A} \right\|}^{2}$ $\sigma \!\!=\!\!2\!\!\times\! \! {10}^{-4}$ $ {\rm{\omega }}= 1.7 $ $t\!=\!1.9$ 来进行验证,同时与ISM[27](implementable splitting method)进行比较。如图2所示,分别表示在2种算法下,4组实验的SNR和迭代次数的情况。


图 2 ISM与IADMM算法的试验比较 Fig. 2 Experimental comparison of ISM and IADMM algorithms

经过实验比较可知,改进后的IADMM算法无论是在信噪比(SNR)上,还是迭代次数上都有明显的优势。如图3所示,经IADMM算法运算后恢复的图像,相较于被噪声损坏的模糊图像,算法处理过的图像已剔除了绝大部分噪声对图像清晰度的影响,模糊的细节变得清晰可见。由此可见,本算法在去模糊化的过程中得到了良好的体现。


图 3 恢复后的图像 Fig. 3 Restored images

同时,在 $t = 1.9$ 的条件下对不同的终止准则分别进行了实验,针对IADMM算法设置了4个不同的公差数值,分别为 $tol = \left\{ {{10}^{ - 3}},\;5 \times {{10}^{ - 4}},\;{{10}^{ - 4}},5 \times\;\right.$ $\left. {{10}^{ - 5}} \right\}$ ,并在表1中列出了相应的结果。分析表1可知,综合考虑迭代时间和重建质量,当 $tol$ 取值为 ${10^{ - 4}}$ 时,为本算法最优终止准则。


表 1 不同 $ tol $ 值下IADMM算法的实验结果 Table 1 Experimental results of the IADMM algorithm under different tol

将2个算法进行比较,可以看出,IADMM算法比原始的ISM算法花费更少的迭代次数的同时获得更高的信噪比,这验证了本文提出的改进算法对迭代方面性能的提高。本文的实验验证了IADMM算法的有效性和可靠性。

6 结 论

由于 $ \ell _{1} $ 范数正则化问题不可微的性质,很多传统的迭代方法无法直接应用于 $ \ell _{1} $ 正则化的模型。本文对子问题 $ x $ 和对偶算子 $ \lambda $ 引入了新的参数,在取值恰当的情况下,提高了算法的收敛性,并减少了迭代次数。数值实验的结果也验证了算法的有效性和可靠性。

参考文献
[1]
CENSOR Y, ELFVING T. A multiprojection algorithm using Bregman projections in a product space[J]. Numerical Algorithms, 1994, 8(2): 221-239. DOI:10.1007/BF02142692
[2]
EICKE B. Iteration methods for convexly constrained ill-posed problems in Hilbert space[J]. Numerical Functional Analysis and Optimization, 1992, 13(5/6): 413-429.
[3]
SABHARWAL A, POTTER L C. Convexly constrained linear inverse problems: iterative least-squares and regularization[J]. IEEE Transactions on Signal Processing, 1998, 46(9): 2345-2352. DOI:10.1109/78.709518
[4]
POTTER L C, ARUN K S. A dual approach to linear inverse problems with convex constraints[J]. SIAM Journal on Control and Optimization, 1993, 31(4): 1080-1092. DOI:10.1137/0331049
[5]
ENGL H W, HANKE M, NEUBAUER A. Regularization of inverse problems[M]. Dordrecht: Kluwer, 1996.
[6]
FRICK K, GRASMAIR M. Regularization of linear ill-posed problems by the augmented Lagrangian method and variational inequalities[J]. Inverse Problems, 2012, 28(10): 104005. DOI:10.1088/0266-5611/28/10/104005
[7]
HOCHSTENBACH M E, REICHEL L. Fractional Tikhonov regularization for linear discrete ill-posed problems[J]. BIT Numerical Mathematics, 2011, 51(1): 197-215. DOI:10.1007/s10543-011-0313-9
[8]
SCHÖPFER F, LOUIS A K, SCHUSTER T. Nonlinear iterative methods for linear ill-posed problems in Banach spaces[J]. Inverse Problems, 2006, 22(1): 311-329. DOI:10.1088/0266-5611/22/1/017
[9]
CENG L C, ANSARI Q H, YAO J C. Relaxed extragradient methods for finding minimum-norm solutions of the split feasibility problem[J]. Nonlinear Analysis: Theory, Methods & Applications, 2012, 75(4): 2116-2125.
[10]
CENSOR Y, GIBALI A, REICH S. Algorithms for the split variational inequality problem[J]. Numerical Algorithms, 2012, 59(2): 301-323. DOI:10.1007/s11075-011-9490-5
[11]
XU H K. Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces[J]. Inverse Problems, 2010, 26(10): 105018. DOI:10.1088/0266-5611/26/10/105018
[12]
YAO Y H, WU J G, LIOU Y C. Regularized methods for the split feasibility problem[J]. Abstract and Applied Analysis, 2012, 2012: 140679.
[13]
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.
[14]
YANG J F, ZHANG Y. Alternating direction algorithms for ℓ1-problems in compressive sensing [J]. SIAM Journal on Scientific Computing, 2011, 33(1): 250-278. DOI:10.1137/090777761
[15]
CHEN S S, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1): 129-159. DOI:10.1137/S003614450037906X
[16]
DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306. DOI:10.1109/TIT.2006.871582
[17]
FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems[J]. IEEE Journal of Selected Topics in Signal Processing, 2007, 1(4): 586-597. DOI:10.1109/JSTSP.2007.910281
[18]
CAI J F, OSHER S, SHEN Z W. Linearized Bregman iterations for compressed sensing[J]. Mathematics of Computation, 2009, 78(267): 1515-1536. DOI:10.1090/S0025-5718-08-02189-3
[19]
WRIGHT S J, NOWAK R D, FIGUEIREDO M A T. Sparse reconstruction by separable approximation[J]. IEEE Transactions on Signal Processing, 2009, 57(7): 2479-2493. DOI:10.1109/TSP.2009.2016892
[20]
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.
[21]
BAI Z J, CHEN M X, YUAN X M. Applications of the alternating direction method of multipliers to the semidefinite inverse quadratic eigenvalue problem with a partial eigenstructure[J]. Inverse Problems, 2013, 29(7): 075011. DOI:10.1088/0266-5611/29/7/075011
[22]
CHAN R H, YANG J F, YUAN X M. Alternating direction method for image inpainting in wavelet domains[J]. SIAM Journal on Imaging Sciences, 2011, 4(3): 807-826. DOI:10.1137/100807247
[23]
CHEN C H, HE B S, YUAN X M. Matrix completion via an alternating direction method[J]. IMA Journal of Numerical Analysis, 2012, 32(1): 227-245. DOI:10.1093/imanum/drq039
[24]
HE B S, LIAO L Z, HAN D R, et al. A new inexact alternating directions method for monotone variational inequalities[J]. Mathematical Programming, 2002, 92(1): 103-118. DOI:10.1007/s101070100280
[25]
MA S Q. Alternating direction method of multipliers for sparse principal component analysis[J]. Journal of the Operations Research Society of China, 2013, 1(2): 253-274. DOI:10.1007/s40305-013-0016-9
[26]
YUAN X M. Alternating direction method for covariance selection models[J]. Journal of Scientific Computing, 2012, 51(2): 261-273. DOI:10.1007/s10915-011-9507-1
[27]
HE H J, LING C, XU H K. An implementable splitting algorithm for the ℓ1-norm regularized split feasibility problem [J]. Journal of Scientific Computing, 2016, 67(1): 281-298. DOI:10.1007/s10915-015-0078-4
[28]
ECKSTEIN J, BERTSEKAS D P. On the Douglas−Rachford splitting method and the proximal point algorithm for maximal monotone operators[J]. Mathematical Programming, 1992, 55(1): 293-318.
[29]
BERTSEKAS D P, TSITSIKLIS J N. Parallel and distributed computation: numerical methods[M]. New Jersey: Prentice Hall, 1989.