﻿ 求解凸优化问题的改进对称交替方向乘子法
 上海理工大学学报  2020, Vol. 42 Issue (3): 269-274 PDF

A modified symmetric alternating direction method of multipliers for convex optimization problems
JIANG Feng, DANG Yazheng
Business School, University of Shanghai for Science and Technology, Shanghai 200093, China
Abstract: Symmetric alternating direction method of multipliers （S-ADMM） is an efficient method for convex optimization problems with separable structure. The algorithm makes use of the separability of the objective function to decompose the original problem into several minimization subproblems and to solve them alternately.Whether the subproblems can be effectively solved affects the effectiveness of the algorithm. In many practical applications, subproblems cannot be solved precisely, or the cost of solving subproblems precisely is relatively high. To solve this problem, a modified symmetric alternating direction method of multipliers (MS-ADMM) is proposed. Compared to the general symmetric ADMM, this algorithm adds a semi-proximal term to x-subproblem which is then solved approximately. This overcomes the shortcoming of the previous algorithm. The convergence of the sequence generated by the proposed algorithm is proved under some suitable assumptions. Preliminary numerical experiments illustrate the effectiveness of proposed algorithm.
Key words: convex optimization     modified symmetric alternating direction method of multipliers     convergence
1 问题的提出

 $\min\left\{ f\left( x \right) + g\left( {\textit{z}} \right)|{{A}}x = {\textit{z}},\;x \in X,\;{\textit{z}} \in Z\right\}$ (1)

 \left\{\begin{aligned} &{x}^{k+1}={\rm{argmin}}\left\{ {f\left(x\right)-{\left({y}^{k}\right)}^{\rm T}\left({{A}}x-{\textit{z}^{k}}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}{x}-{\textit{z}^{k}} \right\|}^{2}}\right\}\\ &{\textit{z}}^{k+1}={\rm{argmin}}\left\{ {g\left({\textit{z}}\right)-{\left({y}^{k}\right)}^{\rm T}\left({{A}}{x}^{k+1}-{\textit{z}}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}{x}^{k+1}-{\textit{z}} \right\|}^{2}}\right\}\\ & {y}^{k+1}={y}^{k}-\gamma \left({{{A}}x}^{k+1}-{{\textit{z}}}^{k+1}\right)\end{aligned}\right. (2)

 \left\{\begin{aligned}&{x}^{k+1}={\rm{argmin}}\left\{ {f\left(x\right)-{\left({y}^{k}\right)}^{\rm T}\left({{A}}x-{{\textit{z}}}^{k}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\frac{\gamma }{2}{\left\| {{{A}}x-{{\textit{z}}}^{k}} \right\|}^{2}+ \frac{1}{2}{\left(x-{x}^{k}\right)}^{\rm T}{ G}\left(x-{x}^{k}\right)} \right\}\\ & {\textit{z}}^{k+1}={\rm{argmin}}\left\{ {g\left({\textit{z}}\right)-{\left({y}^{k}\right)}^{\rm T}\left({{A}}{x}^{k+1}-{\textit{z}}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}{x}^{k+1}-{\textit{z}} \right\|}^{2}}\right\}\\ &{y}^{k+1}={y}^{k}-\gamma \left({{A}}{x}^{k+1}-{{\textit{z}}}^{k+1}\right)\end{aligned}\right. (3)

 \left\{\begin{aligned}&{x}^{k+1}={\rm{argmin}}\left\{ {f\left(x\right)-{\left({y}^{k}\right)}^{\rm T}\left({{A}}x-{\textit{z}^{k}}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}{x}-{\textit{z}^{k}} \right\|}^{2}}\right\}\\ & {y}^{k+\frac{1}{2}}={y}^{k}-\gamma \left({{A}}{x}^{k+1}-{{\textit{z}}}^{k}\right)\\& {\textit{z}}^{k+1}={\rm{argmin}}\left\{ {g({\textit{z}})-{\left({y}^{k+\frac{1}{2}}\right)}^{\rm T}\left({{A}}{x}^{k+1}-{\textit{z}}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}{x}^{k+1}-{\textit{z}} \right\|}^{2}}\right\}\\ & {y}^{k+1}={y}^{k+\frac{1}{2}}-\gamma \left({{A}}{x}^{k+1}-{{\textit{z}}}^{k+1}\right)\end{aligned}\right. (4)

