求解变分不等式的外部近似投影方法

《Communications in Nonlinear Science and Numerical Simulation》：Outer approximation projection methods for solving variational inequalities

　　

**摘要**

在本研究中，我们研究了求解变分不等式的新近似投影方法。一个显著特点是我们提出了两个解映射并证明了它们的拟非扩张性。利用这些映射，我们开发了两个求解具有利普希茨连续代价映射的变分不等式问题的近似投影算法，该算法既适用于强单调情形，也适用于单调情形，并建立了所得迭代序列的收敛性。最后，我们在若干个显式算例上测试了所提出的方法，并观察到其实际性能与文献中若干使用近似投影的相关方法相当，在某些情况下表现更优。

**引言**

设 $\mathcal{R}^n$ 为配备内积 $\langle \cdot, \cdot \rangle$ 及其诱导范数 $\|\cdot\|$ 的 $n$ 维欧几里得实空间。设 $C \subset \mathcal{R}^n$ 为一个非空、闭的凸集。我们考虑如下变分不等式问题，简记为 VI$(C, F)$：

$$\text{求 } \hat{x} \in C \text{ 使得 } \langle F(\hat{x}), x - \hat{x} \rangle \geq 0, \quad \forall x \in C.$$

映射 $F: \mathcal{R}^n \to \mathcal{R}^n$ 通常称为代价映射，且 $c_i: \mathcal{R}^n \to \mathcal{R}$，对每个 $i \in I := \{1, 2, \cdots, m\}$，是下半连续、凸且 Gateaux 可微的，并且 $C = \bigcap_{i \in I} \{x \in \mathcal{R}^n : c_i(x) \leq 0\}$ 满足 Slater 条件。如通常所记，问题 VI$(C, F)$ 的解集记为 $\Omega(C, F)$。注意当 $F$ 是单调的时，$\Omega(C, F)$ 是凸的[1, 命题 1.1.2]。

问题 VI$(C, F)$ 涉及广泛的实际问题，如纳什合作博弈论、网络分析、优化、不动点理论和运筹学[2]–[7]。值得注意的是，近年来，当代价映射 $F$ 为单调时，已有许多有效方法用于求解问题 VI$(C, F)$。让我们简要回顾一些优秀的求解方法，如 Rockafellar[8] 的 PPM（近端点方法）、Solodov 等[9]、[10] 的 PM（投影方法）、Burachik 等[11]、[12] 的 IPPM（非精确近端点方法）、Censor 等[13]、[14] 的 SEM（次梯度额外梯度方法）、Malitsky 和 Semenov[15]、[16] 的 RPGM（反射投影梯度方法）、Gibali 等[17]、[18] 的 OAM（外近似方法）、Cegielski 和 Zalas[19]、[20] 的 FPIM（不动点迭代方法）、Shehu 和 Iyiola[21]、[22] 的 IEM（惯性额外梯度方法）、Yang 等[23]、[24]、[25] 的 MSEM（改进次梯度额外梯度方法）以及许多其他方法[8]、[21]、[26]–[37]和其中引用的文献。这些求解方法中，大多数在每次迭代时使用一次或两次投影。注意在某些约束 $C$ 的情况下，$\Pi_C: \mathcal{R}^n \to C$ 可以以简单形式计算。例如，当集 $C$ 为非负象限、箱型、半空间或两个半空间的交集时，则对所有 $x \in \mathcal{R}^n$，$\Pi_C(x)$ 均具有显式形式。然而，在一些 $C$ 的一般情形下，投影 $\Pi_C$ 的计算代价过高。

受可行集 $C$ 可能具有复杂结构的实际应用所启发，并借鉴 He 和 Wu[38] 的工作，He 等人在[39]中提出了 TRSSEM（完全松弛自适应次梯度额外梯度方法）用于求解问题 VI$(C, F)$。其迭代步骤将下一迭代点 $x_{k+1}$ 计算如下：

