精读笔记
Problem Setting
[A Variable-Metric Non-monotone Line Search Method for Mixed Variational Inequalities and Equilibrium Problems]（arXiv preprint / 2026）
这篇论文处理的是闭凸集上的 VI、MVI 和 EP 的统一数值求解，重点不是定义这些问题，而是为这三类问题构造一个共享的 gap-descent 算法框架。关键矛盾在于：这些问题没有天然 objective，但 line search 和 descent analysis 需要一个可下降的 merit；同时普通 projection map 只有在强单调+Lipschitz 下才是 contraction，在弱单调或伪单调下很容易退化。已有方法要么走 extragradient，靠额外投影修正非收缩性；要么走 gap-function reformulation，但通常没有同时结合 variable metric 和 modified non-monotone line search。作者真正想解决的是：能否把优化里的 scaled non-monotone projected-gradient 机制，变成一个对 VI/MVI/EP 都成立的 gap-residual 框架。
Motivation
已有路线缺的是“方向、残差、gap 证书”的统一。优化里 projected-gradient step 天然对应目标函数下降方向；但在 VI/EP 中，F 或 G 不一定来自梯度，直接替换 ∇f 为 F 并不能给出目标下降。作者的核心观察是 Fukushima regularized gap 的 maximizer 正好是 scaled projection point，这让 projection residual 不再只是 fixed-point residual，而是 gap 的内在构造方向。这个观察使得 Ansari et al. 的 scaled gradient modified non-monotone line search 可以脱离优化目标 f，迁移到一般 operator / bifunction。关键缺口不是“再设计一个投影法”，而是让 gap-function descent 与 scaled projection step 在数学上对齐。
Core Idea
核心思想可以压缩成一句：用 regularized gap 把 VI/EP 的 fixed-point residual 变成一个可下降的 merit，并选择正则项/metric 使得 gap 的 inner optimizer 正好等于算法步。
这改变了建模方式：不是先设计迭代再找 Lyapunov 函数，而是先选 gap，使算法步天然成为 gap-defining direction。这样信息流被重新组织为：当前点 x 通过 scaled projection/resolvent 产生 yα(x)，差值 d 同时编码 stationarity、gap value、line-search direction 和 contraction residual。和 prior 的本质差异在于，它不是单纯把 extragradient 换成 variable metric，也不是单纯对 gap 做 descent，而是把 projection residual 与 gap maximizer 绑定起来。这个 inductive bias 很强：只要 inner projection/resolvent 可算，算法就能在 VI/MVI/EP 三类问题间共享一套分析。
Method
1. Scaled Fukushima/Mastroeni gap：解决无 objective 的问题。它提供非负 merit，零点等于解集，并且其 inner optimizer 是 scaled projection/resolvent。核心变化是把求解 VI/EP 变成驱动 gap→0，而不是直接处理变分不等式。
2. Variable-metric projection/resolvent：解决几何尺度和 conditioning 问题。Dk 改变投影范数，相当于预条件化 operator。它不是收敛机制的根源，但在病态且结构匹配的算子上能显著加速。
3. Modified non-monotone Armijo：解决下降过于保守的问题。line search 用 moving-average reference Tk，而不是要求每步 gap 单调下降；二次修正项提供额外 sufficient decrease。理论上它保证全局下降证书，但实验显示在强单调光滑场景中常常没有被真正激活。
4. 强单调 contraction / error bound：这是线性率的来源。VI/MVI 的 R-linear rate 来自 scaled projection/resolvent map 在合适 α 下收缩，而不是来自 Armijo decrease 本身。gap error bound 只是把 residual/distance 的 contraction 转译成 gap 收敛。
Key Insight / Why It Works
最重要的 insight 是结构同一性：scaled projection step = Fukushima gap 的 maximizer。没有这个同一性，算法只是把优化 line search 生硬套到 VI；有了它，d=yα(x)-x 同时具备三种身份：算法更新方向、自然残差、gap 证书方向。这是论文最实质的贡献。
真正有效的部分是 strong monotonicity-induced contraction。强单调+Lipschitz+合适 α 给出 T(x)=PK,D^{-1}(x−αDF(x)) 的收缩，relaxed update 继承 contraction，于是 distance、residual、gap 都线性下降。换句话说，R-linear rate 主要来自 operator geometry，而不是 non-monotone line search。line search 负责可接受步长和全局下降，但不是线性率发动机。
variable metric 的作用更像 scaling / preconditioning。它能改变有效条件数，尤其在作者构造的 diagonal ill-conditioning 上收益很明显；但这个增益可能主要来自 scaling 与 data/operator structure 匹配，而不是算法框架本身的泛化能力。若困难来自旋转耦合或非对角结构，简单 diagonal metric 的优势会减弱。
non-monotone Armijo 在这篇里的贡献偏辅助。理论框架里它让 gap descent 更接近优化中的成熟策略，但实验中强单调问题的 gap 本来就单调下降，Tk 基本贴着 gap 走，non-monotone 机制没有展现不可替代性。因此它更像一个可迁移组件，而不是核心创新。
EP 部分更像“框架延伸”而非完整闭环。Mastroeni gap 给出 global convergence 和 error bound，但 gap 对 residual 是一阶控制，不能自动推出几何率。作者也承认 α 条件冲突：error bound 需要 α 大，而 contraction 通常需要 α 小。这说明 EP 线性率不是简单补一个 lemma 就能解决，而是当前框架的真实上限。
Relation To Prior Work
最接近的三条线是 Fukushima/Yamashita/Peng 的 gap-function reformulation，Korpelevich/extragradient 与 projection-contraction VI 方法，以及优化中的 scaled projected-gradient + non-monotone Armijo。论文的新增不是发明这些组件，而是把它们通过 gap maximizer = scaled projection 这个身份绑定到一起。
相对 extragradient，SGFM 不靠额外外推点处理非收缩性，而是依赖 gap descent 和强单调 contraction；因此在弱单调/旋转主导问题上不如 extragradient 是预期内的。相对传统 gap descent，它引入 variable metric 和 modified non-monotone reference，但真正新增的信息是方向不是外选的 descent direction，而是 gap 定义自身给出的 residual。相对 Ansari et al. 的优化方法，它去掉了 gradient-origin 假设，把 ∇f 替换成一般 F/G，并用 gap function 补上 objective 的缺失。
所以这篇属于“merit-function reformulation + preconditioned projection + line-search globalization”的技术谱系。实质创新是统一机制和分析拼接；看似新的 variable metric/non-monotone 组合更多是成熟组件重组。
Dataset / Evaluation
实验覆盖 VI、MVI、EP 三类，但主要是 controlled problems：强单调 affine/asymmetric VI、弱单调族、ℓ1-MVI、合成强单调 EP，以及一个 Nash–Cournot EP 和 Kojima–Shindo NCP。它们适合验证理论常数、rate 和 scaling 效果，但不是强泛化证据。
实验确实支持几个 claim：强单调下 residual 呈线性收敛；diagonal metric 在对角病态上带来数量级加速；gap 和 D-gap 在受控强单调问题上同步消失；SGFM 可覆盖 VI/MVI/EP。问题是这些 claim 大多是 theory-driven 的 sanity check，不是 stress test。
和 baseline 的比较反而暴露边界：VI 上 extragradient 更快，弱单调时差距扩大；非单调 Kojima–Shindo 上 SGFM 失败；Nash–Cournot 这种仅单调 EP 上只有 D-gap 方法成功。也就是说 evaluation 支持“统一框架在强单调区间可工作”，不支持“比专门方法更强”或“对弱/伪单调问题有真实优势”。文中未充分说明 large-scale inner solve 成本，也没有真实高维部署场景。
Limitation
1. 线性率强依赖强单调和 Lipschitz。没有强单调，核心 contraction 消失，方法退回 sublinear floor 或直接失效。所谓统一性主要覆盖问题形式，不等于覆盖难度类别。
2. EP 理论没有闭合到 R-linear rate。Mastroeni gap error bound 只控制距离，且与 residual 一阶关系导致 sufficient decrease 不足以推出几何率。α 的大/小条件冲突是结构性问题，不是证明技巧问题。
3. non-monotone line search 的增益来源不清。在作者主要实验中 gap 已单调下降，non-monotone reference 基本 dormant。因此它目前更像从优化中迁移来的合理 engineering，而不是被实验证明的核心机制。
4. variable metric 的收益可能主要来自 scaling / data。对角预条件在对角病态合成算子上很强，但对旋转耦合或非对角病态没有同等保证。若 metric 选择本身需要问题知识，scalability 上限会转移到 metric design。
5. MVI 的 gap rate 需要 ∂φ 沿迭代有界，非光滑更一般情形没有真正解决。V2 residual route 只被提出，没有完整分析。
6. 实验不是 deployment-grade。多数 benchmark 是已知常数的可控问题，适合验证定理，不适合证明实际 solver 竞争力。代码也只是 promised release，复现实证目前依赖论文描述。
Takeaway
- 1. 最值得迁移的不是 non-monotone Armijo，而是“让算法步成为 gap-defining optimizer”的设计原则。
- 对其他 operator problems，也可以先找 residual 与 merit 的结构同一性，再设计 line search。
- 2. 强单调场景下，gap descent 的线性率最好从 operator map contraction / error bound 来拿，不要指望 sufficient decrease 本身给几何率。
- 3. Variable metric 是实用加速点，但必须和 operator geometry 匹配。
一句话总结
这篇论文把 scaled projection residual 与 regularized gap maximizer 对齐，从而把优化中的 variable-metric non-monotone line search 重组为 VI/MVI/EP 的统一 gap-descent 框架；其核心理论收益来自强单调 contraction，工程收益主要来自 scaling。