精读笔记

Problem Setting

论文标题：Strict complementarity in semidefinite programming, singularity degree, and the (dis)connection of forward and backward errors（arXiv preprint / 2026-07-15）。

这篇论文解决的不是 SDP strict complementarity 的定义问题，而是其失败时的结构、生成与数值可检测性问题。核心对象是 primal-dual SDP 的最大秩最优解 X*, Z*。若 rank(X*) + rank(Z*) < n，则 optimal primal face 和 dual slack face 没有填满整个空间，中间留下 gap。这个 gap 正是 backward error 与 forward error 脱钩的几何来源。

困难点在于，strict complementarity failure 在原始数据 A_i, b, C 中通常不可见。简单例子里可以手工看出某些行列必须为零，但一旦做行初等变换或 congruence rotation，这些证书会被打散。已有方法卡在两个层面：error-bound 理论知道 singularity degree 会导致 Hölder 型恶化，但它不是一个可生成全类 SDP 的 normal form；已有 hard-instance generator 能造例子，但没有覆盖所有 lack strict complementarity 的问题。

关键矛盾是：solver 通常报告的是 backward error，即约束违反、duality gap、DIMACS residual；但真正关心的是到 optimal set 的距离。在线性规划中两者有 Hoffman 型稳定联系；在 SDP 中，只要最优面与对偶最优面之间存在 rank gap，这个联系可以断裂，而且断裂未必伴随明显的 Slater failure 或坏 scaling。

Motivation

已有路线不够，是因为它们大多把 pathology 当成少数构造例子或 error-bound 上界现象来处理。Sturm 的例子已经说明 backward error epsilon 可以对应 forward error epsilon^(1/2^d)，但这不能回答这些例子是否代表一个大类，也不能告诉我们如何系统地产生和控制这种病态。

作者的核心观察是：lack of strict complementarity 可以被转化为两个最大秩证书的同时存在。primal 侧，Z* 加上一些约束矩阵可以作为 facial reduction sequence，把所有 primal optimal solutions 压到 X* 所在的最小面；dual 侧，X* 加上一些 Y_j 可以作为另一个 facial reduction sequence，把所有 dual optimal slacks 压到 Z* 所在的面。两个 sequence 覆盖不到的坐标就是 strict complementarity gap。

关键缺口是 normal form。没有 normal form，就很难区分“这个 SDP 本身坏”与“只是表示方式坏”；也很难判断 Slater 条件是否足以恢复 backward/forward error 的联系。论文的路线是把问题推进到结构层面：先刻画全体坏实例，再用生成器和实验问这种坏行为是否普遍。

Core Idea

论文最核心的思想是：把 strict complementarity failure 看成两个 regular facial reduction sequences 在 PSD cone 上的错位覆盖问题。给定 X* 和 Z*，通过允许的 reformulation，把它们放成块对角形式：Z* 在左上角有正定块，X* 在右下角有正定块，中间是 gap set。然后构造或证明存在两套证书：一套由 Z*, A'_1,...,A'_k 组成，证明 primal optimal set 只能落在右下角；另一套由 X*, Y_1,...,Y_l 组成，证明 dual optimal slack set 只能落在左上角。

这个建模改变很重要。它不再把 SDP 的困难理解为某个 residual 小不小，而是理解为可行/最优面如何通过 facial reduction 被逐步暴露。normal form 把“最大秩最优性”变成了线性代数上可读的 row/column elimination 结构。直觉上它有效，是因为 PSD cone 的面结构完全由支撑子空间决定；一旦某个 psd 矩阵与一个带正定块的证书内积为零，对应行列就必须为零。反复使用这个事实，就能把隐藏的最优面剥离出来。

与 prior 的本质区别是覆盖性。之前的生成器更多是构造一些失败 strict complementarity 的实例；本文的算法在 reformulation 意义下包含所有这类 SDP。它引入的 inductive bias 是 gap partition：所有坏实例都可以按 primal certificate 如何消去 gap、dual certificate 如何消去 gap 来组织。这比单个 Sturm chain 更 general，也更适合系统 benchmark。

Method

第一，normal form 负责把不可见的 rank gap 显式化。它解决的是证书在原始坐标中被混合的问题。通过 elementary row operations 和 admissible rotations，论文把最大秩 primal/dual optimality 转化为两套 regular facial reduction sequences。核心变化是：strict complementarity failure 不再是 rank 不等式的后验判断，而是 gap set 上两个 partition 的结构事实。