$$y_k = \Pi_{C_k}[x_k - \beta_k F(x_k)], \quad x_{k+1} = \Pi_{H_k}[x_k - \beta_k F(y_k)],$$

其中 $C = \{x \in \mathcal{R}^n : c_i(x) \leq 0\}$，$c_i: \mathcal{R}^n \to \mathcal{R}$ ($i \in \{1, 2, \ldots, m\}$) 是凸且可微的，

$$C_k := \{x \in \mathcal{R}^n : c_i(x_k) + \langle \nabla c_i(x_k), x - x_k \rangle \leq 0, \quad i \in \{1, 2, \ldots, m\}\},$$

$$H_k := \{x \in \mathcal{R}^n : \langle x_k - \beta_k F(x_k) - y_k, x - y_k \rangle \leq 0\},$$

$\beta_k$ 通过 Armijo 线搜索技术计算。

在外近似方向上，Gibali 等人在[18, 定理 3.1]中最近研究了用一类称为 cutter 的拟非扩张算子 $T_k$ 的不动点集 $T_k$ 从外部近似约束 $C$ 的 VI$(C, F)$ 问题，其中 $C \subset \text{Fix}(T_k)$。迭代序列 $\{x_k\}$ 的显式形式如下：

$$x_{k+1} = \Pi_{H_k}[x_k - \lambda_k F(x_k)],$$

其中 $R_k := Id + \alpha_k(\Pi_{H_k} - Id)$，$H_k := \{z : \langle z - T_k(x_k), x_k - T_k(x_k) \rangle \leq 0\}$，$Id$ 表示恒等映射。$\{x_k\}$ 的收敛性要求 $F$ 强单调且利普希茨连续。

众所周知，求解问题 VI$(C, F)$ 的一种流行方法是利用度量投影 $\Pi_C$ 的解映射方法。事实上，一个点 $q^* \in C$ 属于解集 $\Omega(C, F)$ 当且仅当 $q^* \in \text{Fix}(S_\lambda)$，其中

$$S_\lambda(x) = \Pi_C[x - \lambda F(x)], \quad \forall x \in \mathcal{R}^n,$$

其中 $\lambda > 0$。当 $F$ 是 $L$-利普希茨连续且 $\theta$-强单调时，在[40, 定理 5]中，在限制 $0 < \lambda < \frac{2\theta}{L^2}$ 下，映射 $S_\lambda$ 是收缩的。然后，可以利用 Banach 收缩映射原理求解问题 VI$(C, F)$ 来找到解映射 $S_\lambda$ 的唯一不动点。当 $F$ 是单调且利普希茨连续时，在[41, 引理 3.1]中，基于 SEM 方法，Kraikaew 和 Saejung 提出了映射 $G_\tau: \mathcal{R}^n \to \mathcal{R}^n$，如下所示，对每个 $x \in \mathcal{R}^n$：

$$G_\tau(x) = \Pi_{K_x}[x - \tau F(\Pi_C(x - \tau F(x)))],$$

$$K_x = \{w \in \mathcal{R}^n : \langle x - \tau F(x) - \Pi_C(x - \tau F(x)), w - \Pi_C(x - \tau F(x)) \rangle \leq 0\}.$$

然后，在条件 $0 < \tau < \frac{1}{L}$ 下，映射 $G_\tau$ 是拟非扩张的。然而，它不是强拟非扩张的。此外，

$$\|G_\tau(x) - q^*\|^2 \leq \|x - q^*\|^2 - (1 - \tau L)\|x - \Pi_C(x - \tau F(x))\|^2 - (1 - \tau L)\|G_\tau(x) - \Pi_C(x - \tau F(x))\|^2, \quad \forall q^* \in \Omega(C, F).$$

作者证明了 $\Omega(C, F) \subset \text{Fix}(G_\tau)$，并且求解问题 VI$(C, F)$ 等价于寻找 $G_\tau$ 的一个不动点。然而，在计算解映射 $G_\tau$ 时存在一个困难问题，即投影 $\Pi_C$ 的计算。

