¹上海理工大学管理学院，上海

²上海出版印刷高等专科学校，信息与智能工程系，上海

收稿日期：2024年1月29日；录用日期：2024年3月22日；发布日期：2024年3月29日

摘要

多集分裂等式问题作为分裂可行性问题的重要拓展，在图像重建、语言处理、地震探测等领域具有重要应用。本文针对欧氏空间中多输出集的分裂可行性问题进行研究，并提出了一种新颖的松弛方法。与传统方法不同，我们采用了对两个半空间交点的投影方法。在理论上，我们在特定条件下证明了该方法的收敛性。通过数值模拟实验，进一步证实了本算法在实际应用中的有效性。

关键词

多集分裂可行性问题，CQ算法，投影算法

Algorithmic Research on the Multi-Set Splitting Feasibility Problem

Ya Zhu¹, Yazheng Dang^1*, Ding Ma¹, Zhonghui Xue²

¹Business School, University of Shanghai for Science and Technology, Shanghai

²Department of Information and Intelligent Engineering, Shanghai Publishing and Printing College, Shanghai

Received: Jan. 29^th, 2024; accepted: Mar. 22^nd, 2024; published: Mar. 29^th, 2024

ABSTRACT

The problem of multi-set splitting equations, an important extension of the split feasibility problem, has significant applications in fields such as image reconstruction, language processing, and seismic exploration. This paper investigates the split feasibility problem for multiple output sets in Euclidean spaces and proposes a novel relaxation method. Unlike traditional approaches, our method projects onto the intersection of two half-spaces. Theoretically, we prove the convergence of this method under certain conditions. Through numerical simulation experiments, the effectiveness of our algorithm in practical applications is further validated.

Keywords:Multi-Set Split Feasibility Problem, CQ Algorithm, Projection Method

Copyright © 2024 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

分裂可行性问题 [1] (split feasibility problem)，即SFP，是指对于Hilbert空间H₁和H₂，C，Q分别为H₁和H₂的非空闭凸子集。 $B:H_1\to H_2$ 为有界线性算子。寻找满足下列要求的点x：

$x\in C,Bx\in Q$ . (1)

基于以上问题，本文研究的是N维欧氏空间中的多集分裂可行性问题，设C和 $Q_i,i=1,\cdots ,N$ ，分别为H和 $H_i,i=1,\cdots ,N$ 中的非空、闭合且凸子集。对于给定上述的H， $H_i$ 和 $B_i$ ，多输出集的分割可行性问题(简称SFPwMOS) [2] 是寻找一个元素 $x^{*}$ 满足特定条件：

$x^{*}\in \Gamma :=C\cap \left({\displaystyle {\cap }_{i=1}^N{B}_i^{-1}\left(Q_i\right)}\right)\ne \varnothing ,i=1,2,\cdots ,N$ . (2)

当 $i=1$ 时，修改后的问题等同于初始的分裂可行性问题。

多输出集的分割可行性问题(SFPwMOS)的研究及其在图像重建、语言处理、地震探测等领域的应用，体现了它跨学科的价值和广泛的应用前景。特别是在图像重建领域，该问题的解决方案极大地增强了对受噪声干扰图像处理的能力 [3] [4] ，尤其体现在医疗成像和卫星遥感技术中。在语言处理领域，该问题的应用有效优化了语言模型，提升了机器翻译和自动文摘的准确性 [5] 。同时，在地震探测领域，通过精确模拟地震波的传播路径，该问题为地质结构的分析及资源勘探提供了技术支撑。

近年来，有关此问题的研究不断深入，涌现出许多创新算法和理论。Reich [6] 等人提出了以下迭代方法来解决 SFPwMOS (2)。对于任何给定的点 $x^0\in H$ ， $\left\{x^k\right\}$ 序列通过以下迭代产生：

$x^{k+1}:={\alpha }_{k}f\left(x^k\right)+\left(1-{\alpha }_k\right)P_C\left(x^k-{\lambda }_k{\displaystyle \underset{i=1}{\overset{n}{\sum }}{B}_i^{\text{T}}\left(I-P_{Q_i}\right)B_i{x}^k}\right)$ ,

其中， $f:C\to C$ 是H到其自身的严格压缩映射 [7] ，具有压缩常数 ${\lambda }_k\subset \left(0,\infty \right)$ 。为了提高多集分裂可行性问题求解的效率，Dang等人(2012)引入了一种带有外推因子的加速算法 [8] ，通过迭代更新公式

$x^{k+1}=x^k+{\lambda }_k\left(P_C\left(x^k\right)-x^k\right)$ . (3)

