上海理工大学学报  2020, Vol. 42 Issue (3): 269-274   PDF    
求解凸优化问题的改进对称交替方向乘子法
蒋峰, 党亚峥     
上海理工大学 管理学院 上海 20093
摘要: 对称交替方向乘子法(简称S-ADMM算法)是求解可分离凸优化问题的一种有效方法。该算法利用目标函数的可分离性,将原问题分解成多个极小化子问题,然后交替求解。能否有效地求解子问题对算法的有效性有重要影响。在很多实际应用中,不能精确地求解子问题,或者精确求解子问题花费代价较大。为解决这一问题,提出了一种改进的对称交替方向乘子法(简称MS-ADMM算法)。与一般的S-ADMM算法相比,该算法在x子问题中引入一个半近邻项,近似地求解x子问题,克服了之前算法的不足。在适当的假设下,证明了其收敛性。最后,通过数值计算说明了该算法的有效性。
关键词: 凸优化     改进的对称交替方向乘子法     收敛性    
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)

式中: ${{A}}\in {\mathbb R}^{m\times n}; \;X\subset {\mathbb R}^{n}$ $ {Z}\subset{\mathbb R}^{m}$ 是给定闭凸集;mn为矩阵的维数; $f:{\mathbb R}^{n}\to {\mathbb R}\cup \left\{+\infty \right\}$ $g:{\mathbb R}^{m}\to {\mathbb R}\cup \left\{+\infty \right\}$ 为凸函数。假设问题(1)的解集非空。

Glowinski等[1-2]提出了交替方向乘子法(ADMM),并用此算法来求解问题(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)

式中: $ y\in {\mathbb R}^{m}$ 为拉格朗日乘子; $\gamma > 0$ 是惩罚参数。与同时求解xz极小化问题的拉格朗日乘子法不同,ADMM算法先求解x最小化问题,再求解z最小化问题,最后再更新拉格朗日乘子y,这很大程度提升了求解问题(1)的效率。目前,ADMM算法已经被广泛应用于图像处理、机器学习和金融统计等领域[3],在实际应用中也衍生了许多ADMM算法的变体。

因为经典的ADMM算法难以求得子问题的精确解,为了弥补这一缺陷,何炳生等[4]x子问题中加入了 $ \dfrac{1}{2}{\left(x-{x}^{k}\right)}^{\rm T}{ G}(x-{x}^{k})$ 项,得到了下面的新算法:

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

式中,G是一个半正定矩阵。何炳生等[4]证明了该算法的收敛速率。

从问题(1)本身来看,变量xz是平等的,在设计算法时也希望能够平等对待xz子问题。因此何炳生等[5]提出了对称ADMM算法,其迭代格式如下:

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

与原来的ADMM算法不同,式(4)在每一次迭代中更新拉格朗日乘子两次。文献[4]中分析了该算法的全局收敛性,数值计算表明该算法比原始的ADMM算法收敛速度更快。

然而,在很多实际应用中,精确地求解式(4)中的x子问题难以实现,或者要付出很大代价。因此本文提出了一种改进的对称ADMM算法。该算法的主要创新之处是在对称ADMM算法的x极小化子问题中加入半近邻项近似求解此问题,同时给出了收敛性证明。数值计算表明,改进的对称ADMM算法的收敛速度比对称ADMM算法更快。

2 算 法

问题(1)等价于一个变分不等式VI $\varOmega ,{ F},\theta $ ),求

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

式中: ${ u}=\left( {\begin{array}{*{20}{c}}x\\{\textit{z}}\end{array}} \right); \;{ w}=\left(\begin{array}{*{20}{c}}x\\{\textit{z}}\\y\end{array}\right); \;{ F}\left({ w}\right)=\left(\begin{array}{*{20}{c}}{-{{{ A}}}^{{\rm T}}y}\\y\\{{ A}x - {\textit{z}}}\end{array}\right);\; \theta \left( { u}\right)=$ $ f\left(x\right)+g\left({\textit{z}}\right)$ F是单调的。定义Ω*VI $\varOmega ,{ F},\theta $ )的解集,在问题(1)有解的假设下,Ω*非空。

本文在对称ADMM算法的x子问题中加入了半近邻项,提出了改进的对称ADMM算法。下面详述该算法。

步骤1 给定半正定矩阵G,初始点 $\left({{x}^{0},z^{0},{y}^{0}}\right)\in $ $X\times Z\times {\mathbb R}^{m}, \;{\mathrm{\alpha }}\in \left(\mathrm{0,1}\right)$ $\gamma > 0$ ,置k= 0。

步骤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. {\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 如果满足终止条件,停止迭代返回运行结果;否则, $k = k + 1$ ,返回步骤2。

特别地,当G= 0时,算法为对称ADMM算法。

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)

引理1 $\alpha \in \left( {0,1} \right)$ G是半正定矩阵时,式(6)定义的矩阵H是半正定矩阵。

证明

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

因为G是半正定矩阵,所以等号右侧的第一部分是半正定矩阵,只需证明第二部分也是半正定即可。令

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

又因为 $\alpha \in \left( {0,1} \right)$ ,矩阵

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

