求解凸优化问题的改进对称交替方向乘子法

您所在的位置：网站首页 › admm算法收敛条件 › 求解凸优化问题的改进对称交替方向乘子法

求解凸优化问题的改进对称交替方向乘子法

2024-04-26 13:03| 来源: 网络整理| 查看: 265

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}$ 是给定闭凸集；m，n为矩阵的维数； $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$ 是惩罚参数。与同时求解x，z极小化问题的拉格朗日乘子法不同，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）本身来看，变量x和z是平等的，在设计算法时也希望能够平等对待x和z子问题。因此何炳生等[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假设H，M，Q是式（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}}$ 。

证明利用矩阵H，Q，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得证。再次使用H，Q，M的定义，有

$ {{{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）定义的序列，H，M，Q是式（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)

证明对于同一空间中的向量a，b，c，d和具有适当维度的矩阵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}}$ 。此外，x，y，z的初始值皆为零。

算法的收敛准则参照文献[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(Table 1) 表 1 LASSO问题数值结果 Table 1 Numerical results for LASSO 算法 m k/次 CPU时间/s 对称ADMM 5 000 28 29.67 6 000 32 34.13 8 000 53 59.93 改进的对称ADMM 5 000 11 11.70 6 000 14 13.61 8 000 25 27.91 表 1 LASSO问题数值结果 Table 1 Numerical results for LASSO

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

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

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

【本文地址】

公司简介

联系我们