在本文中，我们专注于与问题 VI$(C, F)$ 相关的两个新外近似映射：

- 对所有 $\chi > 0$，我们提出 $\Psi_\chi: \mathcal{R}^n \to \mathcal{R}^n$，其形式为

$$\Psi_\chi(x) = \Pi_{C_x}[x - \chi F(x)], \quad \forall x \in \mathcal{R}^n, \tag{1}$$

其中 $\nabla c_i(x)$ 是函数 $c_i$ 在 $x$ 处的梯度向量，$C_x := \bigcap_{i \in I} \{y \in \mathcal{R}^n : c_i(x) + \langle \nabla c_i(x), y - x \rangle \leq 0\}$。

- 对每个 $\gamma > 0$，$\chi > 0$ 和 $\zeta > 0$，映射 $T_{\chi, \zeta}: \mathcal{R}^n \to \mathcal{R}^n$ 给出如下：

$$T_{\chi, \zeta}(x) = \Pi_{W_x}[x - \chi \zeta F(\Psi_\chi(x))], \quad \forall x \in \mathcal{R}^n, \tag{2}$$

其中 $\Psi_\chi(x)$ 定义在(1)中，对每个 $x \in \mathcal{R}^n$，$W_x$ 是由

$$W_x = \{t \in \mathcal{R}^n : \langle x - \chi F(x) - \Psi_\chi(x), t - \Psi_\chi(x) \rangle \leq \gamma \|x - \Psi_\chi(x)\|^2\}$$

定义的半空间。

**注 2.1** 令 $\gamma = 0$，$\zeta = 1$ 且 $\chi := \beta_k$，由 $x_{k+1} = T_{\chi, \zeta}(x_k)$ 定义的序列 $\{x_k\}$，则序列 $\{x_k\}$ 可以写成算法 TRSSEM 的形式。

受现有研究的启发和激励，通过使用定义在(1)中的映射 $\Psi_\chi$ 和定义在(2)中的映射 $T_{\chi, \zeta}$，我们的贡献体现在以下三个方面：第一，我们证明两个解映射 $\Psi_\chi$ 和 $T_{\chi, \zeta}$ 的不动点集与解集 $\Omega(C, F)$ 重合。第二，我们在 $F$ 的局部单调和利普希茨连续假设下，证明了 $T_{\chi, \zeta}$ 的强拟非扩张性和 $\Psi_\chi$ 的强收缩性。第三，利用这些映射，我们设计了求解问题 VI$(C, F)$ 的新算法，然后证明了所提出算法的收敛性。我们的收敛定理与当前结果所提出的方案有很大不同。事实上，我们不需要在每次迭代时计算到集 $C$ 的投影。

本文其余部分组织如下。在第2节中，我们给出一些概念、若干有用结果以及解映射与解集 $\Omega(C, F)$ 之间的关系。收敛性定理在第3节给出。第4节展示了所提出算法的一些计算和讨论。

**分节片段**

**外近似解映射**

记号说明：
- 序列 $\{x_k\} \subset \mathcal{R}^n$ 收敛到 $x$ 记为 $x_k \to x$；
- 点 $x \in \mathcal{R}^n$ 到非空、凸、闭子集 $C \subset \mathcal{R}^n$ 上的投影记为 $\Pi_C(x)$。

根据定义，我们得到

$$\|\Pi_C(x) - x\| \leq \|y - x\|, \quad \forall y \in C.$$

然后，对每个 $x \in \mathcal{R}^n$，$v \in C$，以下不等式成立：

$$\|\Pi_C(x) - v\|^2 \leq \|x - v\|^2 - \|x - \Pi_C(x)\|^2.$$