是半正定矩阵,故引理1成立。

引理2假设HMQ是式(6)定义的矩阵,则有

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

证明利用矩阵HQM的定义,通过简单计算可得

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

由式(6)和式(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)

因为 $\alpha \in \left( {0,1} \right)$ G是半正定矩阵,所以式(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 $

因此D是半正定矩阵。所以

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

根据式(8)和式(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)

由式(12)和M的定义可得

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

引理3 $ \left\{{ w}^{k}\right\}$ 是由改进的对称ADMM产生的序列,Q为式(6)定义的矩阵。那么对于 $ \forall { w}\in \varOmega $ ,有

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

证明 通过推导x极小化问题的最优性条件可得

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

因为 ${\tilde {y}}^{k}={y}^{k}-\gamma \left({{A}}{\tilde {x}}^{k}-{{\textit{z}}}^{k}\right)$ ,上式可被写为

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

同理,根据z极小化问题的最优性条件,可得

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

由式(12)的定义可知

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

所以,式(17)变为

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

由式(12)可得

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

结合式(16)、式(19)和式(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) $

所以式(21)可被写成

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

故引理3得证。

引理4 $ \left\{{ w}^{k}\right\}$ 是由改进的对称ADMM算法产生的序列, $\left\{{\tilde { w}}^{k}\right\}$ 是式(12)定义的序列,HMQ是式(6)定义的矩阵。那么对于 $ \forall { w}\in \varOmega $ ,有

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

证明对于同一空间中的向量abcd和具有适当维度的矩阵H,满足

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

因为 $ { w}^{k+1}={ w}^{k}-{{M}}({ w}^{k}-{\tilde { w}}^{k})$ ,所以有

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

将式(24)代入式(23),式(22)成立。故引理4得证。

定理1假设 $ \left\{{ w}^{k}\right\}$ $ \left\{{\tilde { w}}^{k}\right\}$ 是由改进的对称ADMM算法产生的序列,那么对于 $ \forall { w}\in \varOmega $ ,有

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

证明 根据式(14)和式(22)得

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

因为 $F\left({\text{·}} \right)$ 是单调的,则

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

将式(26)和式(27)相加,可得式(25)。

定理2假设 $ \left\{{ w}^{k}\right\}$ $ \left\{{\tilde { w}}^{k}\right\}$ 是由改进的对称ADMM算法产生的序列, $\alpha \in \left( {0,1} \right)$ , $\forall { w}^{*}\in {\varOmega }^{*}$ ,则有

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

证明 ${\mathrm{w}}={ w}^{*}$ ,式(25)变为

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

因为 $ { w}^{*}\in {\varOmega }^{*}$ ,所以

$ {\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 数值计算

将改进的对称ADMM算法应用于LASSO问题[6-9]

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

式中, ${{P}}\in {\mathbb R}^{m\times n}$ 特别地,它可以写成式(1)的形式[10-12]

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

在进行数值计算时,选取不同维数的矩阵P并且规范化P中所有列。取 $ a\in {\mathbb R}^{n}$ 为随机变量,ε是噪音,那么 $ b={ P}a+\varepsilon $ ,正则化参数 $ u= $ $0.01\left\|{ P}^{\rm T}b\right\|$ 。取n= 4 000,α= 0.9, $\gamma=1$ ${{G}}=\dfrac{3}{2}\gamma { I}_{n}-$ $\gamma {{{A}}}^{{\rm{T}}}{{A}}$ 。此外,xyz的初始值皆为零。

算法的收敛准则参照文献[4]。定义初始残差 ${p}^{k}=\gamma \left\| {{z}^{k}-{z}^{k+1}} \right\|$ 和对偶残差 $ {d}^{k}=\dfrac{1}{\gamma }\left\| {{u}^{k}-{u}^{k+1}} \right\|$ 。对于改进的对称ADMM算法,其收敛准则为

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

式中,δ=10−4

表1为应用对称ADMM算法和改进的对称ADMM算法解决该问题的结果,其中m表示矩阵P的维数,k表示迭代次数。从表1可以看出,当矩阵P的维数较低时,改进的对称ADMM算法明显快于对称ADMM算法;而当P的维数较高时,对比CPU时间发现,改进的对称ADMM算法的数值表现优势更大。


表 1 LASSO问题数值结果 Table 1 Numerical results for LASSO

为了进一步观察两种算法的收敛性,比较了初始残差和对偶残差随迭代次数的变化情况。从图1图2可以直观地发现,尽管在算法迭代的某些阶段,对称ADMM算法的初始残差、对偶残差减小得更快,但是本文提出的算法先于对称ADMM算法达到收敛条件,因此改进的对称ADMM算法更高效。


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

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

提出了一种求解目标函数具有可分离结构的凸优化问题的改进的对称ADMM算法,并证明了其收敛性。该方法的基本思想是在x子问题中引入一个半近邻项,从而达到加快其收敛速度的目的。数值实验表明,该算法在求解高维的LASSO问题时相对于对称ADMM算法具有明显的优势,但是如何选择最优的 $ \alpha $ 还需要进一步研究。

参考文献
[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.