面向函数约束变分不等式问题的镜像下降类算法

# 镜面下降型算法用于带函数约束的变分不等式问题 来源: https://arxiv.org/html/2605.16262

11institutetext:Innopolis University, Innopolis, Universitetskaya Str., 1, 420500, Russia.  
22institutetext:Moscow Institute of Physics and Technology, 9 Institutsky lane, Dolgoprudny, 141701, Russia.  
33institutetext:V. I. Vernadsky Crimean Federal University, 4 Academician Vernadsky Avenue, Simferopol, 295007, Republic of Crimea, Russia.  
33email:[email protected], [email protected], [email protected], [email protected]

###### 摘要

变分不等式在机器学习研究中扮演着关键角色，例如生成对抗网络、强化学习、对抗训练和生成模型。本文致力于研究带函数约束（不等式型约束）的约束变分不等式问题。我们提出了一些镜面下降型算法，这些算法根据迭代点处函数约束的值，在有效步和无效步之间切换，并采用多种不同的步长规则和停止准则。我们分析了所提出的算法，并证明了对于具有有界单调算子和Lipschitz凸函数约束的问题，这些算法在达到所需精度解时具有最优收敛速度。此外，我们还提出了一种修改方案，即在执行有效步时将每个函数约束都纳入计算，同时只考虑第一个违反可行性的约束。当存在多个函数约束时，这种修改可以节省算法的运行时间。同时，我们还针对$\delta$-单调算子提供了所提算法的分析，这使得所提算法作为一个特例，能够应用于无法获得目标函数次梯度精确信息的约束最小化问题。文中还给出了说明所提算法工作和性能的数值实验。

## 引言

