mPDLP
一种基于一阶优化方法（PDHG框架矩阵化变体）的线性规划求解算法，通过矩阵-向量乘法迭代逼近最优解，天然适合GPU大规模并行计算，可将线性规划求解扩展至亿级变量
时间轴 (近 90 天)
NVIDIA 在 cuOpt 中引入了 mPDLP（matrix Primal-Dual Linear Programming）方法
mPDLP 能够将线性规划的求解规模扩展到 1 亿个变量乃至更大规模
mPDLP 建立在一阶（first-order）优化方法的基础之上，主要通过矩阵-向量乘法来迭代逼近最优解
mPDLP 采用的是 PDHG（原始对偶混合梯度法）框架的矩阵化变体
PDHG 每次迭代只需计算约束矩阵与当前解向量的乘积以及一个简单的投影步骤，计算复杂度与问题规模呈近似线性关系
一阶方法的代价是收敛通常需要更多迭代次数，且对问题的数值条件较为敏感
矩阵-向量乘法等一阶方法运算天然适合在 GPU 上并行执行，而内点法依赖矩阵分解难以利用 GPU 大规模并行能力
能够一次性处理亿级变量意味着决策者可以获得更接近真实约束的全局解，避免因切分子问题而损失整体最优性
全部知识事实 (8)
能够一次性处理亿级变量意味着决策者可以获得更接近真实约束的全局解，避免因切分子问题而损失整体最优性
50%待验证mPDLP 能够将线性规划的求解规模扩展到 1 亿个变量乃至更大规模
50%待验证mPDLP 建立在一阶（first-order）优化方法的基础之上，主要通过矩阵-向量乘法来迭代逼近最优解
50%待验证mPDLP 采用的是 PDHG（原始对偶混合梯度法）框架的矩阵化变体
50%待验证PDHG 每次迭代只需计算约束矩阵与当前解向量的乘积以及一个简单的投影步骤，计算复杂度与问题规模呈近似线性关系
50%待验证一阶方法的代价是收敛通常需要更多迭代次数，且对问题的数值条件较为敏感
50%待验证矩阵-向量乘法等一阶方法运算天然适合在 GPU 上并行执行，而内点法依赖矩阵分解难以利用 GPU 大规模并行能力
50%待验证NVIDIA 在 cuOpt 中引入了 mPDLP（matrix Primal-Dual Linear Programming）方法
50%