精读笔记

Problem Setting

论文研究的问题是一般形式的 polyhedral projection：目标是把 c 投影到 {x | Ax=b, x in K}，其中 K 是“简单”polyhedron，可高效计算 Pi_K 及其 multiplier。表面上这是一个强凸 QP，primal 解唯一；真正困难在 dual SSN 解 ∇φ(y)=A Pi_K(A^T y+c)-b=0 时，退化会让 generalized Jacobian AUA^T 奇异。

关键矛盾是：dual residual 由 primal projection 决定，但 Newton 线性化依赖 dual representative 和 active multiplier 支持集。多个 y 可以给出同一个 Pi_K(A^T y+c)，因此 residual 相同，却可能产生完全不同的 Han-Sun generalized Jacobian。classical SSN 默认当前 y 是合适代表；在 LICQ 失败、active gradients 线性相关、multipliers 非唯一时，这个默认选择会失效。

以前方法通常在奇异系统上 regularize 或 perturb。这样可以让线性代数步骤跑下去，但没有解释为什么该 Newton 模型仍然对应正确的局部几何，也不能恢复标准超线性机制。本文实际要解决的是：在不假设 LICQ / strict complementarity / generalized Jacobian nonsingularity 的情况下，是否能结构性地恢复一个可用的 Newton linearization。

Motivation

已有 dual SSN 的理论瓶颈在于 nonsingular generalized Jacobian 通常被当作假设，而退化 projection 中这个假设恰好最容易失败。尤其在 OT 小正则、simplex/product-simplex 稀疏解、nested box 约束同时活跃时，A 的行空间和 active inequality gradients 的张成空间会发生重叠，导致 AUA^T 退化。

作者的关键观察是：singularity 不一定属于 primal projection 本身，而可能属于选中的 dual representative。因为 Pi_K(A^T y+c) 只依赖某个等价类，沿着 projection-equivalent directions 移动 y 和 multiplier w，可以保持 projection/residual 不变，却改变 active multiplier support J；而 J 决定 Han-Sun Jacobian 中的 U=I-G_J^T(G_JG_J^T)^{-1}G_J。

缺口在于：一般 polyhedron 下，纯 dual 等价类 P(y) 可能没有 extreme point，因此不能直接复用 nearest doubly stochastic matrix 中的 vertex-selection 思路。需要一个更一般的几何对象，既总有 extreme point，又能把 extreme-point property 和 nonsingular Newton matrix 严格对应起来。

Core Idea

论文真正的核心是把退化 Newton 问题转成 representative selection 问题：不再修补一个坏的 Newton system，而是在保持 primal projection 不变的等价类里换一个 dual-primal multiplier representative，使新的 generalized Jacobian 天然 nonsingular。这改变了问题建模方式：regularity 不是外部假设，也不是通过 diagonal perturbation 强加，而是从同一个 projection-equivalence class 的极点几何中恢复。

为此引入 primal-dual lifted set Q(y,w)。这个 lift 的意义不是形式扩维，而是让集合获得 polyhedral extreme points，并让 extreme point 等价于 [A^T, G_J^T] 满列秩。换句话说，lift 把 multiplier nonuniqueness 从麻烦变成可利用的信息：support-reduction 逐步删除冗余 active multiplier，直到 active constraints 与 equality constraints 在 Newton 意义下不再冲突。

和 prior 的本质区别在于，prior 通常固定当前 dual 表示再处理病态线性系统；本文在 residual 不变的前提下重选 representation。这是一种 latent structure / representation alignment 型改进，而不是单纯更强 linear solver 或更多 regularization。它更 general 的原因也在这里：只要 polyhedral K 和 projection multiplier 结构存在，就可以在 lifted equivalence class 上做几何选择，而不依赖 Birkhoff / bipartite graph 等特殊结构。

Method

