上海理工大学学报  2020, Vol. 42 Issue (5): 460-466 PDF

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 研究现状

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

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

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

 $\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)

 $\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)

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范数。

 ${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)

 $\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)$

 $\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}$

 $\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)

 ${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)

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)

 $\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}$

 $\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}={\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{\eta }}\left({\rm{w}},{\tilde w}\right):=\left(\begin{array}{c}{\eta }_{1}\left(x,{\tilde x}\right)\\ 0\\ 0\end{array}\right)$ (15)

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 收敛性

 $\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}$

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

 $\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)

 $\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)

 $\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)

 $\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)$

$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$

 $\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$

 $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)

 $\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}$

 ${\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)

 $\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}$

 $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}$

 $\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)

 $\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)

 $\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)

 $\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}$

 ${\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)

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

 $\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)

5 数值实验

 $\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)

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

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

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

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

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

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

6 结　论

 [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.