用于求解变分不等式和不动点问题的两种多参数次梯度外推方法

《Communications in Nonlinear Science and Numerical Simulation》：Two subgradient extragradient methods with multiple parameters for solving variational inequalities and fixed point problems

　　

摘要
本文提出了两种改进的次梯度外梯度方法，用于求解希尔伯特空间中的变分不等式和不动点问题。通过应用线搜索规则，我们避免了依赖所涉算子的 Lipschitz 连续性。此外，我们引入了一些新的常数参数，增加了步长选择的灵活性和通用性，从而促进了更精确数值解的计算。在适当条件下，我们对两种迭代方法进行了严格的数学分析，并建立了它们各自的强收敛定理。最后，我们给出了数值示例，并与现有的代表性方法进行了比较，以说明我们所提算法的性能和有效性。

引言
在本文中，我们考虑如下定义的希尔伯特空间中的变分不等式问题 (VIP)：寻找一个解 $q \in C$ 使得 $\langle Aq, p-q \rangle \geq 0, \forall p \in C$，其中 $C$ 是实希尔伯特空间 $H$ 的非空闭凸子集，$A: C \to H$ 是非线性算子。具体而言，我们将变分不等式 (1.1) 的解集记为 $VI(C, A)$。
自从 Fichera [1], [2] 的开创性工作以及对 VIP 领域的深入研究以来，这一主题引起了研究人员的广泛关注。对该问题的高度重视不仅源于其在数学理论上的重要性，还源于其在各个领域的广泛应用。在力学中，变分不等式被广泛用于建模接触问题和非光滑结构系统 [3], [4]。在经济学中，它们是描述经典和扩展经济模型以及网络经济问题中均衡条件的根本工具 [5], [6]。在医学及相关应用科学中，变分不等式出现在最优控制公式化和复杂系统的迭代求解方法中 [7], [8]。因此，对 VIP 的彻底研究不仅具有推进数学理论的巨大潜力，还为解决众多实际挑战提供了强大的数学工具。
求解 VIP 主要有两种方法：正则化和投影方法。正则化方法侧重于通过引入正则化项来简化问题，而投影方法则强调通过投影操作寻找解。每种方法都有其自身的优点和局限性，使其适用于不同的问题场景。在本研究中，我们主要关注投影方法，并深入探讨其在 VIP 中的应用。
在当前的研究背景下，为了解决 VIP，出现了各种迭代算法，其中投影方法 (PM) 因其经典性和有效性而备受关注。然而值得注意的是，PM 主要适用于强单调算子。一旦算子的单调性减弱，算法的收敛性可能会受到影响，甚至可能导致生成的序列发散。为了克服这一局限性并拓宽算法的适用范围，Korpelevi? [9] 提出了以下外梯度法 (EM)，可以有效地避免算子强单调性的严格要求。EM 的过程如下：
$\{ q_k = P_C(t_k - \tau A t_k), t_{k+1} = P_C(t_k - \tau A q_k) \}$
其中 $P_C$ 表示度量投影，$A$ 是单调的 $L$-Lipschitz 连续算子，且 $\tau \in (0, 1/L)$。EM 最初应用于有限维空间中的鞍点问题。随后，认识到鞍点问题与 VIP 的等价性，众多研究人员将该算法的应用扩展到求解无限维空间中的 VIP，参见例如 [10], [11], [12], [13], [14] 及其中的参考文献。
应当注意的是，EM 要求每次迭代计算两次向可行集的投影，这可能会对迭代效率产生显著影响。为了缓解这一挑战并提高算法的整体性能，众多研究人员致力于解决这一问题。他们的努力旨在减少计算负担并改善 EM 的收敛性质，从而为其在求解 VIP 中的更广泛应用做出贡献。2011 年，Censor 等人 [15] 构建了一个半空间 $T_k$。他们用向 $T_k$ 的投影替代了 EM 中向可行集 $C$ 的第二次投影。这种方法被称为次梯度外梯度法 (SEM)。具体步骤如下：
$\{ q_k = P_C(t_k - \tau A t_k), t_{k+1} = P_{T_k}(t_k - \tau A q_k) \}$
其中 $T_k := \{x \in H : \langle t_k - \tau A t_k - q_k, x - q_k \rangle \leq 0 \}$ 是一个半空间。$P_C, A$ 和 $\tau$ 与 EM 中定义的一样。所提出的算法基于估计步长获得的迭代点构建次梯度半空间。通过利用向该半空间的投影来近似向一般凸区域的投影，该算法简化了投影计算的复杂性。在上述算法的基础上，Thong 和 Hieu [16] 将惯性技术应用于 SEM，产生了一种具有改进收敛性质的新型算法。这一改进已通过数值实验得到验证，进一步证实了其有效性。该算法概述如下：
$\{ s_k = t_k + \alpha_k(t_k - t_{k-1}), q_k = P_C(s_k - \tau A s_k), T_k := \{x \in H : \langle s_k - \tau A s_k - q_k, x - q_k \rangle \leq 0 \}, t_{k+1} = P_{T_k}(s_k - \tau A q_k) \}$
其中 $\{\alpha_k\}$ 是适当选择的序列，$P_C, A$ 和 $\tau$ 与 EM 中定义的一样。
由于这些方法需要事先了解 Lipschitz 常数，众多研究人员探索了避免这一要求的方法。提出了诸如线搜索和自适应性技术等方法，这些方法不需要事先了解 Lipschitz 常数，详见例如 [17], [18], [19], [20] 及其中的参考文献。这些进展旨在简化计算过程，同时保持甚至提高收敛性质。2021 年，Xie 等人 [18] 将线搜索规则应用于 EM，其详细过程如下：
这里，$A$ 是均匀连续的伪单调算子，假设不是 Lipschitz 连续的或单调的。$\{\alpha_k\}, \{\eta_k\}$ 是给定的适当序列，$f: H \to H$ 是压缩映射。通过适当的参数选择，Xie 等人 [18] 证明了算法 1.1 的强收敛结果。
此外，在 SEM 的基础上，Khanh 等人 [21] 将线搜索规则与 Mann 型迭代相结合，构建了以下算法。在适当的参数选择和假设下，他们获得了算法 1.2 的强收敛结果：
本文方法中的几个组件已在相关工作中得到研究。Thong 和 Hieu [17] 将惯性次梯度外梯度步与线搜索过程相结合，用于变分不等式和不动点问题，并在其假设下建立了弱收敛性。Ceng 和 Yuan [22] 研究了涉及多个不动点约束的复合惯性次梯度外梯度方法。Cai, Dong 和 Peng [23] 开发了一种用于具有 Lipschitz 连续算子和准非扩张映射的伪单调变分不等式的惯性粘性外梯度法，并在适当的参数条件下获得了强收敛。这些研究为结合惯性外推、投影步骤和不动点更新提供了基础。
本工作的主要新颖性不在于各个组件——惯性外推 [17], [20]、线搜索规则 [18] 和半压缩不动点步 [21], [24]——而在于通过具有两个独立参数 $\alpha$ 和 $\beta$ 的分裂步长策略将它们综合在一起。与采用单一步长的现有算法 [17], [18], [20], [21], [24] 不同，我们的方法解耦了变分不等式和不动点组件的步长控制，使每个组件可以分别进行自适应调整——当问题数据表现出不同尺度或灵敏度时，这是一个真正的实际优势，而单一步长方案必然在竞争需求之间妥协，往往导致过于保守的选择。受上述工作的启发，我们提出了两种具有以下特征的新算法：
• 我们基于算法 1.1 和 1.2 完善了线搜索规则。此外，为了提高算法的收敛性能，我们引入了一个可调节参数 $\epsilon$，便于选择更合适的数值参数。
• 为了增加参数选择的灵活性，我们引入了两个不同的参数 $\alpha$ 和 $\beta$，它们可以在一定范围内独立调整，旨在优化算法的收敛性能。值得注意的是，当 $\alpha = \beta = 1$ 时，这是 SEM 和算法 1.2 中的常见情况。
• 我们在两种算法中分别引入了粘性迭代和 Mann 型迭代，并通过数值实验验证了算法在不同迭代下的收敛性能。这些迭代旨在提高算法的稳定性和收敛速度，使其更适合求解广泛的数学问题。此外，我们将算法应用于图像恢复问题和控制优化问题，以展示其适用性。我们的结果表明，通过引入这些迭代，算法表现出更好的收敛性，并为数学研究和应用提供了有价值的工具。

章节片段
预备知识
在这一节中，我们回顾一些与本文相关的基本概念和现有结果。
设 $H$ 是一个实希尔伯特空间，$C$ 是 $H$ 的一个非空、闭、凸子集。对于每个点 $x \in H$，存在 $C$ 中唯一的最近点，记为 $P_C(x)$，使得 $P_C(x) := \arg\min \{ \|x-y\|, y \in C \}$。$P_C$ 称为 $H$ 到 $C$ 的度量投影。众所周知，$P_C$ 是非扩张的。
定义 2.1 假设 $T: H \to H$ 是一个非线性算子，且 $Fix(T) \neq \emptyset$，其中 $Fix(T)$ 表示 $T$ 的不动点集。那么，$I-T$

主要结果
在这一节中，为了求解实希尔伯特空间中的变分不等式和不动点问题，我们使用粘性迭代和 Mann 型迭代来获得两种具有线搜索过程的改进次梯度外梯度方法。首先，我们给出以下条件：
条件 C1. 解集 $Fix(T) \cap VI(C, A) \neq \emptyset$。
条件 C2. 算子 $A: H \to H$ 是伪单调的、一致连续的，并满足：
$\{v_k\} \subset C, v_k \rightharpoonup q, \liminf_{k \to \infty} \|A v_k\| = 0 \implies A q = 0$。
条件 C3. 算子 $T: H \to H$ 是 $\lambda$

数值实验
在这一节中，我们展示了几个计算实验，并将第 3 节中提出的方法与文献中的一些现有方法进行比较。所有代码均使用 MATLAB R2023b 编写，并在配备 Intel(R) Core(TM) i5-12500 CPU @ 3.00 GHz, RAM 8.00 GB 的台式 PC 上运行。
例 1 设 $A(x) := Mx + q$，其中
$M = BB^T + C + D$
且 $B$ 是一个 $m \times m$ 矩阵，$C$ 是一个 $m \times m$ 反对称矩阵，$D$ 是一个 $m \times m$ 对角矩阵，其对角线元素为非负数（因此 $M$ 是半正定的），$q$

结论
在本文中，我们引入了两种具有多参数的改进次梯度外梯度方法，用于求解希尔伯特空间中的伪单调变分不等式和不动点问题。惯性技术和改进的线搜索程序的应用消除了对涉及算子的 Lipschitz 连续性条件的需要。在适当的假设下，通过选择合适的参数，我们证明了两个强收敛定理。此外，数值

CRediT 作者贡献声明
Zhongbing Xie: 写作–审阅与编辑，写作–初稿，方法论。Min Li: 写作–审阅与编辑，软件，资金获取。

利益冲突声明
作者声明，他们没有已知的可能影响本文所报告工作的竞争经济利益或个人关系。

Zhongbing Xie|Min Li
数学科学学院，重庆理工大学，重庆，400054，中国