我们回顾到半空间 $D := \{y \in \mathcal{R}^n : \langle a, y \rangle \leq b\}$ 上的度量投影的显式公式，其中 $0 \neq a \in \mathcal{R}^n$ 且 $b \in \mathcal{R}$。则以下关系成立：

$$\Pi_D(x) = \begin{cases} x - \frac{\langle a, x \rangle - b}{\|a\|^2} a, & \text{若 } x \notin D, \\ x, & \text{否则。} \end{cases}$$

对每个 $i \in I$，函数 $c_i: \mathcal{R}^n \to \mathcal{R}$ 被称为 Gateaux 可微的。

**外近似方案**

在本节中，我们应用上述解映射 $\Psi_\chi$ 和 $T_{\chi, \zeta}$ 的性质，提出新的外近似方案来求解问题 VI$(C, F)$。

**定理 4.1** 设代价映射 $F$ 是 $\eta$-强单调且 $L$-利普希茨连续的，且函数 $c_i$ ($i \in I$) 满足假设 (C1)、(C3) 和 (C4)。设 $\{x_k\}$ 是由以下公式定义的序列：

$$x_k \in \mathcal{R}^n, \quad x_{k+1} = \Pi_{C_{x_k}}[x_k - \chi F(x_k)], \quad \forall k \geq 0,$$

其中 $C_{x_k} := \bigcap_{i \in I} \{y \in \mathcal{R}^n : c_i(x_k) + \langle \nabla c_i(x_k), y - x_k \rangle \leq 0\}$，且 $\chi$ 满足限制条件(20)。则 $\{x_k\}$ 收敛到 $q^* \in \Omega$。

**数值实验**

在每次迭代 $k$ 中，容易看出定理 4.2 和定理 4.3 中的投影 $\Pi_{W_{x_k}}$ 可以以显式形式计算：

$$\Pi_{W_{x_k}}[x_k - \chi \zeta F(y_k)] = x_k - \chi \zeta F(y_k) - \frac{\langle v_k, w - y_k \rangle - \gamma \|x_k - y_k\|^2}{\|v_k\|^2} v_k,$$

其中 $v_k = x_k - \chi F(x_k) - y_k$。

现在我们讨论在定理 4.1–4.3 中，在每次迭代 $k$ 处投影 $\Pi_{C_{x_k}}[x_k - \chi F(x_k)]$ 的计算。我们考虑集 $C$ 的以下情形：

**情形 1：** 当 $m = 1$ 时，集的形式为 $C := \{x \in \mathcal{R}^n : c(x) \leq 0\}$，其中 $c: \mathcal{R}^n \to \mathcal{R}$ 是下半连续、凸且 Gateaux 可微的。显然 $\Pi_{C_{x_k}}[x_k - \chi$……

**结论**

本文提出了两个关于变分不等式的新解映射。我们声称，如果 $F$ 是单调且利普希茨连续的，则这两个映射具有强拟非扩张性或强收缩性。然后，利用这些解映射和到多面体的度量投影技术构建外近似方案。这里一个非常有趣的现象是，我们不需要在每次迭代时计算到集 $C$ 的投影。

**未引用的浮动体** 图 1 和图 2。

**未引用的参考文献** [51]

**资金支持** 无资金支持。

**作者贡献声明**

Nong Thu Trang：写作 – 审阅与编辑，软件，方法论，形式分析，概念化。

Do Duy Thanh：写作 – 审阅与编辑，写作 – 初稿，软件，方法论，调查，形式分析。

Cao Thi Thu Trang：写作 – 审阅与编辑，写作 – 初稿，软件，方法论，调查，形式分析。

Pham Ngoc Anh：写作 – 审阅与编辑，写作 – 初稿，指导，资源，方法论，形式分析，概念化。

**利益冲突声明** 作者声明他们不存在利益冲突。

Nong Thu Trang | Do Duy Thanh | Cao Thi Thu Trang | Pham Ngoc Anh

数学系，越南河内市延华区 trung Kinh 街 171 号 ph??ng ??ng 大学