和Marroco^[12], Gabay和Mercier ^[11]提出了求解两分块凸优化问题的ADMM算法, 其收敛性发展的相对成熟, 参见文献[7,23]. 在一定的假设条件下, 文献[8,10,17]分析了具有三块可分离结构的凸优化问题的ADMM算法收敛性. 近年来, 对于非凸领域的研究成为了主要研究方向. 非凸情况下的ADMM算法收敛性是很难得到的, 困难性体现在该算法产生的迭代序列的Fejer单调性在非凸的情况下是不能成立的. 为了解决此类问题, Wang等人^[20]针对两块可分离非凸优化问题

其中, $A \in {\Bbb R^{m \times {n_1}}},~B \in {\Bbb R^{m \times {n_2}}},~f:{\Bbb R^{{n_1}}} \to \Bbb R\bigcup {\left\{ { + \infty } \right\}},~g: {\Bbb R^{{n_2}}} \to \Bbb R,~X \subset {\Bbb R^{{n_1}}}, ~Y \subset {\Bbb R^{{n_2}}},$$c \in \Bbb R$. 提出Bregman ADMM算法(简记为BADMM算法)

其中${L_\beta }(x,y,\lambda ) = f(x) + g(y) + \langle \lambda,Ax + By - c \rangle + \frac{\beta }{2}\left\| {Ax + By - c} \right\|_2^2$ 为增广拉格朗日函数, $\lambda $ 为乘子, $\beta > 0$ 为惩罚参数, ${\Delta _\psi },{\Delta _\phi }$ 分别是函数 $\psi,\phi $ 导出的Bregman散度. 文献[7]中不仅提出只要$\beta $足够大, 则算法(1.2)就能收敛到平稳解集合, 而且构造出的效益函数在满足K-L性质后, 该算法(1.2)产生的序列收敛到增广拉格朗日函数的稳定点. 这是一种解决非凸问题的有效方法, 并取得了良好的发展^{[6-7,13⇓-15,19,24]}.

下面我们讨论的是三块不可分结构的非凸优化问题

其中 ${A_i} \in {\Bbb R^{m \times {n_i}}},~B \in {\Bbb R^{m \times n}},~X \subset {\Bbb R^{{n_i}}},~Y \subset {\Bbb R^n},~c \in {\Bbb R^m},~{f_i}:{\Bbb R^{{n_i}}} \to \Bbb R\bigcup {\left\{ { + \infty } \right\}}$$ (i = 1,2)$ 是非凸可微函数且 $g: {\Bbb R^{{n_1} + {n_2} + n}} \to \Bbb R$ 是可微函数. 问题(1.3)的增广拉格朗日函数为

Wang等^[21]提出用Bregman散度代替增广拉格朗日函数中的二次惩罚项得到广义BADMM算法. 受文献[21]的启发, 对于问题(1.3)我们得到新的增广拉格朗日函数

Feng等^[10]引入了一种将算法中子问题的二次惩罚项进行线性化的技术, 并且文献[21]中举例说明对算法中不同部分进行线性化以后依然可以得到算法的收敛性. 不精确ADMM^[3] 和广义ADMM^[9]通过线性化函数以及增加其他二次项来解决算法收敛性问题. Chao等^[6]针对三块不可分的非凸优化问题提出一种线性化BADMM算法.

本文针对问题(1.3)提出一种具有线性化技术的广义BADMM算法(L-G-BADMM)

其中${\Delta_\psi },~{\Delta_{{\varphi _1}}},~{\Delta_{{\varphi _2}}},~{\Delta_\phi }$分别是函数$\psi,{\varphi _1},{\varphi _2},\phi $ 导出的Bregman散度. 文献[6]提出的L-BADMM算法采用的是二范数作为二次惩罚项, 而本文算法中的二次惩罚项则使用的是Bregman散度. 由定义2.4可知二范数是Bregman散度的特例, 因此这对于经典的ADMM 算法来说具有更广泛的意义. 目前, 在目标函数非凸情况下, 还没有二次惩罚项不是二范数的理论证明, 这也是本文将要解决的问题.

定义2.1^[20]$f:{\Bbb R^n} \to \Bbb R\bigcup{\left\{ + \infty \right\} }$ 为下半连续函数.