加速算法的收敛，其中 ${\lambda }_k$ 是控制迭代步长的外推因子。基于此基础，Zhaoa等人(2012)进一步优化了这种方法 [9] ，通过自适应调整步长

${\lambda }_{k+1}=\min \left\{{\lambda }_{\max },\frac{x^k-x^{k-1},x^k-P_C\left(x^k\right)}{x^k-P_C{\left(x^k\right)}^2}\right\}$

来增强算法的灵活性和应用范围。随着研究的深入，Cui等人(2013)转向探索分裂共同固定点问题(SCFP) [10] ，采用了基于Eicke的阻尼投影方法提出了一个新的循环迭代方案，

$x^{k+1}={\alpha }_k{x}^k+\left(1-{\alpha }_k\right)T(\; x\; k\; )$

该方案在一些温和的假设下证明了其强收敛性。此外，Latif等人(2016)在无限维希尔伯特空间中为广义多集分裂可行性问题(GMSSFP)引入了基于粘度逼近方法的新算法 [11] ，这一算法专注于求解最小化问题的变分不等式，并确保了强收敛性。考虑到并行处理的重要性，Reich等人(2019)提出了三种新的并行算法 [12] ，用于在希尔伯特空间中求解分裂共同固定点问题，同时考虑了多集分裂可行性问题的特殊情况。与此同时，Taddele等人(2020)通过将封闭凸集放松为半空间 [13] ，并引入松弛CQ算法中的步长选择形式

${\lambda }_k=\frac{\langle x^k-P_C\left(x^k\right),x^k-x^{k-1}\rangle }{{\Vert x^k-P_C\left(x^k\right)\Vert }^2}$ ,

旨在提高多集分裂可行性问题求解的实用性。为了进一步优化算法并提高其适应性，Taddele等人(2020)又提出了一种带有惯性外推的迭代算法 [14] ，并通过自适应技术选择步长，使算法更加灵活有效。紧接着，AL-HOMIDAN等人(2020)在巴拿赫空间中研究广义多集分裂可行性问题 [15] ，他们构建了一种不依赖

算子范数的迭代算法 $x^{k+1}=x^k-{\lambda }_k{A}^{\ast }\left(A{x}^k-b\right)$ ，并证明了其强收敛性。

最近，Sunthrayuth等人(2021)在特定的巴拿赫空间框架内提出了一种求解多集分裂可行性问题的广义自适应方法 [16] 。此方法在无需先验知识的情况下，通过新的步长选择方式，证明了生成序列的强收敛性。Cuong等人(2022)针对实希尔伯特空间中的强单调变分不等式问题 [17] ，提出了一种新的算法，该算法解决了具有多输出集约束的分裂可行性问题，且无需了解映射的Lipschitz和强单调常数，体现了算法设计的进一步创新。尽管最近的进展为问题的求解提供了新的视角和方法，但仍然存在一些挑战。特别是，在处理高维空间和复杂约束条件时，现有算法在收敛速度、稳定性以及对先验知识的依赖方面仍显不足。针对这些挑战，本文提出一种新的松弛算法。我们的方法旨在通过使用当前迭代和上一次迭代的空间交集投影来提高算法的收敛性，这种策略不仅能够加快收敛速度，还能提高算法对不同问题设置的适应性和鲁棒性。此外，通过引入松弛技术，我们的算法减少了对先验知识的依赖，使之更加适用于实际应用中的复杂问题。通过数值仿真的结果，我们将展示本文提出的算法相较于已有算法具有较好的收敛性，从而证明了我们方法的有效性和实用性。

2. 预备知识

我们用H表示N维欧氏空间，用I表示上的恒等算子。对于可微函数f，用 $\nabla f$ 表示f的梯度。给定序列 $\left\{x_n\right\}$ 在H中， ${\omega }_w\left(x_n\right)$ 分别表示 $x^n$ 的聚点集。 $x_n\to x$ 意味着序列 $\left\{x_n\right\}$ 到x是收敛的。

定义 2.1. [18] [19] 设D是H的非空子集，设 $T:D\to H$ 。那么T具备如下性质：

(1) 如果满足以下条件，则称算子T具备非扩张性(nonexpansive)

$\Vert Tx-Ty\Vert \le \Vert x-y\Vert ,\forall x,y\in D$ , (4)

(2) 如果满足以下条件，则称算子T为稳定非扩张性(firmly nonexpansive)：

${\Vert Tx-Ty\Vert }^2\le {\Vert x-y\Vert }^2-{\Vert \left(I-T\right)x-\left(I-T\right)y\Vert }^2,\forall x,y\in D$ , (5)

