精读笔记
Problem Setting
【On finding exact solutions of linear programs in the oracle model】（arXiv preprint / 2026）
这篇论文实际处理的是一个经典但长期不干净的问题：在 separation oracle 模型下，如何从近似 LP 算法得到 exact primal 和 exact dual certificate。这里的难点不是求一个 ε-optimal point；cutting plane / ellipsoid 已经能做。难点是 oracle 只在被查询点附近吐出被违反的不等式，算法并不知道完整 A,b，更不知道哪些约束最终会形成最优面或 infeasibility certificate。
关键矛盾是：exactness 需要识别线性依赖、tight face、Farkas multiplier 这类离散/代数结构；而 oracle cutting-plane 过程天然只给连续的 approximate geometry。GLS 和 Frank-Tardos 的路线靠 bit-complexity 把连续问题离散化：高精度近似 + Diophantine approximation / rounding / LLL 识别低维子空间。本文试图把这件事完全改写为几何问题：只要约束法向之间没有太小的角度间隙，就能从 approximate dual certificate 中可靠地恢复 exact face structure。
以前方法卡在两点：一是 exact dual certificate 在 oracle model 中并不是 approximate primal solver 的自然输出；二是非满维可行域会让 volume-based cutting plane 停在“很薄”而不是“空/可行”，需要额外机制判断薄方向对应的真实等式。本文的核心就是把“薄方向”解释为由 δ_M 控制的可认证线性依赖，而不是通过数论 rounding 来猜。
Motivation
已有路线不够的地方很明确：oracle LP 的 polynomial exact algorithms 基本依赖 rational polyhedra 和 bounded facet complexity；在 real model 下，这些 bit arguments 没有意义。即便在 rational setting，GLS 的 dual recovery 也比较间接：先 primal ellipsoid，收集大量 oracle inequalities，再解 restricted dual，复杂且概念上绕。
作者的核心观察是：LP exactness 需要的不是 bit-length 本身，而是一个可分辨的几何间隙。若任意独立约束法向的线性组合都不能过度 cancel，即 δ_M 为正且不太小，那么 approximate Farkas combination 一旦足够小，就要么是真正的依赖/face 证书，要么暴露出 δ̂ 估计过大。这使得算法可以“自校准”：不需要预先知道 δ_M，也不用靠 rational rounding。
关键缺口因此变成：如何让近似 solver 不只说“没找到点/集合很薄”，而是吐出由 oracle 返回不等式组成的 approximate dual certificate。论文把 Burrell-Todd 对 ellipsoid 的 dual-variable 观点推广为一个黑盒 certificate extraction 框架，这是整篇工作的第二个动机支点。
Core Idea
最核心的建模变化是从 polyhedral LP 转到 conic embedding 后的 exact conic problems。Primal feasibility、dual feasibility、optimization 分别变成 strong conic feasibility、conic validity、conic minimum-ratio。这样 exact LP 的不同失败/成功情况都能用 cone 上的 valid inequality / Farkas certificate 来表达，避免在原 LP 里分别处理 feasibility、boundedness、optimality 的边界情况。
真正的算法思想是“approximate certificate drives exact face recursion”。每次调用 Approx-Conic-Dual：若得到 feasible point 就结束；若得到一个小范数非负组合，则用 Carathéodory reduction 和 δ_M 的角度间隙判断它是否对应真实线性依赖或真实 tight constraints。若是，就把这些约束设为 equality，投影到更低维子空间继续；若不是，则这组向量本身证明当前 δ̂ 过大。于是算法的信息流从 prior 的“近似点 → 数论 rounding → exact basis”变成“近似 dual combination → 几何间隙判别 → face recursion”。
和 prior 的本质区别在于：它不是把 c round 成短整数，也不是靠 vertex/facet complexity 定位 rational subspace，而是把 oracle 返回过的约束当作一组有限法向集合，在这组集合上做几何 conditioning。目标向量 c 只进入 validity/min-ratio 的查询，不进入复杂度条件数；优化的 condition 依赖 (A,b) 的 conic embedding M，而不是 c 的 encoding。
Method
1. Conic embedding：解决 LP 情况分裂的问题。P={x:Ax≤b} 被嵌入 K={(x,t): tb-Ax≥0,t≥0}。t>0 对应 primal feasible point，t=0 对应 recession cone。这样 feasibility、dual feasibility、optimization 都能归约到 cone 上的 validity/minimum-ratio。必要性在于 exact certificate 在 cone dual 里更自然，且 face recursion 可以统一写成 M_F x=0。
2. δ_M condition number：解决 approximate-to-exact 的阈值问题。δ_M 是行向量集合的最小独立线性组合间隙，等价于任一行到其他行 span 的最小角度。它保证 extreme ray 对非 incident constraint 的 slack 要么为 0，要么至少 δ_M·norm-scale。这是把“近似 tight”变成“真正 tight”的关键。
3. Adaptive δ̂：解决 δ_M 不可知且难算的问题。算法从 δ̂=1/n 开始，若某步无法把 approximate certificate 合法解释为 exact certificate，就输出一组独立行及系数，证明 δ̂>δ_M，然后把 δ̂ 降低到 min(δ̂^2, failure bound)。这个机制避免了预处理估计 condition number。
4. Recursive face identification：解决非满维和 exact subspace 识别。若 approximate Farkas combination 可转成 M^T λ=0，则 support 上约束对整个 K tight，可递归到 ker(M_F)。在 validity/minimum-ratio 中，递归可能基于“若 δ̂≤δ_M 则某些约束必须 tight”的条件判断，因此还需要后续 pullback 检查。
5. Pullback：解决递归证书只在投影子空间有效的问题。子问题得到的 dual certificate 可能含有对新 equality 的负系数，不能直接作为原问题证书。Lemma 4.4 的作用是：要么把 precertificate 修成非负 certificate，要么构造 δ̂ failure。这个步骤是技术核心之一，也是 n^5 log log 项的主要来源。
6. Approx-Conic-Dual extraction：解决 cutting-plane 方法 primal-only 的问题。论文用 certified concave quadratic forms 统一解释 ellipsoid、geometric rescaling、Vaidya/JLSW volumetric cutting plane：如果算法证明可行域在某方向很薄，则可以从已见 oracle inequalities 的组合中抽出 approximate Farkas certificate。这里的实质不是新 cutting-plane，而是把 primal progress measure 翻译成 dual certificate。
Key Insight / Why It Works
最重要的 insight 是：exact LP in oracle model 的核心不是高精度求解，而是 face lattice 的可认证恢复；δ_M 给出了 face lattice 的几何分辨率。只要 approximate certificate 的误差小于这个分辨率，极射线和约束之间存在 gap：slack 不能处于模糊中间态。这使得算法能安全地把某些约束固定为 equality。
强 conic feasibility 部分最干净：Approx-Conic-Dual 返回近似零的非负组合。若 Carathéodory 后的独立 support 仍非零但范数太小，就直接违反 δ_M 定义，说明 δ̂ 错；否则得到真实依赖 M^Tλ=0，说明 support 约束在 K 上恒 tight。这个机制非常像“conditioned linear algebra + facial reduction”，但它是在 oracle 返回的稀疏约束子集上动态做。
validity/min-ratio 更难，因为 c 或 c-γd 不属于 M 的行集合，复杂度又不能依赖 c 的 condition。作者通过让 approximate certificate 中 c 的 multiplier τ 分情况处理：τ 小则去掉 c，退化为 feasibility；τ 大则说明 M 的某些大系数约束必须在反例/最优集中 tight。这里真正有效的是 δ_M 对 extreme rays 的二值化：某约束对 relevant extreme ray 的 slack 若小于 δ_M 阈值，就只能是 0。
最可能的核心贡献有两个：第一是自适应 δ̂ + failure certificate，使算法不需要知道 condition number；第二是 pullback，把“可能错误的递归降维”变成可验证过程，失败时反证 δ̂。Approx-Conic-Dual 的 JLSW 实现更多是 scaling/engineering 层面的最优 oracle complexity 接入；概念贡献在于说明 primal cutting-plane methods 其实隐含 dual certificates。
这不是 data/scaling/retrieval 类工作；如果类比机器学习术语，它更像引入了一个 better inductive bias：用几何 condition 控制 latent face structure 的恢复。JLSW 带来的 O(n log(1/ε)) oracle complexity 是 scaling component，但 exactness 的来源不是更快 solver，而是 certificate-aware 的 facial recursion。
Relation To Prior Work
最接近的谱系有三条：GLS/ellipsoid for rational polyhedra，Frank-Tardos cost rounding，和 conic/geometric rescaling/facial reduction。本文与 GLS 的共同点是都使用 separation oracle 和 cutting-plane thinness；本质差异是 GLS 用 bit-complexity + simultaneous Diophantine approximation 识别低维子空间，本文用 δ_M 的几何间隙和 approximate dual certificate 识别 tight constraints。
与 Frank-Tardos 的关系更微妙。Frank-Tardos 解决的是把任意目标 c 替换为短整数目标，从而让 optimization exact 且不依赖 c 的 encoding。本文也得到复杂度不依赖 c，但不是通过 rounding c，而是通过 conic minimum-ratio 和 validity certificate，使 c 只作为查询方向出现。对整数有界数据，δ_M 下界给出类似甚至更直接的 oracle-polynomial bound。
与 Burrell-Todd 的关系是实质继承和扩展。Burrell-Todd 说明 ellipsoid method generates dual variables；本文把这个思想抽象为 certified concave quadratic forms，并推广到 ellipsoid、geometric rescaling、volumetric cutting-plane/JLSW。这部分看似辅助，但对整个黑盒框架必要：没有 approximate dual certificate，后续 exact recursion 无从启动。
与 Vavasis-Ye / Tardos / circuit imbalance 相关工作相比，本文更 general 但也更弱。显式 LP 中 κ_A 或 χ̄_A 可以给出只依赖约束矩阵的优化算法；论文证明在 oracle model 下不能期望只依赖 A 的 optimization bound，因为 duplicate rows / hidden RHS 可以让 oracle 查询数任意大。因此 δ_M 依赖 (A,b) 不是缺陷，而是 oracle setting 的结构性代价。
哪些是已有思想重组：homogenization、Farkas duality、Carathéodory reduction、ellipsoid dual variables 都不是新概念。实质创新在于把它们组织成一个 oblivious-to-δ 的 exact oracle LP framework，并证明 approximate cutting-plane certificates 足以驱动 exact facial reduction。
Dataset / Evaluation
这篇是理论论文，没有实验数据集，也不应按 empirical benchmark 评价。它的 evaluation 是复杂度和适用性覆盖：feasibility、dual feasibility、bounded optimization、rational polyhedra、strong-to-polyhedral oracle 转换、显式 LP condition comparison，以及 impossibility results。
这些理论结果基本支持核心 claim：在 polyhedral separation oracle 下，可以在 real model 中找到 exact primal/dual solutions，复杂度由几何 condition δ 控制，而非 bit-complexity 或目标 c 的编码长度。尤其是 approximate solver 可用 JLSW 接入这一点，说明 oracle complexity 与当前最优 cutting-plane 近似求解器只差一个 O(n) 层级。
但 evaluation 的边界也清楚：它没有证明在一般 strong separation oracle 下完全摆脱 bit assumptions；Section 7 对 rational polyhedra 的处理仍在某些情况下回到 rounding/Diophantine post-processing。实际部署层面的 oracle 成本、数值稳定性、证书大小常数、real RAM 假设与 Turing bit growth，都不是本文主要验证对象。
Limitation
第一，polyhedral separation oracle 是强假设。它要求 oracle 返回来自某个有限不等式系统的真实行；标准 strong separation oracle 只返回任意 separating hyperplane。论文能在 bounded bit complexity 下转换，但这重新引入 rational/rounding 条件；因此“完全几何”主要成立在 polyhedral oracle 或 real-valued finite-row oracle 模型中。
第二，复杂度被 δ_M 控制，而 δ_M 可能极小，且即使显式给出矩阵也难近似。算法不需要预知 δ_M 只是避免输入参数，并没有消除 condition dependence。最坏情况下这不是 strongly polynomial；Proposition 1.1/1.4 也说明 oracle model 里不能期待完全强多项式，但这仍限制实际可扩展性。
第三，optimization 依赖 conic embedding M=(0,1; -A,b)，因此 RHS b 的几何位置会影响运行时间。作者证明不能只依赖 A，但这也意味着某些接近退化的 RHS 会让算法很慢。这里的困难不是 engineering，而是模型内在。
第四，pullback 和 certificate maintenance 较重。n^5 log log(1/δ) 项很可能主要来自证明型线性代数和失败检测框架，而不是不可避免的信息论成本。论文没有给出 lower bound 说明该项必要。
第五，Approx-Conic-Dual 的 JLSW 实现使用 real arithmetic 和 square roots；在 Turing model 中需要额外 rounding 控制。Remark 7.5 明确没有展开 bounded bit implementation。因此若关注 bit-level exact algorithm，本文给的是路线和多项式性，而非完整工程化 bit-complexity solver。
第六，dual certificate with oracle inequalities 的语义依赖 oracle 返回过的约束。若应用需要 standard facet dual solution，而 oracle 不返回 facets，则仍需额外处理；GLS 的 polarity/standard dual machinery并未完全被替代。
Takeaway
- 1. Exact oracle LP 的核心可以被看成 conditioned facial reduction：approximate solver 负责发现薄方向，δ_M 负责把薄方向转成真实面结构。
- 2. Dual certificate extraction 应被视为 cutting-plane 方法的一等输出，而不是后处理。
- Burrell-Todd 风格的 certified quadratic forms 可能可迁移到更多 oracle convex optimization 问题。
- 3. 目标向量 c 的复杂度不应是 oracle LP exact optimization 的瓶颈；真正瓶颈是约束系统 (A,b) 的几何退化。
一句话总结
这篇论文把 oracle model 下 exact LP 从 bit-complexity/Diophantine rounding 路线推进到 condition-number-driven 的几何 facial-reduction 路线，核心贡献是用 approximate dual certificates 和 δ_M 间隙自适应恢复 exact primal/dual certificates。