-
本文考虑解决以下的一类线性约束凸优化问题
其中：θ1(x)：
$ {{\mathbb{R}}^{{{\mathit{n}}_{\rm{1}}}}}\to \mathbb{R}$ ，θ2(y)：$ {{\mathbb{R}}^{{{\mathit{n}}_{\rm{2}}}}}\to \mathbb{R}$ 是凸函数(但不一定光滑)；矩阵$ \mathit{\boldsymbol{A}}\in {{\mathbb{R}}^{\mathit{m}\times {{\mathit{n}}_{\rm{1}}}}}, \mathit{\boldsymbol{B}}\in {{\mathbb{R}}^{\mathit{m}\times {{\mathit{n}}_{2}}}}$ ；向量$ \mathit{\boldsymbol{b}}\in {{\mathbb{R}}^{\mathit{m}}};\mathscr{X}\subset {{\mathbb{R}}^{{{\mathit{n}}_{\rm{1}}}}}$ 与$ \mathscr{Y}\subset {{\mathbb{R}}^{{{\mathit{n}}_{\rm{2}}}}}$ 是给定的闭凸集.在本文中，假设问题(1)的解集是非空的.将问题(1)的增广Lagrange函数定义为其中：λ∈
$ {{\mathbb{R}}^{\mathit{m}}}$ 为Lagrange乘子，β＞0为罚因子.经典的乘子交替方向法(ADMM)主要是为了解决带约束的凸优化问题，最先在20世纪70年代中期由文献[1-2]提出. ADMM被广泛地应用于各个领域，如机器学习、图像处理、统计学习、无线网络等方面.原始的ADMM形式如下：
运行ADMM(2)时，为了能够求得唯一的点(xk+1，yk+1)，通常通过增加一个平方临近项来正则化(2)式的子问题.不失一般性，可以只讨论正则化ADMM(2)第二步子问题的情形.文献[3-4]将算法进一步改进成下面的形式：
其中
$ \mathit{\boldsymbol{D}}\in {{\mathbb{R}}^{{{\mathit{n}}_{2}}\times {{\mathit{n}}_{2}}}}$ 为正定矩阵.通常，在很多文献中都会要求矩阵D必须要满足正定性，在(3)式中，$ \frac{1}{2}$ ‖y-yk‖D2就是添加的平方临近项.另外，也可以考虑对ADMM(2)的第一、二步都进行正则化的情形，可以参考文献[5].进一步，文献[6]提出，PD-ADMM(3)中的矩阵D可以不满足正定性，若取D=τγIn2-βBTB，其中γ＞β‖BTB‖，τ∈(0，1)，显然D此时不一定正定.此时，平方正则项$ \frac{1}{2}$ ‖y-yk‖D2在目标函数中所占比重减少，y的迭代步长变大.特别地，文献[6]说明了当取τ=0. 8时为最佳值，并且证明了τ=0. 8时算法的收敛性及其在遍历意义下的收敛速率.另一方面，文献[7]对原始的增广拉格朗日算法(ALM)进行了一些改进，扩大了生成Lagrange乘子λ的步长，从而加快收敛速度.与文献[6]类似，文献[7]中还提出了平方临近项中的矩阵D可以为非正定的矩阵，即把原始的ALM改进为其中：D0=D-(1-τ)βATA，τ∈(0，1)，D∈
$ {{\mathbb{R}}^{\mathit{l}}}$ 是任意给定的正定矩阵；Lagrange函数L(x，λ)=θ(x)-λT(Ax-b).文献[1]中确定当系数τ和γ满足数量关系$ \mathit{\tau >}\frac{2+\mathit{\gamma }}{4}$ 时，算法PIDP-ALM(4)仍然保持收敛性.受文献[6-7]的启发，本文考虑将文献[6]中带有非正定正则项的ADMM算法进行改进，引入松弛变量γ，对生成Lagrange乘子λ的子问题步长进行调整.本文将讨论如下算法1：
其中：D0=D-(1-τ)βBTB，D∈
$ {{\mathbb{R}}^{\mathit{l}}}$ 是任意给定的正定矩阵，$ \mathit{\tau }\in \left[\frac{1\rm{+}\mathit{\beta }}{2\mathit{\beta }}, 1 \right)$ ；松弛变量$ \mathit{\gamma }\in \left( 0, \frac{2}{1\rm{+}\mathit{\beta }} \right]$ .另外在本文中设罚参数β＞1且为一固定值.相对于文献[6]，本文中对生成Lagrange乘子λ的子问题引入松弛变量γ，使得对偶变量的迭代步长范围变大，更具有一般性，在理论上有更好的计算性能，并且非正定矩阵D0中的系数τ，松弛变量γ与罚参数β之间产生了相互约束的作用.
全文HTML
-
本节将回顾一些本文所涉及的主要理论基础知识.
在
$ \mathscr{X}\times \mathscr{Y}\times {{\mathbb{R}}^{\mathit{m}}}$ 上定义问题(1)的Lagrange函数其中λ∈
$ {{\mathbb{R}}^{\mathit{m}}}$ 为Lagrange乘子.点((x*，y*)，λ*)若满足则被称为Lagrange函数的鞍点.鞍点问题等价于下面的变分不等式组：
如果记
以及
问题(6)可以写成变分不等式
将问题(8)的解集记作Ω*.定义在(7)式中的算子F是一个带有斜对称矩阵的仿射单调算子，并且对于任意的ω，ω∈Ω有
引理1[6] 设
$ \mathscr{X}\in {{\mathbb{R}}^{\mathit{n}}}$ 是一个闭凸集合，θ(x)和f(x)是定义在$ \mathscr{X}$ 上的凸函数.若函数f是可微的，且问题min{θ(x)+f(x)|x∈$ \mathscr{X}$ }的解集是非空的.则有当且仅当存在x*∈
$ \mathscr{X}$ ，θ(x)-θ(x*)+(x-x*)T▽f(x*)≥0，∀x∈$ \mathscr{X}$ .
-
本节将用预估校正方法解释算法1，这样的形式有助于在后文中对算法的收敛速率进行分析.首先定义
由引理1知算法1的子问题可以分别写作
和
对于给定的(yk，λk)算法1生成了(xk+1，yk+1)，分别定义
$ {{{\mathit{\boldsymbol{\tilde{x}}}}}^{\mathit{k}}}={{{\mathit{\boldsymbol{\tilde{x}}}}}^{\mathit{k}\rm{+1}}}, {{{\mathit{\boldsymbol{\tilde{y}}}}}^{\mathit{k}}}={{{\mathit{\boldsymbol{\tilde{y}}}}}^{\mathit{k}\rm{+1}}}$ ，以及辅助变量因此不等式(9)可以写作
另外，由λk+1，
$ {{{\mathit{\boldsymbol{\tilde{ \lambda} \rm{ }}}}}^{\mathit{k}}}$ 和yk+1的定义，有则不等式(10)可以写为
由
$ {{{\mathit{\boldsymbol{\tilde{ \lambda} \rm{ }}}}}^{\mathit{k}}}$ 的定义，有联立(12)-(14)式，可以得到：
由(7)式中的定义，(15)式等价于变分不等式
其中
另一方面，由λk+1，
$ {{{\mathit{\boldsymbol{\tilde{ \lambda} \rm{ }}}}}^{\mathit{k}}}$ 和yk+1的定义，有因此，有
其中
由上面的内容可知，算法1从理论上可以看作是分为两个阶段的.第一步由变分不等式(16)生成一个预测点(
$ {{{\mathit{\boldsymbol{\tilde{y}}}}}^{\mathit{k}}}\rm{, }{{{\mathit{\boldsymbol{\tilde{ \lambda} \rm{ }}}}}^{\mathit{k}}}$ )；第二步再通过(18)式对($ {{{\mathit{\boldsymbol{\tilde{y}}}}}^{\mathit{k}}}\rm{, }{{{\mathit{\boldsymbol{\tilde{ \lambda} \rm{ }}}}}^{\mathit{k}}}$ )进行校正，生成新的迭代点(yk+1，λk+1).
-
本节将分析算法1在遍历意义下的收敛速率.首先给出以下的几个引理：
引理2 设定义在(1)式中的矩阵B是列满秩的，罚参数β＞1.定义矩阵
则
另外，当
$ \mathit{\tau }\in \left[\frac{1\rm{+}\mathit{\beta }}{2\mathit{\beta }}, 1 \right)\mathit{, }\ \mathit{\gamma }\in \left( 0, \frac{2}{1\rm{+}\mathit{\beta }} \right]$ 时，有H$ \succ $ 0.证 由(17)式和(19)式，有
等式(20)立即证得.
另一方面，
并且D为正定矩阵.因此，若矩阵
$ \left( \begin{align} & \mathit{\tau \beta }{{\mathit{\boldsymbol{B}}}^{\rm{T}}}\mathit{\boldsymbol{B}}\ \ \mathit{\boldsymbol{-}}{{\mathit{\boldsymbol{B}}}^{\rm{T}}} \\ & -\mathit{\boldsymbol{B}}\ \ \ \ \ \ \ \frac{1}{\mathit{\lambda \beta }}{{\mathit{\boldsymbol{I}}}_{\mathit{m}}} \\ \end{align} \right)$ 为正定矩阵，则H一定正定.矩阵由假设矩阵B是列满秩的，因此只需
即
由于
$ \mathit{\gamma }\in \left( 0, \frac{2}{1\rm{+}\mathit{\beta }} \right]$ ，只需τ＞γ.对于任意固定的罚参数β＞1，当$ \mathit{\tau }\in \left[\frac{1\rm{+}\mathit{\beta }}{2\mathit{\beta }}, 1 \right)\mathit{, }\ \mathit{\gamma }\in \left( 0, \frac{2}{1\rm{+}\mathit{\beta }} \right]$ 时，一定有τ＞γ，因此有H$ \succ $ 0.定义对称矩阵G=QT+Q-MTHM，因为HM=Q，MTHM=MTQ，有
所以
引理3 设(ωk)为算法1所生成的序列
$ {{{\mathit{\boldsymbol{\tilde{ \omega} \rm{ }}}}}^{\mathit{k}}}$ 由(11)式定义，则有$ {{{\mathit{\boldsymbol{\tilde{ \omega} \rm{ }}}}}^{\mathit{k}}}$ ∈Ω以及其中G在(21)式中被定义.
由于证明过程与文献[6]中的引理2类似，故而省略.
如果矩阵G是正定的，则由(22)式很容易推导出算法1的收敛性以及在遍历意义下的收敛速率.本文需要处理的难点在于定义在(21)式中的矩阵G不一定是正定的，为了解决这个问题，考虑寻找(
$ {{\mathit{\boldsymbol{v}}}^{\mathit{k}}}-{{{\mathit{\boldsymbol{\tilde{v}}}}}^{\mathit{k}}}$ )TG($ {{\mathit{\boldsymbol{v}}}^{\mathit{k}}}-{{{\mathit{\boldsymbol{\tilde{v}}}}}^{\mathit{k}}}$ )的一个下界.引理4 设(ωk)为算法1所生成的序列，
$ {{{\mathit{\boldsymbol{\tilde{ \omega} \rm{ }}}}}^{\mathit{k}}}$ 由(11)式定义，则有证 由(21)式G的定义和
$ {{{\mathit{\boldsymbol{\tilde{y}}}}}^{\mathit{k}}}$ =yk+1，有而从
有
所以
和
将(25)式和(26)式代入(24)式中，有
接下来处理(27)式右边的交叉项，由Cauchy-Schwarz不等式以及γ∈(0，1)知
结合(27)式和(28)式，即可得到(23)式.
由引理3和引理4可以得到下面的引理：
引理5 设(ωk)为算法1所生成的序列，
$ {{{\mathit{\boldsymbol{\tilde{ \omega} \rm{ }}}}}^{\mathit{k}}}$ 由(11)式定义，罚参数β＞1，则对任意的$ \mathit{\tau }\in \left[\frac{1\rm{+}\mathit{\beta }}{2\mathit{\beta }}, 1 \right)\mathit{, }\ \mathit{\gamma }\in \left( 0, \frac{2}{1\rm{+}\mathit{\beta }} \right]$ 有证 (29)式可直接由(22)式和(23)式得到.
由(29)式，结合文献[6]中第6部分中关于IP-LADMM的收敛性证明过程，可类似推出算法1的收敛性成立，故此处省略.
下面分析算法1在遍历意义下的收敛速率.
定理1 设(ωk)为算法1所生成的序列，
$ {{{\mathit{\boldsymbol{\tilde{ \omega} \rm{ }}}}}^{\mathit{k}}}$ 定义在(11)式中，罚参数β＞1，则对任意的$ \mathit{\tau }\in \left[\frac{1\rm{+}\mathit{\beta }}{2\mathit{\beta }}, 1 \right)\mathit{, }\ \mathit{\gamma }\in \left( 0, \frac{2}{1\rm{+}\mathit{\beta }} \right]$ 以及迭代次数t有其中
证 由(29)式，且其中φ(vk，vk+1)为非负函数，有
从k=1，2，…，t对(31)式进行求和，有
因为θ(·)是凸函数，并且
所以有
结合(31)式，即可得到(30)式.
下载: