用于伪单调变分不等式的方向增强 Frank-Wolfe 算法

《Communications in Nonlinear Science and Numerical Simulation》:Direction-Enhanced Frank–Wolfe Algorithm for Pseudomonotone Variational Inequalities

【字体: 大 中 小 】 时间:2026年09月21日 来源:Communications in Nonlinear Science and Numerical Simulation 3.8

编辑推荐:

   # 摘要 本文提出了Frank–Wolfe方法的新扩展,用于求解紧凸集上的伪单调变分不等式问题。与传统Frank–Wolfe方法仅依赖标准Frank–Wolfe方向、容易导致锯齿状行为不同,我们采用内循环增强机制动态优化搜索方向。理论分析和数值实验均证实了所提方法相比现有方

  

# 摘要

本文提出了Frank–Wolfe方法的新扩展,用于求解紧凸集上的伪单调变分不等式问题。与传统Frank–Wolfe方法仅依赖标准Frank–Wolfe方向、容易导致锯齿状行为不同,我们采用内循环增强机制动态优化搜索方向。理论分析和数值实验均证实了所提方法相比现有方法具有更高的有效性和稳定性。

# 引言

设$U\subseteq\mathbb{R}^n$为一个非空、闭且凸的集合。给定算子$G:U\to\mathbb{R}^n$,变分不等式问题(VIP)定义为:寻找$u^*\in U$使得

$$\langle G(u^*), u - u^*\rangle \geq 0, \quad \forall u \in U.$$

该问题为建模众多平衡问题和优化问题提供了统一的数学框架[1][2][3]。变分不等式问题的研究可追溯至20世纪60年代,由Hartman和Stampacchia[4]开创,旨在求解无限维空间中的复杂平衡问题。如今,变分不等式问题在众多应用中自然产生,包括:

- **优化视角**:变分不等式问题可视为优化问题的推广。当算子$G$由可微凸函数$g$的梯度$\nabla g$给出时,对应的变分不等式问题即为与$g$相关的约束最小化问题。此时,变分不等式退化为约束凸优化的经典一阶最优性条件[5][6][7]。

- **与不动点问题的联系**:变分不等式问题与不动点问题密切相关。在标准假设下,点$u^*$求解变分不等式问题当且仅当它在基于投影的算子$T(u) = P_U(u - \delta G(u))$下保持不变。这一联系启发了许多基于投影的迭代方案[1]。

- **实际应用**:变分不等式问题被广泛应用于交通流优化、图像处理、最优控制问题求解以及电网运行管理,以确保效率和可靠性[1][8][9][10]。

变分不等式问题的数值方法开发仍是活跃的研究领域,研究者们致力于改善收敛性和计算效率。经典方法如基本投影法[11]已较为成熟,但通常需要强单调性假设才能确保满意的收敛行为。然而,为伪单调和非单调算子设计高效算法仍然是一项具有挑战性的任务。

在伪单调变分不等式问题的求解方法中,研究最为广泛的两种方法是额外梯度法(EG)[7]和Tseng的前向–后向–前向(FBF)法[12]。EG方法采用两步投影:

$$\begin{cases} y_k = P_U(x_k - \alpha G(x_k)), \\ x_{k+1} = P_U(x_k - \alpha G(y_k)), \end{cases}$$

而FBF方法将其简化为单步投影后结合巧妙的代数更新:

$$\begin{cases} y_k = P_U(x_k - \alpha G(x_k)), \\ x_{k+1} = y_k - \alpha (G(y_k) - G(x_k)). \end{cases}$$

然而,这两种方法都存在显著的 computational 缺陷。具体而言,EG方法在每次迭代时需要两次向可行集$U$的正交投影。在高维问题中或当可行集具有复杂几何时,这些重复的投影变得计算代价极高,成为计算瓶颈。另一方面,尽管FBF方法及其扩展(如[10][13])通过仅需一次投影改进了EG方法,但该算法生成的序列可能位于约束集之外。中间迭代点的不可行性往往导致收敛速度降低。

为了克服这一局限性,Frank–Wolfe算法提供了一种有效的替代方案,通过在凸约束上求解线性逼近子问题来实现。Frank–Wolfe类方法也已被扩展到更一般的优化场景,包括某些非凸问题类[14]。与此同时,随着Wolfe型对偶模型在分数规划中的探索以及惯性技术在伪单调变分不等式求解器中的加速应用[15],优化的理论格局也在不断演变。受这些观察的启发,我们提出了针对伪单调和非单调变分不等式问题的Frank–Wolfe类框架。与EG算法(每次迭代需要两次投影)不同,我们的方法用线性最小化预言机(LMO)替代了第一次投影。由于LMO通常比计算正交投影的计算代价更低,所提框架带来了更高的计算效率。此外,通过采用内循环增强机制,所提方法表现出更好的稳定性和收敛特性,即使在使用传统方法时可能出现振荡或不收敛行为的条件下也是如此。

