精读笔记

Problem Setting

[论文标题] On the Singularity Degree of Shor Relaxations for 0-1 Programs（arXiv preprint / 2026-07-15）

这篇论文实际处理的是 Shor SDP 松弛的 facial degeneracy：给定一个非空 0-1 可行集，其 Shor relaxation 是否满足 Slater；若不满足，需要多少步 facial reduction 才能到达 minimal face。关键不是优化目标，也不是 relaxation bound 的强弱，而是 feasible conic system 本身的正则性。

真正困难点在于 singularity degree 对 formulation 很敏感。相同的二进制集合可以有不同的约束描述，而 Shor lifting 保留的是描述中的约束结构，不只是集合本身。已有路线通常能做 facial reduction 或给 partial FR，但没有精确回答：线性定义的 0-1 集合是否可能有深层 SDP 退化？如果不可能，边界在哪里？如果允许二次定义，是否只是小幅恶化，还是可以恢复 Sturm 型长链？

这篇论文的关键矛盾是：arrow constraints 看起来已经把二进制结构强烈嵌入 PSD cone，似乎会压低退化复杂度；但二次约束的 linearization 又可能在 lifted space 中制造高阶 facial chain。作者证明两者的分界不是 arrow lift 本身，而是 defining constraints 是否仅为线性。

Motivation

已有工作给了几类局部或算法性 FR 工具，例如基于 LP 的 partial facial reduction、diagonally dominant cone 的一阶 reduction、以及利用原组合可行点的 primal FR。但这些工作更多是在“怎么做 reduction”，而不是“Shor relaxation 的 minimal face 到底有多深”。

作者抓住的缺口是：对 linearly constrained binary programs，Shor relaxation 的退化可能完全由 LP relaxation 的相对内部结构决定；如果这是真的，就不需要求解辅助 SDP 来恢复 Slater，只需要 LP 和线性代数。反过来，如果二次约束也有同样性质，那么 arrow constraints 可能提供了某种普适保护；论文的第二个结果正是反驳这一点。

所以动机不是改进一个 SDP relaxation，而是给出一个 sharp regularity boundary：线性描述下退化最多一层；二次描述下退化深度可随矩阵阶线性增长。这个边界对理解 Shor relaxation 的数值病态比单个 FR 算法更基础。

Core Idea

核心思想可以概括为：在线性约束情形，把 Shor relaxation 的 Slater 问题完全投影到 LP relaxation 的 relative-interior 问题；在二次约束情形，构造一种 formulation 让 Shor linearization 继承 Sturm SDP 的长 facial-reduction 链。

第一部分的关键是 arrow-constrained spectrahedron 的投影恒为 [0,1]^n，并且 x 有正定 lift 当且仅当 0<x<1。于是 Shor system 的严格可行性等价于存在一个 LP 点同时位于 open cube 且严格满足所有不等式。若不存在，退化只来自 LP slice 中固定为 0、固定为 1、或永远 tight 的 slack。Goldman-Tucker 证书把这些恒零分量一次性暴露出来，因此 singularity degree 只能是 1。

第二部分的核心不是简单把 Sturm 例子写成二进制 quadratic constraints，因为直接写 x_i^2-x_{i+1}=0 会被 arrow constraints 合并成一步暴露。作者通过 Vandermonde 旋转，把 Sturm 链施加到一组非奇异线性形式 ell_i(x) 上，使得原集合仍是 {0}，但 lifted constraints 的结构被旋转成每一步只能消去一个坐标的形式。这说明 formulation 可以把同一个离散集合从浅退化改写成深退化。

Method

1. LP 投影与正定 lift 判别：论文利用 B_n={Y PSD, Y_00=1, diag(X)=x} 的投影等于 [0,1]^n，并用 Schur complement 构造 Y(x)= [[1,x^T],[x,xx^T+D(x)]]. 这一步解决的是 SDP strict feasibility 看似高维的问题；必要性在于只有把正定 lift 和 open cube 精确对应起来，才能把 Slater 条件转化为 LP 条件。