2 算　法

 ${\left({x}^{*},{{\textit{z}}}^{*},{y}^{*}\right)}^{\rm T}={ w}^{*}\in \varOmega$

 ${\theta \left({ u}\right)-\theta \left({ u}^{*}\right)+\left({ w}-{ w}^{*}\right)}^{\rm T}{ F}\left({ w}^{*}\right)\geqslant 0,\;\;\forall { w}\in {{\varOmega }}$ (5)

 \left\{\begin{aligned}&{x}^{k+1}={\rm{argmin}} \left\{ {f\left(x\right)-{\left({y}^{k}\right)}^{\rm T}\left({{A}}x-{\textit{z}}^{k}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}x-{\textit{z}}^{k} \right\|}^{2}+\dfrac{1}{2}{\left\| x-{x}^{k} \right\|}_{ G}^{2}} \right\}\\ &{y}^{k+\frac{1}{2}}={y}^{k}-\alpha \gamma \left({{A}}{x}^{k+1}-{\textit{z}}^{k}\right)\\ &{\textit{z}}^{k+1}={\rm{argmin}}\left\{ {g({\textit{z}})-{\left({y}^{k+\frac{1}{2}}\right)}^{\rm T}\left({{A}}{x}^{k+1}-{\textit{z}}\right)+} \right.\\&\;\;\;\;\;\;\;\;\;\;\;\left. {\dfrac{\gamma }{2}{\left\| {{A}}{x}^{k+1}-{\textit{z}} \right\|}^{2}}\right\}\\ & {y}^{k+1}={y}^{k+\frac{1}{2}}-\alpha \gamma \left({{A}}{x}^{k+1}-{\textit{z}}^{k+1}\right)\end{aligned}\right.

3 收敛性分析

 $\left\{ \begin{array}{l} { H} = \left( {\begin{array}{*{20}{c}} {2{{G}}}&0&0\\ 0&{\left( {2 - \alpha } \right)\gamma {{{I}}_m}}&{{{{I}}_{m}}}\\ 0&{{{{I}}_{m}}}&{\dfrac{1}{{\alpha \gamma }}{{{I}}_{m}}} \end{array}} \right)\\ { M} = \left( {\begin{array}{*{20}{c}} {{{{I}}_{n}}}&0&0\\ 0&{{{{I}}_{m}}}&0\\ 0&{\alpha \gamma {{{I}}_{m}}}&{2\alpha {{{I}}_{m}}} \end{array}} \right)\\ { Q} = \left( {\begin{array}{*{20}{c}} {{G}}&0&0\\ 0&{\gamma {{{I}}_{m}}}&{\alpha {{{I}}_{m}}}\\ 0&{{{{I}}_{m}}}&{\dfrac{1}{\gamma }{{{I}}_{m}}} \end{array}} \right) \end{array}\right.$ (6)

 ${{H}} = \left( {\begin{array}{*{20}{c}} {{G}}&0&0\\ 0&0&0\\ 0&0&0 \end{array}} \right) + \frac{1}{2}\left( {\begin{array}{*{20}{c}} 0&0&0\\ 0&{\left( {2 - \alpha } \right)\gamma {{{I}}_{m}}}&{{{{I}}_{m}}}\\ 0&{{{{I}}_{m}}}&{\dfrac{1}{{\alpha \gamma }}{{{I}}_{m}}} \end{array}} \right)$

 ${{{H}}}_{1}=\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \left(2-\alpha \right)\gamma {{{I}}}_{{m}}& {{{I}}}_{{m}}\\ 0& {{{I}}}_{{m}}& \dfrac{1}{\alpha \gamma }{{{I}}}_{{m}}\end{array}\right)$

 $\begin{array}{l} {{{H}}}_{1}=\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \sqrt{r}{{{I}}}_{{m}}& 0\\ 0& 0& \sqrt{\dfrac{1}{\gamma }}{{{I}}}_{{m}}\end{array}\right)\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \left(2-\alpha \right){{{I}}}_{{m}}& {{{I}}}_{{m}}\\ 0& {{{I}}}_{{m}}& \dfrac{1}{\alpha }{{{I}}}_{{m}}\end{array}\right){\text{·}} \\ \end{array}$
 $\begin{array}{l} \;\;\;\;\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \sqrt{r}{{{I}}}_{{m}}& 0\\ 0& 0& \sqrt{\dfrac{1}{\gamma }}{{{I}}}_{{m}}\end{array}\right) \end{array}$

 $\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \left(2-\alpha \right)& 1\\ 0& 1& \dfrac{1}{\alpha }\end{array}\right)$

