基于纤维丛的变分不等式路径跟踪求解框架 A path-following framework on fiber bundle for variational inequalities
将VI解集几何化为纤维丛，用路径跟踪加纤维跳跃实现无假设的全局线性收敛
前置知识
变分不等式（VI）
给定紧凸集 $K\subseteq\mathbb{R}^n$ 与连续映射 $H:K\to\mathbb{R}^n$，变分不等式 $\mathrm{VI}(H,K)$ 要找 $x^\star\in K$ 使得 $\langle H(x^\star), x'-x^\star\rangle\ge 0$ 对所有 $x'\in K$ 成立。它是优化、博弈论、经济学均衡、交通分配等问题的统一语言：取 $H=-\nabla f$ 时退化为约束优化的一阶最优性条件，取 $H$ 为多个玩家梯度时描述纳什均衡。
本文的目标就是给出求解一般 VI 的通用算法，全文理论（FPKKT、纤维丛、路径、收敛证明）全部围绕 $\mathrm{VI}(H,K)$ 展开。
Gap 函数
$\mathrm{gap}(x)=\sup_{x'\in K}\langle H(x), x-x'\rangle\ge 0$，度量当前点违反变分不等式的程度；$\mathrm{gap}(x^\star)=0$ 当且仅当 $x^\star$ 是解。它把「求解 VI」转化为「把 gap 降到 0」这一可量化的目标，是衡量算法精度的标准指标。
论文的理论收敛率 $\mathrm{gap}(\sigma_t)<C(1-\eta)^t$ 与实验精度 $\epsilon=10^{-5}$ 都以 gap 为度量；定理 6 更证明 $\mathrm{gap}(\sigma)=1^ op\check\mu(\sigma)$，把 gap 与纤维丛截面联系起来。
KKT 条件与中心路径
内点法把互补/约束问题的 KKT 条件中的互补项 $\sigma\circ r=0$ 扰动为 $\sigma\circ r=\mu$（$\mu>0$）。每个 $\mu$ 对应的解连成一条「中心路径」，$\mu\to 0^+$ 时路径终点即原问题的解；路径跟踪（path-following）就是沿这条路径预测-校正地前进。
本文的 FPKKT 系统正是这种扰动 KKT 型方程组，论文证明其路径是某个混合互补问题（MCP）的特殊中心路径，因此整个方法本质上是一个特化的内点法。
纤维丛与截面
纤维丛由底空间、每点上的纤维（fiber）和投影映射组成。本文底空间是单纯形 $\Delta$，纤维 $B(\sigma)=\{\sigma\circ F(\sigma)+v\sigma\mid v\in\mathbb{R}\}$ 是一条仿射直线，总空间 $E$ 是所有纤维的不交并；截面（section）是给每个 $\sigma$ 指定其纤维上一个点的映射。
纤维丛是全文核心创新：非负截面 $\check\mu$ 之和恰为 gap 函数，光滑截面 $ ilde\mu$ 经矩阵 $J(\sigma)$ 决定微分结构；沿纤维移动 $\mu$ 提供了绕过奇点的「跳跃」机制。
Brouwer 不动点定理
连续映射把非空紧凸集映到自身必有不动点。VI 解的存在性本身就由它保证；本文进一步定义 Brouwer 函数 $(\hat\sigma,r,v)=M(\sigma,\mu)$——对每个 $(\sigma,\mu)$ 解扰动 KKT 条件得到 $\hat\sigma$——它是 $\Delta$ 到自身的连续映射，其不动点与 FPKKT 的解等价（定理 5）。
定理 4 用它证明对每个 $\mu>0$ 路径都存在，这是路径跟踪可行的前提；不动点指数论证还给出非奇解个数必为奇数的奇数定理（定理 8）。
预测-校正框架
路径跟踪的标准迭代模式：预测步沿路径切线方向前进以降低 $\mu$，校正步固定 $\mu$ 用牛顿法把迭代点拉回路径上（解 $G(\sigma,\mu)=0$）。牛顿校正具有局部二次收敛，若在一致有界的邻域内工作，则整体可获得线性收敛率。
算法 1 正是该框架：预测子用微分方程 (4.10) 走切线步，校正子用（正则化）牛顿方程 (6.2)/(6.5)；收敛证明（命题 12–14）正是「校正二次收敛 + 预测步不掉出收敛域」的组合。
研究动机
变分不等式自 Fichera 与 Stampacchia 在 1960 年代提出以来，是优化、博弈论、经济学、交通分配、接触力学、流体与机器学习的统一建模语言：求 $x^\star\in K$ 使 $\langle H(x^\star), x'-x^\star\rangle\ge 0$。但在算法层面，「对每个连续映射 $H$ 都有全局收敛保证」始终未解决。现有方法各有短板：投影法与邻近点法通常需要单调性且只保证渐近弱收敛；merit-function 方法把 gap 函数当目标做梯度/牛顿迭代，但 gap 非凸非光滑；内点法依赖互补结构；同伦法虽然对几乎每个起点保证路径存在，但路径存在不等于有全局收敛的迭代——尤其当路径上出现奇点时跟踪会中断；算子分裂、自适应步长、惯性项、随机估计等现代变体大多仍需要单调性、伪单调性或类似结构性假设。换句话说，对多面体 $K$ 上任意连续 $H$——例如由 tanh 神经网络定义的非单调映射——此前没有任何方法能无条件保证渐近全局收敛。
本文的目标是本文要为有限维变分不等式建立第一个「无条件」的通用求解框架：映射 $H$ 只需连续，不需要单调、伪单调或任何其他结构性假设；域 $K$ 是多面体（多面体经凸体逼近又可推广到一般紧凸集）。具体目标分三层：其一是设计一个具有全局渐近收敛保证的路径跟踪算法——从任意指定起点出发，对非奇异的解做到 gap 函数全局线性收敛到 0，即 $\mathrm{gap}(\sigma_t)0$ 的全局线性收敛，即允许在离精确解 $\zeta$ 处停止。其二是算法要能系统化地处理路径上的奇点，而不是像传统同伦法那样在奇点处失败。其三是要求方法真正可运行：在随机生成、维数上千的非单调实例上（如 tanh 神经网络映射）稳定求解到 $10^{-5}$ 精度，并开源代码与数据。
与已有工作不同的是，本文的独特切入是把「解方程」变成「研究几何」。作者不直接求解 FPKKT 方程组，而是把它的解集整体看作底空间为单纯形 $\Delta$、纤维为一维 $\mu$-仿射线的纤维丛（fixed-point bundle）。这一几何化带来三项已有方法不具备的系统能力：(1) 起点自由——解析曲线 $\Gamma(\sigma_{init})$ 从任意指定 $\sigma_{init}$ 出发；(2) 奇点规避——奇点恰为纤维上 $1^\top\mu$ 等于 $-J(\sigma)$ 实特征值的点，沿纤维跳一步 $\mu\leftarrow\mu+\beta\sigma$ 即可绕开并切换到另一条解析曲线，而同伦法对路径奇点束手无策；(3) 精度度量——非负截面 $\check\mu(\sigma)$ 的和恰好是 gap 函数，路径推进量直接换算成解的精度。传统内点法有路径跟踪但起点与问题结构受限，本文用纤维丛把起点选取、路径跟踪与奇点规避统一在同一个几何对象上。
核心方法
整体思路是「先化简、再几何化、后跟踪」。第一步预处理：任何多面体 $K$ 都是单纯形的线性像，写 $x=V\sigma$ 后 $\mathrm{VI}(H,K)$ 变为单纯形上的 $\mathrm{VI}(F,\Delta)$，$F(\sigma)=V^\top H(V\sigma)$；再用 Dirichlet 分布做核平均，$F_{\epsilon,i}(\sigma)=\int_\Delta F_i(y)\,\mathrm{Dir}(y;\sigma/\epsilon+c)\,dy$，把任意连续映射磨成实解析函数（命题 1），值与导数用蒙特卡洛估计，样本量 $N=O(\epsilon_{MC}^{-2}\epsilon^{-2})$，与原 VI 的 gap 误差被 $\|H(V\sigma)\|\epsilon_{set}+2\epsilon_{map}$ 控制。第二步，把光滑 VI 的解等价刻画为不动点 KKT 系统（FPKKT），并从线性规划、Brouwer 不动点、混合互补问题三个角度证明路径存在且是特殊中心路径（定理 2/4/5）。第三步，把 FPKKT 的解集几何化为纤维丛 $E$，基本方程 $G(\sigma,\mu)=(I-\sigma 1^\top)(\sigma\circ F(\sigma)-\mu)=0$；在丛上构造从起点通往解的路径 $\tilde\Gamma$ 与紧致无奇点邻域 $N_{\tilde\Gamma}(\zeta)$，最后用预测-校正算法跟踪路径并证明 $\mathrm{gap}$ 的全局线性收敛。
核心创新是固定点丛（fixed-point bundle）。与已有方法的本质区别在视角：内点法把扰动 KKT 当作「要解的方程」，本文把 FPKKT 的解集当作「要研究的空间」——$E=\bigcup_{\sigma\in\Delta}\{\sigma\}\times B(\sigma)$，$B(\sigma)=\{\sigma\circ F(\sigma)+v\sigma\mid v\in\mathbb{R}\}$。这个几何把运动分解为底空间上的 $\sigma$ 运动与纤维上的 $\mu$ 运动：两个截面各司其职——非负截面 $\check\mu(\sigma)=\sigma\circ(F(\sigma)-\min_i F_i\,1)$ 度量解的质量（定理 6：$\mathrm{gap}(\sigma)=1^\top\check\mu(\sigma)$），光滑截面 $\tilde\mu(\sigma)$ 经矩阵 $J(\sigma)$ 决定微分结构。奇点被完全刻画：每条纤维上至多 $n-1$ 个，恰为 $1^\top\mu$ 等于 $-J(\sigma)$ 实特征值的点（奇点流形 $S$），沿纤维跳一步 $\mu\leftarrow\mu+\beta\sigma$ 即可绕开并切换解析曲线。定理 8 还证明非奇解个数必为奇数，与纳什均衡的经典奇数定理呼应。
方法步骤详情
算法 1 流程：输入 $F$、$\partial F/\partial\sigma$、起点 $\sigma_{init}$、精度 $\epsilon$。(1) 初始化：取充分大的 $v_{init}$，令 $(\sigma_0,\mu_0)=(\sigma_{init},\,v_{init}\sigma_{init})$，落在起点上方的纤维上。(2) 内层校正循环：一维二分法解 $q(v)=1^\top\frac{\mu}{F(\sigma)+v1}-1=0$ 得 Brouwer 函数 $(\hat\sigma,r,v)=M(\sigma,\mu)$；构造 $J(\sigma)$（式 4.8）；解正则化牛顿方程 $(J_G^\top J_G+\delta_H I)d\theta=-J_G^\top\tilde G$（式 6.2）或 $(J_G^\top\circ\sigma\circ J_G+\delta_H I)d\theta=-J_G^\top(\sigma-\hat\sigma)$（式 6.5），取 $\delta_H=\|G\|/n$；经 softmax 更新 $\sigma\leftarrow\mathrm{softmax}(\ln\sigma+d\theta)$；直到 $\|G\|\le\epsilon/n$，此时 $|G|\le\mu$ 成立。(3) 奇点规避：选 $\beta_t$ 使 $\hat\mu_t=\mu_t+\beta_t\sigma>0$ 且 $1^\top\mu_t+\beta_t$ 避开 $-J(\sigma)$ 的非零特征值。(4) 外层预测步：$\mu_{t+1}=(\hat\mu_t-\eta_t u_t).\mathrm{clip}(\min=\epsilon/n)$，解切线方程 $(J(\sigma)+(1^\top\mu)I)d\theta=(I-1\sigma^\top)(d\mu/\sigma)$ 得 $d\theta_t$ 并更新 $\sigma$。(5) 当 $1^\top\check\mu(\sigma)\le\epsilon$ 时返回 $\sigma$。理论保证：校正子一致二次收敛 $\|\tilde G(\sigma_{k+1},\mu)\|\le C_1\|\tilde G(\sigma_k,\mu)\|^2$（命题 12），预测步残差变化一致有界 $\le C_2\eta$（命题 13），整体 $\mathrm{gap}(\sigma_t)<C(1-\eta)^t$（命题 14），每个校正步 $O(\log t)$ 次子迭代足够。值得注意的是，实践中预测方向简单地取 $u_t=\pm\hat\mu_t$ 而不必严格回到原解析曲线，实验表明已足够；奇点规避、路径推进与回归校正三个步骤分别对应纤维运动、解析曲线切换与回到丛上的几何操作，结构上互不干扰。
技术新颖性
技术新颖性体现在四个层面。(1) 问题一般性：Dirichlet 核平滑把「连续」直接提升到「实解析」（比常用的 $C^\infty$ 结论更强，依赖全纯参数积分定理），从而解析曲线每段都有唯一解析延拓（Newton-Puiseux 定理），这是有限段路径存在性的关键；此前没有任何框架对任意连续 $H$ 给出全局收敛保证。(2) 几何工具：用纤维丛、截面与特征值刻画奇点流形 $S=\{(\sigma,\tilde\mu(\sigma)-\lambda_j(J(\sigma))\sigma)\}$，把内点法中「中心路径撞上奇点就失败」的难题变成「沿纤维跳跃」的平凡操作；$\ln\sigma$-坐标邻域与内点法的 Dikin 椭球呼应，显示作者深谙 IPM 传统又突破了其结构限制。(3) 两个正则化牛顿校正子分别从扰动 KKT 条件与障碍问题导出（在内点法中二者本同源，这里并不完全一致），都混含牛顿与梯度成分，$\delta_H$ 在步长稳定性与收敛速度之间折衷。(4) 奇数定理把不动点指数论引入 VI 求解，从理论上解释了路径分支为何成对连接起点与解，并暗示可用多起点策略枚举多个解。
实验结果
实验在随机生成的 $\mathrm{VI}(F,\Delta)$ 上进行：$F$ 由 tanh 神经网络表示，架构一为 $[n,n,n]$（$n=2..1024$），架构二为 $[256,\ldots,256]$（深度 $d=2..8$），Xavier 正态初始化，随机起点，精度 $\epsilon=10^{-5}$，每点 200 个实例共 6400 个。核心发现：(1) 6400 个实例全部成功，无一失败。(2) 两种正则化牛顿校正子对比：式 (6.5) 一致更快，如 $n=1024$ 时平均/中位迭代 892/452 对 (6.2) 的 948/553，原因是 (6.2) 右端 $G/\sigma$ 在单纯形边界附近易溢出。(3) 维度趋势：迭代数随 $n$ 先增后减——$n=2$ 约 280 次，$n=128$ 达峰值 1194 次，$n=1024$ 回落至 948 次；作者推测因解的个数也随维度增加。(4) 深度趋势：迭代数随 $d$ 单调下降——(6.5) 从 $d=2$ 的 1258 次降至 $d=8$ 的 584 次，源于 Xavier 初始化下 tanh 网络有效复杂度随深度下降。(5) 奇点规避：中位数在小维度为 0，而 $[256]\times2$ 平均高达 72.9 次，说明纤维跳跃在实践中被频繁但成功地使用。理论上，命题 12/13/14 依次给出校正子一致二次收敛、预测步一致界、$\mathrm{gap}(\sigma_t)0$）。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 随机生成 VI(F,Δ)（tanh 神经网络映射，维数 2–1024，共 6400 个实例） | 求解成功率（gap ≤ 10^{-5}） | 6400/6400，成功率 100% | 无外部基线：现有方法在无单调性等假设下不具备全局收敛保证 | 首个对任意连续映射无条件全部成功的通用算法 |
| 维度扩展性 [1024,1024,1024] 架构 | 迭代次数（平均/中位） | (6.5) 校正子 892/452 | (6.2) 校正子 948/553 | 平均约降 6%，中位约降 18% |
| 深度扩展性 [256]×8 架构 | 迭代次数（平均/中位） | (6.5) 校正子 584/376 | 同校正子 [256]×2 架构为 1258/837 | 迭代数减少约 54% |
| 奇点规避开销 [256]×2 架构 | 奇点规避次数（平均/中位） | (6.2) 校正子 72.9/34.5 次 | 小维度 [2]×3 仅为 0.1/0.0 次 | 高频奇点场景下仍 100% 成功，验证纤维跳跃机制有效 |
局限与改进
作者承认的局限：预处理（单纯形内逼近 + 解析平滑）与路径跟踪阶段分离，误差 $\epsilon_{set},\epsilon_{map},\epsilon_{MC}$ 虽可控，但更紧密的整合可能显著改善实际性能；对奇异解只能收敛到指定精度 $\zeta>0$。我的补充观察：(1) 蒙特卡洛评估要求 $N=O(\epsilon_{MC}^{-2}\epsilon^{-2})$ 个样本，高精度下代价平方级膨胀，且导数方差含 $1/\epsilon^2$ 因子，$\epsilon$ 小时噪声放大拖累牛顿步；(2) 奇点规避需计算 $J(\sigma)$ 的实特征值，实验中平均 60+ 次跳跃意味着可观开销；(3) 实验只有迭代次数，无墙钟时间，也未与任何现有求解器（如 PATH、外梯度法）对比，实际竞争力无法横向评估；(4) 测试映射全是 Xavier 初始化的 tanh 网络，属于「温和」的连续映射，对极端病态或平坦区域未验证；(5) 收敛率常数 $C,\eta$、邻域半径 $d$ 均为存在性结果，无法指导步长的先验设定。
独立分析的弱点
独立分析的弱点与改进方向：(1) 采样成本——$N=O(\epsilon_{MC}^{-2}\epsilon^{-2})$ 在 $\epsilon\to 0$ 时爆炸，导数噪声被 $1/\epsilon^2$ 放大；改进：拟蒙特卡洛、控制变量降方差，或换用带精确求积规则的确定性平滑核。(2) 奇点检测代价——每步计算 $J(\sigma)$ 特征值为 $O(n^3)$ 量级，且只规避实特征值；改进：利用论文自身的 Sard 论证（几乎处处非奇）做随机微扰回避，或沿路径对特征值做延拓预测、提前绕行。(3) 缺乏外部基线——无法判断相对 PATH 等成熟 MCP 求解器或单调情形外梯度法的竞争力；改进：统一实例库上补齐对比与墙钟时间。(4) 预处理与跟踪解耦——$\epsilon$ 固定导致解的是近似问题；改进：把 $\epsilon$ 作为第二个同伦参数与 $\mu$ 联合调度。(5) 理论常数不可计算——$C_1,C_2,\eta,d$ 只证存在；改进：给出可估计的界，发展自适应步长与 $\delta_H$ 调度。
未来方向
作者在结论中明确提出：把内单纯形逼近与解析平滑更紧密地整合进路径跟踪阶段以提升实际性能。基于本文成果可自然延伸的方向：(1) 多解枚举——解析曲线从不同 $\sigma_{init}$ 出发通向不同解，奇数定理保证非奇解个数为奇数，可设计多起点并行策略并利用路径分支结构系统枚举解；(2) $\epsilon$–$\mu$ 联合同伦，消除两阶段误差叠加；(3) 随机与在线变体——当 $F$ 本身只能蒙特卡洛估计时，研究采样噪声下的鲁棒校正与复杂度界，对接随机 VI 文献；(4) 应用落地——非单调博弈（如生成对抗训练中的均衡）、交通分配与接触力学中的非单调补问题；(5) 理论深化——给出 $C,\eta$ 的显式界、把实解析性放松到 $C^2$（路径存在性论证目前依赖解析延拓）、研究奇异解处 $\zeta\to 0$ 的极限行为与加速策略。
复现评估
复现条件较好：代码与数据已在 GitHub 开源（https://github.com/shb20tsinghua/FiberBundle_VI），实验设置完全明确——tanh 神经网络映射、Xavier 正态初始化、架构 $[n]\times 3$（$n=2..1024$）与 $[256]\times d$（$d=2..8$）、每个数据点 200 个实例共 6400 个、精度 $\epsilon=10^{-5}$。算法每个迭代包含：一维二分求 $v$（廉价）、构造 $J(\sigma)$ 并解 $n\times n$ 线性系统（$O(n^3)$ 量级，$n=1024$ 时单机可行）、偶发的特征值计算用于奇点规避；所需算力为单机级别，论文未报告墙钟时间，但数百到一千余次的迭代数表明计算量适中。理论部分自包含，但门槛较高：读懂完整证明需要纤维丛、不动点指数、Newton-Puiseux 解析延拓、Sard 定理等微分拓扑工具；工程实现难度中等——校正与预测的线性代数直接，难点在 softmax 参数化下的数值稳定性（论文的 (6.5) 校正子正是为避免 $1/\sigma$ 溢出而设计）。总体评级：代码齐全、设置清晰，复现实验容易，复现理论证明需要较强数学背景。
论文图表