(1)给定 $x \in {\rm dom}f$, $f$ 在 $x$ 处的 Frechet 次微分记做 $\hat \partial f(x)$, 对所有的 $\mu \in {\Bbb R^n}$ 都满足

(2)如果

则称 $f$ 在 $x$ 处的极限次微分或者简单次微分, 记做 $\partial f(x)$.

(3)如果 ${x_0}$称为函数$f$的稳定点或者临界点, 则 $0 \in \partial {f(x_0)}$.

定义2.2^[20] (鞍点定理) ${w^ * } = ({x^ * }, {y^ * }, {\lambda ^ * })$ 是拉格朗日函数 $L$ 的稳定点, 则满足

定义2.3^[2] 设函数$f: {\Bbb R^n} \to \Bbb R\cup \left\{ { + \infty } \right\}$ 是真且下半连续, 如果存在 $\eta > 0, \delta > 0, \varphi \in {A_n}$, 使得对所有

我们有

则称函数 $f$ 在 ${x_0}$ 处满足Kurdyka-Łojasiewicz性质(K-L 性质). 其中, $\varphi $ 表示 $\left[ {0,\eta } \right] \to {\Bbb R^ + }$上的函数, ${\rm dist}(0,\partial f(x)) = \inf \left\{ {\left\| {{x_0} - y} \right\|:y \in \partial f(x)} \right\}$ 且满足

(a) $\varphi $在$\left[ {0,\eta } \right]$ 上连续,

(b) $\varphi $ 在 $\left[ {0,\eta } \right]$ 上光滑凹,

(c) $\varphi (0) = 0, \varphi '(x) > 0,\forall x \in (0,\eta )$.

引理2.1^[6] (一致K-L性质) 设 $\Omega$ 是紧集, $f:{\Bbb R^n} \to \Bbb R\cup \left\{ { + \infty } \right\}$是真且下半连续函数, 若函数$f$ 在集合上取常数$f({x_0})$, 并在$\Omega $ 中任意一点满足K-L性质, 则存在$\eta > 0, \delta > 0, \varphi \in {A_n}$, 使得对所有

我们有

定义2.4^[4] 对于一个凸可微的函数$\Phi $, 定义Bregman散度如下

特别地, 如果$\Phi (x) = \left\| x \right\|_Q^2 = {x^{\rm T}}Qx$, 则有${\Delta _\Phi }(x,y) = \left\| {x - y} \right\|_Q^2$, 其中$Q$是对称半正定矩阵.

定义2.5 (强凸性) 设$f:{\Bbb R^n} \to \Bbb R\cup \left\{ { + \infty } \right\}$是真函数, 如果存在$\delta > 0$, 使得

引理2.2^[1]${\Delta _\phi }$是可微的凸函数, 则有

(i) (非负性) ${\Delta _\Phi }(x,y) \ge 0,{\Delta _\Phi }(x,x) = 0$.

(ii) (凸性) ${\Delta _\Phi }(x,y)$对$x$具有凸性.

(iii) (强凸性) $\Phi $如果是一个强凸函数, 强凸系数为$\delta $, 则${\Delta _\Phi }(x,y) \ge \frac{\delta }{2}{\left\| {x - y} \right\|^2}$.

引理2.3^[6] (下降性引理) 设$g:{\Bbb R^n} \to \Bbb R$ 是利普西茨可微函数, 其利普西茨系数为${l_g}$, 则对任意$x,y \in {\Bbb R^n}$都有

假设1 (i) $\nabla g$,$\nabla {f_1},\nabla {f_2}$关于${l_g}$,${l_{{f_1}}},{l_{{f_2}}}$是利普希茨连续;

(ii) 存在$\mu > 0$, 使得${B^{\rm T}}B \succ \frac{1}{\mu }I$;

(iii) ${\nabla _\psi }, {\nabla _{{\varphi _1}}},{\nabla _{{\varphi _2}}},{\nabla _\phi }$满足利普希茨连续, 且利普希茨系数分别为${l_\psi },{l_{{\varphi _1}}},{l_{{\varphi _2}}},{l_\phi };$