a. ${{H}}{{M}}={{Q}}$

b. ${{{Q}}}^{\rm T}+{{Q}}-{{{M}}}^{\rm T}{{H}}{{M}}\succeq \dfrac{1-\alpha }{2\left(1+\alpha \right)}{{{M}}}^{\rm T}{{H}}{{M}}$

 $\begin{array}{l} {{H}}{{M}}=\dfrac{1}{2}\left(\begin{array}{*{20}{c}}2{{G}}& 0& 0\\ 0& \left(2-\alpha \right)\gamma {{{I}}}_{{m}}& {{{I}}}_{{m}}\\ 0& {{{I}}}_{{m}}& \dfrac{1}{\alpha \gamma }{{{I}}}_{{m}}\end{array}\right){\text{·}} \\ \;\;\;\;\;\;\;\;\;\;\;\;\left(\begin{array}{*{20}{c}}{{{I}}}_{{n}}& 0& 0\\ 0& {{{I}}}_{{m}}& 0\\ 0& \alpha \gamma {{{I}}}_{{m}}& 2\alpha {{{I}}}_{{m}}\end{array}\right)=\left(\begin{array}{*{20}{c}}{{G}}& 0& 0\\ 0& \gamma {{{I}}}_{{m}}& \alpha {{{I}}}_{{m}}\\ 0& {{{I}}}_{{m}}& \dfrac{1}{\gamma }{{{I}}}_{{m}}\end{array}\right) \end{array}$

HM= Q得证。再次使用HQM的定义，有

 ${{{M}}}^{{\rm{T}}}{{H}}{{M}}={{{M}}}^{{\rm{T}}}{{Q}}=\left(\begin{array}{*{20}{c}}{{G}}& 0& 0\\ 0& \gamma \left(1+\alpha \right){{{I}}}_{{m}}& 2\alpha {{{I}}}_{{m}}\\ 0& 2\alpha {{{I}}}_{{m}}& \dfrac{2\alpha }{\gamma }{{{I}}}_{{m}}\end{array}\right)$ (7)

 ${{{Q}}}^{{\rm{T}}}\!+\!{{Q}}\!-\!{{{M}}}^{{\rm{T}}}{{H}}{{M}}\!=\!\left(1\!-\!\alpha \right)\left(\begin{array}{*{20}{c}}\!\!\dfrac{1}{1-\alpha }{{G}}& \!0\!& 0\!\!\\\!\! 0& \gamma {{{I}}}_{{m}}\!&\! {{{I}}}_{{m}}\!\!\\\!\! 0& {{{I}}}_{{m}}\!&\! \dfrac{2}{\gamma }{{{I}}}_{{m}}\!\!\end{array}\right)$ (8)

 $\begin{array}{l} {{D}}=2\left(1+\alpha \right)\left(\begin{array}{*{20}{c}}\dfrac{1}{1-\alpha }{{G}}& 0& 0\\ 0& \gamma {{{I}}}_{{m}}& {{{I}}}_{{m}}\\ 0& {{{I}}}_{{m}}& \dfrac{2}{\gamma }{{{I}}}_{{m}}\end{array}\right)-{{{M}}}^{{\rm{T}}}{{H}}{{M}}=\\\;\;\;\;\;\;\;\; \left(\begin{array}{*{20}{c}}\dfrac{1+3\alpha }{1-\alpha }{{G}}& 0& 0\\ 0& \gamma \left(1+\alpha \right){{{I}}}_{{m}}& 2{{{I}}}_{{m}}\\ 0& 2{{{I}}}_{{m}}& \dfrac{4+2\alpha }{\gamma }{{{I}}}_{{m}}\end{array}\right)\\[-30pt] \end{array}$ (9)

 $\begin{split}& {{D}}=\left(\begin{array}{*{20}{c}}\dfrac{1+3\alpha }{1-\alpha }{{G}}& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\right)+\\& \;\;\;\;\;\;\;\;\;\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \gamma \left(1+\alpha \right){{{I}}}_{{m}}& 2{{{I}}}_{{m}}\\ 0& 2{{{I}}}_{{m}}& \dfrac{4+2\alpha }{\gamma }{{{I}}}_{{m}}\end{array}\right) \end{split}$ (10)

 $\left(\begin{array}{*{20}{c}}0& 0& 0\\ 0& \gamma \left(1+\alpha \right)& 2\\ 0& 2& \dfrac{4+2\alpha }{\gamma }\end{array}\right)\succeq 0$

 $\left(\begin{array}{*{20}{c}}\dfrac{1}{1-\alpha }{{G}}& 0& 0\\ 0& \gamma {{{I}}}_{{m}}& {{{I}}}_{{m}}\\ 0& {{{I}}}_{{m}}& \dfrac{2}{\gamma }{{{I}}}_{{m}}\end{array}\right)\succeq \dfrac{1}{2(1+\alpha )}{{{M}}}^{{\rm{T}}}{{H}}{{M}}$ (11)

 ${{{Q}}}^{{\rm{T}}}+{{Q}}-{{{M}}}^{{\rm{T}}}{{H}}{{M}}\succeq \frac{1-\alpha }{2\left(1+\alpha \right)}{{{M}}}^{{\rm{T}}}{{H}}{{M}}$

