The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm¶
会议: NeurIPS 2026
arXiv: 2605.25635
OpenReview: https://openreview.net/forum?id=A5qzAwIMSD
领域: 模型压缩
关键词: 线性规划压缩、决策相关子空间、仿射投影、样本压缩方案、快速收敛率
一句话总结¶
本文从几何视角揭示了重复求解线性规划（LP）中精确保持最优解的最小子空间结构，提出了基于样本压缩理论的自适应仿射降维学习算法，实现了在无非退化性假设下 \(1 - \widetilde{O}(d^{\star}/n)\) 的快速泛化保证与零最优性损失。
研究背景与动机¶
在物流调度、网络路由、资源分配以及上下文线性优化等实际决策场景中，系统往往需要在固定可行域多面体上反复求解目标函数随时间或环境波动的线性规划（LP）。当问题维度极大时，每次在线完整求解开销昂贵。近年来涌现的数据驱动降维投影方法（如 Sakaue & Oki 2024、Iwata & Sakaue 2025）试图通过样本学习低维替代 LP 来加速求解，但此类方法依赖基于伪维数的一致收敛界，不仅只能提供近似目标值保证、泛化收敛速率慢至 \(\widetilde{O}(1/\sqrt{n})\)，而且通过原点的齐次线性投影往往会破坏全单模结构与极点整性，导致松弛解无法直接映射回离散组合极值。
这一瓶颈的核心矛盾在于：现有降维方法将投影矩阵视为黑盒参数进行启发式优化，未从优化几何层面刻画究竟何种子空间能够在压缩变量维度的同时「严格保持最优解集不变」。先前的充分决策数据集（SDD）理论虽证明了决策相关子空间 \(\operatorname{dir}(\mathcal{X}^{\star}(\mathcal{C}))\) 决定了最优性判定所需的信息，但在求解器端缺乏可操作的降维重构体系，且已知精确重构该全局基底在计算上具有 NP-hard 与 coNP-hard 复杂度；此外已有的样本学习算法强依赖非退化性假设，在实际退化的重复 LP 中容易失效。
本文的切入角度是打破通过原点的传统齐次投影范式，转向以可达最优极点为锚点的仿射切片，并建立决策相关子空间与求解器端低维重构的精确等价关系。核心 idea：将线性规划压缩严格约束在由可达极点锚定的决策相关仿射流形上，利用主动探测违约极点的序贯采样算法逐步扩张基底，借助稳定样本压缩理论建立无退化性假设且具备 \(1 - \widetilde{O}(d^{\star}/n)\) 快速率保证的零损失低维 LP 学习范式。
方法详解¶
整体框架¶
本文方法的目标是针对固定多面体 \(\mathcal{X} = \{x \in \mathbb{R}^d : Ax \le b\}\) 与动态成本向量 \(c \in \mathcal{C}\)，构建维度 \(r \ll d\) 的压缩 LP，使得求解低维问题后的仿射逆映射能够精确恢复原始高维 LP 的最优解集 \(\mathcal{X}^{\star}(c)\)。
整体流程包含三个核心阶段：离线先验校准（构建高概率凸先验集 \(\widehat{\mathcal{C}}\) 排除极端离群实例）、自适应基底扩张（序贯检验样本最优面是否完全落入当前仿射切片，若不满足则拉取未覆盖极点作为新基向量）以及在线仿射求解（在降维变量空间求解紧凑 LP 并无损映射回原多面体极点）。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["历史成本样本集<br/>{c_1, ..., c_n}"] --> B["校准凸先验集<br/>Mahalanobis 椭球截断"]
B --> C["锚点选择与基底初始化<br/>x_0 in X*(C), U_0 = []"]
C --> D["自适应基底扩张<br/>最优面包含检验与极点增广"]
D --> E["生成精确低维 LP<br/>z in R^r, r <= d*"]
E --> F["在线极点解重构<br/>x* = x_0 + U_n z*"]关键设计¶
1. 基于可达极点锚定的仿射切片与极点无损保持：破除齐次投影的维度与整性冗余
传统降维方法采用齐次投影 \(x = P y\)，将可行域限制在穿过原点的线性子空间 \(\mathcal{X} \cap \operatorname{range}(P)\) 中。当原多面体的最优解集合远离原点时，齐次子空间必须白白浪费额外的基维度来拟合原点到最优面的偏移位移；对于二维平面上的右侧边界线段（如 \(x_1=1, x_2 \in [-1, 1]\)），任何一维齐次投影都会导致期望目标值至少 \(1/2\) 的不可消除次优间隙。
本文建立精确仿射降维定理：选取任意可达最优解 \(x_0 \in \mathcal{X}^{\star}(\mathcal{C})\) 作为空间锚点，若列满秩矩阵 \(U \in \mathbb{R}^{d \times r}\) 满足 \(\operatorname{range}(U) \supseteq \operatorname{dir}(\mathcal{X}^{\star}(\mathcal{C}))\)，则仿射子空间 \(V = x_0 + \operatorname{range}(U)\) 精确保持全部最优解。定义低维压缩可行域 \(\mathcal{Z}_{U,x_0} := \{z \in \mathbb{R}^r : A(x_0 + U z) \le b\}\)，原高维 LP 可严格等价转化为仅有 \(r\) 个变量的紧凑形式： $$ \min_{x \in \mathcal{X}} c^{\top} x = c^{\top} x_0 + \min_{z \in \mathcal{Z}_{U,x_0}} (U^{\top} c)^{\top} z $$ 更关键的是极点对应性质：逆变换 \(T_{U, x_0}(z) = x_0 + Uz\) 是从 \(\mathcal{Z}_{U,x_0}\) 的极点集到原多面体极点集 \(\mathcal{X}^{\angle}\) 的一一映射。当原问题具有全单模约束（如最短路、最小费用流、二分图匹配）时，低维求解器返回的极点解经变换后必然保持原始问题的离散整数特性，彻底解决了传统投影无法保证极点解可行性的难题。
2. 最优面包含检验与自适应贪心增广：规避非退化假设的序贯基底学习
精确构造最小维度基底 \(d^{\star} = \dim \operatorname{dir}(\mathcal{X}^{\star}(\mathcal{C}))\) 属于 NP-hard 且 coNP-hard 难题，且现实系统存在大量几何退化（多个约束同时激活导致最优解不唯一）。先前的 SDD 学习依赖强非退化性假定，无法处理退化最优面。
本文提出基于多面体人脸包含判据的主动增广机制。算法顺序遍历训练样本 \(c_i\)，首先求解原 LP 得到最优值 \(v(c_i)\)，再针对当前子空间正交补空间 \(S^{\perp} = \operatorname{range}(U_i)^{\perp}\) 的正交基 \(a_j\)（\(j=1,\dots,d-r\)），构建辅助验证 LP： $$ \max_{x \in \mathcal{X}, c_i^{\top} x = v(c_i)} a_j^{\top} (x - x_0), \qquad \min_{x \in \mathcal{X}, c_i^{\top} x = v(c_i)} a_j^{\top} (x - x_0) $$ 当且仅当所有辅助 LP 最值均为零时，证明最优面完全被当前切片包含；若存在任意非零值，该辅助 LP 的极值解即为落在当前子空间外的原生极点 \(x \in \mathcal{X}^{\star}(c_i) \cap \mathcal{X}^{\angle}\)。算法直接将其差分向量 \(x - x_0\) 拼接入 \(U\)，使子空间秩严格递增 1。该机制无需任何非退化性假设，确保在至多 \(d^{\star}\) 次增广后彻底终止，且每次更新仅需多项式复杂度的标准 LP 求解。
3. 基于稳定样本压缩方案的快速泛化保证：从根源实现 \(O(1/n)\) 收敛速率
传统基于伪维数（pseudo-dimension）的统一收敛界分析投影误差时，收敛速率受限于慢速的 \(O(1/\sqrt{n})\)。本文将增广算法形式化为二值预测问题上的「可实现且稳定」的样本压缩方案（Stable Sample Compression Scheme）。
在算法运行过程中，仅有触发了增广操作的「困难样本」（hard instances）会被加入压缩子序列 \(T_n\)。由此建立关键代数性质： - 稳定性（Stability）：从训练集中删除任何未触发增广的非困难样本，算法在子集上重新运行将产出完全相同的基底矩阵 \(U_n\)； - 可实现性（Realizability）：最终学得的仿射切片在所有历史训练样本上均达到零失败率（即包含全部训练最优面）； - 基数上界：困难样本总数满足 \(|T_n| \le \operatorname{rank}(U_n) \le d^{\star}\)。
借助稳定样本压缩泛化理论，对任意测试成本 \(c \sim P_c\)，算法在不可见实例上精确恢复全最优解的概率满足： $$ \mathbb{P}_{c \sim P_c}\left[\mathsf{Exact}(U_n, x_0, c)\right] \ge 1 - \frac{4}{n} \left(6 |T_n| + \log \frac{e}{\delta}\right) \ge 1 - \frac{4}{n} \left(6 d^{\star} + \log \frac{e}{\delta}\right) $$ 该界建立了严格的 \(1/n\) 快速率保证，且复杂度仅依赖内生决策维度 \(d^{\star}\) 而非环境维度 \(d\)。
4. 容忍度校准先验与压缩-最优性可控权衡：主动剔除极端尾部实例
在实际未知先验分布的情形下，为了避免为发生概率极低的罕见离群样本付出巨大的维度开销，本文设计了基于非参数容忍区间的估计先验 \(\widehat{\mathcal{C}}_{\rho, \delta_0}\)。
将独立试验样本划分为拟合集与校准集，拟合岭岭 Mahalanobis 距离度量 \(s_{\widehat{\theta}}(c) = (c - \widehat{\mu})^{\top} (\widehat{\Sigma} + \lambda I)^{-1} (c - \widehat{\mu})\)，并根据二项分布分位数截断得到凸椭球先验 \(\widehat{\mathcal{C}}\)，使得样本落在先验外的尾部概率被严格控制在 \(\rho\) 以内。在估计先验内保留的 \(n_1\) 个样本上运行算法，可得泛化保证： $$ \mathbb{P}{c \sim P_c}\left[\mathsf{Exact}(U}, \widehat{x0, c)\right] \ge 1 - \rho - \frac{4}{n_1} \left(6 \widehat{d}\right) $$ 用户可通过调节容忍度参数 } + \log \frac{e}{\delta_1\(\rho\)，在压缩率（更小的降维维度 \(\widehat{d}_{\star}\)）与最优性恢复概率之间进行精确权衡。
实验关键数据¶
主实验¶
在未给验先验集合的实用设定下（Unknown-Prior），对比本文校准精确压缩方法（OursEstC，目标外部质量参数 \(\rho=0.1\)）、基于 PCA 的数据驱动投影方法（DataDrivenProj，Sakaue & Oki 2024）以及基于神经网络的实例级投影基线（FCNN-c，Iwata & Sakaue 2025）。基线被赋予与 OursEstC 相同的降维预算 \(K = d(\rho)\)。评价指标为测试集平均目标值比率（Test Objective Ratio = 方法求得解的目标值 / 全量 LP 真实最优值，值越接近 1.0 越优）。
| 实例名称 | 原始维度 \(d\) | 生成子空间秩 \(r_c\) | 学得维度 \(d(\rho)\) | OursEstC (本文) | DataDrivenProj (PCA) | FCNN-c (神经网络) | 相对最优间隙消除 |
|---|---|---|---|---|---|---|---|
| Packing | 360 | 28 | ~22 | 0.9998 ± 0.0001 | 0.9852 ± 0.0031 | 0.9915 ± 0.0020 | 完全恢复 |
| MinCostFlow | 360 | 28 | ~8 | 1.0000 ± 0.0000 | 0.9984 ± 0.0012 | 0.9950 ± 0.0025 | 零误差且保持整性 |
| ShortestPath | 480 | 16 | ~10 | 1.0000 ± 0.0000 | 0.9991 ± 0.0005 | 0.9972 ± 0.0011 | 零误差且保持整性 |
| RandomLP A | 140 | 24 | ~18 | 0.9995 ± 0.0002 | 0.8120 ± 0.0210 | 0.9230 ± 0.0150 | 提升 +8.3%~18.7% |
| RandomLP B | 180 | 26 | ~20 | 0.9997 ± 0.0002 | 0.7450 ± 0.0280 | 0.8910 ± 0.0180 | 提升 +12.2%~25.5% |
| RandomLP C | 220 | 28 | ~22 | 0.9994 ± 0.0003 | 0.7810 ± 0.0250 | 0.9050 ± 0.0160 | 提升 +10.4%~23.4% |
| RandomLP D | 260 | 30 | ~24 | 0.9996 ± 0.0002 | 0.7230 ± 0.0310 | 0.8840 ± 0.0200 | 提升 +13.1%~27.7% |
| GROW7 (Netlib) | 301 | 20 | ~19 | 0.9989 ± 0.0005 | 0.6520 ± 0.0350 | 0.8110 ± 0.0240 | 提升 +23.1%~34.7% |
| SC205 (Netlib) | 203 | 20 | ~15 | 0.9992 ± 0.0004 | 0.7180 ± 0.0320 | 0.8650 ± 0.0210 | 提升 +15.5%~28.1% |
消融实验：先验容忍度 \(\rho\) 与降维维度的权衡¶
以典型难解测试实例（Packing 与 RandomLP B）为例，分析改变高概率凸先验丢弃尾部质量 \(\rho\) 时，学得的决策维度 \(d(\rho)\)、最优解完全恢复率以及目标值比率的变化表现。
| 配置 (\(\rho\) 设定) | 学得维度 \(d(\rho)\) (Packing) | 目标比率 (Packing) | 学得维度 \(d(\rho)\) (RandomLP B) | 目标比率 (RandomLP B) | 说明 |
|---|---|---|---|---|---|
| \(\rho = 0.02\) (极度保守) | 26.8 ± 0.8 | 1.0000 ± 0.0000 | 24.5 ± 0.5 | 0.9999 ± 0.0001 | 保留近乎全集，维度接近 \(d^{\star}\) 上限 |
| \(\rho = 0.05\) (低容忍) | 24.1 ± 0.6 | 0.9999 ± 0.0001 | 22.2 ± 0.6 | 0.9998 ± 0.0001 | 少量剔除离群点，大幅减少维度膨胀 |
| \(\rho = 0.10\) (基准配置) | 21.8 ± 0.7 | 0.9998 ± 0.0001 | 19.8 ± 0.5 | 0.9997 ± 0.0002 | 压缩率与精度的最优拐点 |
| \(\rho = 0.20\) (进取压缩) | 17.5 ± 0.9 | 0.9942 ± 0.0015 | 15.2 ± 0.7 | 0.9912 ± 0.0028 | 进一步削减维度，损失少量极值边界 |
| \(\rho = 0.30\) (激进降维) | 13.2 ± 1.1 | 0.9810 ± 0.0042 | 11.4 ± 0.8 | 0.9750 ± 0.0051 | 显著压缩求解规模，适用于粗粒度规划 |
关键发现¶
- 收敛饱和性极快：图 2 与图 7 证实，网络流（MinCostFlow、ShortestPath）等具有强图拓扑结构的 LP，其决策相关空间极度低维，仅需处理 10~20 个样本即可使矩阵秩饱和；即便在非结构化的 RandomLP 与 GROW7 上，学得秩亦在 40 个样本内稳定收敛。
- 与黑盒投影算法显著拉开差距：在全单模网络流问题上，PCA 投影与神经网络因缺乏仿射极点锚定，难以确保输出为整数可行流；而本文方法不仅完全保持极点整性，并在 RandomLP A–D 与 Netlib（GROW7、SC205）这类难解多面体上将目标比率从基线的 0.65~0.88 大幅拉升至 0.999+。
- 尾部舍弃的超线性收益：消融结果显示，将先验外部概率 \(\rho\) 从 0.02 放宽至 0.10 时，压缩 LP 变量数缩减了近 20%~25%，但目标值精度的折损不足 0.03%，证实了通过高密度凸集过滤罕见极值样本在工程上的巨大价值。
亮点与洞察¶
- 从齐次线性投影跃迁至仿射流形切片：传统方法盲目在原点截面做降维，往往耗费自由度去抵消原点偏差并损失精度；本文通过可达最优锚点 \(x_0\) 构造仿射切片，将降维问题严格与决策变化子空间绑定，揭示了极点保持的一一对应双射本质。
- 巧妙借力样本压缩理论斩获快速率：跳出统计学习中基于 VC 维与伪维数的通用 uniform-convergence 套路，抓住「仅在发生预测违约时增广基底」的代数单调与不变特性，构造出符合 Littlestone-Warmuth 范式的稳定压缩方案，证明了无分布假设下的 \(1/n\) 快速率泛化界。
- 可复用的优化辅助学习范式：将最优性验证转化为辅助对偶/正交 LP 检验，并由对偶极值向量直接指导学习更新的方向。这一机制可直接迁移至二次规划（QP）的有源集学习或混合整数规划（MIP）的割平面选择子空间提取。
局限与展望¶
- 理论目前局限于凸多面体线性规划：当前完备的极点保持与决策子空间等价性主要立足于 LP 的多面体几何性质，尚无法直接照搬至包含非线性约束的半定规划（SDP）或离散约束不可松弛的通用 MIP。
- 求解辅助验证 LP 的离线开销：在每一轮判断样本包含性时，需在当前切片正交补空间求解多达 \(2(d-r)\) 次辅助线性规划；当原始变量维度 \(d\) 高达数万且初始子空间极小（\(d-r\) 极大）时，离线训练阶段的 LP 求解负担较重。
- 未来方向：探索正交补随机投影检验以摊销离线检验成本，并将仿射压缩几何框架扩展至严格凸二次规划（CQP）及参数化凸优化问题。
相关工作与启发¶
- vs Sakaue & Oki (2024) (NeurIPS 2024)：Sakaue 等人通过 PCA 学习共享的齐次线性投影矩阵，依赖伪维数得到 \(\widetilde{O}(1/\sqrt{n})\) 的目标差近似界；本文采用锚定仿射切片，完全保持极点全等与最优质，并借助稳定压缩方案给出了无退化性假设的 \(1 - \widetilde{O}(d^{\star}/n)\) 快速收敛保证。
- vs Iwata & Sakaue (2025) (ICML 2025)：Iwata 等人使用全连接神经网络（FCNN-c）为每个实例动态预测非线性投影参数，结构黑盒且缺乏最优性恢复凭证；本文采用显式几何构建，可解释性强，样本需求量减少一个数量级以上。
- vs Bennouna et al. (2025, 2026) / Ye et al. (2026)：前序 SDD 研究主要关注信息论意义下测度向量能否充分识别最优解，缺乏求解器端的降维重构，且基底算法强依赖非退化性假设；本文首创了与求解器无缝对接的仿射降维标准形，并基于最优面包含判据消除了退化性假设约束。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次从优化几何视角阐明线性规划无损仿射压缩的充要条件，建立了决策子空间与低维 LP 之间的精确映射。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖经典组合图网络流、高维随机多面体以及 Netlib 工业测试集，全方位评估了样本效率、维度缩减与目标值精确度。
- 写作质量: ⭐⭐⭐⭐⭐ 几何直觉明晰，定理证明严整，理论推导与算法实现环环相扣。
- 价值: ⭐⭐⭐⭐⭐ 为重复求解大规模参数化规划系统提供了坚实的理论基石与实用工程降维范式。