广义循环Douglas-Rachford算法

郭 科，张有才

（西华师范大学 数学与信息学院，四川 南充 637009）

0 引 言

在本文中，H是实希尔伯特空间，〈·，·〉和‖·‖分别表示相应的内积和范数。给定N个非空的闭凸集C1，C2，…，CN⊆ H，假定Ci≠Φ，N集凸可行问题就是在交集中寻找到某一个点，即：

当N＝2时，（1）退化为经典的凸可行问题

对于凸可行问题（2），有很多的求解方法，但最常用的方法是投影算法。值得注意的是，使用投影算法是通常需要假定在这些集合上的投影相对简单且容易计算。一些著名的投影算法包括Von Neumann的交替投影算法［1-8］，Douglas-Rachford分裂算法（DRSM）［9-11］和 Dykstra算法［12-14］等。最近，文献［15-17］指出，与经典的投影类算法相比，DRSM具有更好的收敛性和明显的数值优势。对于问题（2），Douglas-Rachford算子TC1，C2：H→ H定义为

这里，RS∶＝2PS-I是集合S的反射算子，PS为到集合S的投影算子，定义为

显然，TA，B与TB，A通常不相等。虽然DRSM具有良好的收敛性，但它仅能处理两个集合的凸可行问题。对于N集凸可行问题时，常用的办法是采用乘积空间技术，N集凸可行问题转化为两个集合的凸可行问题来处理。然而，该方法增加了空间的维数，使计算变得复杂。最近，Borwein和Tam在文献［18］中提出了循环DRSM来求解问题（1）。其迭代格式如下：

这里 T［C1C2，…，CN］为循环 Douglas-Rachford算子，定义 T［C1C2…CN］：H→ H为

对于问题（2），循环Douglas-Rachford算子退化为

该算法与DRSM相比，其收敛速度更快而且能直接处理N集凸可行问题，弥补了DRSM不能直接处理N集凸可行问题的不足。

另一方面，DRSM可看作邻近点算法（PPA）的一个应用［9，16］。而PPA现已经得到了很好的研究，其迭代格式为

其中，JcT∶＝（I+cT）-1为集值映射T的预解算子，c为邻近参数且c＞0。PPA具有广泛的应用，比如文献［19-20］中的增广拉格朗日法（ALM）、文献［21］中的乘子交替方向法（ADMM）、文献［22］中的投影梯度法和文献［23］中的外梯度法等都可看作PPA的应用。鉴于PPA广泛的应用，文献［24］中提出了广义PPA，该算法可看作PPA的加速版本，其迭代格式为

其中，γ∈（0，2）为松弛参数。当γ＝1时，广义PPA退化为PPA。文献［25］指出，广义PPA继承了原PPA的所有重要性质，且广义PPA具有更好的收敛性和明显的数值优势。研究发现，当γ越趋近于2时，广义PPA的收敛速度更快。值得注意的是，当γ＝2时，最近文献［25］中给出了γ＝2序列发散的例子。类似地，对广义PPA做应用可得到广义ALM［26］，广义ADMM［27］和广义DRSM［28-29］等等。广义DRSM比DRSM的灵活性更好，最近，文献［30］中更是指出在保证凸性的条件下，松弛一些正则性条件，选择合适的参数α可得到广义DRSM线性收敛的结果。对于问题（2），广义Douglas-Rachford算子：H→ H定义为

其中，α∈（0，1）。自然地，与通常是不相等的。然而广义DRSM也仅能直接处理两个集合的凸可行问题。对于N集凸可行问题时，通常使用的办法也是乘积空间技术。

考虑到广义DRSM的局限，受J.M.Borwein和M.K.Tam的研究成果［18］启发，我们提出使用广义循环DRSM来求解多集凸可行问题，借助均值算子的性质，我们给出了算法的收敛性。

本文的安排如下：在第1节中，我们给出了一些理论分析所需的概念和结论；在第2节中，介绍我们的主要研究成果——广义循环DRSM，以及其收敛性证明。

1 预备知识

我们首先回顾一些相关的概念和结论来作为我们理论分析的主要工具。

我们定义算子 T的不动点集为 Fix（T）∶＝｛x∶Tx＝x｝。令 D⊆ H且 T∶D→ H，若对所有的x，y∈D，都有 ‖Tx-Ty‖ ≤ ‖x-y‖ 成立，我们则称 T是非扩张的；若对所有的 x，y∈D，都有 ‖Tx-Ty‖2+‖（I-T）x-（I-T）y‖2≤ ‖x-y‖2成立，我们则称T是稳定非扩张的；若lnim∞‖Tnx-Tn+1x‖ ＝0，我