2. 一步 facial reduction 证书：当不存在 open-cube 且 strict-slack 的 LP 点时，作者考虑 polyhedral slice U={(u,v,s)>=0: u+v=1, Au=b, Cu+s=d}. Goldman-Tucker 给出支持集正好等于恒零分量的非负 dual certificate。这个证书被组装成 W=sum alpha_i e_i e_i^T + sum beta_i(e_0-e_i)(e_0-e_i)^T 以及 slack 证书 gamma。它解决的是如何不用 SDP auxiliary system 就找到 minimal face；核心变化是把 PSD exposing vector 的构造降为 LP facial geometry。

3. minimal face 验证：论文不只给 exposing vector，还构造了 S 与 ri(F x G) 的交点。通过固定 0/1 坐标、保留自由坐标 J，并在自由坐标上构造正定 Schur complement，证明暴露出的 face 已经是 minimal face。这一步保证 singularity degree 不是“至多一步”的松界，而是精确的 0/1 dichotomy。

4. 高 singularity degree 构造：先说明直接二进制化 Sturm 链会失败，因为 arrow constraints 与 quadratic linearizations 可线性组合出 Diag(0,1,...,1)，一次暴露全部非零坐标。随后用 Vandermonde 矩阵 C 和其逆的行 d_i 定义 ell_i(x)=d_i^T x，并约束 ell_i(x)^2-ell_{i+1}(x)=0, ell_n(x)^2=0。congruence 后系统等价于一族 T_s；Hankel moment 结构迫使任何 first-step exposing matrix 只能是 E_ss 的倍数，因此 FR 必须逐坐标进行。

Key Insight / Why It Works

最核心贡献是把 linearly constrained case 的 SDP facial degeneracy 精确还原为 LP slice 的恒零结构。这里不是“LP 近似 SDP”，而是 arrow lift 的几何刚好让正定性只依赖 x 是否处在 open cube；不等式 slack 是否正则也完全是 LP 层面的事情。因此 Slater failure 没有空间形成多层 PSD degeneracy，它在第一步就被 LP strict-complementarity 证书全部暴露。

这也是为什么 sd≤1 的结果成立得很强：它不是 algorithm engineering，而是 minimal face 的结构定理。辅助的 LP relative-interior 构造只是实现层面的 consequence；真正的数学机制是 PSD cone 中 e_i 和 e_0-e_i 两类方向正好对应 x_i=0 与 x_i=1 两种 LP 边界。

第二个 insight 更重要：arrow constraints 本身并不防止长 singularity degree。直接 Sturm transcription 被 arrow constraints “短路”，但经过非奇异线性变换后，二次约束的 lifted 表示不再与 arrow constraints 对齐。Vandermonde/Hankel 结构让 PSD 条件递归地杀掉一行一列，而不是一次杀掉所有坐标。换句话说，高退化来自 representation misalignment：底层集合仍是 {0}，但 quadratic formulation 把简单集合编码成了长 facial chain。

最可能是核心贡献的是这两个 sharp contrast：线性描述 uniformly sd≤1；二次描述可达到 sd=n。LP-based Slater restoration 是重要推论，但不是最本质创新。不存在 scaling、data coverage、benchmark leakage 这类问题；这是一篇纯理论构造与刻画论文。若说有 engineering 部分，只是“可以用 LP 恢复 Slater”这一算法后果，核心增益来自几何结构识别。

Relation To Prior Work

这篇论文属于 conic optimization / SDP facial reduction 与 0-1 Shor relaxation 的交叉谱系。它最接近 Tunçel 关于 SDP relaxation Slater 条件的工作、Hu-Li/Hu-Yang/Hu-Xu 关于 Shor relaxation facial reduction 的工作，以及 Sturm 关于任意大 singularity degree 的经典例子。