(iv) $\psi, {\varphi _1}, {\varphi _2},\phi $是强凸函数, 所对应的强凸系数分别为${\delta _\psi }, {\delta _{{\varphi _1}}},{ \delta _{{\varphi _2}}}, {\delta _\phi }$, 且${\delta _{{\varphi _1}}},{\delta _{{\varphi _2}}},{\delta _\phi }$均大于${l_g}$;

(v) ${A_1},{A_2}$均为正交矩阵, 即${A_1}^{\rm T}{A_1} = I,{A_2}^{\rm T}{A_2} = I;$

(vi)

引理3.1$\left\{ {{w^k} = (x_1^k,x_2^k,{y^k},{\lambda ^k})} \right\}$是L-G-BADMM算法产生的点列, 若假设1(ii)成立, 对任意的$k \in N$, 我们有

证 由假设1 (ii), 得到

求(1.4)式中子问题最优性条件并移项可得

即

得出

最后一步是由${\nabla _g},{\nabla _{_\phi }},{\nabla _\psi }$ 的利普西茨连续性得到的. 下面我们将上式代入(3.2)式可得

引理结论显然可得.证毕.

注3.1 由范数的三角不等式性$\left\| {A + B} \right\| \le \left\| A \right\| + \left\| B \right\|$, 再将其左右两边平方可得

又因为基本不等式$2\left\| A \right\|\left\| B \right\| \le {\left\| A \right\|^2} + {\left\| B \right\|^2}$, 所以综上可得

设$\left\{ {{w^k} = {{(x_1^k,x_2^k,{y^k},{\lambda ^k})}^{\rm T}}} \right\}$是L-G-BADMM算法产生的点列, 为了证明${\hat L_\beta }({w^k})$ 的单调性, 下面构造函数$\hat L({\hat w^k})$

其中,

下面证明序列$ {\left\{ {\hat L({{\hat w}^k})} \right\}_{k \in N}}$的单调性.

引理3.2 设$\left\{ {{w^k} = (x_1^k,x_2^k,{y^k},{\lambda ^k})} \right\}$是L-G-BADMM算法产生的序列且 $\{ {u^k} = (x_1^k,x_2^k,$${y^k}) \}$是有界序列, 序列对任意的$k \in N$, 下面有

其中

证 显然(1.4)式中${x_1}$子问题变换可得

我们可以由假设1(iv)和引理2.2(iii)得到${\Delta _{{\varphi _1}}}(x_1^{k + 1},x_1^k) \ge \frac{{{\delta _{{\varphi _1}}}}}{2}{\left\| {x_1^{k + 1} - x_1^k} \right\|^2}$, 于是有

同理(1.4)式中${x_2}$和${y}$子问题类似可以得到上式的式子, 我们将其相加变换可得

由(3.11)式和引理2.3可得

又由(1.4)式中乘子迭代可得

将(3.12)式与(3.13)式相加变化可得

将(3.1)式代入(3.14)式, 可得

引理由此得证.

注3.2经过上述证明我们可以得到辅助函数

引理3.3 设$\left\{ {{w^k} = (x_1^k,x_2^k,{y^k},{\lambda ^k})} \right\}$是L-G-BADMM算法产生的序列且 $\big\{ {u^k} = (x_1^k,x_2^k,$${y^k}) \big\}$是有界序列, 则

那么$\left\| {{w^{k + 1}} - {w^k}} \right\| \to 0,k \to \infty $ 成立.

证 首先, 我们需要证明序列$\left\{ {{{\hat w}^k}} \right\}$有界. 由(3.3)式可得

由假设1 (ii)和(3.17)式可知

因此, 由$\left\{ {{u^k}} \right\}$有界可知$\left\{ {{\lambda ^k}} \right\}$有界, 那么我们得到序列$\left\{ {{w^k}} \right\}$与$\left\{ {{{\hat w}^k}} \right\}$有界.

其次, 我们将证明${\left\{ {\hat L({{\hat w}^k})} \right\}_{k \in N}}$序列收敛, 由$\left\{ {{{\hat w}^k}} \right\}$有界可得$\left\{ {{{\hat w}^k}} \right\}$有收敛子列$\left\{ {{{\hat w}^{{k_j}}}} \right\}$, 设其极限点为${\hat w^*}$. 又由函数$\hat L( \cdot )$的下半连续性可得$\mathop {\lim }\limits_{j \to \infty } \inf \hat L({\hat w^{{k_j}}}) \ge \hat L({\hat w^*})$, 则$\hat L({\hat w^{{k_j}}})$ 有下界, 故$\hat L({\hat w^{{k_j}}})$ 单调递减有下界, 则$\hat L({\hat w^{{k_j}}})$收敛, 从而${\left\{ {\hat L({{\hat w}^k})} \right\}_{k \in N}}$ 收敛. 最后, 对(3.7)式两边$k$从1到$t$分别求和, 得到