经典的Frank–Wolfe算法往往收敛缓慢,因为通过LMO获得的搜索方向可能严重偏离最优最速下降方向($-G(u_k)$)。这种方向不匹配导致低效的"锯齿状"行为,从而造成收敛缓慢。为了解决这一问题,人们探索了各种增强技术,如引入远离步或面内方向,旨在不显著增加每次迭代计算开销的情况下优化搜索方向[16][17]。在本文中,我们提出了一种新颖的内循环增强Frank–Wolfe算法,专门针对伪单调变分不等式问题设计。我们的方法采用"方向追踪"过程,通过迭代组合多个LMO输出来获得精细化的更新方向。数值实验表明,在迭代次数和计算墙钟时间方面,我们提出的方法均显著优于传统Frank–Wolfe变体和标准基于投影的算法(如额外梯度法以及Yan等人[18]提出的两种方法)。

本文其余部分组织如下:第2节介绍必要的预备知识。第3节专门讨论研究的主要结果,分为两个主要部分。具体而言,3.1节介绍了一种具有显式步长规则的单向Frank–Wolfe算法,并建立了其收敛性。3.2节提出了方向增强Frank–Wolfe算法,该算法集成了"方向追踪"机制,旨在改善搜索方向的对齐并缓解特征性的"锯齿状"行为。第4节展示了若干数值实验和比较,说明了所提算法的有效性。

# 预备知识

**定义2.1** 映射$G:U\to\mathbb{R}^n$被称为:

1. 在$U$上伪单调的,如果对所有的$u, v \in U$,
$$\langle G(u), v - u \rangle \geq 0 \implies \langle G(v), v - u \rangle \geq 0;$$

2. 在$U$上单调的,如果对所有的$u, v \in U$,
$$\langle G(u) - G(v), u - v \rangle \geq 0;$$

3. 在$U$上$\gamma$-强单调的,如果存在$\gamma > 0$使得对所有的$u, v \in U$,
$$\langle G(u) - G(v), u - v \rangle \geq \gamma \|u - v\|^2.$$

可以容易验证以下关系:(3) $\Rightarrow$ (2) $\Rightarrow$ (1)。

与$(G, U)$相关的变分不等式问题,记为VI$(G, U)$,定义为寻找$u^* \in U$使得

$$\langle G(u^*), v - u^* \rangle \geq 0, \quad \forall v \in U.$$

其解集记为

$$U^* := \{u \in U \mid \langle G(u), v - u \rangle \geq 0, \forall v \in U\}.$$

# 主要结果

**假设3.1** 在全文中,我们假设:

(i) $U$是$\mathbb{R}^n$中的非空、闭、有界且凸的子集;

(ii) $G:U\to\mathbb{R}^n$在$U$上Lipschitz连续,即存在$L > 0$使得

$$\|G(u) - G(v)\| \leq L\|u - v\|, \quad \forall u, v \in U;$$

(iii) $G$在$U$上伪单调;

(iv) 原问题解集$U^* := \{u^* \in U \mid \langle G(u^*), v - u^* \rangle \geq 0, \forall v \in U\}$非空。

# 数值结果

在本节中,我们进行数值实验以说明所提方法的有效性。这些实验在配备Intel(R) Core(TM) i5 1235U处理器和8GB内存的笔记本电脑上使用MATLAB R2026a完成。

总体而言,我们通过四个代表性测试类评估所提方法的实际性能。实验旨在评估不仅收敛速度,还包括几何行为、对维度的鲁棒性以及在标准场景之外的适用性。

# 结论

本文提出了两种专门为求解紧凸集上伪单调变分不等式问题而设计的Frank–Wolfe类算法。我们在算子伪单调性和Lipschitz连续性的假设下建立了所提算法的全局收敛性。这些算法的核心优势在于使用线性最小化预言机(LMO)替代了计算代价高昂的正交投影,从而显著降低了每次迭代的计算成本。

# 数据与材料可用性

支持本研究结果的数据可向通讯作者合理请求获取。

# CRediT作者贡献声明

Trinh Ngoc Hai:撰写 – 审阅与编辑、监督、方法论、调查研究。

Nguyen Trong Doan:软件、调查研究。

Nguyen Van Manh:软件、调查研究。

# 利益冲突声明

作者声明他们不存在已知的可能影响本文所述工作的竞争性经济利益或个人关系。

Trinh Ngoc Hai | Nguyen Trong Doan | Nguyen Van Manh

河内科技大学数学与信息学系,越南河内Dai Co Viet街1号
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号