第二，Algorithm 1 负责生成所有 lack strict complementarity 的 SDP。它先固定 X*, Z* 和 gap partition，再选 A_i 与 Y_j，使两套 facial reduction sequences 同时成立，并通过 BASE 方程保证 dual-side certificate 与 primal constraints 正交。这里真正需要的是 BASE 正交关系，因为 Y_j 不直接出现在 SDP 中，但必须对所有 dual feasible slacks 都有效。

第三，Algorithm 3 加入 Slater 约束。它通过选择严格可行 Xbar, Zbar，并令 Delta X = Xbar - X*, Delta Z = Zbar - Z*，再强制 ORTH 条件和 Delta Z 属于 span{A_i}，使生成实例同时满足 primal/dual Slater。这个机制的意义是隔离变量：把 Slater failure 从病因候选中剥离出去，只保留 non-strict complementarity。

第四，Theorem 4 给出 singularity degree 等于约束数的判别：在 RR form 中，所有约束都参与最大秩证书且每个 critical block 非零。它解决的是生成实例困难度可控的问题。critical block 非零保证 facial reduction steps 不能被合并；否则多个步骤可被线性组合压缩，实际 singularity degree 会降低。

Key Insight / Why It Works

最重要的 insight 是：forward/backward error disconnect 的根源不是 solver 没把 residual 压够，也不只是 Slater failure，而是 optimal face 的暴露深度与 strict complementarity gap。backward error 看的是当前点离方程和 cone 的违反程度；forward error 看的是离 exact optimal face 的距离。当最优面需要多步 facial reduction 才能暴露时，一个点可以在 residual 上很接近，但仍在被隐藏的 gap directions 上离最优集很远。

normal form 成立的关键是 PSD cone 的零内积规则：若 X psd, Y psd 且 <X,Y>=0，则两者 range 正交；如果 Y 含某个正定块，则 X 对应行列必须为零。regular facial reduction sequence 把这个规则迭代化。每一步用一个证书消掉一批坐标，直到只剩 X* 或 Z* 的支撑。strict complementarity 失败则意味着 primal 和 dual 两个支撑之外仍有未被 rank 填满的 gap。

我认为最核心的贡献是 Theorem 1 的 normal form，而不是实验本身。实验重要，但它的说服力来自 normal form 生成器给出的结构覆盖性。Algorithm 1/3 是 normal form 的工程化结果；Theorem 4 是控制难度的关键补强。相对而言，condition number/spread 控制和随机旋转更像必要的 experimental hygiene，不是理论核心。

这不是 scaling 论文。困难不是来自更大 n、更差 conditioning 或更密集约束；反而作者刻意控制这些因素。也不是 retrieval/data coverage 问题。它本质上是 latent facial structure：solver residual 没有携带足够信息去恢复隐藏的 minimal face。若没有显式 facial reduction 或其他能识别 gap certificate 的机制，backward error 本来就不应该被期待成为 forward error 的可靠 proxy。

Slater 结果尤其值得注意。很多人会把 SDP 数值病态粗略归因于 Slater failure；本文表明这不够。两边 Slater 只能保证原始可行区域和对偶可行区域内部存在点，但它不保证 optimal face 上的 primal-dual pair strictly complementary。最优性引入了额外方程 <Z*,X>=0；病态发生在这个 enlarged optimal system 的 facial structure 中。

Relation To Prior Work

这篇最接近三条线：Sturm 的 SDP error bound 与 worst-case examples；facial reduction / singularity degree 理论；以及 Pataki 系列关于 SDP bad behavior 的 normal forms。它不是在 IPM 收敛理论上改进某个假设，也不是提出新 solver，而是为 strict complementarity failure 建立 normal-form 级别的结构理论。

相对 Sturm，本文的新增信息是从单个 worst-case chain 推广到全类参数化。Sturm 说明 singularity degree d 可以导致 epsilon^(1/2^d) 级别的 forward error；本文说明类似 disconnect 可以在大量非 Sturm、较少结构化、甚至双 Slater 的实例中出现。

相对已有 instance generators，如 Wei-Wolkowicz 或 Mohammadisiahroudi 等，本文的实质创新是覆盖性：生成器不是只产生一族 bad instances，而是在 reformulation 意义下包含所有 lack strict complementarity 的 SDP。这一点很强，因为它把 generator 从 benchmark tool 提升为结构定理的构造性版本。

相对 facial reduction 文献，本文的特别之处是双侧同步。单独把 primal optimal set 做 facial reduction 并不新；难点是同时安排 primal 证书和 dual 证书，并保持它们在允许 reformulation 下兼容。Theorem 1 的证明中最技术的部分正是把两个 reformulations 合并，而不破坏另一侧的 regular sequence。