(3) 若存在一个正实数 $\nu >0$ ，使得下列条件成立，则称T具备v-逆强单调性(v-inverse strongly monotone，简称(v-ism)：

$\langle Tx-Ty,x-y\rangle \ge \nu {\Vert Tx-Ty\Vert }^2,\forall x,y\in D$ , (6)

对任意给定的点，定义对非空闭合凸集C的投影为：

$P_{C}x=\text{argmin}\left\{\Vert y-x\Vert |y\in C\right\}$ , (7)

投影 $P_C$ 具有以下性质。

引理2.2. 设 $C\subseteq H$ 是一个非空闭凸子集。对于所有 $x,y\in H$ 和 $z\in C$ ，

(1) $\langle x-P_{C}x,z-P_{C}x\rangle \le 0$ ；

(2) $P_C$ 和 $I-P_C$ 都是非扩张的；

(3) $P_C$ 和 $I-P_C$ 都是可逆强单调的；

定义 2.2. 设 $f:H\to ℝ$ 为特征函数， $\sigma \in \left(0,1\right)$ ：

(1) 若f满足以下条件，则称其为凸函数(convex)：

$f\left(\delta x+\left(1-\delta \right)y\right)\le \delta f\left(x\right)+\left(1-\delta \right)f\left(y\right),\forall x,y\in H$ , (8)

(2) 若f满足以下条件，并具有常数 $\sigma$ (其中 $\sigma >0$ )，则称其为强凸函数(strongly convex)：

$f\left(\delta x+\left(1-\delta \right)y\right)+\frac{\sigma }{2}\delta \left(1-\delta \right){\Vert x-y\Vert }^2\le \delta f\left(x\right)+\left(1-\delta \right)f\left(y\right),\forall x,y\in H$ , (9)

(3) 如果一个向量满足以下条件，则称其为函数f在点x处的次梯度(subgradient)：

$f\left(y\right)\ge f\left(x\right)+\langle \omega ,y-x\rangle ,\forall y\in H$ , (10)

(4) 所有凸函数 $f:H\to ℝ$ 在点 $x\in H$ 的次梯度的集合，记作 $\partial f\left(x\right)$ ，称为f的次微分(subdifferential)，对于 $y\in H$ 定义为：

$\partial f\left(x\right)=\left\{\omega \in H:f\left(y\right)\ge f\left(x\right)+\langle \omega ,y-x\rangle \right\}\text{.}$ (11)

若函数f是连续可微的，则其次微分等于其梯度，即 $\partial f\left(x\right)=\left\{\nabla f\left(x\right)\right\}$ 。凸函数在其定义域的每一点

都是次可微的。

引理2.3. [20] 设 $f:H\to \left[-\infty ,+\infty \right)$ 为一个特征函数，定义如下：

$f\left(x\right)=\frac{1}{2}{\Vert \left(I-P_Q\right)Bx\Vert }^2.$ (12)

则有

(1) f是凸的和可微的

(2) $\nabla f\left(x\right)=B^{\ast }\left(I-P_Q\right)Bx$ ， $x\in H$ ；

(3) f在H上是弱下半连续的；

(4) $\nabla f$ 是 ${\Vert B\Vert }^2$ -Lipschitz：

$\Vert \nabla f\left(x\right)-\nabla f\left(y\right)\Vert \le {\Vert B\Vert }^2\Vert x-y\Vert ,x,y\in H.$

引理 2.4. [20] 设C和Q分别为欧氏空间H₁和H₂中的闭合凸子集，且 $f:H_1\to ℝ$ 定义为 $f\left(x\right)=\left(I-P_Q\right)B{x}^2$ ，其中 $B:H_1\to H_2$ 是有界线性算子。那么，对于 $\delta >0$ 和 $x^{\ast }\in H_1$ ，以下陈述是等价的：

(1) 点 $x^{\ast }$ 为分裂可行性问题(SFP)的解，即 $x^{\ast }\in \left\{x\in C:Bx\in Q\right\}$ 。

(2) 点 $x^{\ast }$ 是映射 $P_C\left(I-\delta \nabla f\right)$ 的不动点。

(3) 点 $x^{\ast }$ 解决了关于f梯度的变分不等式问题，即找到一个点 $x^{\ast }\in C$ ，使得

$\langle \nabla f\left(x\right),y-x\rangle \ge 0,\forall y\in C$ , (13)

引理 2.5. [21] 设 $\tau >0$ 。若 $\bar{x}\in H_1$ 为分裂可行性问题(SFP)的解，当且仅当 $\bar{x}$ 为了固定点方程的解，算法的收敛性分析基于Fejér单调性。

$\tilde{x}=P_C\left(\tilde{x}-\tau B^{\ast }\left(I-P_Q\right)B\tilde{x}\right).$

引理 2.6. [22] 设C是H中的非空闭凸子集。若序列 $\left\{x_n\right\}$ 在H中对C为Fejér单调的，则表示引理2.3设 $C_i$ 是C中的非空闭凸子集。如果序列 $\left\{x^n\right\}$ 对C是Fejér单调的，则以下结论成立：

(I) $\left\{x^n\right\}$ 收敛到 $x^{\ast }\in C$ 当且仅当 ${\omega }_w\left(\left\{x^n\right\}\right)\subseteq C$ ；

(II) 序列 $\left\{P_C{x}_n\right\}$ 收敛；

(III) 如果 $\left\{x^n\right\}$ 收敛到 $x^{\ast }\in C$ ，则 $x^{\ast }=\underset{n\to \infty }{\lim }{P}_C{x}^n$ 。

3. 算法及其收敛性

在本节中，我们考虑了SFPwMOS的一般情形，其中非空闭凸的集合C和 $Q_i\left(i=1,\cdots ,N\right)$ 由凸函数的水平集给出。

在整个本节中，我们假设 $c:H\to ℝ$ 和 $q_i:H_i\to ℝ$ 是下半连续的凸函数，并且集合C和 $Q_i$ 由以下公式给出：

$\begin{array}{l}C:=\left\{x\in H:c\left(x\right)\le 0\right\}\\ Q_i:\left\{y\in H_i:q_i\left(y\right)\le 0\right\}\end{array}$ , (14)

在 $x^k$ 处的松弛集合(半空间) $C_k$ 定义为：

$C_k:=\left\{x\in H:c\left(x^k\right)+\langle {\xi }^k,x-x^k\rangle \le 0\right\}$ , (15)

其中 ${\xi }^k\in \partial c\left(x^k\right)$ 。

在 $x^k$ 处的松弛集合(半空间) $Q_i\left(i=1,\cdots ,N\right)$ 定义为：

$\begin{array}{l}{Q}_i^k:=\left\{x\in H:c\left(x^k\right)+\langle {\xi }^k,x-x^k\rangle \le 0\right\},\\ \left\{y\in H_i:q_i\left(B_i{x}^k\right)+\langle {\eta }_i^k,y-B_i{x}^k\rangle \le 0\right\}\end{array}$ (16)

其中 ${\eta }_i^k\in \partial q_i\left(B_i{x}^k\right)$ 。由此可知，对于每个 $k\ge 0$ ，都有 $C\subset C_k$ 和 $Q\subset Q_i^k$ 。

我们得到以下(松弛的)邻近函数；对于 $x\in H$ ，

$g\left(x\right):=\frac{1}{2}{\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(I-P_{Q_i}\right)B_i{x}^2}$ , (17)

因为 $g(.)$ 是可微的，其梯度由以下公式给出：

$\nabla g\left(x\right):={\displaystyle \underset{i}{\overset{N}{\sum }}{B}_i^{\text{T}}}\left(I-P_{Q_i}\right)B_i{x}^2$ , (18)

其中每个 $Q_i$ 是在上文中给出的半空间。我们注意到 $g_k$ 是弱下半连续的凸可微函数，且 $\nabla g\left(x\right)$ 是Lipschitz连续的。

我们提出一个新的松弛CQ算法来求解SFPwMOS(1)。

算法1.

Step 1：初始化迭代。任选初始点 $x^0$ 和 $x^1$ 。

Step 2：对于给定的 $x^n$ ，计算下一个迭代点 $x^{n+1}$ 如下：

$x^{n+1}=P_{C_n^2}\left(x^n-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_{{}^i}^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n}\right)$ , (19)

