精读笔记

Problem Setting

论文标题：Lifting-Free Quadratic Sum-Of-Squares Programming（arXiv preprint / 2026-07-16）。

这篇论文解决的不是 SOS 建模能力问题，而是 QSOS 的求解表示问题。应用里自然出现的目标是 convex quadratic loss，比如 constrained regression 或 polynomial system identification；约束仍然是 coefficient matching 加 SOS/PSD cone membership。困难点在于，一旦用标准 conic solver 接收这个二次目标，常见做法会把它 lift 成 SOCP 或 SDP 约束，或者引入 slack/embedding，让本来已经由多项式次数和变量数导致组合增长的 cone structure 进一步膨胀。

真正卡住的是 solver interface 与问题结构之间的不匹配：QSOS 的二次项只作用在 free polynomial coefficients 上，而 SOS variables 主要承担 cone feasibility；通用 conic reformulation 往往把这些结构摊平成更大的线性锥问题。关键矛盾是：如果保留原始结构，通用 IPM/HSDE/ADMM 不容易直接给出高效闭式步；如果迎合通用 solver，又会引入额外 cone、slack 和 factorization 成本。

Motivation

已有路线不够的地方很明确：Schur-complement lifting 和 rotated-SOC lifting 本质上是在用更大的 cone 表达二次目标，这在小中型问题可接受，但在 SOS 中会和 monomial basis 的组合爆炸叠加。SCS、COSMO、Clarabel 虽然能处理 quadratic objective，但仍要依赖 slack variables、HSDE 或 repeated cone projections/factorizations，结构上并没有真正回到原始 QSOS。

作者的核心观察是：QSOS 的难点不一定需要通过 lifting 解决。若只 dualize affine coefficient-matching constraints，把 PSD cone membership 留在 primal minimization 里，那么每个 SOS block 的子问题天然就是一个 cone projection。缺的是让这个 primal minimization 足够 well-posed、smooth，并能提供可证明的 dual gradient；正则化正是为这个缺口服务。

Core Idea

核心思想是用一个很小但结构性很强的改动替代 lifting：给 SOS-constrained variables 加 ρ/2 ||ξ_sos||^2 正则项。这个正则不是普通 numerical stabilization，而是把 cone block 的 Lagrangian minimization 变成 PSD cone 上的 proximal projection，从而把原始 QCP 改写成一个 smooth concave dual maximization problem。

和 prior 的本质区别在于，它没有把 quadratic objective 编码成新 cone，也没有把 PSD membership 通过 slack equality 交给通用 embedding，而是重新组织了信息流：dual variable 只负责 affine constraints；free coefficients 通过 Q^{-1} 显式响应 dual signal；SOS blocks 通过 PSD projection 响应 dual signal。scalability 的来源不是更聪明的 factorization，而是避免生成更大的 conic problem，并把每步计算压缩为矩阵乘法加 blockwise PSD projection。

Method

1. 正则化 SOS variables：解决的是 dual subproblem 不够 smooth / primal minimizer 不够稳定的问题。引入 ρ 后，SOS block 的 minimization 变成 projection onto PSD cone，核心变化是把 cone-constrained optimization 变成显式 proximal map。

2. Partial Lagrangian dualization：解决的是 full conic lifting 带来的结构膨胀。只 dualize Aξ=b，不 dualize ξ∈K，因此 PSD cone 仍以原始 block 形式出现。核心变化是 dual space 维度只跟 equality constraints 相关，而不是跟 lifted cone embedding 一起增长。

3. 闭式 primal recovery：free variables 给出 S_f(λ)=Q^{-1}(A_f^T λ-w_f)，SOS variables 给出 S_sos(λ)=P_{S_+}(ρ^{-1}(A_sos^T λ-w_sos))。这一步不是实现细节，而是整个方法能成立的机制核心：dual gradient 可以直接写成负的 affine residual。

4. Smooth concave dual + accelerated gradient：通过 Moreau decomposition 和 PSD projection nonexpansiveness，得到 g(λ) 凹、可微且 L-smooth。于是求解变成无约束 smooth concave maximization。加速梯度只是自然选择，贡献不在 Nesterov 本身，而在问题被改造成适合 Nesterov 的形式。

5. 非渐近误差分解：最终 bound 同时包含 optimization error O(L/N) 和 regularization bias O(ρ)。这说明方法并不是精确免费午餐，而是在 lifting cost、iteration count、regularization bias 之间换取一个可控折中。

Key Insight / Why It Works

最重要的 insight 是：QSOS 的 quadratic objective 不必通过 conic lifting 消除；相反，可以通过 primal regularization 让 dual 变得光滑，并把 primal update 保持在原始 cone 上。这个视角把“二次目标导致通用 conic 表达困难”转化为“正则化后 dual 有 Lipschitz gradient，可用 first-order method 直接推进”。

真正有效的部分大概率是 partial dualization + PSD projection closed form，而不是 accelerated gradient 本身。Nesterov acceleration、adaptive restart、termination criteria 都是辅助工程；核心贡献是把原始 conic structure 保留下来，并让每个 SOS block 的响应变成独立投影。

这不是 retrieval / data coverage / representation alignment 一类机制，也不是 scaling law。它更接近 optimization formulation engineering：通过改变正则化和 dualization 的位置，避免 solver-level lifting。增益来源主要是 scaling：少了额外变量、额外 cone、HSDE/slack 结构，以及某些大线性系统或大 lifted PSD factorization。论文把这一点说成 lifting-free，是准确的。

但也要直接指出：它没有消灭 PSD projection 的成本。若 SOS block 本身很大，eigendecomposition 仍然贵；如果问题由少数巨大 PSD blocks 主导，而不是大量 equality constraints 或 lifted structures 主导，优势可能会收缩。文中“memory scaling only in number of equality constraints”的表述需要谨慎理解，因为 projection 所需的 block matrix 存储和谱分解成本并不会凭空消失。

Relation To Prior Work

最接近的谱系是 semidefinite least-squares / nearest correlation matrix 的 dual projection methods，以及 regularized SDP / Moreau-Yosida / augmented Lagrangian 相关思想。它不是从零发明一种新的一阶 conic solver，而是把 Malick/Higham 一类 dual projection 分析迁移到一般 QSOS/QCP 表达，并给出适配 SOS block structure 的 regularization 和收敛说明。

和 Schur/SOCP lifting 的差异是实质性的：prior 是把 quadratic objective 转成 cone constraint；本文是保留 quadratic objective，通过正则化使 dual smooth。和 SCS/COSMO/Clarabel 的差异也不是“first-order vs first-order”，而是是否通过 slack/embedding 改写 cone structure。本文的新增信息在于证明这种 partial dual + regularized SOS projection 可以形成一个完整 solver pipeline，并且给出 Reg-QCP 到 QCP 的误差项。

看似新的部分中，Nesterov acceleration、restart、PSD projection、Moreau decomposition 都是已有工具重组；实质创新是把这些工具放在 QSOS 的正确结构位置上，避免 lifting 后再求解一个更大的问题。

Dataset / Evaluation

evaluation 的覆盖比较窄：主要是 synthetic constrained regression，ground-truth SOS polynomial 生成数据，规模通过 polynomial dimension 和 degree 扩展。这类任务能很好地测试 coefficient matching + SOS PSD block + quadratic loss 组合下的 solver scaling，但不能代表完整 SOS 应用生态，尤其不能覆盖 control synthesis、region-of-attraction、system identification with noise/side information 等更复杂建模。

实验确实支持核心 claim 的一部分：lifting-free 方法在这些构造问题上比 lifted MOSEK 更可靠，也比 SCS 快一些。这基本验证了“避免 lifting / slack 可以带来内存和时间收益”。但实验没有充分隔离收益来源：到底是 regularized dual formulation 的优势，还是 MATLAB/SOSTOOLS parsing、problem conditioning、ρ=1e-6、SCS 设置、MOSEK 默认参数、synthetic data distribution 的共同结果，文中未充分说明。

更重要的是，benchmark 几乎是为该方法的结构优势量身合适的：Q 被构造成正定，数据规模和 conditioning 被控制，任务是单一 constrained regression。它没有证明在 ill-conditioned、sparse/chordal、multi-constraint heterogeneous SOS 或真实工程控制问题上仍然保持同样优势。

Limitation

1. 正则化 bias 是方法内生代价。Theorem 4.5 明确给出 O(ρ) 项；ρ 不是无害超参数。ρ 小则更接近原 QCP，但 L 含 1/ρ，导致步长变小、迭代数上升；ρ 大则解偏离原问题。这个 trade-off 是核心上限，不是实现细节。

2. 理论条件偏强。Q 需要正定，Slater 条件用于强对偶和 coercivity，Theorem 4.3 还假设每个 Z^{(j)}=A_sos^{(j)}A_sos^{(j)T} invertible。很多实际 SOS 问题存在冗余等式、退化 cone face、低秩 Gram representation 或病态 coefficient matching，这些条件未必自然满足。

3. 成本被转移而非消除。lifting-free 避免了额外 cone 和 embedding，但每轮仍要做 PSD projection。若 block dimension h_j 很大，eigenvalue decomposition 会成为主瓶颈。论文强调 memory scaling with equality constraints，但对 PSD block spectral cost 的实证拆分不足。

4. evaluation 不足以支撑广泛 solver claim。当前实验只覆盖 constrained regression synthetic benchmark，增益可能主要来自 scaling / data construction / solver reformulation mismatch。对真实 SOS workloads 的泛化能力文中未充分说明。

5. 收敛保证与实际可用精度之间仍有空隙。理论 bound 依赖 B、L、||λ0-λ*|| 和未知 ξ*_sos norm，实际并不直接给可操作 iteration budget。termination 用 residual 和 gap，但与原始 unregularized QCP 的最终误差之间仍需更清楚的 practical calibration。

Takeaway

• 1. 最值得迁移的 insight 是：在结构化 conic QP 中，不一定要把二次目标 lift 成标准锥形式；可以通过轻量正则化把 primal cone operation 变成 proximal map，再在 dual 上做 smooth optimization。
• 2. 对 SOS solver 设计而言，真正重要的是保留 block cone structure 和 affine matching 的分离，而不是盲目追求统一标准形式。
• solver interface 的“标准化”本身可能就是 scalability bottleneck。
• 3. 未来更有价值的方向不是再换一个一阶优化器，而是 adaptive regularization、block sparsity/chordal decomposition、warm-start continuation in ρ，以及针对 degenerate SOS constraints 的 robust dual formulation。

一句话总结

这篇论文在 QSOS 求解谱系中的位置是：用正则化和 partial dualization 替代二次目标 lifting，把大规模 SOS-QCP 从通用锥嵌入问题改造成原始 cone 上的光滑 dual projection 方法。