精读笔记
Problem Setting
论文标题：Limiting Stationarity of Regularized Gap-Function Reformulations for Bilevel Optimization with Unbounded Multipliers（arXiv preprint / 2026-07-21）。
这篇论文实际解决的是 bilevel optimization 中 regularized gap-function reformulation 的极限 stationarity 失真问题。它不是在问 gap reformulation 是否等价于原 bilevel，也不是单纯提出一个更快算法；它问的是：当求解 penalty/relaxation 近似问题时，如果 gap constraint 的乘子 rho 发散，近似一阶条件在原始 KKT-based MPCC 上还能推出什么 stationarity。
真正困难点在于 value-function-type constraint 是退化的。gap constraint 在可行点满足 G_gamma = 0，而 G_gamma >= 0，因此它不像普通 inequality 那样有正常的横截方向；标准 NLP CQ 很容易失败。已有 bounded-multiplier 分析本质上绕开了最坏情况，一旦 rho -> infinity，直接取 KKT 极限就不可用。
关键矛盾是：regularized gap reformulation 之所以有吸引力，是因为它避免显式处理 lower-level KKT/MPCC；但它的极限 stationarity 又必须回到 MPCC 语言中才能被正确解释。论文的贡献就是把这两套语言之间的极限映射讲清楚。
Motivation
已有 value-function / Moreau-envelope / regularized-gap 路线的共同问题是，它们把 lower-level optimality 包成一个标量或光滑 surrogate constraint。算法上这更友好，但理论上这个 constraint 几乎必然退化，导致普通 constraint qualification 无法保证乘子有界。
作者抓住的缺口是：很多 penalty-based bilevel 方法事实上运行在 rho -> infinity 或 relaxation -> 0 的极限中，但文献通常要么假设乘子有界，要么只在特殊线性/仿射结构下处理无界乘子。对于 constrained convex lower-level 的 regularized gap function，无界乘子极限到底对应 MPCC 的 C/M/S 哪一级 stationarity，此前并不清楚。
所以这篇论文的动机不是“提出一个新 gap function”，而是修补 regularized gap-function 方法的理论底座：在不对 gap constraint 本身施加 CQ 的情况下，识别其近似 KKT 序列的真实极限含义。
Core Idea
核心思想是把 gap-gradient 的无界乘子效应重新解释为 MPCC 乘子。regularized gap function 内部有两个 proximal objects：theta*(x,y,z) 来自 lower-level Lagrangian 的 Moreau envelope，lambda*(x,y,z) 来自 PHR-type multiplier projection。当 G_gamma -> 0 时，theta* - y -> 0、lambda* - z -> 0；但 rho(theta*-y) 和 rho(lambda*-z) 不必趋零，它们正好成为 MPCC stationarity 中的 omega 与 eta。
这一步改变了建模理解：gap reformulation 表面上是一个单标量约束，极限上却隐含了一套 KKT-MPCC 乘子系统。标准 penalty 没有足够信息控制 biactive indices 上 eta 与 nu 的符号结构，因此只能得到 C-stationarity；slack formulation 通过显式保留 (z,s) ∈ C，把 lower-level feasibility slack 与 multiplier 的互补关系作为 hard geometry 留在近似问题里，再用 rho2/rho1 -> infinity 让 feasibility residual 支配 gap residual，从而恢复 M-stationarity。
和 prior 的本质差别是：它不是为了让 reformulation 更光滑，而是为了让无界乘子极限更可解释、更强。slack 不是普通松弛变量，而是一个 stationarity-preserving device。
Method
1. Regularized gap reformulation：把 lower-level optimality 编码为 G_gamma(x,y,z) <= 0，其中 G_gamma >= 0 且 G_gamma = 0 等价于 y 是 lower-level 解、z 是 lower-level KKT multiplier。它解决的是 constrained lower-level bilevel 中显式 KKT 系统昂贵、MPCC 直接处理困难的问题。
2. Approximate KKT under unbounded gap multiplier：定义 penalty/relaxation 共同诱导的 approximate KKT 条件。关键不是形式本身，而是允许 rho^k 无界，并研究 rho^k ∇G_gamma 的极限。
3. Gap-gradient decomposition：利用 theta* 与 lambda* 的一阶条件，把 rho ∇_{x,y}G_gamma 写成 ∇_y∇_{x,y}L · omega + ∇g^T eta 加高阶残差，其中 omega = -rho(theta*-y)，eta = rho(lambda*-z)。这一步是整篇证明的核心机械结构。
4. MPCC-MFCQ 排除异常极限：当 multiplier tuple 可能发散时，归一化后会产生 abnormal multiplier system。MPCC-MFCQ 的作用就是排除这个系统，从而证明 omega、eta、mu、nu 有界并可取极限。
5. C-stationarity sharpness example：论文构造一维例子说明标准 penalty 的极限可以是 C-stationary 但不是 M-stationary。这不是装饰性例子，它证明了不能靠更细证明把 Theorem 3.3 自动加强到 M-stationarity。
6. Slack two-parameter penalty：引入 s >= 0、g(x,y)+s=0，并硬约束 (z,s) ∈ C；只惩罚 gap 与 equality residual。rho2/rho1 -> infinity 迫使 feasibility-slack 误差比 gap 乘子误差更快消失，进而修正 biactive indices 上的符号关系。
7. iG-BSPM：算法上采用 alternating projected gradient，对 theta* 只要求 residual 近似，并通过 feasibility correction 与增长截断边界保证生成 approximate KKT 序列。这里算法是理论闭环的一部分，不是论文最强贡献。
Key Insight / Why It Works
最重要的 insight 是：regularized gap constraint 的 degeneracy 并不意味着极限一阶信息完全丢失；丢失的是普通 NLP KKT 解释，保留下来的是 MPCC stationarity 结构。gap function 的 Moreau/PHR 结构恰好提供了从 surrogate 梯度到 MPCC 乘子的桥。
标准 gap penalty 为什么只能到 C-stationarity？因为 rho(lambda*-z) 与 rho(g(y)-g(theta*)) 的符号关系在 biactive set 上不够强。C-stationarity 只要求 eta_i nu_i >= 0；M-stationarity 要求更接近 limiting normal cone 的 disjunctive 结构，即要么两个正，要么乘积为零。标准 penalty 没有机制阻止 eta,nu 同时为负，Example 3.5 精准展示了这一点。
slack formulation 有效的原因不是“多了一个变量”，而是保留了 exact complementarity geometry。把 g(x,y)<=0 变成 g+s=0 并保持 z_i s_i=0，使得近似子问题的 normal cone 已经携带 MPCC biactive geometry；rho2/rho1 -> infinity 则保证 feasibility residual 的尺度足够强，避免标准 penalty 中负-负乘子组合进入极限。
最可能的核心贡献是 Theorem 3.3 + Example 3.5 + Theorem 4.3 这一组三段论：先说明无界 gap multiplier 仍有 C-stationarity，再证明 C 是 sharp，最后指出必须改变 formulation 才能得到 M。这比算法部分更实质。
算法 iG-BSPM 的增益来源更像 engineering/theory closure：inexact theta、adaptive penalty、feasibility correction 都是为了让生成序列满足 Definition 4.1。它是否在实际大规模 bilevel 上比已有 Hessian-free/value-function 方法更强，文中未充分说明。这里不存在 dataset scaling 或 retrieval/memory 类因素；核心是 variational geometry 与 stationarity-preserving reformulation。
Relation To Prior Work
这篇属于 value-function-type / regularized gap-function bilevel reformulation 与 MPCC stationarity 理论的交叉谱系。最接近的是 Yao et al. 2025 的 regularized gap function 路线，以及 classical value-function reformulation、Moreau-envelope reformulation、MPCC KKT reformulation stationarity 文献。
和直接 MPCC reformulation 的差别是：MPCC 路线显式处理 lower-level stationarity 与 complementarity，理论站位清楚但算法上涉及 lower-level Hessian/Lagrangian 二阶项；regularized gap 路线把这些结构隐藏进一个光滑 gap constraint，更适合一阶近似，但 stationarity 风险更大。本文正是在解释隐藏结构极限上补了一块。
和普通 value-function/Moreau-envelope penalty 的差别是：本文不满足于证明 approximate feasibility 或 weak stationarity，而是精确追踪无界 penalty multiplier 在 MPCC stationarity hierarchy 中落在哪一级。这个角度更偏 variational analysis，不是算法 trick。
Slack two-parameter penalty 看似是经典 slack/penalty 思路重组，但实质创新在于它不是为了处理 inequality feasibility，而是为了保留 multiplier-slack complementarity 的 normal-cone 信息，从而改变 biactive index 上的 stationarity 类型。这是本文相对已有 gap-function 方法最有迁移价值的部分。
Dataset / Evaluation
这篇是优化理论论文，没有传统 dataset、benchmark 或真实系统实验。Evaluation 主要由定理、反例和算法收敛证明构成。
理论验证覆盖了三个核心 claim：标准 regularized gap approximate KKT 在无界 multiplier 下能保证 C-stationarity；该结论不能一般加强到 M-stationarity；slack two-parameter formulation 在 domination condition 下能恢复 M-stationarity。这个 evidence 对论文的理论 claim 是匹配的。
但它没有验证算法在真实大规模 bilevel learning、hyperparameter optimization 或 constrained ML 场景中的数值优势。iG-BSPM 的 line search、projection、feasibility correction、lower-level correction oracle 是否实际可承受，文中未充分说明。因此算法层面的 scalability claim 只能视为理论可实现性，而不是 empirical superiority。
Limitation
第一，lower-level convexity in y 是根本前提。regularized gap 的非负性、theta* 唯一性、gap=0 等价 lower-level optimality 都依赖这个结构。对非凸 lower-level bilevel，这套证明不能直接迁移。
第二，MFCQ 与 MPCC-MFCQ 仍然是强假设。论文避免了对 gap constraint 施加 CQ，但没有摆脱原 constraint systems 与 limiting MPCC 的 CQ。也就是说，它不是“无 CQ 收敛理论”，而是把 CQ 从 degenerate gap constraint 转移回更合理的 MPCC/TNLP 系统。
第三，slack 方法把 stationarity 变强的代价转移到更难的 feasible geometry：每个子问题要处理 (z,s) ∈ C 的非凸互补集合。虽然投影有闭式形式，但整体问题仍是非凸交替 projected scheme，实践稳定性未知。
第四，rho2/rho1 -> infinity 是一个明显的尺度 domination 条件。它在证明中用于压制 bad biactive sign patterns，但实际算法中 penalty 同步增长后通过 rho2 = sigma1 sigma2 / 2 间接满足。这个尺度选择是否会导致 ill-conditioning，文中未充分说明。
第五，feasibility correction 依赖 Assumption 5.3：对每个 x 都存在 upper-feasible lower-level solution 及 KKT multiplier。这个假设在实际 constrained bilevel 中不轻，可能比算法描述看起来更限制。
第六，算法没有复杂度结果，也没有数值 evidence。所谓 scalable 更多来自避免显式二阶 KKT 线性化的结构潜力，而不是已经被实验确认的 scaling。
Takeaway
- 1. 对 value-function-type bilevel reformulation，关键不是只问 surrogate 是否等价，而是问 surrogate 的 approximate KKT sequence 在 penalty 极限下对应哪一级 MPCC stationarity。
- 2. Regularized gap function 的梯度内部天然携带 MPCC 乘子信息；theta*-y 与 lambda*-z 的一阶小量在乘以无界 penalty 后成为真正的 stationarity carrier。
- 3. 标准 penalty 的极限 C-stationarity 是本质上限，不是证明技术不够。
- 若要 M-stationarity，必须改变近似问题的几何结构，保留 complementarity normal cone 信息。
一句话总结
这篇论文把 regularized gap-function bilevel 方法从“光滑 surrogate 求解”推进到“无界惩罚乘子下的 MPCC stationarity 保真分析”，并说明标准 gap penalty 的极限只能到 C-stationarity，而要获得 M-stationarity 必须通过 slack-complementarity 几何重构近似问题。