第一，定义 Q(y,w)。它解决的是纯 dual equivalence set 可能无极点的问题。Q 同时记录 y 和 projection multiplier w，用约束 A^T(y'-y)=G^T(w'-w), w'<=0, w'_{I^C}=0 保证 Pi_K(A^T y'+c)=Pi_K(A^T y+c)。核心变化是 residual-preserving move 被显式参数化。

第二，建立 extreme point 与 nonsingularity 的等价。若 J=supp(w)，则 (y,w) 是 Q 的 extreme point 等价于 [A^T, G_J^T] 满列秩，也等价于 G_J 满行秩且 W=A(I-G_J^T(G_JG_J^T)^{-1}G_J)A^T nonsingular。这一步是论文的理论中轴：它把“能不能做 Newton step”变成了“是不是 lifted polyhedron 的极点”。

第三，support-reduction correction。它解决如何从任意 representative 到达 extreme representative。机制上就是沿着 [A^T, G_J^T] 的 null direction 移动，同时保持 Q 可行并减少 multiplier support，直到满列秩。这个步骤不是优化目标本身，而是 active-set 去冗余。

第四，displacement bounds。它解决 correction 会不会破坏局部 Newton 收敛的问题。论文证明当 y 接近 P* 时，corrected representative 到最优 extreme representative 集 P_hat* 的距离由 dist(y,P*) 控制。因此 correction 不是任意跳跃，而是与局部误差同阶。

第五，globalized version。monotone extreme-point selection 保证 φ(y_hat)<=φ(y)，再用 Wolfe line search 处理 Newton step 的全局下降。这个组合解决远离解集时 correction 可能增加目标、Newton direction 可能非全局有效的问题。

Key Insight / Why It Works

最重要的 insight 是：退化 SSN 的病根不一定是 projection map 不够光滑，而是当前 dual representative 没有暴露正确的局部面结构。polyhedral projector 在每个面上是 affine 的；Newton matrix 实际上依赖选出的 active face normal 子集 J。如果 J 包含与 A^T 冲突的冗余方向，AUA^T 会丢 rank。extreme-point correction 的作用就是选择一个 minimal / independent support，使 A^T 与 G_J^T 的列空间不相交，从而恢复正定性。

这不是 scaling，也不是更强线性代数求解器；本质上是 representation alignment。它把同一个 residual 对齐到一个适合 Newton linearization 的 representative。可以类比为在多重 dual certificate 中选择一个 nondegenerate certificate，而不是对 degenerate certificate 做 regularization。

最可能的核心贡献是 Theorem 1 加 Proposition 4 的组合。Theorem 1 说明 extreme point 一定给出 nonsingular Jacobian；Proposition 4 说明这种选择在局部不会把点带离 Newton basin。只有前者会变成“每步可解但可能乱跳”，只有后者才支撑 superlinear convergence。

monotone correction 和 Wolfe line search 是必要的 globalization engineering，但相对核心机制是辅助。它们让算法成为完整可收敛方法，不过真正的新信息不是 Wolfe，而是 φ 在 Q 上变成 affine，从而可用 monotone pivot 找到不升目标的 extreme representative。

实验增益主要来自 correction 避免 singular / ill-conditioned Jacobian，而不是更好 stopping rule 或更多 test-time compute。需要注意的是，Algorithm 4 的每步 correction 有明显额外成本；在某些大规模 MDP 实例中，可靠性提升是用大量 correction time 换来的。因此“更鲁棒”成立，“更快”不普遍成立。

Relation To Prior Work

最接近的是 dual SSN for polyhedral projection、Han-Sun generalized Jacobian、nearest doubly stochastic matrix 的 vertex-selection 方法，以及退化约束优化中的 SRCQ / W-SRCQ 正则性分析。本文属于 semismooth Newton 在 degenerate variational geometry 下的 regularity recovery 路线。

与 classical SSN 的差异不是 Newton-CG 或 line search，而是 Newton step 之前先改变 dual representative。classical SSN 在当前 y 上取 generalized Jacobian，遇到奇异就 perturb；本文在同一 projection class 中选择 y_hat，使 generalized Jacobian 自身 nonsingular。

与 Hu et al. nearest doubly stochastic matrix 工作的差异更实质。后者依赖 orthant + bipartite graph 结构，projection-equivalent set 在该结构下有可操作 vertex；本文指出一般 polyhedron 中纯 dual set 可能没有 extreme point，因此必须 primal-dual lift。这个 lift 是本文相对 prior 的真正新增信息。

与 LICQ / strict complementarity / strong regularity 路线相比，本文不是假设 solution 满足正则性，而是证明每个 lifted equivalence class 都存在一个代表满足与 W-SRCQ 等价的 full-rank condition。这一点比较强：正则性从代表选择中恢复，而不是问题实例本身在原始代表上天然满足。

Dataset / Evaluation

实验覆盖三类场景：quadratically regularized OT、battery scheduling feasibility restoration、occupation-measure projection。它们都能产生大量 active constraints 和 LICQ 失败，因此与论文 claim 匹配。尤其 MDP occupation-measure 的构造明确制造 LICQ failure，能直接检验 correction 是否解决 generalized Jacobian singularity。

评价重点是 high-accuracy robustness，而不是 wall-clock superiority。结果基本支持核心 claim：classical SSN 在困难退化实例上常停滞到 1e-2 甚至更差，而 Algorithm 4 能稳定到高精度并呈现快局部收敛。这说明 representative correction 确实改变了局部 Newton 机制。

但实验也暴露 trade-off：correction 的开销在某些大规模实例非常大，尤其 m_E 大时。论文没有充分展示与 interior-point、active-set QP、first-order splitting 等非 SSN 方法的比较；作者也明确说实验目的不是证明整体最优。因此 evaluation 验证的是“修复 SSN 退化”而不是“解决所有 polyhedral projection 的最佳算法”。

benchmark leakage / hidden supervision 这类问题在这里不 relevant；数据构造透明，核心风险不是泄漏，而是 benchmark 偏向于能体现 correction 优势的强退化场景。这个偏向合理，但限制了对一般场景 runtime 优势的外推。

Limitation

第一，方法把 singular Newton system 的困难转移成 extreme-point selection 的困难。理论上 support-reduction 有有限步和多项式线性代数界，但一般 polyhedron 下这个步骤可能非常贵。文中未充分说明在大规模稀疏、复杂 K 上如何避免 correction 成为瓶颈。

第二，算法依赖能够高效计算 Pi_K 及 associated multiplier。论文假设 K 是 simple polyhedron；如果 K 的投影本身不便宜，整个框架的吸引力会明显下降。

第三，local theory 的关键是 displacement bound 和 active-set stability。虽然不需要预设 nonsingular Jacobian，但仍依赖 polyhedral structure、A full row rank、feasible set nonempty、projection multiplier 可获得等条件。它不是一般 nonsmooth convex optimization 的 universal degeneracy cure。

第四，数值上是否总应选择 extreme point 值得怀疑。极点保证 nonsingular，但不一定保证 condition number 最好。可能存在非极点或近极点代表能给出更好-conditioned W 且 correction 更便宜。文中未充分说明 extreme-point choice 在数值 conditioning 上是否最优。

第五，增益归因在实验上主要是 correction，但 monotone selection、Wolfe、regularized classical baseline 的实现细节都会影响曲线。对于 runtime，增益来源不清；有些案例 Algorithm 4 明显更慢，只是最终精度更高。

Takeaway

• 1. 退化 SSN 可以不靠 regularization 修补，而通过 equivalent representative selection 恢复 Newton regularity；这是可以迁移到其他多重 dual certificate / multiplier-nonunique 的问题中的思路。
• 2. primal-dual lift 是关键抽象：当纯 dual geometry 不够好时，把 multiplier 一起纳入状态空间，可以把不存在极点的问题变成可操作的 polyhedral extreme-point 问题。
• 3. 对退化约束优化，未来值得做的不是继续调 perturbation，而是设计低成本、结构化的 representative selection，最好直接优化 conditioning 而不只是满足 nonsingularity。
• 4. 这篇论文真正推动的是 SSN 退化理论的几何化：把局部正则性从假设变成可构造对象，但工程上还需要针对具体 K 和 A 的 fast correction 才能成为通用高性能 solver。

一句话总结

这篇论文把 degenerate polyhedral projection 中 dual SSN 的奇异 Jacobian 问题重写为 projection-equivalence class 内的 primal-dual extreme-point representative selection，是一条从 regularization 补丁转向几何正则性恢复的方法演化。