-
考虑下列无约束优化问题
其中：H是实的无穷维希尔伯特空间;
$f, g:H\to \mathbb{R}\cup \{+\infty \} $ 为闭、真凸函数.对于优化问题(1)，现在已有多种求解方法[1-5].文献[5]第一次提出寻求单调算子和为零的分裂方法(Douglas-Rachford分裂法)求解如下形式的变分包含问题这里
$A, B: H \longrightarrow{ }^2{H} $ 是两个极大单调算子.因为闭的凸函数的次微分是极大单调的[6]，根据一阶最优性条件，求解优化问题(1)等价于寻找$\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} \in H $ 使得$ 0 \in \partial f(\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} ) + \partial g(\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} )$ .近年来，求解优化问题(1)的Douglas-Rachford分裂算法被广泛运用于诸多领域，例如信号处理[7]、压缩感知[8]、图像去噪[9]和平衡问题[10]等方面.对于问题(2)的求解，常常是通过算子A，B相对应的预解式JA，JB进行分离的，算子A预解式JA：
$ H \to H$ 定义为其中Id为恒等算子，若
$ f:H\to \mathbb{R}\cup \{+\infty \}$ 是凸函数，当$A = \partial f $ 时，有JA=proxf，这里proxf为临近算子[11]，其定义如下求解优化问题(1)的Douglas-Rachford分裂算法的迭代公式为
其中α∈(0，2)通常称为松弛因子，Rf称为反射临近算子，其定义为
对于凸优化问题(1)，可以等价转化成变分包含问题(2).文献[5]证明了若A，B都为极大单调算子，则Douglas-Rachford分裂算法产生的序列弱收敛于最优点; 文献[12]证明了若A，B中有一个算子既是强单调的又是Lipschitz连续的，则Douglas-Rachford分裂算法具有收敛性，并给出了其收敛速度为
$ O\left( {\sqrt k } \right)$ ; 文献[13]利用共轭函数和辅助函数的关系证明了当问题(1)中的一个函数同时具有强凸性和光滑性时，Duglas-Rachford分裂算法产生的迭代序列具有线性收敛性; 紧接着，文献[14]给出了3种情形下Douglas-Rachford分裂法具有全局线性收敛率.本文针对问题(1)，若
$f:H\to \mathbb{R}\cup \{+\infty \} $ 为光滑强凸函数时，给出了Douglas-Rachford分裂方法的线性收敛性的新证明，并得到不同于文献[13]的线性收敛结果.
HTML
-
全文结论建立在实的希尔伯特空间(记作H)上.对H中任意两点x，y，其内积用〈x，y〉表示，且由内积诱导出的范数定义为
$ \parallel \mathit{\boldsymbol{x}}\parallel = \sqrt {\langle \mathit{\boldsymbol{x}}, \mathit{\boldsymbol{x}}\rangle } $ .设X是H的一个子集，集合X的子集的全体为2X，F为X上的集值映射$ F: X \longrightarrow 2^{X}$ .函数$f:H\to \mathbb{R}\cup \{+\infty \} $ 在x∈H处的次微分用$\partial f(\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} ) $ 表示，定义$\partial f(\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} ) $ =$ \{\boldsymbol{u} \mid f(\boldsymbol{y}) \geqslant f(\boldsymbol{x})+\langle\boldsymbol{u}, \boldsymbol{y}-\boldsymbol{x}\rangle, \forall \boldsymbol{y} \in H\}$ .定义1 (强单调算子)称算子
$A: H \longrightarrow 2^{H} $ 为σ -强单调的，如果$\exists \sigma > 0, \forall \mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}} \in H, \quad \forall \mathit{\boldsymbol{u}} \in A\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{v}} \in A\mathit{\boldsymbol{y}} $ 都有注1 当σ=0时，称算子A是单调的.
定义2 (强制算子)如果
$ \exists \beta \ge 0, \forall \mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}} \in H$ 都有则称算子
$A: H \longrightarrow 2^{H} $ 为β -强制的.定义3 (Lipschitz连续)如果存在常数L≥0，使得
则称算子A：
$ H \to H$ 为L-Lipschitz连续的.称L为Lipschitz常数.当L=1时，称算子A为非扩张的；当L∈[0，1)时，称算子A为L-压缩的.定义4 如果
$\exists \sigma > 0 $ ，对于$\exists \sigma>0, \text { 对于 } \forall u \in \partial f $ 都有且当f为连续可微函数时有
$\partial f=\{\nabla f(\boldsymbol{x})\} $ ，其中$ \nabla f(\mathit{\boldsymbol{x}})$ 为f在x处的梯度，则称函数$f:H\to \mathbb{R}\cup \{+\infty \} $ 是σ-强凸函数.显然，f是强凸函数等价于
其中
$\forall \mathit{\boldsymbol{u}} \in \partial f(\mathit{\boldsymbol{x}}), \forall \mathit{\boldsymbol{v}} \in \partial f(\mathit{\boldsymbol{y}}) $ .由定义1可知，f是σ-强凸函数的充要条件为$ \partial f$ 是σ-强单调算子.定义5 如果对于
$\forall \mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}} \in H, \beta > 0 $ 都有其中
$ \nabla f(\mathit{\boldsymbol{x}})$ 为f在x处的梯度，则称函数f是β -光滑凸函数.对于不等式(12)，交换x与y的位置，将两个不等式相加得到f是β -光滑函数的另一种表达形式
引理1 [15] 若
$f, g:H\to \mathbb{R}\cup \{+\infty \} $ 是连续函数，f是σ -强凸函数当且仅当$f-\frac{\sigma}{2}\|\cdot\|^{2} $ 是凸函数; g是β -光滑函数当且仅当$\frac{\beta}{2}\|\cdot\|^{2}-g $ 是凸函数.引理2 [16] 设f是H中的实、闭、真凸函数，下列命题等价：
1) f是β -光滑函数;
2)
$\nabla f $ 是β -Lipschitz连续的;3)
$\nabla f$ 是$\frac{1}{\beta } $ -强制的.引理3 [16] 若算子
$A: H \longrightarrow 2^{H} $ 是极大单调的，那么算子$ J_{A}, I d-J_{A}: H \longrightarrow H$ 是严格非扩张极大单调的; 反射预解式${{R}_{A}}:\mathit{\boldsymbol{x}}\to 2{{J}_{A}}\mathit{\boldsymbol{x}}-\mathit{\boldsymbol{x}} $ 是非扩张的.引理4 [16] 若算子
$A: H \longrightarrow 2^{H} $ 是σ -强单调的，则预解式JA是(1+σ)-强制的.
-
求解优化问题(1)等价寻找最优点
$\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} $ 使得$ 0 \in \partial f(\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} ) + \partial g(\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} )$ ，因此求解优化问题(1)转化为求解变分包含问题(2).利用Douglas-Rachford分裂法能解决问题(2)，任意给定一个初始点z0，Douglas-Rachford分裂算法如下其中proxf为临近算子，其定义见(4)式.将(14)式的3式相加，利用Rf的定义得到如下的迭代结果
其中α∈(0，2)，当α=1时，即有
${\mathit{\boldsymbol{z}}^{k + 1}} = {R_g}{R_f}{\mathit{\boldsymbol{z}}^k} $ ，此时产的算法称之为Peaceman-Rachford分裂法[2].由引理3知，Rg，Rf是非扩张的，因此它们的复合RgRf也是非扩张的，故在一般情形下Peaceman-Rachford分裂算法产生的点列不具有收敛性.当$ \alpha = \frac{1}{2}$ 时，式(15)退化为${\mathit{\boldsymbol{z}}^{k + 1}} = \frac{1}{2}\left( {Id + {R_g}{R_f}} \right){\mathit{\boldsymbol{z}}^k} $ ，这就是文献[17]中提及的Douglas-Rachford分裂算法.在本文中引入松弛因子α，相比较于Peaceman-Rachford分裂法和特定的Douglas-Rachford分裂法，具有良好的收敛性.
-
定理1 假设f是σ -强凸函数、β -光滑函数，且满足
$\beta+\frac{1}{\sigma} \geqslant 2 $ ，则算法(15)迭代产生的Rf是$ \sqrt{\frac{\beta \sigma-2 \sigma+1}{\beta+2 \sigma+1}}$ -压缩的.证 因f是σ -强凸函数，由式(3)和引理4知proxf是(1+σ)-强制的，令T=proxf，由定义2可知，对
$ \forall \mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}} \in H$ 对式(16)两边同乘以2并减去‖x－y‖2得
由式(6)知
$ R_{f}=2 { prox }_{f}-I d=2 T-I d$ ，整理式(17)可得与之等价的表达对式(18)两边同乘以
$\frac{2}{\sigma+1} $ ，并将不等式右侧第一项展开，整理得又因f是β -光滑函数，由引理2可知
$\nabla f $ 是$ \frac{1}{\beta }$ -强制的.则对u，v∈H有对式(20)两边同时加‖u－v‖2，整理得
对式(21)，令
$\mathit{\boldsymbol{x}} = (\nabla f + Id)\mathit{\boldsymbol{u}}, \mathit{\boldsymbol{y}} = (\nabla f + Id)\mathit{\boldsymbol{v}} $ ，由式(3)，式(4)可知：$\mathit{\boldsymbol{x}} = (\nabla f + Id)\mathit{\boldsymbol{u}} $ 当且仅当$\mathit{\boldsymbol{u}} = {(\nabla f + Id)^{ - 1}}\mathit{\boldsymbol{x}} = pro{x_f}\mathit{\boldsymbol{x}};\quad \mathit{\boldsymbol{y}} = (\nabla f + Id)\mathit{\boldsymbol{v}} $ 当且仅当$\mathit{\boldsymbol{v}} = {(\nabla f + Id)^{ - 1}}\mathit{\boldsymbol{y}} = pro{x_f}\mathit{\boldsymbol{y}} $ .则式(21)化为对式(22)两侧同乘以2再同时减去‖x－y‖2，整理得
将不等式右侧第一项展开，整理得
将式(19)加上式(23)再乘以
$\frac{\sigma}{\sigma+1} $ 得当
$ \beta \sigma-2 \sigma+1 \geqslant 0$ ，即$\beta+\frac{1}{\sigma} \geqslant 2 $ 时，有$ 0 \leqslant \frac{\beta \sigma-2 \sigma+1}{\beta+2 \sigma+1} <1$ ，则有即Rf是压缩的.
定理2 假设f是σ -强凸函数、β -光滑函数，
$\alpha \in\left(0, 1+\frac{\beta+1}{2 \sigma}-\sqrt{\left(\frac{\beta+1}{2 \sigma}\right)^{2}-1}\right) $ ，则Douglas-Rachford分裂算法(15)线性收敛到不动点$ \overset{\wedge }{\mathop{\mathit{\boldsymbol{z}}}} $ ，且收敛率至少为$|1 - \alpha | + \alpha \sqrt {\frac{{\beta \sigma - 2\sigma + 1}}{{\beta \sigma + 2\sigma + 1}}} $ .即有证 由引理3和定理1可知Rg是非扩张的，Rf是
$\sqrt{\frac{\beta \sigma-2 \sigma+1}{\beta \sigma+2 \sigma+1}} $ 压缩的，则RgRf也是$\sqrt{\frac{\beta \sigma-2 \sigma+1}{\beta \sigma+2 \sigma+1}} $ 压缩的.因为对$\forall {\mathit{\boldsymbol{z}}_1}, {\mathit{\boldsymbol{z}}_2} \in H, \left\| {{R_g}{R_f}{\mathit{\boldsymbol{z}}_1} - {R_g}{R_f}{\mathit{\boldsymbol{z}}_2}} \right\| \le \left\| {{R_f}{\mathit{\boldsymbol{z}}_1} - {R_f}{\mathit{\boldsymbol{z}}_2}} \right\| \le \sqrt {\frac{{\beta - 2\sigma + 1}}{{\beta \sigma + 2\sigma + 1}}} \left\| {{\mathit{\boldsymbol{z}}_1} - {\mathit{\boldsymbol{z}}_2}} \right\| $ .令$T=(1-\alpha) I d+\alpha R_{g} R_{f} $ ，则式(15)可化为zk+1=Tzk，因为$ \overset{\wedge }{\mathop{\mathit{\boldsymbol{z}}}} $ 是Douglas-Rachford分裂算法(15)的不动点，故有$\overset{\wedge }{\mathop{\mathit{\boldsymbol{z}}}} = T\overset{\wedge }{\mathop{\mathit{\boldsymbol{z}}}} $ 其中第一个小于等于关系式是利用三角不等式，第二个小于等于关系式是利用RgRf的压缩性.令
$ {\rm{ }}|1 - \alpha | + \alpha \sqrt {\frac{{\beta \sigma - 2\sigma + 1}}{{\beta + 2\sigma + 1}}} < 1$ ，当α≤1时，显然$|1 - \alpha | + \alpha \sqrt {\frac{{\beta \sigma - 2\sigma + 1}}{{\beta \sigma + 2\sigma + 1}}} < 1 $ 恒成立; 当α>1时，解得$ {\rm{ }}\alpha < 1 + \frac{{\beta + 1}}{{2\sigma }} - \sqrt {{{\left( {\frac{{\beta + 1}}{{2\sigma }}} \right)}^2} - 1} $ .综上，当$ \alpha \in \left( {0, 1 + \frac{{\beta + 1}}{{2\sigma }} - \sqrt {{{\left( {\frac{{\beta + 1}}{{2\sigma }}} \right)}^2} - 1} } \right)$ 时，Douglas-Rachford分裂算法式(17)线性收敛率至少为$|1-\alpha|+\alpha \sqrt {\frac{{\beta \sigma - 2\sigma + 1}}{{\beta \sigma + 2\sigma + 1}}} $ .注2 文献[13]的定理1说明当f是σ -强凸函数、β -光滑函数，γ∈(0，+∞)时，算法(15)迭代产生的Rf是
$\max \left(\frac{\gamma \beta-1}{\gamma \beta+1}, \frac{1-\gamma_{\sigma}}{\gamma_{\sigma}+1}\right) $ 压缩的，而本文的定理1说明了当f是σ -强凸函数、β -光滑函数，且$ \beta + \frac{1}{\sigma } \ge 2$ 时，算法(15)迭代产生的Rf是$\sqrt{\frac{\beta \sigma-2 \sigma+1}{\beta \sigma+2 \sigma+1}} $ -压缩的.注3 文献[13]的定理2与本文的定理2都说明了在适当条件下，Douglas-Rachford分裂算法(15)产生的序列{zk}是线性收敛的.
推论1 若f是σ -强凸函数、β -光滑函数，设
$\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} $ 是优化问题(1)的解，则利用Douglas-Rachford分裂算法式(16)产生的迭代序列{xk}满足证 f是σ -强凸函数，则
$ \partial f$ 是σ -强单调算子，可知proxf是(1+σ)-强制的，由定义2及Cauchy-Schwarz不等式可得proxf是$\frac{1}{{\sigma + 1}} $ -Lipschitz连续.因$\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} $ 是优化问题(1)的解，那么有$\overset{\wedge }{\mathop{\mathit{\boldsymbol{x}}}} $ =proxf($ \overset{\wedge }{\mathop{\mathit{\boldsymbol{z}}}} $ )，其中$ \overset{\wedge }{\mathop{\mathit{\boldsymbol{z}}}} $ 是Douglas-Rachford分裂算法(15)的不动点.因此，第一个不等式是利用proxf是
$ \frac{1}{{1 + \sigma }}$ -Lipschitz连续的，第二、三个不等式利用定理2的结论，则推论得证.
DownLoad: