一种基于并行投影的求解变分不等式问题的方法

《Journal of Computational and Applied Mathematics》：A parallel projection-based method for solving variational inequality problems

　　

## 摘要

在本文中，我们提出了一种求解可微凸函数水平集上拟单调变分不等式问题的新方法。与正交投影不同，我们使用计算效率更高的平行投影。我们的方法涉及构建一个基于平行投影的动力系统，并证明该系统具有一个全局解，该解收敛于变分不等式问题的期望解。对该动力系统进行离散化，得到了一个新的迭代格式。理论分析和数值实验均证实了所提方法相对于基于正交投影的传统方法的有效性。

## 引言

变分不等式问题（VIP）是指：找到 $x^* \in C$ 使得
$$\langle F(x^*), y - x^* \rangle \geq 0, \quad \forall y \in C,$$
其中 $C$ 是 $\mathbb{R}^n$ 中的一个非空闭凸子集，$F: \mathbb{R}^n \to \mathbb{R}^n$。记 $Sol(F, C)$ 为 $VI(F, C)$ 的解集，假设全文中该解集非空。

VIP 是一个自然产生于多个领域的数学工具，涵盖理论领域和应用科学（[1]、[2]、[3]）。其理论意义在于它作为一个统一框架的能力和普适性，涵盖并推广了以下关键概念：

- **在优化中**：当函数 $F$ 是可微凸函数 $f$ 的梯度（即 $F = \nabla f$）时，问题 $VI(F, C)$ 退化为 $x^*$ 是 $f$ 在集合 $C$ 上的极小值点的充要条件（约束问题的Karush-Kuhn-Tucker条件）。因此，VIP 为研究约束优化问题提供了一个框架（见[4]、[5]、[6]）。
- **在不动点分析中**：问题 $VI(F, C)$ 与寻找映射 $T(x) = P_C(x - \delta F(x))$ 的不动点密切相关，其中 $P_C$ 是到可行集 $C$ 的正交投影（见[1]、[3]）。
- **在工程和应用科学中**：VIP 用于描述网络中的平衡态、交通流、接触力学和能源系统。其多功能性和坚实的理论基础使其成为分析和求解涉及均衡、竞争和稳定性的现实问题的有力工具（[1]、[7]、[8]）。

VIP 数值方法的设计与发展是一个充满活力的领域，来自许多研究小组的持续努力和贡献。一些流行的方法包括：基本投影（[1]、[2]、[9]）、外梯度投影（[6]、[10]）和超平面投影（[11]）。通常，为了确保收敛性，现有方法是针对特定类别的变分不等式设计的，由算子 $F$ 的单调性性质决定（例如，单调、强单调等）。本文所处理的 VIP 仅限于算子 $F$ 满足定义 2.1 中意义的拟单调性的情况。与此设置相关的是直接算法（Direct Algorithm），最初由[12]提出：
$$\begin{cases} x_0 \in C, \\ x_{k+1} = P_C\left[x_k - \alpha_k \frac{F(x_k)}{\max\{1; \|F(x_k)\|\}}\right]. \end{cases} \tag{1}$$
在假设 $\sum_{k=0}^{\infty} \alpha_k = \infty$，$\sum_{k=0}^{\infty} \alpha_k^2 < \infty$ 的条件下，[12] 证明了由直接算法 (1) 生成的序列 $\{x_k\}$ 收敛于 $VI(F, C)$ 的一个解。最近，[13] 将该算法发展为动力系统：
$$\begin{cases} x(0) \in C, \\ x'(t) = P_C\left[x(t) - \alpha(t) \frac{F(x(t))}{\max\{1; \|F(x(t))\|\}}\right] - x(t). \end{cases} \tag{2}$$
在假设 $\int_0^{\infty} \alpha(t) dt = \infty$，$\int_0^{\infty} \alpha^2(t) dt < \infty$ 的条件下，建立了 $x(t)$ 收敛于 $VI(F, C)$ 一个解的结论。动力系统 (2) 的收敛条件与[12]所述的条件呈现明显的类似性；然而，建立其收敛性分析需要应用源自常微分方程理论框架的高级方法。从算法到其连续对应物产生了常微分方程。反之，算法本身可以通过常微分方程的离散化来设计（见[14]）。

上述方法以及许多其他方法（如[15]、[16]、[17]、[18]、[19]、[20]、[21]）的一个显著缺点是需要使用正交投影 $P_C$。该操作引入了相当大的计算负担，因为计算一个点到约束集 $C$ 的正交投影，从根本上要求在每次迭代中求解一个辅助优化问题。这一观察激励我们将正交投影替换为计算更简单的操作，即平行投影。

**定义 1** 设 $C \subset \mathbb{R}^n$ 为一个闭集，$x \in \mathbb{R}^n$，$d \neq 0$ 为 $\mathbb{R}^n$ 中的一个向量。如果集合 $\{t \geq 0: x + td \in C\}$ 非空，则点 $y = x + t_0 d$，其中
$$t_0 = \min\{t \geq 0: x + td \in C\}$$
称为 $x$ 沿方向 $d$ 到 $C$ 的平行投影。我们记 $y = \Pi_d^C(x)$。

由于 $C$ 是闭的且映射 $t \mapsto x + td$ 是连续的，集合 $\{t \geq 0: x + td \in C\}$ 在 $[0, \infty)$ 中是闭的。因此，每当该集合非空时，它必有一个唯一的最小元素，从而平行投影是良定义的。一般来说，计算平行投影比正交投影的计算成本低得多。

在本文中，我们研究问题 $VI(F, C)$ 的特定情况，其中：

- 算子 $F$ 是拟单调或强伪单调的；
- 约束集 $C$ 由 $C := \{x \in \mathbb{R}^n: g(x) \leq 0\}$ 给出，其中 $g: \mathbb{R}^n \to \mathbb{R}$ 假设为可微且凸的。

尽管平行投影为替代正交投影提供了一种有吸引力的方案，但它并不是唯一旨在减轻投影步骤计算负担的方法。文献中已提出多种替代正交投影的方法，包括次梯度投影方法、切割平面方法和无投影技术（见[7]、[22]、[23]、[24]、[25]）。次梯度和切割平面方法用适当的支持半空间替代原始可行集，而无投影方法则通过每次迭代求解一个线性极小化子问题来完全避免投影。

我们的方法与这些方法有根本性的不同。我们不是近似可行集或用线性优化预言机替换投影步骤，而是保留原始可行集，用沿约束函数梯度方向的平行投影替换正交投影。这一替换自然地导致一个连续时间动力系统，其时间离散化得到一个高效的迭代算法。此外，在拟单调性和强伪单调性假设下，连续和离散两种形式的收敛性分析均已建立。这些特征将所提框架与现有的基于投影和无投影方法区分开来，构成了本文的主要创新点。

本文其余部分的组织结构如下。

在第 2 节中，我们介绍一些与平行投影相关的基本概念和辅助引理。

在第 3 节中，我们提出基于平行投影的动力系统来求解问题 $VI(F, C)$。分析从定理 3.1 中建立此类系统的全局存在性准则开始。随后的收敛性结果在定理 3.5 和 3.7 中建立，两者均受益于对函数 $g$ 条件的放松，相较于定理 3.1 的要求。定理 3.5 和 3.7 之间的主要区别在于对算子 $F$ 的假设：定理 3.5 要求在（可能无界的）集合 $C$ 上具有拟单调性，而定理 3.7 要求在有界集上具有强伪单调性。值得注意的是，定理 3.7 中对 $F$ 更强的单调性要求提供了一种权衡，使得对其他参数的条件可以比定理 3.5 中施加的条件更为宽松。

数值框架的构建在第 4 节中涵盖，其中我们给出了动力系统的离散化，并正式定义了基于平行投影的结果新迭代算法。随后在定理 4.4 和 4.6 中进行收敛性分析。与连续时间情况类似，分析受 $F$ 的性质支配：定理 4.4 专用于拟单调设置，而定理 4.6 处理强伪单调设置。值得注意的是，定理 4.6 中 $F$ 的强单调性显著改善了对其余参数的条件，使其比定理 4.4 中为较少受限的拟单调情况推导出的条件更为宽松。

在第 5 节中，我们通过数值实验说明该方法的有效性和优势。我们的比较专门针对直接算法 (1) 和动力系统 (2)，因为它们的收敛性分析共享拟单调性和使用平方可和但不可和的步长的要求。

## 节选片段

### 预备知识

在本节中，我们回顾一些将在论文中使用的定义和性质。

**定义 2** 映射 $A: C \to \mathbb{R}^n$ 被称为：
1. **在 $C$ 上单调的**，如果对所有的 $x, y \in C$，$\langle A(x) - A(y), x - y \rangle \geq 0$；
2. **在 $C$ 上拟单调的**，如果它在 $C$ 上单调且对所有的 $x, y \in C$，$\langle A(x) - A(y), x - y \rangle = 0 \Rightarrow A(x) = A(y)$；
3. **在 $C$ 上 $\gamma$-强单调的**，如果对所有的 $x, y \in C$，$\langle A(x) - A(y), x - y \rangle \geq \gamma \|x - y\|^2$；
4. **在 $C$ 上 $\gamma$-强伪单调的**，如果对所有的 $x, y \in C$，$\langle A(y), x - y \rangle \geq 0 \Rightarrow \langle A(x), x - y \rangle \geq \gamma \|x - y\|^2$。

**引理 2.1** [26] 设 $\{a_k\}$, $\{b_k\} \subset (0, \infty)$ 为两个序列，满足
$$a_{k+1} \leq a_k + b_k, \quad \forall k \geq 0.$$
如果 $\sum_{k=0}^{\infty} b_k < \infty$，则 $\lim_{k \to \infty} a_k$ 存在。

### 基于平行投影的动力系统

为了求解问题 $VI(F, C)$，我们提出如下动力系统：
$$\begin{cases} y(t) = x(t) - \beta(t) \frac{F(x(t))}{\max\{\|F(x(t))\|; 1\}}, \\ x'(t) = -x(t) + \Pi(y(t)), \quad \forall t \geq 0, \\ x(0) = x_0, \end{cases} \tag{6}$$
其中映射 $\Pi$ 由 (4) 给出。主要结果如下。定理 3.1 建立了动力系统 (6) 解的全局存在性条件。随后的收敛性分析在定理 3.5 和 3.7 中给出，两者均利用了对函数 $g$ 比定理 3.1 所需条件更为宽松的假设。收敛性分析依赖于...

### 动力系统的离散时间化

在本节中，我们对动力系统 (6) 进行离散化，得到以下算法：

**步骤 0**：选择 $x_0 \in C$。

**步骤 1**：给定 $x_k$。如果 $F(x_k) = 0$，则停止；否则计算 $x_{k+1}$ 如下：
$$\begin{cases} y_k = x_k - \beta_k \frac{F(x_k)}{\max\{\|F(x_k)\|; 1\}}, \\ x_{k+1} = \Pi(y_k). \end{cases}$$

**步骤 2**：如果 $x_{k+1} = x_k$，则停止。否则，更新 $k := k+1$ 并返回步骤 1。

### 数值实验

在本节中，我们通过数值实验比较了平行投影和正交投影的效率，其中集合 $C$ 被选择为椭圆体或抛物面。对于这样的集合 $C$，可以获得平行投影的闭式表达式。

考虑 $C$ 为椭圆体的情况：
$$C := \{x \in \mathbb{R}^n \mid \langle x - c, D^{-1}(x - c) \rangle \leq 1\},$$
其中 $D = \text{diag}(d_1, \cdots, d_n)$，$d_i > 0$。设 $x_0 \in \mathbb{R}^n \setminus C$ 且 $d \neq 0$ 为一个向量，使得平行投影 $x_p := \Pi_d^C(x_0)$ 存在。我们有
$$g(x) = \langle x - c, D^{-1}(x - c) \rangle - 1,$$
以及 $x_p$ 为...

## 结论

在本工作中，我们引入了一种求解可微凸函数水平集上拟单调变分不等式的新方法。通过使用平行投影代替正交投影，所提出的方法实现了更高的计算效率。基于平行投影的动力系统 (6) 被引入并证明具有一个全局解，该解收敛于问题 $VI(F, C)$ 的一个解。此外，其离散化导致了一个有效的迭代格式。

### 利益冲突声明

作者声明他们没有已知的可能影响本文工作的竞争性财务利益或个人关系。

Pham Viet Hai | Trinh Ngoc Hai | Nguyen Trong Doan
河内科技大学数学与信息学院，越南河内大陈国街 1 号