精读笔记
Problem Setting
论文标题：Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization（arXiv preprint / 2026）。
这篇论文实际解决的是一类凸 nonlinear conic programs：min f(x) s.t. Ax=b, g(x) in -K，其中 g 可以是非线性的 K-convex 映射。QCQP 是主要示例。问题的难点不在于写出 Lagrangian，而在于 saddle reformulation 中的 coupling Phi(x,y)=f(x)+<v,Ax-b>+<lambda,g(x)> 对 x,y 通常不是双线性的。
这直接破坏了过去 LP/QP 一阶 primal-dual 方法的核心结构：PDHG/PDLP/PDQP 的理论和实现都依赖线性算子 coupling Kx 与 y 的双线性项 <Kx,y>，因此可以用固定算子范数控制步长、用 Hoffman bound 建立 sharpness/quadratic growth、用 restart 放大 sublinear rate。这里 g(x) 非线性后，局部曲率随 x 和 lambda 同时变化，步长、误差界、gap 控制都需要重建。
关键矛盾是：想保留大规模一阶法的 matrix-vector / GPU-friendly 优势，同时又要处理 nonlinear functional constraints 带来的非双线性曲率。内点法可靠但 factorization-heavy；传统 FOPD scalable 但建模假设太窄。本文正是在这个缝隙里做扩展。
Motivation
已有路线不够的原因很明确：LP/QP/LCP 上的 restarted PDHG 成功并不是自动推广到 NCP 的。它依赖问题可化为 bilinear minimax；而 QCQP/NCP 的 <lambda,g(x)> 会让 x-gradient 中出现 lambda 加权 Hessian/curvature，算子不再是固定线性映射。
APDB 是自然起点，因为它本来就是为 smooth convex-concave 非双线性 saddle problem 设计的，并带有 backtracking，可以适应局部曲率。问题是 APDB 原始理论主要是 O(1/K) 或强凸情形 O(1/K^2) 的 sublinear guarantee，对中高精度求解不够。
作者看到的关键缺口是：能不能像 LP/QP 那样，把 APDB 的 sublinear gap decay 通过 restart 变成 linear convergence？但这需要新的 sharpness/quadratic growth 机制，因为 Hoffman bound 不再直接适用。论文的理论主线就是用 KKT mapping 的 metric subregularity 替代线性系统 Hoffman bound，并把它转化为 self-centered smoothed duality gap 的 quadratic growth。
Core Idea
真正核心思想不是“给 APDB 加 restart”这么简单，而是重建了非双线性 saddle problem 中 restart 能成立的证据链。base APDB 提供一个阶段内的 ergodic gap bound：运行 K 步后，smoothed duality gap 可以被当前初始点到解集距离平方乘以 O(1/K) 或 O(1/K^2) 控制。metric subregularity 再提供反向控制：距离平方可以被 self-centered smoothed duality gap 控制。两者闭合后，选足够大的 K 就得到外层收缩。
和 prior 的本质区别在于，LP/QP 的 restarted PDHG 依赖 bilinear coupling 下的 normalized gap / smoothed gap sharpness；本文把这个 sharpness 来源从线性代数结构转移到 variational analysis 的 KKT metric subregularity。这个迁移很重要：它允许 functional nonlinear constraints，但代价是理论常数变抽象，且 regularity 假设更难验证。
另一个实际核心是非单调 adaptive stepsize。论文理论允许 monotone 与 non-monotone backtracking，但实验上非单调步长几乎是主要性能来源。直觉上，这是因为 nonlinear coupling 的局部 Lipschitz 常数变化大，强行单调缩小步长会过度保守；允许步长回升等价于利用局部曲率的 test-time adaptation。
Method
1. APDB as base solver：解决非双线性 coupling。相比 PDHG，它不要求 coupling 是 <Kx,y>，而是通过线性化和 Bregman proximal step 处理 smooth convex-concave Phi。必要性在于 QCQP/NCP 的 dual multiplier 会改变 primal curvature，固定线性算子模型不成立。
2. Backtracking / adaptive stepsize：解决全局 Lipschitz 常数过大和难估的问题。论文给出 monotone 与 non-monotone 两种策略；non-monotone 允许步长在局部平坦区域增大。机制上，这不是普通调参，而是把曲率估计放入迭代过程，使方法不被最坏情况常数支配。
3. xy 与 yx 两种更新顺序：xy 先 primal 后 dual，yx 先 dual 后 primal。yx 在实验中更强，可能因为 dual update 先吸收当前约束残差，再给 primal 一个更即时的约束曲率信号。但 yx 理论上需要 dual domain restriction，以保证 compactness 和 Lipschitz 控制；这说明它的优越性并非完全 free。
4. Fixed restart：每 K_hat 步重启，用阶段输出作为下一阶段初值。它解决 APDB 只 sublinear 的问题。理论上 K_hat 只要大到使 gap-to-distance 的乘子小于 1，即可得到外层线性收缩。
5. Adaptive restart：用 self-centered smoothed duality gap 是否下降到 q 倍作为触发条件。它试图替代未知理论 K_hat，但计算 gap 需要解辅助强凸问题，因此实践中未必便宜。
Key Insight / Why It Works
最关键的技术 insight 是：对非双线性 saddle problem，直接使用普通 duality gap 往往不可行，尤其 dual domain 无界时 gap 可能为无穷；但 self-centered smoothed duality gap 是有限的，并且在 metric subregularity 下具有 quadratic growth。这个 gap 既能被 APDB 的阶段性 sublinear 分析上界，又能反过来控制到解集的距离，因此成为 restart 分析的中介变量。
这比简单套用 error bound 更细。作者没有假设 gap sharpness，而是从 KKT map metric subregularity 推出 gap quadratic growth。证明结构是：smoothed gap 的 maximizer T(z) 给出一个近似 KKT residual；该 residual 被 ||T(z)-z|| 控制；metric subregularity 把 residual 变成 distance；而 smoothed gap 的强正则项又下界 ||T(z)-z||^2。这个链条是本文理论上最实质的部分。
最可能的核心贡献：metric subregularity -> self-centered smoothed gap quadratic growth -> restarted APDB linear convergence。相比之下，xy/yx variants、固定/自适应 restart、GPU implementation 更偏工程和框架化组合。
性能增益的归因需要谨慎。实验看起来最强的因素是 non-monotone stepsize，其次是 yx update order，再其次才是 restart。在 non-monotone setting 下，APDB baseline 已经很强，restart 的边际收益变小。这说明实际速度提升不完全来自理论 restart 机制，很多来自更 aggressive local curvature adaptation。GPU speedup 则明显是 scaling/implementation 收益，不应解读为算法理论优势。
这篇没有 retrieval/data/memorization 这类机器学习问题；这里的“泛化”应理解为算法结构对问题类的覆盖。其 generality 来自 variational regularity 假设，而不是从实验中证明出来的普适性能。
Relation To Prior Work
最接近的谱系是 restarted first-order primal-dual methods for LP/QP：Applegate et al. 的 restarted PDHG/PDLP、Fercoq 的 smoothed gap quadratic growth、Lu-Yang 的 accelerated PDHG for QP、PDHCG、以及近期 HPR-LP/QP。那些工作本质上服务于 bilinear saddle formulation，核心 sharpness 多来自 Hoffman bound 或线性/二次结构。
本文的实质差异是把这套 restart 逻辑迁移到 nonlinear conic constraints 下的非双线性 saddle formulation。它没有发明全新的 primal-dual step，而是以 Hamedani-Aybat APDB 为 base，把 restart、smoothed gap、metric subregularity 重新组织起来。因此算法形态上是已有思想重组，但理论桥梁是新的。
和 Díaz et al. 的 EGM for QCQP 相比，本文更 general，且目标是 global linear convergence under metric subregularity，而不是 active-set identification 后的 local linear behavior。代价是方法和理论更复杂，尤其 yx 需要 dual bound/restriction。
和 APDB 原作相比，本文真正新增的是 restart 线性收敛理论，而非 APDB 本身。和 PDLP/PDQP 相比，本文牺牲了 bilinear simplicity，换来 nonlinear functional constraint 的覆盖。和 PDCS/一阶 conic solver 相比，本文理论保证更明确，但实验和实现成熟度还远不是 solver-level。
Dataset / Evaluation
实验覆盖两个场景：随机凸 QCQP 和 kernel matrix learning。它们确实对应论文主张中的 nonlinear / quadratic functional constraints，也能展示 matrix-vector/GPU-friendly 的价值。但覆盖范围仍集中在 QCQP/KML，没有展示 SOCP/SDP/指数锥等更广泛 cone，也没有真实工业规模 conic benchmark。
实验支持的 claim 有三个：APDB-type 方法在这些问题上比 EGM 更有效；non-monotone stepsize 非常重要；GPU 对这类一阶迭代有稳定加速。固定 restart 在 monotone setting 下有明显价值，在 non-monotone setting 下增益有限。adaptive restart 在 iteration count 上可行，但 wall-clock 被 smoothed gap 计算和辅助 QP 拖累。
实验没有充分支持“通用 nonlinear conic solver”这一强说法。随机 QCQP 的分布较人工，KML 只有少数规模设置；MOSEK 作为 baseline 合理，但一阶法目标通常是中等精度和大规模，实验没有系统展示精度-时间 tradeoff、内存极限、稀疏/低秩结构差异、病态 regularity 情形。增益来源也没有完全拆解：非单调步长、restart、yx 顺序、GPU scaling 混在一起，虽然有部分 ablation，但理论贡献和实际性能之间的因果并不完全清楚。
Limitation
第一，理论成立依赖 metric subregularity。作者给了 polyhedral cone 下的充分条件，并强调不需要 strict complementarity 或 multiplier uniqueness，这是有价值的；但这些条件仍然是局部二阶/critical cone 条件，实践中很难验证，常数也不可用。
第二，固定 restart 的理论周期依赖 quadratic growth 常数 rho，这基本不可调。实际只能 heuristic tuning。adaptive restart 看似解决这个问题，但 smoothed duality gap 计算需要解额外强凸问题；在实验里 wall-clock 代价明显，说明它可能只是把调参问题转移成 gap-evaluation overhead。
第三，yx 版本理论上需要 dual domain 截断，依赖 dual bound。这个 bound 可由 Slater point 给出，但实际求 Slater point和选择合适 B 并不总是便宜。更重要的是，实验中作者说明 yx variants 没有 impose set B，这意味着最强实践结果和最干净理论之间并不完全一致。
第四，compact X 是核心假设之一。很多大规模 conic/QP formulation 未必天然有简单 compact primal domain，或者 compactification 会引入额外尺度问题。
第五，性能上限可能由 smoothed gap computation、projection/prox 子问题、以及非线性 g 的 Jacobian/Hessian-vector 成本决定。论文强调 matrix-vector products，但对一般 nonlinear g，计算 ∇g(x)^T lambda 未必只是廉价 matvec；QCQP/KML 是相对友好的结构化案例。
第六，实验增益可能主要来自 aggressive non-monotone backtracking 和 GPU scaling。restart 理论很漂亮，但在最强 non-monotone 设置下，APDB baseline 已经接近 rAPDB，说明 restart 不是唯一甚至未必是主要 practical driver。
Takeaway
- 1. 对非双线性 convex-concave saddle problem，restart 分析的关键不是照搬 PDHG，而是找到一个既能被算法下降控制、又能通过 regularity 控制 distance 的 gap。
- self-centered smoothed duality gap 是可迁移工具。
- 2. Metric subregularity 是 nonlinear conic 一阶法线性收敛的自然替代品：它替代了 LP/QP 中 Hoffman bound 的角色。
- 但它带来的常数不可见问题会长期限制理论到 solver 的落地。
一句话总结
这篇论文把 LP/QP 中“sublinear primal-dual method + sharpness/error bound + restart = linear convergence”的范式，迁移到非双线性 nonlinear conic convex optimization；真正贡献是用 metric subregularity 建立 self-centered smoothed gap 的 quadratic growth，从而给 APDB restart 一个可证明的线性收敛闭环。