其中 $C_n^2$ 、 $Q_{nj}^2$ 和 ${\tau }^n$ 分别定义如下：

$C_n^2=C_n\cap C_{n-1}$ , $Q_{in}^2=Q_{in}\cap Q_{i\left(n-1\right)}$ , (20)

${\tau }_i^n=\frac{{\rho }_n{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}{{\Vert B_j^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2},\left(i=1,2,\cdots ,n\right)$

且满足 $0<{\rho }_n<2$ [23] 。

Step 3：检查停止准则。如果 $x^{n+1}=x^n$ ，则算法终止。

Step 4：更新迭代计数。设 $n:=n+1$ 。

Step 5：返回Step 2，计算下一个迭代。

注 3.3. (1) 由于 $C_{n-1}$ 、 $C_n$ 和 $Q_{j\left(n-1\right)}$ 、 $Q_{jn}$ 均为半空间， $C_n^2$ 和 $Q_{jn}^2$ 都是两个半空间的交集，通过对两个半空间交集进行投影，算法能够在保持所有约束条件的同时，更直接地朝着问题的可行解区域前进，从而加快收敛速度，同时可以提高其在面对多约束和高维问题时的适应性和鲁棒性。

显然 $C\subset C_{n-1}$ ， $C\subset C_n$ 以及 $Q_i\subset Q_{i\left(n-1\right)}$ ， $Q_i\subset Q_{in}$ 。因此我们有 $C\subset C_n^2$ 和 $Q_i\subset Q_{in}^2$ 。

定理 3.4. 在算法1中，如果对某个 $n\ge 0$ ，有 $x^{n+1}=x^n$ ，则 $x^n$ 是SFPwMOS (1)的解。

证明 从算法1，若 $x^{n+1}=x^n$ ，则 $x^n$ 是SFPwMOS (1)的解。

从算法1得，若 $x^{{}_{n+1}}=x^n$ ，则有 $x^n=P_{C_n^2}\left(x^n-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_{{}^i}^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n}\right)$ 。根据引理2.7，我们可以得出 $x_n\in C_n^2$ 和 $B_i{x}_n\in Q_{jn}^2$ 。这意味着 $x_n\in C_n$ 和 $B_i{x}_n\in Q_{jn}$ 。然后，我们有 $x_n\in C$ 和 $B_i{x}_n\in Q_i$ 。证明完成。

根据定理3.4，我们可以看到，如果算法1在有限(比如n)步迭代中终止，则 $x^n$ 是SFPwMOS(1)的解。因此，在本节的剩余部分中，我们假设算法1不会在有限次迭代中终止，因此会产生无限序列 $\left\{x^n\right\}$ 。

定理3.5. 假设 ${\inf }_n{\rho }_n\left(2-{\rho }_n\right)>0$ 。则由算法1生成的序列 $\left\{x^n\right\}$ 收敛到SFPwMOS(1)的解。

证明. 设 $x^{*}\in S$ 。令 $y_n=x^n-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n}$ 。那么我们有：