由${\sigma _4} > 0$, 以及$t$的任意性可知

结合(3.1)式可得

那么我们有

则显然$\left\| {{w^{k + 1}} - {w^k}} \right\| \to 0,k \to \infty $成立. 引理由此得证.

引理3.4 设$\left\{ {{w^k} = (x_1^k,x_2^k,{y^k},{\lambda ^k})} \right\}$是L-G-BADMM算法产生的有界序列, 存在$\gamma > 0$, 对于任意$k \in N$, 使得

证 通过上述对$\hat L\left( {\hat w} \right)$的定义, 我们可以得到

由L-G-BADMM算法中子问题的最优性条件整理可得

下面我们将(3.21)式代入(3.20)式, 化简可得

因此$(\rho _1^k,\rho _2^k,\rho _3^k,\rho _4^k,\rho _5^k,\rho _6^k,\rho _7^k) \in \partial \hat L({\hat w^k})$, 则

因为$\left\{ {{u^k}} \right\}$有界, 所以

其中${\gamma _1} > 0$. 又因为${\nabla _\psi },{\nabla _{{\varphi _1}}},{\nabla _{{\varphi _2}}},{\nabla _\phi },{\nabla _g}$满足利普希茨连续以及引理3.1可知, 存在$\gamma > 0$, 使得(3.19)式成立. 证毕.

定理3.1 设$\left\{ {{w^k} = (x_1^k,x_2^k,{y^k},{\lambda ^k})} \right\}$是L-G-BADMM算法产生的有界序列, 以及$S({\hat w^0})$ 是序列$\left\{ {{{\hat w}^k}} \right\}$的全体极限点集,

1) 故$\mathop {\lim }\limits_{k \to \infty } d({\hat w^k},S({\hat w^0})) = 0$;

2) 若$(x_1^*,x_2^*,{y^*},{\lambda ^*},\hat x_1^*,x_2^*,{y^*}) \in S({\hat w^0})$, 则${\hat w^*}$是$\hat L( \cdot )$的稳定点;

3) 则$\hat L( \cdot )$在集合$S({\hat w^0})$上取值为常数且$\mathop {\inf }\limits_{k \in N} \hat L({\hat w^k}) = \mathop {\lim }\limits_{k \to \infty } \hat L({\hat w^k})$.

证1) 由定义可得$\mathop {\lim }\limits_{k \to \infty } d({\hat w^k},S({\hat w^0})) = 0.$

2) 设${\hat w^*} \in S({\hat w^0})$, 则存在$\left\{ {{{\hat w}^k}} \right\}$的收敛子列$\left\{ {{{\hat w}^{{k_j}}}} \right\}$收敛于$\left\{ {{{\hat w}^*}} \right\}$. 由$x_1^{k + 1}$的最优性条件可得

由$\mathop {\lim }\limits_{j \to \infty } {\hat w^{{k_j}}} = {\hat w^*}$, 可得

又由$\hat L( \cdot )$的下半连续性, 可知

结合(3.25)式和(3.26)式可得

又由${\nabla _g}$的连续性和$\partial f$的闭性并对(3.21)式中序列$\left\{ {{{\hat w}^{{k_j} + 1}}} \right\}$取极限, 则有

故${\hat w^*}$是$\hat L( \cdot )$的稳定点.

3) 结合(3.25)式和${\left\{ {\hat L({{\hat w}^k})} \right\}_{k \in N}}$单调递减可得$\mathop {\lim }\limits_{k \to \infty } \hat L({\hat w^k}) = \hat L({\hat w^*})$, 并有函数$\hat L( \cdot )$在非空紧集$S({\hat w^0})$上是常数, 以及$\mathop {\inf }\limits_{k \in N} \hat L({\hat w^k}) = \mathop {\lim }\limits_{k \to \infty } \hat L({\hat w^k})$成立. 证毕.