Theorem 4 也有独立价值。singularity degree 的计算复杂性仍不清楚，因此给出 RR form 下最大奇异度的精确 critical-block 判别，是一个可迁移的结构工具。

Dataset / Evaluation

evaluation 的目标不是证明新算法更快，而是验证 normal-form generator 产生的 SDP 是否真的表现出 forward/backward error disconnect。任务覆盖两类实例：interval partition 结构和 Sturm-like 结构；每类又分 nonSlater 与双 Slater。这样设计基本覆盖了论文核心 claim 所需的对照：结构化 worst-case vs 随机化 gap partition，Slater failure vs non-strict complementarity。

实验有几个优点。第一，作者控制了 svec(A) 的条件数和 coefficient spread，避免把现象简单归因于坏 scaling。第二，用随机正交旋转打散显式 sparsity，使实例不像手写反例那样容易被结构识别。第三，sanity check 中 strict complementarity 成立的随机 SDP forward error 很小，这支持“主要困难来自 lack of strict complementarity”的归因。

但 evaluation 也有明显上限。forward error 实际使用的是下界，不是 exact distance；这足以证明存在严重误差，但不足以全面刻画误差分布。实验依赖 SDPT3/YALMIP 和 DIMACS residual，不能代表所有算法或所有 termination policy。没有系统测试 facial-reduction preprocessing、high precision、iterative refinement 或专门利用 normal form 的诊断算法。因此实验更像是 existence-and-prevalence evidence，而不是 deployment-level benchmark。

结论上，benchmark 支持核心 claim：小 backward error 不能可靠预测 true optimal-set distance，且 Slater 条件不能单独修复这个问题。但它还没有证明真实应用 SDP 中这种 gap structure 的频率，也没有证明所有 solver 都同等脆弱。

Limitation

第一，normal form 是存在性和生成性结果，不等于实用诊断算法。要把一个实际 SDP 自动 reformulate 到该 normal form，需要找到最大秩最优解、alternative certificates 或 facial reduction sequences；这些步骤本身可能数值不稳定或计算困难。文中未充分说明如何在真实问题中可靠恢复这些对象。

第二，strict complementarity failure 被刻画得很完整，但 forward error 的实际计算仍是下界。对于展示 disconnect 这没问题，但如果要比较不同实例族的困难度，定量结论要谨慎。

第三，Algorithm 1/3 的覆盖性是在 reformulation 意义下成立；实验分布仍然由作者选择的 partitions、random dense blocks、spread filtering 和 orthogonal rotations 决定。真实应用中的 SDP 是否落在这些分布附近，文中未充分说明。可能主要来自 scaling / data 的说法在这里不准确，因为作者确实控制了 scaling；但实例难度是否主要来自所选生成分布中的特定 gap geometry，仍有空间追问。

第四，双 Slater 结果容易被误读。论文并不是说 Slater 条件无用，而是说 Slater 对原始 primal/dual feasible sets 的正则性不足以控制 optimal set 的 forward error。真正应检查的是 optimality-augmented system 的 facial structure。这个 distinction 很关键。

第五，实验没有充分覆盖 solver ecosystem。SDPT3 的 residual 行为可能代表经典 IPM 的一种症状，但对于带 facial reduction preprocessing 的算法、精确 rational recovery、iterative refinement 或 custom certificate recovery，结论可能不同。增益来源不清的地方主要在实验层面：不同 generator 参数、singularity degree、gap partition size、constraint density 对 forward error 的相对贡献没有被完全分离。

Takeaway

• 1. lack of strict complementarity 应该被视为 SDP 数值分析中的一等结构病因，而不是 strict complementarity 假设缺失后的普通 degeneracy。
• 2. forward/backward error 的关系取决于 optimal face 的 facial-reduction geometry；仅检查 Slater、condition number 或 DIMACS residual 不够。
• 3. normal form 的价值在于把坏实例从少数反例变成可参数化对象。
• 以后构造 SDP benchmark 或设计 solver diagnostics，应该显式控制 gap set、facial reduction sequence 和 singularity degree，而不是只控制 n, m, sparsity, conditioning。

一句话总结

这篇论文把 SDP 中 strict complementarity 失败从零散病态例子提升为 normal-form 可参数化理论，并说明 forward/backward error 脱钩本质上来自隐藏的 facial structure，而不是简单的 Slater failure 或坏 scaling。