$\begin{array}{c}{\Vert y^n-x^{*}\Vert }^2={\Vert \left(x^n-x^{*}\right)-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n}\Vert }^2\\ ={\Vert x^n-x^{*}\Vert }^2-2\langle {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n},\left(x^n-x^{*}\right)\rangle +{\Vert {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n}\Vert }^2\\ \le {\Vert x^n-x^{*}\Vert }^2-2\langle {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n},\left(x^n-x^{*}\right)\rangle +{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i}{\Vert {\tau }_i^n{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2\\ ={\Vert x^n-x^{*}\Vert }^2-2{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n\langle B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n,x^n-x^{*}\rangle }+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\left({\tau }_i^n\right)}^2}{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2.\end{array}$ (21)

注意到 $I-P_{Q_{in}^2}$ 是1-ism的。这意味着：

$\begin{array}{c}\langle B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n,x^n-x^{*}\rangle =\langle \left(I-P_{Q_{in}^2}\right)B_i{x}^n,B_i{x}^n-B_i{x}^{*}\rangle \\ =\langle \left(I-P_{Q_{in}^2}\right)B_i{x}^n-\left(I-P_{Q_{in}^2}\right)B_i{x}^{*},B_i{x}^n-B_i{x}^{*}\rangle \\ \ge {\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2,\end{array}$ (22)

因此，

$\begin{array}{c}{\Vert y^n-x^{*}\Vert }^2\le {\Vert x^n-x^{*}\Vert }^2-2{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\tau }_i^n{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i}{\left({\tau }_i^n\right)}^2{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2\\ ={\Vert x^n-x^{*}\Vert }^2-2{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i\frac{{\rho }_n{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^4}{{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i}\frac{{\rho }_n^2{\Vert \left(I-P_{Q_{in}^2}\right)B_j{x}^n\Vert }^4}{{\Vert B_j^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}\\ ={\Vert x^n-x^{*}\Vert }^2-{\rho }_n\left(2-{\rho }_n\right){\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i}\frac{{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^4}{{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2},\end{array}$ (23)

由于 $C\subseteq C_n$ ，则 $x^{*}=P_C\left(x^{*}\right)=P_{C_n^2}\left(x^{*}\right)$ 。因此，我们有：

$\begin{array}{c}{\Vert x^{n+1}-x^{*}\Vert }^2={\Vert P_{C_n^2}\left(y^n\right)-P_{C_n^2}\left(x^{*}\right)\Vert }^2\\ \le {\Vert y^n-x^{*}\Vert }^2-{\Vert \left(I-P_{C_n^2}\right)y^n\Vert }^2\\ \le {\Vert x^n-x^{*}\Vert }^2-{\rho }_n{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i\frac{{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^4}{{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}}-{\Vert \left(I-P_{C_n^2}\right)y^n\Vert }^2.\end{array}$ (24)

由于 ${\inf }_n{\rho }_n\left(2-{\rho }_n\right)>0$ ，序列 $\left\{x^n\right\}$ 对S是Fejér单调的。这意味着序列 $\left\{x^n\right\}$ 是收敛的，因此 $\left\{x^n\right\}$ 是有界序列。此外，根据(24)和对 ${\rho }_n$ 的假设，我们可以立即得出：

${\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\Vert \left(I-P_{C_n^2}\right)y^n\Vert }^2}<\infty$ ,

和

${\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\frac{{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^4}{{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}}<\infty$ . (25)

特别地，我们有：

$\underset{n\to \infty }{\lim }\Vert \left(I-P_{C_n^2}\right)y^n\Vert =0$

和

$\underset{n\to \infty }{\lim }\frac{{\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^4}{{\Vert B_i^{*}\left(I-P_{Q_n^2}\right)B_i{x}^n\Vert }^2}=0$ , (26)

由于 $I-P_{Q_{in}^2}$ 是非扩张的，我们有：

${\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2={\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n-B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^{*}\Vert }^2\le {\Vert B_i\Vert }^4{\Vert x^n-x^{*}\Vert }^2$ , (27)

这意味着 $\left\{{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}_n\Vert }^2\right\}$ 是有界的。然后根据(26)，我们得出：

$\underset{n\to \infty }{\lim }\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert =0$ . (28)

根据引理2.6，为了证明 $\left\{x^n\right\}$ 对SFPwMOS (1)的解的收敛性，只需证明 ${\omega }_w\left(x_n\right)\subseteq S$ ，因为 $\left\{x^n\right\}$ 对S是Fejér单调的。现在设 $\bar{x}\in {\omega }_w\left(x_n\right)$ 并且 $\left\{x^{n_k}\right\}$ 是 $\left\{x^n\right\}$ 的一个子序列，满足 $x^{n_k}\to \bar{x}$ 。接下来，我们证明 $\bar{x}\in S$ 。首先我们证明 $B_i\bar{x}\in Q_i$ 。由于 $\partial q_i$ 在有界集上是有界的，存在一个常数 ${\delta }_1>0$ ，使得 $\Vert {\eta }_n\Vert \le 1$ 对所有 $n\ge 0$ 成立。根据(16)和 $P_{Q_{in}^2}\left(B_i{x}_n\right)\in Q_{in}^2\subseteq Q_{in}$ ，可以得出：

$q_i\left(B_i{x}^n\right)\le \langle {\eta }_n,B_i{x}^n-P_{Q_{in}^2}\left(B_i{x}^n\right)\rangle \le {\delta }_1\Vert \left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert$ , (29)

根据 $q_i$ 下半连续性和(29)表明：

$q_i\left(B_i\bar{x}\right)\le \underset{k\to \infty }{\lim \inf }{q}_i\left(B_i{x}_k^n\right)\le \underset{k\to \infty }{\lim }{\delta }_1\Vert \left(I-P_{Q_{i{n}_k}^2}\right)B_i{x}_k^n\Vert =0$ , (30)

得到 $B_i\bar{x}\in Q$ 。

接下来我们证明 $\bar{x}\in C$ 。根据 ${\tau }_i$ 的定义，我们有：

$\begin{array}{c}{\Vert y^n-x^n\Vert }^2={\Vert {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\tau }_i^n}{\lambda }_i{B}_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2\\ \le {{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i{\left({\tau }_i^n\right)}^2\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }}^2\\ ={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\lambda }_i\frac{{\rho }_n^2{\Vert \left(I-P_{Q_{kn}^2}\right)B_i{x}^n\Vert }^4}{{\Vert B_i^{*}\left(I-P_{Q_{in}^2}\right)B_i{x}^n\Vert }^2}}\to 0,\end{array}$ , (31)

由于 $\partial c$ 在有界集上是有界的，存在一个常数 ${\delta }_2>0$ ，使得 $\Vert {\zeta }_n\Vert \le {\delta }_2$ 对所有 $n\ge 0$ 成立。根据 $C_n$ 的定义和 $P_{C_n^2}\left(y_n\right)\in C_n^2\subseteq C_n$ 的事实，我们得到：

$\begin{array}{c}c\left(x^n\right)\le \langle {\xi }_n,x_n-P_{C_n^2}{y}^n\rangle \\ =\langle {\xi }_n,\left(x^n-y^n\right)+\left(I-P_{C_n^2}\right)y^n\rangle \\ \le {\delta }_2\left(\Vert x^n-y^n\Vert +\Vert \left(I-P_{C_n^2}\right)y^n\Vert \right),\end{array}$ (32)

同样，c的下半连续性和(32)表明

$c\left(\bar{x}\right)\le \underset{k\to \infty }{\lim \inf }c\left(x_k^n\right)\le \underset{k\to \infty }{\lim }{\delta }_2\left(\Vert x_k^n-y_k^n\Vert +\Vert \left(I-P_{C_{n_k}^2}\right)y_k^n\Vert \right)=0$ , (33)

因此可以得到 $\bar{x}\in C$ 。我们可以的到 $\bar{x}\in S$ 。证毕。

4. 数值结果

在本节中，我们通过解决一些问题，展示了一些数值示例，以说明与现有结果相比，我们提出的方法的实施和效率。在我们的数值实验中，迭代次数(Iter. (n))代表迭代次数，CPU(s)代表以秒为单位的运行时间。

例1 考虑 $H={ℝ}^{10},H_1={ℝ}^{20},H_2={ℝ}^{30}$ 和 $H_3={ℝ}^{40}$ 。找到一个点 $p^{\ast }\in {ℝ}^{10}$ ，使得

$p^{\ast }\in \Omega :=C\cap B_1^{-1}\left(Q_1\right)\cap B_2^{-1}\left(Q_2\right)\cap B_3^{-1}\left(Q_3\right)\ne \varnothing ,$

其中集合C和 $Q_i$ ，以及线性有界算子 $B_i$ 由下式定义：

$\begin{array}{l}C=\left\{x\in {ℝ}^{10}:{\Vert x-c\Vert }^2\le r^2\right\},\\ Q_1=\left\{A_{1}x\in {ℝ}^{20}:{\Vert A_{1}x-c_1\Vert }^2\le r_1^2\right\},\\ Q_2=\left\{A_{2}x\in {ℝ}^{30}:{\Vert A_{2}x-c_2\Vert }^2\le r_2^2\right\},\\ Q_3=\left\{A_{3}x\in {ℝ}^{40}:{\Vert A_{3}x-c_3\Vert }^2\le r_3^2\right\}.\end{array}$

其中 $c\in {ℝ}^{10}$ ， $c_1\in {ℝ}^{20}$ ， $c_2\in {ℝ}^{30}$ ， $c_3\in {ℝ}^{40}$ ， $r,r_1,r_2,r_3\in ℝ$ ，且 $B_1:{ℝ}^{10}\to {ℝ}^{20}$ ， $B_2:{ℝ}^{10}\to {ℝ}^{30}$ ， $B_3:{ℝ}^{10}\to {ℝ}^{40}$ 。在这种情况下，对于任何 $x\in {ℝ}^{10}$ ，我们有 $c\left(x\right)={\Vert x-c\Vert }^2-r^2$ 和 $q_i\left(A_{i}x\right)={\Vert A_{i}x-c_i\Vert }^2-r_i^2,i=1,2,3$ 。根据(22)和(23)，集合 $C_n$ 和 $Q_i^n\left(i=1,2,3\right)$ 的半空间C和 $Q_i$ ，分别在点 $x^n$ 和 $B_i{x}^n$ 处确定：

$\begin{array}{l}{C}_n^2=\left\{x\in {ℝ}^{10}:{\Vert x_n-c\Vert }^2-r^2\le 2\langle x_n-c,x_n-x\rangle \right\},\\ Q_{1n}^2=\left\{y\in {ℝ}^{20}:{\Vert B_1{x}_n-c_1\Vert }^2-r_1^2\le 2\langle B_1{x}_n-c_1,B_1{x}_n-y\rangle \right\},\\ Q_{2n}^2=\left\{y\in {ℝ}^{30}:{\Vert B_2{x}_n-c_2\Vert }^2-r_2^2\le 2\langle B_2{x}_n-c_2,B_2{x}_n-y\rangle \right\},\\ Q_{3n}^2=\left\{y\in {ℝ}^{40}:{\Vert B_3{x}_n-c_3\Vert }^2-r_3^2\le 2\langle B_3{x}_n-c_3,B_3{x}_n-y\rangle \right\}.\end{array}$

接下来，我们可以轻松计算出对半空间 $C_n^2$ 和 $Q_{in}^2\left(i=1,2,3\right)$ 的正交投影。代表矩阵 $B_i$ 的元素是在闭区间 $\left[-5,5\right]$ 中随机生成的，中心点 $c,c_1,c_2,c_3$ 的坐标是在闭区间 $\left[-1,1\right]$ 中随机生成的，半径 $r,r_1,r_2,r_3$ 是分别在闭区间 $\left[10,20\right],\left[20,40\right],\left[30,60\right],\left[40,80\right]$ 中随机生成的。为了简化，初始向量用 $e_1={\left(1,1,\cdots ,1\right)}^{\text{T}}\in {ℝ}^{10}$ 表示。在这个例子中，我们通过解决一个数值问题来检验由我们的算法定义的序列 $\left\{x_n\right\}$ 的收敛性。

我们对比了所提出算法与广泛认可的经典方法——交替投影法(Alteration) [24] 和Douglas-Rachford Splitting Method (Douglas-Rachford) [25] 。对于交替投影法，在多输出集的情况下，迭代过程被扩展为在一系列闭合凸集之间交替进行投影，形式化为：

$x^{n+1}=P_C\left(\cdots \left(P_{Q_2}\left(P_{Q_1}\left(x^n\right)\right)\right)\cdots \right)$

其中， $Q_1,Q_2,\cdots ,Q_n,C$ 表示一系列的闭合凸集， $P_{Q_i},P_C$ 表示对集合 $Q_i$ 和C的投影操作。Douglas-Rachford Splitting Method在多输出集情况下需要对算法进行适当的修改或扩展，迭代更新公式为如下形式：

$x^{n+1}=x^n+\lambda \left(\frac{1}{m}{\displaystyle \underset{j=1}{\overset{m}{\sum }}{P}_C}\left(2P_{Q_i}\left(x^n\right)-x^n\right)-P_{Q_i}\left(x^n\right)\right),$

其中， $P_C$ 和 $P_{Q_i}$ 分别是对集合C和 $Q_i$ 的投影操作， $\lambda$ 是正的步长参数，此处取 $\lambda =1$ ，m是输出集的总数，此处取 $m=3$ 。

由图1我们可以观察得到算法1具有较好的收敛性：

图1. $E_n$ 值随着迭代次数增加而变化

如图1所示，随着迭代次数增加，算法的 $E_n$ 值呈快速下降趋势，并在约20次迭代后趋于平稳。初期 $E_n$ 的显著减少表明算法在搜索最优解的过程中迅速逼近稳定状态，显示出良好的收敛性能。当迭代次数超过20次后， $E_n$ 值下降速度明显放缓，逐渐稳定在一个较小的数值范围内，这暗示算法可能已接近最优解或达到一个稳态解。相对于交替方向法，算法1具有更高的确度和更快的下降速度，由于 $E_n$ 值在后期迭代中的变化幅度较小，若考虑计算效率和资源消耗，可在满足一定收敛精度的前提下适当提前终止迭代过程。整体而言，所采用算法的性能表现符合预期目标，具备实际应用的潜力。

我们计算了算法的收敛速率，并与用于解决SFPwMOS的交替投影法 [13] 和Douglas-Rachford [14] 方法进行比较。并观察在不同的停止准则 $E_n$ 下对应的各项指标，如表1。

表1. 对于不同的 $E_n$ 算法1与交替投影法和Douglas-Rachford的比较

在多种迭代停止准则 $E_n<1e^{-1}$ 至 $E_n<1e^{-5}$ 下，通过比较三种算法——算法1、交替投影法和Douglas-Rachford算法——在收敛性( $E_n$ )、迭代次数(n)和运行时间(s)三个指标上的性能，可以观察到算法1在大多数情况下都表现出更高的效率和稳定性。具体来说，算法1能够以较少的迭代次数达到相同的精度要求，这说明算法1在求解速度上更具优势。同时，算法1所需的计算时间通常低于其他两种算法，特别是在更高精度要求的情况下，这一优势更为显著。此外，从表格中可以看出，随着精度要求的提高，Douglas-Rachford算法的迭代次数增长速度较快，这可能暗示了在处理更复杂或要求更高精度的问题时，其性能可能会受到限制。交替投影法在迭代次数和时间上的表现虽然优于Douglas-Rachford算法，但与算法1相比仍有差距。综上所述，算法1在所考察的性能指标上表现出了更佳的综合性能，对于需要快速准确解决问题的应用场景，是一种更可取的选择。

5. 小结

本文针对欧氏空间中的多集分裂可行性问题，提出了一种新颖的松弛算法。该算法通过对传统投影方法的改进，采用对两个半空间交集进行投影的策略，不仅在理论上展现了创新性，也在实际应用中证明了其有效性。我们对该算法的收敛性进行了严格的理论分析，确立了在特定条件下算法的稳定性和可靠性，为解决复杂的优化问题提供了一种有效的新途径。这一研究成果不仅丰富了多集分裂问题的求解方法，也为相关领域的实际应用开辟了新的可能。

文章引用

朱 亚,党亚峥,马 丁,薛中会. 多集分裂可行问题的算法探究
Algorithmic Research on the Multi-Set Splitting Feasibility Problem[J]. 理论数学, 2024, 14(03): 240-251. https://doi.org/10.12677/pm.2024.143102

参考文献