本质差异在于，已有 FR 路线多提供 procedure 或 sufficient reduction，而本文给的是 exact singularity degree characterization。对线性约束 0-1 set，它不是提出另一个 partial FR heuristic，而是证明 standard singularity degree 只有 0 或 1，并给出 minimal face 的显式结构。

与 Sturm 的关系也不是简单复用。Sturm 例子说明 SDP 可以有任意大 singularity degree，但直接放进 binary Shor setting 会被 arrow constraints collapse。本文新增的信息是如何通过 Vandermonde 旋转让 Sturm 链在 Shor relaxation 中重新出现，并证明每一步只能暴露一个坐标。这是实质创新，因为它精确说明了 high singularity degree 在 binary Shor relaxation 中需要什么样的 formulation misalignment。

Dataset / Evaluation

这篇论文没有 dataset / empirical benchmark，evaluation 是数学证明和构造。核心 claim 也不需要实验支持：线性约束情形由 Theorem 3.1 给出充要条件和 minimal-face 构造；二次约束情形由 Theorem 4.1 给出任意维度上的 sd=n 构造。

从验证范围看，它完整覆盖了“非空、线性等式和不等式定义的 0-1 set”的 standard Shor relaxation，但不覆盖加入 RLT constraints、额外 valid quadratic cuts、quadratic inequalities、higher-order SDP relaxations 或不同 cone strengthening 后的情形。二次约束部分是存在性反例，强力支持“无统一上界”这个 claim，但不说明典型实际 QCQP formulation 的 singularity degree 分布。

因此 evaluation 对理论边界是充分的，对实际数值影响是不充分的。文中未充分说明 sd=1 与 sd=n 在真实 solver 中分别会造成多大 conditioning 差异，也没有比较 LP-based reduction 与现有 solver preprocessing 的实际效果。

Limitation

最主要限制是 formulation dependence 太强。论文的结论同时依赖于“standard Shor relaxation”与“约束如何写入 formulation”。如果加入额外有效不等式、RLT、quadratic valid constraints 或使用更高层 moment relaxation，minimal face 可能改变，sd≤1 的边界未必按原样保留。

线性约束结论很干净，但它的适用范围也很窄：原问题中的二次结构只能出现在 objective，不能作为 defining constraints。很多实际 0-1 quadratic models 会把逻辑关系、互斥关系、产品变量关系写成二次等式或二次不等式；这些 formulation 是否落入高退化风险，文中没有给出可操作判别。

高 sd 构造说明 worst-case 上限可以很坏，但该构造带有明显 adversarial 性质：Vandermonde 旋转制造了特殊 moment/Hankel 结构。它证明“不能指望统一 bound”，但不证明这种退化在自然建模中常见。增益来源不清的问题在这里表现为：理论上 singularity degree 高，但实际 solver 病态是否主要由这个 sd 驱动，还是由系数缩放、Vandermonde conditioning、数值尺度共同驱动，文中未充分说明。

另一个上限是算法后果仍停留在 identification minimal face：LP 可以找 relative-interior point 并恢复 Slater，但大规模 SDP 中如何稳定地完成 basis construction、face parametrization、以及与 solver 接口结合，仍是工程问题。论文没有声称解决这些 deployment 细节。

Takeaway

• 1. 对 standard Shor relaxation，线性约束的 0-1 feasible set 有一个非常强的 regularity guarantee：要么 LP relaxation 有 open-cube strict-slack 点从而 Slater 成立，要么一次 FR 到 minimal face。
• 这个结论可以直接迁移为 preprocessing 思路：先解 LP relative-interior 问题，而不是先碰 SDP auxiliary problem。
• 2. Shor relaxation 的 facial geometry 不是底层二进制集合的不变量，而是 formulation 的不变量。
• 同一个集合 {0} 可以通过线性描述得到 sd=1，也可以通过二次描述得到 sd=n。

一句话总结

这篇论文把 0-1 Shor relaxation 的 singularity degree 从经验性 FR 问题提升为 formulation-level 几何定理：线性描述最多一层退化，而二次描述可通过旋转 Sturm 链产生线性深度退化。