下面证明L-G-BADMM算法的收敛性.

定理3.2 设$\left\{ {{w^k} = (x_1^k,x_2^k,{y^k},{\lambda ^k})} \right\}$是L-G-BADMM算法产生的有界序列, 假设1成立且$\hat L\left( {\hat w} \right)$ 满足K-L性质, 则

(1) $\sum\limits_{k = 0}^{ + \infty } {{{\left\| {{w^{k + 1}} - {w^k}} \right\|}^2}} < + \infty $;

(2) 序列$\left\{ {{w^k}} \right\}$收敛到本文问题(1.3)的稳定点.

证 由定理3.1显然可得, 对于任意${\hat w^*} \in S({\hat w^0})$则有$\mathop {\lim }\limits_{k \to \infty } \hat L({\hat w^{k + 1}}) = \hat L({\hat w^*})$. 下面我们分两种情况证明定理3.2(1).

1a) 若存在整数${k_0}$, 有$\hat L({\hat w^{{k_0}}}) = \hat L({\hat w^*})$, 又由引理3.4可得, 对任意的$k > {k_0}$, 使得

成立, 故对于任意的$k > {k_0}$, 则$x_1^{k + 1} = x_1^k,x_2^{k + 1} = x_2^k,{y^{k + 1}} = {y^k}$. 那么对于任意的$k > {k_0} + 1$, 我们有${\hat w^{k + 1}} = {\hat w^k}$, 故$\sum\limits_{k = 0}^{ + \infty } {{{\left\| {{w^{k + 1}} - {w^k}} \right\|}^2}} < + \infty. $

1b) 对任意${k}$均有$\hat L({\hat w^{{k}}}) = \hat L({\hat w^*})$, 因为$\mathop {\lim }\limits_{k \to \infty } d({\hat w^k},S({\hat w^0})) = 0$, 所以对于任意给定的$\varepsilon > 0$, 存在${k_1} > 0$, 当$k > {k_1}$时, 有$d({\hat w^k},S({\hat w^0})) < \varepsilon $. 又因为$\mathop {\lim }\limits_{k \to \infty } \hat L({\hat w^k}) = \hat L({\hat w^*})$, 所以对任意给定$\eta > 0$, 存在${k_2} > 0$, 且$k > {k_2}$时, 有$\hat L({\hat w^k}) < L({\hat w^*}) + \eta $. 那么当$k > \tilde k = \max \left\{ {{k_1},{k_2}} \right\}$, 有$d({\hat w^k},S({\hat w^0})) < \varepsilon,L({\hat w^*}) < \hat L({\hat w^k}) < L({\hat w^*}) + \eta $. 因为$S({\hat w^0})$为紧集且非空时, 函数$\hat L( \cdot )$在集合$S({\hat w^0})$上为常数, 所以由一致K-L性质, 对任意$k > \tilde k$, 有$\varphi '(\hat L({\hat w^k}) - L({\hat w^*}))d(0,\partial L({\hat w^*})) \ge 1,$$\forall k > \tilde k$, 再由引理3.4, 则有

由函数$\varphi $的凹性, 则有

结合引理3.2, 则有

其中${\Delta _{k,k + 1}} = \varphi (\hat L({\hat w^k}) - \hat L({\hat w^*})) - \varphi (\hat L({\hat w^{k + 1}}) - \hat L({\hat w^*}))$, 上式等价于

又由${\left( {a + b + c} \right)^2} \le 3\left( {{a^2} + {b^2} + {c^2}} \right)$, 可得

结合(3.32)式和基本不等式$2\sqrt {ab} \le a + b(a,b > 0)$可以得到上述结果. 对上式中, 取$k = \tilde k + 1,\cdots,m$, 并求和可得

由于$\varphi (\hat L({\hat w^{m + 1}}) - L({\hat w^*})) > 0$, 左右移项再令$m \to \infty $, 则有

因此, 我们有

结合引理3.1我们有

又因为$\tilde k$的任意性可得

(2) 根据上述证明以及$\left\{ {{w^k}} \right\}$是柯西序列, 可得$\left\{ {{w^k}} \right\}$收敛, 又由定理3.1(2) 可知该定理显然成立. 定理3.2得证.