变分不等式作为特例，涵盖了众多优化问题，如最小化问题、鞍点问题和不动点问题。它们经常出现在各种数学问题中，例如最优控制、偏微分方程、力学、金融等。它们在解决均衡问题和互补问题[1 (https://arxiv.org/html/2605.16262#bib.bib1)]中扮演着关键角色，并且在机器学习研究中，如生成对抗网络[2 (https://arxiv.org/html/2605.16262#bib.bib2)]、监督/无监督学习[3 (https://arxiv.org/html/2605.16262#bib.bib3),4 (https://arxiv.org/html/2605.16262#bib.bib4)]、对抗训练[5 (https://arxiv.org/html/2605.16262#bib.bib5)]和生成模型[6 (https://arxiv.org/html/2605.16262#bib.bib6),7 (https://arxiv.org/html/2605.16262#bib.bib7)]中也至关重要。众多研究人员致力于探索与解的存在性和稳定性相关的理论方面，并构建求解经典变分不等式（我们所说的经典，是指没有函数“不等式型”约束的问题）的迭代方法。20世纪70年代，外梯度方法的提出[8 (https://arxiv.org/html/2605.16262#bib.bib8)]为求解经典变分不等式的数值方法的发展做出了重要贡献。最近，Nemirovski在其开创性工作[9 (https://arxiv.org/html/2605.16262#bib.bib9)]中提出了该方法的非欧几里得变体，称为Mirror Prox算法，该算法可应用于Lipschitz连续算子。在[10 (https://arxiv.org/html/2605.16262#bib.bib10),11 (https://arxiv.org/html/2605.16262#bib.bib11)]中也提出了具有类似复杂度的不同方法。此外，在[11 (https://arxiv.org/html/2605.16262#bib.bib11)]中，Nesterov提出了一种针对算子有界变分（即非光滑算子）的变分不等式方法。还有大量文献涉及外梯度方法的变体，旨在避免每步迭代采取两步或计算两次梯度等（例如，参见[12 (https://arxiv.org/html/2605.16262#bib.bib12)]）。

另一类重要的变分不等式是带函数约束（不等式型）的问题，参见 (4 (https://arxiv.org/html/2605.16262#S1.E4)) 和 (7 (https://arxiv.org/html/2605.16262#S1.E7))。此类约束的存在使得这些问题更难求解。这类问题出现在数学的许多领域，包括经济均衡模型[13 (https://arxiv.org/html/2605.16262#bib.bib13)]、约束马尔可夫势博弈[14 (https://arxiv.org/html/2605.16262#bib.bib14),15 (https://arxiv.org/html/2605.16262#bib.bib15)]、具有联合凸约束的广义纳什均衡问题[16 (https://arxiv.org/html/2605.16262#bib.bib16)]、分层规划问题[17 (https://arxiv.org/html/2605.16262#bib.bib17)]以及数学物理[18 (https://arxiv.org/html/2605.16262#bib.bib18)]。更多细节和例子请参见[19 (https://arxiv.org/html/2605.16262#bib.bib19)]。此外，这类问题还涵盖了机器学习中的重要应用，包括带安全约束的强化学习[20 (https://arxiv.org/html/2605.16262#bib.bib20)]和带公平性约束的学习[21 (https://arxiv.org/html/2605.16262#bib.bib21),22 (https://arxiv.org/html/2605.16262#bib.bib22)]。

对于带函数约束的变分不等式，先前的工作主要集中于基于（增广）拉格朗日函数的原始-对偶算法来处理约束，以及惩罚方法[23 (https://arxiv.org/html/2605.16262#bib.bib23),24 (https://arxiv.org/html/2605.16262#bib.bib24),25 (https://arxiv.org/html/2605.16262#bib.bib25)]。这些算法及其收敛性保证关键依赖于最优拉格朗日乘子的信息。在[26 (https://arxiv.org/html/2605.16262#bib.bib26)]中，提出了一种无需任何最优拉格朗日乘子信息的原始方法，并证明了其在光滑约束下对于单调算子问题的收敛速度。在[27 (https://arxiv.org/html/2605.16262#bib.bib27)]中，提出了一种一阶方法（ACVI），该方法结合了路径跟踪内点法和原始-对偶方法。在[28 (https://arxiv.org/html/2605.16262#bib.bib28)]中，作者通过取ACVI的最后一次迭代，提出了一种原始-对偶方法来求解带一般函数约束的变分不等式。尽管关于带函数约束的变分不等式已有许多工作，但与现有的经典约束问题工作相比仍然很少。

在本文中，为了求解带函数约束（不等式型）(4 (https://arxiv.org/html/2605.16262#S1.E4)) 和 (7 (https://arxiv.org/html/2605.16262#S1.E7)) 的变分不等式问题，我们提出了多种具有不同步长方案的镜面下降型方法。镜面下降方法用于最小化问题，起源于[29 (https://arxiv.org/html/2605.16262#bib.bib29),30 (https://arxiv.org/html/2605.16262#bib.bib30)]，随后在[31 (https://arxiv.org/html/2605.16262#bib.bib31)]中进行了分析。它被认为是标准次梯度方法的非欧几里得扩展，标准次梯度方法历史悠久，始于文献[32 (https://arxiv.org/html/2605.16262#bib.bib32)]中针对确定性无约束问题和欧几里得设置的方法，以及文献[33 (https://arxiv.org/html/2605.16262#bib.bib33),34 (https://arxiv.org/html/2605.16262#bib.bib34)]中针对约束问题的推广，其中提出了在目标函数次梯度方向和约束次梯度方向之间切换步长的思想。镜面下降法不仅推广了标准次梯度方法，而且获得了更好的收敛速度[35 (https://arxiv.org/html/2605.16262#bib.bib35)]。它也适用于梯度下降不适用的Banach空间中的优化问题[35 (https://arxiv.org/html/2605.16262#bib.bib35)]。关于凸函数约束凸优化问题的一阶方法的一些工作包括（例如，但不限于）[36 (https://arxiv.org/html/2605.16262#bib.bib36),37 (https://arxiv.org/html/2605.16262#bib.bib37),38 (https://arxiv.org/html/2605.16262#bib.bib38),39 (https://arxiv.org/html/2605.16262#bib.bib39)]用于确定性设置，以及[40 (https://arxiv.org/html/2605.16262#bib.bib40),41 (https://arxiv.org/html/2605.16262#bib.bib41)]用于随机设置。

本文由引言和五个主要部分组成，外加四个附录。在第1节 (https://arxiv.org/html/2605.16262#S1) 中，我们提到了变分不等式的一些基本事实、定义和工具。第2节 (https://arxiv.org/html/2605.16262#S2) 专门介绍所提出的算法。我们提出了7种算法，具有不同的步长规则和停止准则。在第3节 (https://arxiv.org/html/2605.16262#S3) 中，我们分析了所提出的算法，并证明了它们对于具有有界单调算子和Lipschitz函数约束的变分不等式问题类具有最优收敛速度。在第4节 (https://arxiv.org/html/2605.16262#S4) 中，我们提出了对前一节中算法的修改。在这种修改中，当执行有效步时，我们考虑每个约束，以及第一个违反可行性的约束。在第5节 (https://arxiv.org/html/2605.16262#S5) 中，我们给出了数值实验，比较了所提算法在求解一些约束变分不等式和鞍点问题上的表现。在最后一节，第6节 (https://arxiv.org/html/2605.16262#S6) 中，我们回顾了所得结果。在附录中，我们提供了关于所提算法分析的定理证明，以及当算子为$\delta$-单调时的分析。我们还提供了关于Forsaken游戏的额外实验。

## 1 基础知识

设 $( \mathbf{E}, \| \cdot \| )$ 是一个赋范有限维向量空间，具有任意范数 $\| \cdot \|$，且 $\mathbf{E}^*$ 是 $\mathbf{E}$ 的共轭空间，其范数为
\[
\| y \|_* = \max_{x \in \mathbf{E}} \{ \langle y, x \rangle : \|x\| \leq 1 \},
\]
其中 $\langle y, x \rangle$ 是连续线性泛函 $y \in \mathbf{E}^*$ 在 $x \in \mathbf{E}$ 处的值。

令 $Q \subset \mathbf{E}$ 是一个凸紧集，直径为 $D > 0$，且 $\psi : Q \longrightarrow \mathbb{R}$ 是一个正常闭可微且 $\sigma$-强凸的函数（称为 prox-函数或距离生成函数）。对应的 Bregman 散度定义为
\[
V(x, y) = \psi(x) - \psi(y) - \langle \nabla \psi(y), x - y \rangle \quad \forall x, y \in Q.
\]
对于 Bregman 散度，成立以下不等式
\[
V(x, y) \geq \frac{\sigma}{2} \| y - x \|^2 \quad \forall x, y \in Q. \tag{1}
\]

对于所有 $x \in Q$ 和 $p \in \mathbf{E}^*$，近端映射算子定义为
\[
\operatorname{Mirr}_x(p) = \arg\min_{u \in Q} \big\{ \langle p, u \rangle + V(u, x) \big\}.
\]
我们假设 $\operatorname{Mirr}_x(p)$ 易于计算。

以下众所周知的引理描述了凸函数近端映射算子的主要性质。

###### 引理 1
设 $f : Q \longrightarrow \mathbb{R}$ 是凸集 $Q$ 上的凸次可微函数，且对于某个 $h > 0$ 和 $y, z \in Q$，有 $z = \operatorname{Mirr}_y(h \nabla f(y))$。则对于每个 $x \in Q$，我们有
\[
h \left( f(y) - f(x) \right) \leq h \langle \nabla f(y), y - x \rangle \leq \frac{h^2}{2} \| \nabla f(y) \|_*^2 + V(x, y) - V(x, z). \tag{2}
\]

考虑一组凸次可微泛函 $g_i : Q \longrightarrow \mathbb{R}, i=1,2,\ldots,m$。此外，我们假设所有 $g_i$ 是 Lipschitz 连续的，具有某个常数 $M_{g_i} > 0$，即
\[
\left| g_i(x) - g_i(y) \right| \leq M_{g_i} \| x - y \| \quad \forall \; x, y \in Q \; \; \text{and} \; \; i=1,\ldots,m. \tag{3}
\]
这意味着在每个点 $x \in Q$ 和对于每个 $i=1,\ldots,m$，存在一个次梯度 $\nabla g_i(x)$，使得 $\| \nabla g_i(x) \|_* \leq M_{g_i}$。

在本文中，我们考虑以下约束变分不等式问题：
\[
\text{Find} \quad x^* \in Q:
\quad \langle F(x), x^* - x \rangle \leq 0 \quad \forall x \in Q, \tag{4}
\]
\[
\text{and} \quad g_i(x) \leq 0 \quad \forall i=1,2\ldots,m,
\]
其中 $F : Q \longrightarrow \textbf{E}^*$ 是一个连续单调算子，即
\[
\langle F(x) - F(y), x - y \rangle \geq 0 \quad \forall x, y \in Q. \tag{5}
\]

显然，我们可以将一组 Lipschitz 连续泛函 $\{ g_i(\cdot) \}_{i=1}^m$ 视为一个 Lipschitz 连续泛函约束 $g : Q \longrightarrow \mathbb{R}$，使得
\[
g(x) = \max_{1 \leq i \leq m} \{ g_i(x) \}, \quad \| g(x) - g(y) \| \leq M_g \| x - y \| \; \quad \forall \; x, y \in Q, \tag{6}
\]
其中 $M_g = \max_{1 \leq i \leq m} \{ M_{g_i} \}$。因此，问题 (4 (https://arxiv.org/html/2605.16262#S1.E4)) 等价于以下问题：
\[
\text{Find} \quad x^* \in Q:
\quad \langle F(x), x^* - x \rangle \leq 0 \quad \forall x \in Q, \tag{7}
\]
\[
\text{and} \quad g(x) \leq 0.
\]

我们说算子 $F$ 在 $Q$ 上有界，如果存在 $L_F > 0$ 使得
\[
\| F(x) \|_* \leq L_F, \quad \forall x \in Q. \tag{8}
\]

为了强调问题 (4 (https://arxiv.org/html/2605.16262#S1.E4))（或 (7 (https://arxiv.org/html/2605.16262#S1.E7))）在不考虑函数约束（作为特例）时的广泛性，我们提及变分不等式的三个常见特例。

###### 例 1 (最小化问题)
考虑最小化问题
\[
\min_{x \in Q} f(x), \tag{9}
\]
并假设 $F(x) = \nabla f(x)$，其中 $\nabla f(x)$ 表示 $f$ 在 $x$ 处的（次）梯度。那么，如果 $f$ 是凸的，可以证明 $x^* \in Q$ 是 (4 (https://arxiv.org/html/2605.16262#S1.E4))（不考虑函数约束）的解当且仅当 $x^* \in Q$ 是 (9 (https://arxiv.org/html/2605.16262#S1.E9)) 的解。

###### 例 2 (鞍点问题)
考虑鞍点问题
\[
\min_{u \in Q_u} \max_{v \in Q_v} f(u, v), \tag{10}
\]
并假设 $F(x) := F(u,v) = \left( \nabla_u f(u,v), -\nabla_v f(u,v) \right)^\top$，其中 $Q = Q_u \times Q_v$，且 $Q_u \subseteq \mathbb{R}^{n_u}, Q_v \subseteq \mathbb{R}^{n_v}$。那么如果 $f$ 关于 $u$ 是凸的，关于 $v$ 是凹的，可以证明 $x^* \in Q$ 是所谓的...（原文未完，但此处按原文停止翻译）