利用强化学习加速线性规划的原始-对偶混合梯度方法

arXiv:2610.01546v1 公告类型：cross 摘要：原始-对偶混合梯度（PDHG）方法利用适合 GPU 的矩阵-向量乘法和投影来求解大规模线性规划（LP），但其实际性能取决于算法参数、加速机制和重启策略之间的协调。我们提出 GALLOP，在无需对求解器进行微分的情况下，利用强化学习联合学习连续算法参数和离散重启决策。其广义加速 PDHG 更新结合了分别针对原始变量和对偶变量的外推、历史修正以及重启锚定，并为这些机制配备可独立调节的系数。我们使用分组近端策略优化目标训练与维度无关的反馈策略；该目标针对不同控制组分别裁剪似然比，并在重启转移中排除不活跃的加速控制量。我们在六类 LP 和一个公开的物品放置基准上评估 GALLOP。在六类问题的主要评估设置中，相比 MPAX，GALLOP 将迭代次数降低至原来的 $1.9$—$5.6$ 分之一，并使算法实际运行时间最高加速 $16.0\times$。对于每个问题类别分别训练一个策略时，学习到的策略无需重新训练，即可泛化到同类别中规模比最大训练实例大 $3\times$—$400\times$ 的 LP，包括含有 1024 万个变量的 Transport LP。