$\left\{{ w}^{k}\right\}$ 是由改进的对称ADMM算法产生的序列，定义一个新的序列

 ${\tilde { w}}^{k}=\left({\begin{array}{*{20}{c}}{\tilde {x}}^{k}\\ {\tilde {{\textit{z}}}}^{k}\\ {\tilde {y}}^{k}\end{array}}\right)=\left({\begin{array}{*{20}{c}}{x}^{k+1}\\{{\textit{z}}}^{k+1}\\ {y}^{k}-\gamma \left({{A}}{x}^{k+1}-{{\textit{z}}}^{k}\right)\end{array}}\right)$ (12)

 ${ w}^{k+1}={ w}^{k}-{{M}}({ w}^{k}-{\tilde { w}}^{k})$ (13)

 $\begin{split}& \theta \left({ u}\right)-\theta \left({\tilde { u}}^{k}\right)+\left({ w}-{\tilde { w}}^{k}\right)^{\rm T}\left\{{ F}\left({\tilde { w}}^{k}\right)-\right.\;\;\;\;\;\;\;\;\;\;\qquad\\ &\;\;\;\;\left.{ Q}\left({ w}^{k}-{\tilde { w}}^{k}\right)\right\}\geqslant 0, \;\;{\tilde { w}}^{k}\in \varOmega \;\; \end{split}$ (14)

 $\begin{split}& f\left(x\right)-f\left({\tilde {x}}^{k}\right)+{\left(x-{\tilde {x}}^{k}\right)}^{\rm T}{\text{·}}\\ & \;\;\;\;\left\{{{{A}}}^{{\rm{T}}}\left[\gamma \left({{A}}{\tilde {x}}^{k}-{{\textit{z}}}^{k}\right)- {y}^{k}\right]+{{G}}\left({\tilde {x}}^{k}-{x}^{k}\right)\right\}\geqslant 0 , \\&\;\;\;\;\forall x\in X \end{split}$ (15)

 $\begin{split}& f\left(x\right)-f\left({\tilde {x}}^{k}\right)+{\left(x-{\tilde {x}}^{k}\right)}^{\rm T}{\text{·}}\qquad\qquad\qquad\qquad\\ &\;\;\;\;\left\{-{{{A}}}^{{\rm{T}}}{\tilde {y}}^{k}+ {{G}}\left({\tilde {x}}^{k}-{x}^{k}\right)\right\}\geqslant 0, \;\;\forall x\in X \end{split}$ (16)

 $\begin{split}& g\left({\textit{z}}\right)-g\left({\tilde {{\textit{z}}}}^{k}\right)+{\left({\textit{z}}-{\tilde {{\textit{z}}}}^{k}\right)}^{\rm T}{\text{·}}\qquad\qquad\qquad\quad\\ &\;\;\;\;\left\{-\gamma \left({{A}}{x}^{k+1}-{\tilde {{\textit{z}}}}^{k}\right)+{y}^{k+\frac{1}{2}}\right\}\geqslant 0, \;\;\forall {\textit{z}}\in {\textit{Z}} \end{split}$ (17)

 $\begin{split}& -\gamma \left({{A}}{x}^{k+1}-{\tilde {{\textit{z}}}}^{k}\right)+{y}^{k+\frac{1}{2}}=\qquad\qquad\qquad\qquad\;\\&\;\;\;\;\; {\tilde {y}}^{k}+\alpha \left({\tilde {y}}^{k}-{y}^{k}\right)+\gamma ({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}) \end{split}$ (18)

 $\begin{split}& g\left({\textit{z}}\right)-g\left({\tilde {{\textit{z}}}}^{k}\right)+{\left({\textit{z}}-{\tilde {{\textit{z}}}}^{k}\right)}^{\rm T}{\text{·}}\qquad\qquad\qquad\qquad\;\\ &\;\;\;\; \left\{{\tilde {y}}^{k}+\gamma \left({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}\right)+\alpha \left({\tilde {y}}^{k}-{y}^{k}\right)\right\}\geqslant 0, \;\;\forall {\textit{z}}\in {\textit{Z}} \end{split}$ (19)

 $\left({{A}}{\tilde {x}}^{k}-{\tilde {{\textit{z}}}}^{k}\right)+\left({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}\right)+\frac{1}{\gamma }\left({\tilde {y}}^{k}-{y}^{k}\right)=0$ (20)

 $\begin{split}& {\theta \left({ u}\right)-\theta \left({\tilde { u}}^{k}\right)+\left({ w}-{\tilde { w}}^{k}\right)}^{\rm T}{\text{·}}\\ &\;\;\;\;\left\{\left({\begin{array}{*{20}{c}}-{{{A}}}^{{{T}}}{\tilde {y}}^{k}\\{\tilde {y}}^{k}\\ A{\tilde {x}}^{k}-{\tilde {{\textit{z}}}}^{k}\end{array}}\right)+\left({\begin{array}{*{20}{c}}{{G}}({\tilde {x}}^{k}-{x}^{k})\\\gamma \left({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}\right)+\alpha \left({\tilde {y}}^{k}-{y}^{k}\right)\\ \left({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}\right)+\frac{1}{\gamma }({\tilde {y}}^{k}-{y}^{k})\end{array}}\right)\right\}\geqslant 0 \end{split}$ (21)

 $\left({\begin{array}{*{20}{c}}{{G}}({\tilde {x}}^{k}-{x}^{k})\\ \gamma \left({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}\right)+\left({\tilde {y}}^{k}-{y}^{k}\right)\\ \left({\tilde {{\textit{z}}}}^{k}-{{\textit{z}}}^{k}\right)+\frac{1}{\gamma }({\tilde {y}}^{k}-{y}^{k})\end{array}}\right)=-{{Q}}\left({ w}^{k}-{\tilde { w}}^{k}\right)$

 ${\theta \left({ u}\right)-\theta \left({\tilde { u}}^{k}\right)+\left({ w}-{\tilde { w}}^{k}\right)}^{\rm T}\left\{{ F}{(\tilde { w}}^{k})-{{Q}}\left({ w}^{k}-{\tilde { w}}^{k}\right)\right\}\geqslant 0$

 $\begin{split}& {\left({ w}-{\tilde { w}}^{k}\right)}^{\rm T}{{Q}}\left({ w}^{k}-{\tilde { w}}^{k}\right)\geqslant\qquad\qquad\qquad\qquad\;\\ &\;\;\;\;\dfrac{1}{2}\left({\left\| {{ w}-{ w}^{k}} \right\|}_{{{H}}}^{2}-{\left\| {{ w}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}\right)+\\ &\;\;\;\;{\dfrac{1-\alpha }{2\left(1+\alpha \right)}\left\| {{ w}^{k}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}\end{split}$ (22)

 $\begin{array}{l}{\left({ a}-{ b}\right)}^{\rm T}{{H}}\left({ c}-{ d}\right)=\dfrac{1}{2}\left({\left\| {{ a}-{ d}} \right\|}_{{{H}}}^{2}-{\left\| {{ a}-{ c}} \right\|}_{{{H}}}^{2}\right)+\;\;\;\;\qquad\qquad\\ \;\;\;\;\dfrac{1}{2}\left({\left\| {{ c}-{ b}} \right\|}_{{{H}}}^{2}-{\left\| {{ d}-{ b}} \right\|}_{{{H}}}^{2}\right)\end{array}$

 ${ a}={ w}, \; { b}={\tilde { w}}^{k}, \; { c}={ w}^{k}, \; { d}={ w}^{k+1}$

 $\begin{split}& {\left(w-{\tilde { w}}^{k}\right)}^{\rm T}{{Q}}\left({ w}^{k}-{\tilde { w}}^{k}\right)=\qquad\qquad\qquad\qquad\\ &\;\;\;\;\dfrac{1}{2}\left({\left\| { w-{ w}^{k+1}} \right\|}_{{{H}}}^{2}-{\left\| { w-{ w}^{k}} \right\|}_{{{H}}}^{2}\right)+\\ &\;\;\;\;\dfrac{1}{2}\left({\left\| { { w}^{k}-{\tilde { w}}^{k}} \right\|}_{{{H}}}^{2}-{\left\| { { w}^{k+1}-{\tilde { w}}^{k}} \right\|}_{{{H}}}^{2}\right) \end{split}$ (23)

 $\begin{array}{l} {\left\| {{ w}^{k}-{\tilde { w}}^{k} } \right\|}_{{{H}}}^{2}-{\left\| {{ w}^{k+1}-{\tilde { w}}^{k} } \right\|}_{{{H}}}^{2}= \\\;\;\;\;{\left\| {{ w}^{k}-{\tilde { w}}^{k} } \right\|}_{{ H}}^{2}-{\left\| {{\left({ w}^{k}-{\tilde { w}}^{k}\right)}-\left({ w}^{k}-{ w}^{k+1}\right) } \right\|}_{{{H}}}^{2}= \\\;\;\;\; {\left\| {{ w}^{k}-{\tilde { w}}^{k} } \right\|}_{{{H}}}^{2}-{\left\| {{\left({ w}^{k}-{\tilde { w}}^{k}\right)-{{M}}}\left({{ w}^{k}}-{\tilde { w}}^{k}\right) } \right\|}_{{{H}}}^{2}= \\\;\;\;\;{\left({ w}^{k}-{\tilde { w}}^{k}\right)}^{\rm T}\left({{{Q}}}^{\rm T}+{{Q}}-{{{M}}}^{{\rm{T}}}{{H}}{{M}}\right)\left({ w}^{k}-{\tilde { w}}^{k}\right)\geqslant \\ \;\;\;\;\dfrac{1-\alpha }{2\left(1+\alpha \right)}{\left({ w}^{k}-{\tilde { w}}^{k}\right)}^{\rm T}\left({{{Q}}}^{{\rm{T}}}+{{Q}}-{{{M}}}^{{\rm{T}}}{{H}}{{M}}\right)\left({ w}^{k}-{\tilde { w}}^{k}\right)= \\ \;\;\;\;{\dfrac{1-\alpha }{2\left(1+\alpha \right)}{\left\| {{ w}^{k}-{ w}^{k+1} } \right\|}_{{{H}}}^{2}}\\[-15pt] \end{array}$ (24)

 $\begin{split}& {\theta \left({ u}\right)-\theta \left({\tilde { u}}^{k}\right)+\left( w-{\tilde { w}}^{k}\right)}^{\rm T}{ F}\left({ w}\right)\geqslant \qquad\qquad\quad\\ &\;\;\;\;\dfrac{1}{2}\left({\left\| {{ w}-{ w}^{k}} \right\|}_{{{H}}}^{2}-{\left\| {{ w}-{ w}^{k+1}} \right\|}_{{{ H}}}^{2}\right)+\\ &\;\;\;\;{\dfrac{1-\alpha }{2\left(1+\alpha \right)}{\left\| {{ w}^{k}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}} \end{split}$ (25)

 $\begin{split}& {\theta \left({ u}\right)-\theta \left({\tilde { u}}^{k}\right)+\left({ w}-{\tilde { w}}^{k}\right)}^{\rm T}{ F}{(\tilde { w}}^{k})\geqslant\qquad\qquad\qquad\qquad \\ &\;\;\;\;\dfrac{1}{2}\left({\left\| {{ w}-{ w}^{k}} \right\|}_{{{H}}}^{2}-{\left\| {{ w}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}\right)+\\ &\;\;\;\;{\dfrac{1-\alpha }{2\left(1+\alpha \right)}{\left\| {{ w}^{k}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}}\\[-15pt] \end{split}$ (26)

 ${\left({ w}-{\tilde { w}}^{k}\right)}^{\rm T}\left\{{ F}\left({ w}\right)-{ F}\left({\tilde { w}}^{k}\right)\right\}\geqslant 0$ (27)

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

 $\begin{split}& {\left\| {{ w}^{k}-{ w}^{*}} \right\|}_{{{H}}}^{2}-{\dfrac{1-\alpha }{2\left(1+\alpha \right)}{\left\| {{ w}^{k}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}} \geqslant\qquad\\ &\;\;\;\;2\left\{{\theta \left({\tilde { u}}^{k}\right)-\theta \left({ u}^{*}\right)+\left({\tilde { w}}^{k}-{ w}^{*}\right)}^{\rm T}{ F}\left({ w}^{*}\right)\right\}+\\ &\;\;\;\;{\left\| {{ w}^{k+1}-{ w}^{*}} \right\|}_{{{H}}}^{2} \end{split}$ (28)

 ${\theta \left({\tilde { u}}^{k}\right)-\theta \left({ u}^{*}\right)+\left({\tilde { w}}^{k}-{ w}^{*}\right)}^{\rm T}{ F}\left({ w}^{*}\right)\geqslant 0$

 $\begin{split}& {\left\| {{ w}^{k+1}-{ w}^{*}} \right\|}_{{{H}}}^{2}\leqslant \qquad \qquad\qquad\qquad\qquad\qquad\\ &\;\;\;\;{\left\| {{ w}^{k}-{ w}^{*}} \right\|}_{{{H}}}^{2}-{\frac{1-\alpha }{2\left(1+\alpha \right)}{\left\| {{ w}^{k}-{ w}^{k+1}} \right\|}_{{{H}}}^{2}} \end{split}$ (29)
4 数值计算

 $\min\left\{\frac{1}{2}{\left\| {{{P}}x-{b}} \right\|}^{2}+{ F}{\left\| {x} \right\|}_{1}\right\}$

 $\min\left\{\frac{1}{2}{\left\| {{{P}}x-{b}} \right\|}^{2}+{u}{\left\| {{\textit{z}}} \right\|}_{1} | x-{\textit{z}}=0\right\}$

 ${\max}\left\{{d}^{k},{p}^{k}\right\}\leqslant \sqrt{n}\delta$

 图 1 初始残差的变化情况 Fig. 1 Evolution of primal residual

 图 2 对偶残差的变化情况 Fig. 2 Evolution of dual residual
5 结 论

 [1] 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. [2] CHAN T F, GLOWINSKI R. Finite element approximation and iterative solution of a class of mildly non-linear elliptic equations[R]. Stanford, CA: Stanford University, 1978. [3] 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, 2010, 3(1): 1-122. DOI:10.1561/2200000016 [4] HE B S, LIU H, WANG Z R, et al. A strictly contractive Peaceman-Rachford splitting method for convex programming[J]. SIAM Journal on Optimization, 2014, 24(3): 1011-1040. DOI:10.1137/13090849X [5] HE B S, YUAN X M. On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method [J]. SIAM Journal on Numerical Analysis, 2012, 50(2): 700-709. DOI:10.1137/110836936 [6] DENG W, YIN W. On the global and linear convergence of the generalized alternating direction method of multipliers[J]. Journal of Scientific Computing, 2016, 66(3): 889-916. DOI:10.1007/s10915-015-0048-x [7] 刘柳, 陶大程. Lasso问题的最新算法研究[J]. 数据采集与处理, 2015, 30(1): 35-46. [8] 何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31. [9] 李静, 仝晓云, 王金甲. 基于交替方向乘子法的广义交互LASSO模型用于肝脏疾病分类[J]. 生物医学工程学杂志, 2017, 34(3): 350-356. [10] SUN M, LIU J. Generalized Peaceman-Rachford splitting method for separable convex programming with applications to image processing[J]. Journal of Applied Mathematics and Computing, 2016, 51(1/2): 605-622. [11] XIE J, LIAO A, Yang X. An inexact alternating direction method of multipliers with relative error criteria[J]. Optimization Letters, 2017, 11(3):583-596. [12] WEN Z, GOLDFARB D, YIN W, et al. Alternating direction augmented Lagrangian methods for semidefinite programming[J]. Mathematical Programming Computation, 2010, 2(3/4):203-230.