→们则称T是渐进正则的。

下面，我们给出在后文中对广义循环DRSM收敛性的证明所需要的定义和引理。

定义1［31-32］令D⊆H且D≠Φ，若存在算子R∶D→H是非扩张的，使得T＝（1-α）I+αR，α∈（0，1），则称算子T为α-均值算子。

引理1［33］令A⊆H是闭凸的，PA是到集合A的投影算子，RA＝2PA-I是集合A的反射算子，则PA是稳定非扩张的，RA是非扩张的。

引理 2［33］（Kolmogorov’s Critrerion）令 C⊆ H是闭凸的且 C≠ Φ，则

引理3 令C1，C2⊆H是非空闭凸集，则RC2RC1是非扩张的，从而TC1，C2＝（1-α）I+αRC2RC1为α-均值算子。

证明：由引理 1知，RC1和RC2是非扩张的，则对任意x，y∈ H，有

故RC2RC1非扩张，从而由定义1知TC1，C2是 α-均值算子。

引理4 令 D⊆ H且 D≠ Φ，m≥2为整数，指标集 I＝｛1，…，m｝，（Ti）i∈l是 D到 D的算子集簇，且（αi）i∈l是 （0，1）内的实数，对每个 i∈ I，Ti是 αi-均值算子，令

则T是α-均值算子。

证明：详细证明过程可查阅文献［34］。

引理5 令 D⊆ H且 D≠ Φ，m为正整数，指标集 I＝｛1，…，m｝，（Ti）i∈l是 D到 D的 α-均值算子集簇，且 ∩i∈IFix（Ti）≠ Φ，则令 T＝T1…Tm，我们有 Fix（T）＝∩i∈lFix（Ti）。

证明：详细证明过程可查阅文献［34］。

引理6 令 A，B⊆ H为闭凸集且 A∩ B≠ Φ，则 PAFix（TA，B）＝A∩ B。

证明：详细证明过程可查阅文献［11］或者［35］。

引理 7［36］令 ｛δn｝和 ｛γn｝为非负序列，且满足和 γn+1≤ γn+δn，n＝1，2，… ，则 ｛γn｝是收敛序列。

引理8［37］令 T∶H→H为 α-均值算子，若对任意 x0＝H，序列 ｛Tnx0｝有界，则序列 ｛Tnx0｝弱收敛到T的不动点x。

引理9 （Opial）令 T∶H→ H是非扩张，渐进正则的，且 Fix（T）≠ Φ。则对任意 x0∈ H，序列 ｛Tnx0｝弱收敛到Fix（T）上的一点。

证明：详细证明过程可查阅文献［34］。

2 广义循环DRSM及其收敛性

使用广义DRSM来解决问题（2）时，广义Douglas-Rachford算子∶H→ H写为

则对于问题（1），我们定义广义循环 Douglas-Rachford算子∶H→ H为

对于问题（2），广义循环 Douglas-Rachford算子变为，∶H→ H定义为使用广义循环DRSM来解决问题（1），给定x0∈H，其迭代序列为

为了方便书写和表达美观，我们将一些表达式进行缩写。我们取指标模余 N，将缩 写 为缩写为。特别地，∶＝

定理1 令C1，C2，…，CN⊆H为闭凸集且 Ci≠ Φ，对任意的 x0∈ H，以及任意的指标 i，j，i，j∈ ｛1，2，…，N｝，则序列 ｛｝弱收敛到点 x，使得 PCix＝PCjx。此外，对于每个指标 j，有 PCjx∈Ci≠ Φ。

证明：首先，我们证明序列｝有界。

由引理3知，对每个指标i，是 α-均值算子，α∈ （0，1）。又由引理 4可知，是 α-均值算子。此外，

由引理 7，令 γn+1∶＝‖xn+1-x*‖ ，γn∶＝‖xn-x*‖ 和 δn≡0，则‖xn+1-x*‖存在，故序列 ｛｝有界。

其次，由引理8，可得序列 ｛｝弱收敛到的不动点 x，下证 PCix＝PCjx，我们计算

其中，最后一个不等式由引理2可得。从而，对每个指标i，都有PCix＝PCi-1x，即有PCix＝PCjx。

最后由引理6，对于每个指标 i，都有 PCix∈ Ci+1，从而

推论1 （循环 DRSM）令 C1，C2，…，CN⊆H为闭凸集且 Ci≠ Φ，对任意的x0∈H，以及任意的指标i，j，i，j∈ ｛1，2，…，N｝，则序列 ｛｝弱收敛到点 x，使得 PCix＝PCjx。此外，对于每个指标 j，有 PCjx