精读笔记

Problem Setting

论文标题：Sparsity-Cone SDP Relaxations and Applications to Variable Fixing for Sparse Quadratic Programs（arXiv preprint / 2026-06-23）。这篇论文处理的是带 ||x||0≤k 的一般稀疏二次规划，允许 indefinite Q、线性等式/不等式约束，并可扩展到部分 sparse QCQP。真正问题不是 NP-hard 这一点本身，而是在全局求解框架中需要一个既强又可频繁求解的 root/node relaxation。已有 SDP–RLT 强但太大：把 x 和 support 变量 z 一起 lift，矩阵维度变成 2n+1，还带大量 RLT/indicator 相关约束；普通 SDP 或简单 perspective 类松弛更轻但在一般 indefinite / constrained QP 上不够强或适用范围窄。关键矛盾是：support 选择需要强 convexification，但显式编码 support 会直接摧毁 SDP 的可扩展性。

Motivation

已有路线缺的不是又一个 valid inequality，而是一个能把 support-budget 信息从 binary-variable lift 中“压缩”出来的表示。作者的核心观察是：对 rank-one lift Y=[1;x][1;x]^T，稀疏性不一定要通过 z 表示，而可以通过 Y 的首行/首列和 X 的对角线之间的 perspective-like cone 关系表示。也就是说，SDP–RLT 中许多 support 变量的自由度在 relaxation 层面只是为了表达 x_i^2/X_ii 的 budget 分配，并非必须显式存在。这个缺口很重要：如果可以消去 z 但保留 SDP–RLT bound，就同时解决了建模规模、算法结构和 dual certificate 可读性三个问题。

Core Idea

核心思想是引入 sparsity cone K：要求 D(Y)=[kY11,Y12;Y21,Diag(Y22)]⪰0。对 Y=[1,x^T;x,X]，它等价于 sum_i x_i^2/X_ii≤k；对 rank-one 情形则精确等价于 ||x||0≤k。这是一个非常干净的建模转译：把 cardinality constraint 的 combinatorial budget 变成 diagonal perspective budget。

本质上，SC-SDP 不是削弱 SDP–RLT，而是把 SDP–RLT 中 z 和 n 个 perspective LMI 通过投影/消元合并为单个 cone constraint。它改变的是信息流：不再维护 support 变量之间的 lifted correlations，而只保留决定 SDP–RLT bound 所需的 marginal support allocation。这个选择很有针对性：保留 bound 所需信息，丢掉算法上昂贵但等价证明中可补全的自由度。因此它比 SDP–RLT scalable，也比传统 perspective 更 general，因为它不依赖 Q≻0 或无约束 regression 结构。

Method

第一，SC-SDP formulation 解决的是“强松弛太大”的问题。它保留 [1;x] 的 n+1 维 PSD lift、原始线性约束诱导的 RLT 约束 A(Y)=0,B(Y)≥0，并用 Y∈K 代替 z∈Z 与 perspective LMIs。核心变化是 bound 与 SDP–RLT 等价，但 support 表示从 explicit binary relaxation 变成 cone geometry。

第二，K 的 projection 解决的是“新 cone 是否可计算”的问题。由于 K 只作用于 Y11、Y12 和 diag(Y22)，off-diagonal X 不参与投影；剩余问题通过 Schur complement 化成 sum x_i^2/d_i≤ka，并进一步归约为一维 λ 方程。这是算法可行性的关键，不然 K 只是漂亮但不可用的建模对象。

第三，dual certificate 解决的是“relaxation 是否只给 lower bound”的问题。对偶中的 W 通过 w_i=W_{12,i}^2/W_{22,ii} 形成变量 score；若某变量 score 相对 top-k 边界差距超过 primal-dual gap，就可安全固定 z_i=0 或 z_i=1。screening cut 是同一逻辑的 support-pattern 版本。这里的核心变化是 SDP dual 不再只是 bound certificate，而被组织成 support presolve certificate。

第四，RiNNAL-S 解决的是“compact SDP 仍然大”的问题。低秩 phase 利用预期低秩解降低主计算，convex lifting phase 用投影梯度恢复全局收敛机制。它不是 relaxation 的数学核心，但决定了论文能否在 n 达到几千时跑出结果。

Key Insight / Why It Works

最核心的 insight 是：稀疏性在 SDP relaxation 中真正需要的不是 binary support vector 本身，而是每个坐标能否为 x_i 的二阶质量 X_ii 支付一个 support budget。关系 x_i^2≤z_iX_ii, sum z_i≤k 消去 z 后正好变成 sum x_i^2/X_ii≤k，也就是 K cone。这个消元是论文最实质的贡献，因为它解释了为什么能在不损失 SDP–RLT bound 的情况下砍掉一半 lift 维度。

真正有效的部分大概率是“等价消元 + 投影可解”这对组合。等价消元保证不是 trade-off；投影可解保证一阶/ALM 方法不会被新 cone 拖垮。dual fixing 是重要附加价值，但它的强度依赖 dual solution 和 gap，不如 relaxation 等价性那么基础。dual refinement 更像为了让 presolving certificate 好用而做的后处理；有价值，但不是理论核心。

