精读笔记

Problem Setting

论文研究的是 Hilbert 空间中的约束变分不等式：T 是 point-to-set maximal monotone operator，约束集由非光滑凸不等式 C={x:c(x)≤0} 给出。表面目标是 projection-free，实际目标更具体：不计算难的 metric projection P_C，同时仍获得对解集 S* 的精确 Fejer 型包含和全序列强收敛。

真正困难不在于构造一个可行性 cut；这在 subgradient projection 文献里很成熟。困难在于 operator half-space 的合法性。若 (y,v)∈Gph(T) 且 y∈C，则 Minty/monotonicity 给出 S*⊆{x:<v,x−y>≤0}。但如果 y 只是近似可行，这个包含一般不成立。也就是说，projection-free 方法通常会产生 infeasible trial point，而 VI 的 separation 逻辑又要求 evaluation point 精确可行。这是本文的关键矛盾。

以前方法大多在三处卡住：要么仍需要 P_C 或对 C 的较强投影能力；要么只处理单值/Lipschitz VI；要么在 Hilbert 空间中只能得到弱收敛或 subsequential convergence。本文试图同时拿到：非光滑约束、点到集 maximal monotone、无 P_C、强收敛到 P_{S*}(x0)。

Motivation

已有 relaxed projection 和 subgradient extragradient 已经说明“用支持半空间替代复杂投影”是可行路线，但这些方法没有完全解决多值 monotone VI 下的可行 graph point 问题。对于 optimization，很多时候 objective/subgradient cut 的近似误差还能被 Fejer 不等式吸收；但对 Minty half-space 来说，y∈C 是结构性条件，不是误差项。

作者的核心观察很直接：如果 operator cut 不在可行点生成，解集包含可能失败；一旦包含失败，Haugazeau 或 Fejer 几何都没有基础。因此 projection-free 不能只追求“少投影”，还必须保证 operator evaluation 的 exact feasibility。

缺口是：怎样在不算 P_C、不算 dist(·,C) 的情况下把任意 trial point 变成可行 graph point。Slater 点提供了一个便宜的方向：沿 trial point 到严格可行点 s 的线段做显式凸组合，就能利用 convexity of c 把点拉回 C。这不是为了找到最近可行点，而是为了恢复 Minty separation 的逻辑合法性。

Core Idea

核心思想是把可行性和分离性解耦：可行性不通过 P_C 获得，而通过 Slater correction 获得；收敛驱动力不来自投影到 C，而来自 feasible Minty half-space 对解集的精确外逼近；强收敛不靠 compactness 或 strong monotonicity，而靠 Haugazeau anchoring 到 x0 的 best-approximation 几何。

这改变了传统 projection method 的信息流。普通 projected/extragradient 路线是先把迭代点拉到 C，再评估 operator；本文是允许 trial point 随便来，但在生成 operator cut 前强制把 graph point 修正到 C。于是算法需要的不是 P_C，而是 c 的函数值、子梯度、一个 Slater 点，以及某种能给出 Minty gap 分离的 oracle。

和 prior 的本质区别不在“半空间投影”本身，而在“半空间必须由 feasible graph point 生成”这一条件被放到算法设计中心。Haugazeau half-space 则把这个外逼近过程从弱收敛/聚点收敛升级为收敛到 P_{S*}(x0)，这是 Hilbert 空间里很关键的 anchoring bias。

Method

1. Constraint cut：当 x^k 不可行时，用 g^k∈∂c(x^k) 生成 C_k={x:c(x^k)+<g^k,x−x^k>≤0}。它解决的是当前点不可行但不想求 P_C 的问题。核心变化是把复杂可行集替换成一个包含 C 的外半空间，并且后续可用 x^{k+1}∈C_k 推出 c_+(x^k) 被步长控制。

2. Slater-corrected Minty cut：oracle 给 trial point \tilde y^k，若其不可行，则取 y^k=(1−λ_k)\tilde y^k+λ_k s，其中 λ_k 由 c(\tilde y^k) 和 c(s)<0 显式给出。它解决的是 operator cut 的 exact feasibility 问题。核心变化是 evaluation point y^k∈C，而不是 x^k 或 \tilde y^k 是否可行。

3. Minty half-space：取 v^k∈T(y^k)，构造 H_k={x:<v^k,x−y^k>≤0}。因为 y^k∈C，monotonicity + VI condition 保证 S*⊆H_k。这是整个方法的不可替代部分；如果 y^k 只是近似可行，证明会崩。

4. Haugazeau half-space：W_k={x:<x−x^k,x0−x^k>≤0}，然后 x^{k+1}=P_{C_k∩H_k∩W_k}(x0)。它解决的是 Hilbert 空间中弱收敛不足的问题。核心变化是每步都从 x0 投影到包含 S* 的半空间交，而不是局部投影当前点；这使得范数单调性和 Kadec–Klee 最终可用。

Key Insight / Why It Works

最关键的 insight 是：Minty gap 可以作为判别弱聚点是否属于 S* 的桥梁，而不需要处理弱收敛序列乘积的极限。Φ(x)=sup_{z∈C,w∈T(z)}<w,x−z> 是弱下半连续的，因为它是弱连续 affine 函数的上确界。算法通过 H_k 和 oracle condition 让 Φ_+(x^k)→0；再结合 c_+(x^k)→0，任何弱聚点都在 C 且 Minty gap 非正，于是由 Minty–Stampacchia equivalence 得到属于 S*。

强收敛的来源不是 strong monotonicity，也不是更强的 operator regularity，而是 Haugazeau geometry。W_k 保证 S* 始终在投影目标内，并使 ||x^k−x0|| 单调递增且有上界 ρ=dist(x0,S*)。弱聚点一旦被证明属于 S*，距离链条 ρ≤||\hat x−x0||≤liminf||x^{k_j}−x0||≤ρ 强迫弱聚点必须是 P_{S*}(x0)。再用 Hilbert 空间 Kadec–Klee 从弱收敛+范数收敛得到强收敛。

最可能的核心贡献是 Slater-corrected feasible Minty separation + Haugazeau anchoring 的组合。子梯度 cut 和半空间投影本身更像已有技术的重组；O(N^{-1/2}) best-iterate residual 也基本来自步长平方可和的 projection inequality，不是特别深的新速率。

需要直说的是：算法有效性很大程度上被 oracle condition A4 承担。A4 要求可计算 separation [<v^k,x^k−y^k>]_+ 控制全局 Minty gap Φ_+(x^k) 的固定比例。这不是普通工程细节，而是把全局困难从 P_C 转移到 Minty separation oracle。Slater correction 只修复合法性，不自动产生强 separation。因此理论主结果的真正代价在 oracle，而不是 half-space projection。

Relation To Prior Work

这篇属于 projection / cutting-plane / Haugazeau hybrid method 谱系，而不是 Frank–Wolfe 式 projection-free。这里的 projection-free 明确只指不投影到原始 C；算法仍然投影到半空间交。

和 Fukushima relaxed projection、subgradient extragradient 的关系：都用支持半空间降低投影成本，但本文更强调 operator half-space 必须来自 feasible graph point，并且面向 point-to-set maximal monotone。subgradient extragradient 常见结论是 Hilbert 空间弱收敛；本文通过 Haugazeau half-space 拿强收敛。

和 Solodov–Svaiter 最接近：都使用 monotone VI 的 separating hyperplane。真正不同是本文把 feasible graph point 的生成机制和非光滑 inequality constraint 绑定起来，用 Slater correction 避免 P_C，并把结果表述到 maximal monotone point-to-set 框架。换言之，新意不是 separation，而是 separation 的可行性保障和 best-approximation anchoring 的组合。

和 Halpern/viscosity/Haugazeau 强收敛方法的关系：强收敛机制并非全新，属于 anchoring geometry 的迁移。实质创新在于把这个 geometry 与 Minty representation、Slater-corrected feasibility、projection-free constraint handling 放到同一套 VI 算法里。

Dataset / Evaluation

实验覆盖面较广：max of convex quadratics、离散 optimal control、mixed norm sparse recovery、Cournot–Nash capacity、以及真正 point-to-set 的 l1 subdifferential。覆盖了非光滑约束、大规模有限维、带 skew component 的非优化型 VI、以及多值 operator。作为应用压力测试是合理的。

但 evaluation 对核心理论 claim 的支持有限。理论要求 A4 类型的 Minty-separation oracle，而高维实验主要使用 cheap forward single-candidate variant；作者明确说这不自动满足 A4。因此实验验证的是“这种几何在实践中可能有效、且避免 P_C 有时便宜”，不是严格验证“理论算法在这些实例上满足 oracle 并收敛”。

数值结果的叙事总体克制：在 max-quadratic、Cournot、point-to-set distance-to-solution 上 FSPA 有优势；mixed norm 和小规模 projection feasible 情况下 relaxed baseline 可竞争甚至更好。这个结果支持其 intended regime：当 P_C 是昂贵子问题而 subgradient cut 便宜时，FSPA 有意义。它不支持一个普遍优于 relaxed/extragradient 的结论。

还要注意，CPU 比较基于 Python/NumPy 和不同 inner operation，不能过度解读。实验没有大规模展示 certified finite-candidate oracle 的成本-精度曲线，这是最该补的评价。

Limitation

1. 核心问题被转移到 Minty oracle。A4 要求找到 feasible graph point，使 separation 近似控制 Φ_+(x^k)。在一般高维非紧 C、多值 T 场景下，这可能比 P_C 更难，甚至等价于解一个全局辅助问题。论文承认 oracle 不免费，但这是方法上限。

2. Slater assumption 是硬前提。需要已知严格可行点 s 且 c(s)<0。很多实际约束中 Slater 点本身可能需要求解，或者 margin 很小导致 correction loss 大。文中给出 loss bound，但实际稳定性依赖 Slater margin。

3. 理论与实验实现不完全一致。实验主力是 single-candidate forward variant，未证明满足 A4。因而实验增益可能主要来自工程上的半空间/anchoring行为，而不是主定理所需的 certified Minty separation。这里增益归因不够清楚。

4. Projection-free 不是 oracle-free。对于 exact oracle，若需要在 C 上最大化 <T(y),x−y>，仍可能涉及复杂 constrained optimization。特别是非紧 C、多值 T、非 Lipschitz 或无全局 candidate net 时，可扩展性不明。

5. 单 cut 机制对复杂约束几何可能利用率有限。max-type constraints 中只取一个 active cut，可能丢掉大量约束结构；未来多 cut / memory variant 可能才是真正工程上强的版本。

6. O(N^{-1/2}) 是 best-iterate residual，不是 last-iterate rate，也不是 distance-to-solution rate。强单调情形只给 uniqueness，没有给加速或线性收敛。若追求数值效率，这个理论速率较保守。

Takeaway

• 1. 对 monotone VI，operator cut 的生成点必须精确可行；“近似可行”不是小误差，而可能破坏解集包含。
• 这一点很值得迁移到其他 projection-free / infeasible-start VI 算法。
• 2. Slater correction 是一个简单但有用的 feasibility primitive：它不求最近点，只求合法 graph point。
• 对于需要 separation 而非最小距离的算法，这种思路比 P_C 更自然。

一句话总结

这篇论文把 Slater 可行修正、feasible Minty separation 和 Haugazeau best-approximation 几何组合起来，为非光滑凸约束下的 point-to-set maximal monotone VI 提供了一条不投影到 C 但仍能强收敛的 projection-method 演化路线。