这篇的增益主要不是 better bound，而是 scaling 和 representation compression。它没有声称超过 SDP–RLT；它的强点是“同样的 bound 以更便宜、更结构化的形式得到”。因此如果有人把它理解为新的更强 SDP hierarchy，是误读。它更像把已有 SDP–RLT 的冗余坐标系换成了一个更接近问题 latent structure 的坐标系。

实验中的大幅速度优势很可能主要来自模型维度下降、低秩解结构、以及 K/F projection 的工程化利用。文中未充分隔离这些因素的贡献：例如 SC-SDP formulation 本身、RiNNAL-S solver、低秩 phase、dual refinement 分别贡献多少并不完全清楚。但这不削弱主要结论，因为论文的 claim 本来就是 modeling+algorithm co-design。

Relation To Prior Work

最接近的谱系是 Shor SDP、SDP–RLT、indicator/perspective relaxation、以及 sparse regression screening/presolve。与 SDP–RLT 的本质差异不是 bound 更强，而是消去了显式 support lift；与 perspective relaxation 的差异是适用范围更一般，允许 indefinite Q 和额外线性约束，并通过 SDP lift 处理全局非凸二次结构；与 sparse regression screening 的差异是 certificate 来自 SDP dual，而不是强凸 regression perspective bound。

看似新的部分中，perspective LMI 和 support-budget 消元思想与已有 indicator/perspective 文献有连续性，尤其 Han–Gómez–Atamtürk 一类等价结果已经说明 Shor SDP 与 optimal perspective formulation 有深层关系。本文的实质创新在于把这种 equivalence 提升到带 RLT、一般 sparse indefinite QP 的 compact cone SDP 框架，并把 cone 的投影、对偶结构和 presolving 规则系统打通。

它属于“强 convex relaxation 的结构化压缩”路线，而不是“更高阶 hierarchy”路线。它推动的是同等 relaxation strength 下的 representational efficiency。

Dataset / Evaluation

评估覆盖面相对扎实：从 sparse ridge regression 到 equality-constrained ridge、sparse standard QP、binary QP、quadratic knapsack/QCQP，能说明 SC-SDP 不只是针对无约束 regression 的 trick。实验也覆盖了 bound quality、projection efficiency、solver scalability、presolving/fixing/screening 和 downstream Gurobi gap，基本对应论文主要 claim。

但 evaluation 的边界也很明显。第一，很多比较是 relaxation solver 层面的，不是完整 global solver 层面的；论文展示 presolve 信息能改善 Gurobi，但没有把 SC-SDP 深度集成进 branch-and-bound 并评估整体树规模/节点成本权衡。第二，SDP–RLT reference 有时来自更强或不同实现的模型，比较能说明规模优势，但不是完全 apples-to-apples 的 solver ablation。第三，大规模成功很大程度依赖 RiNNAL-S 和低秩结构；如果实例没有低秩友好性，scaling claim 的外推需要谨慎。总体看，实验支持“同等 bound 更可解”和“presolving 有潜力”，但还没有完全证明“作为通用 exact solver 组件会稳定优于现有 MIP/MIQP pipeline”。

Limitation

最大限制是 SC-SDP 的强度上限被 SDP–RLT 锁定：它保留 SDP–RLT bound，但不会自动突破 SDP–RLT。对于需要更强 convexification 的实例，compactness 不能弥补 relaxation gap。

第二，scalability 不是无限的。虽然矩阵从 2n+1 降到 n+1，但仍是 SDP；F projection 涉及 PSD projection，RLT 约束在 m,l 大时仍可能爆炸。论文提到 Ω(m^2)、Ω(l^2) 约束困难，但真正超大约束场景下的表现文中未充分说明。

第三，presolving 依赖 upper bound、lower bound gap 和 dual certificate 的选择。若 incumbent 差、SC-SDP gap 不够小、或 dual solution 不产生清晰 score separation，fixing/screening 会很弱。dual refinement 本身说明 certificate 非唯一性是实际问题；增益来源不清，可能对实例分布敏感。

第四，RiNNAL-S 的优势可能主要来自 scaling / engineering：低秩 factorization、adaptive ALM、structured projection、warm start 等共同作用。论文没有充分拆分哪些收益来自 cone formulation，哪些来自 solver 技巧。

第五，完整 deployment 仍未闭环。真正的 sparse QP global solution 需要 branch-and-bound 中反复求 relaxation、更新 incumbent、管理 cuts。论文目前更像提供强 root relaxation 和 presolve mechanism，而不是完整 scalable exact solver。

Takeaway

• 第一，最值得迁移的 insight 是：显式 binary support lift 往往包含可消元冗余；如果目标只是保持某个 SDP/perspective relaxation 的 strength，可以寻找作用在原始 lift 上的 cone 表示。
• 第二，K cone 展示了一种很有用的设计范式：rank-one 上精确、relaxation 上等价于已有强 formulation、projection 又低维可解。
• 这比单纯提出 valid inequality 更有长期价值。
• 第三，SDP dual 可以被重新解释为 presolving signal，而不只是 lower-bound certificate。

一句话总结

这篇论文把 sparse QP 的 SDP–RLT support lift 等价压缩成一个可投影的 sparsity cone，从而把强 SDP 松弛从“理论上紧但太大”推进到“同等强度且可用于大规模求解和 presolving”的结构化建模路线。