孙德锋教授分享求解大规模线性规划问题的HPR方法

2024年11月16日上午，香港理工大学应用数学系系主任和应用优化与运筹学讲座教授孙德锋做客天津大学数学学院，在58教414报告厅做主题为“求解大规模线性规划问题的HPR方法”的报告，带领我校师生探寻如何高效解决超大规模线性规划问题。数学学院院长孙笑涛主持本次活动。

孙德锋教授首先从线性规划（LP）及其对偶入手，介绍了目前流行的求解方法以及求解器；然后过渡到具有可分结构的凸优化问题，介绍了预条件的交替方向乘子法（pADMM），通过对问题的等价转化并引入Halpern加速技巧，提出了加速的pADMM，得到了针对Karush-Kuhn-Tucker残差和目标误差均具有O(1/k)的迭代复杂性，大大地改进了之前的复杂性结果。

基于Halpern迭代以及半邻近Peaceman-Rachford分裂算子的思想，孙德锋教授介绍了一种求解超大规模LP问题的一阶加速方法——Halpern Peaceman-Rachford（HPR）方法。理论上，证明了HPR方法在Karush-Kuhn-Tucker残差和目标误差方面具有O(1/k)的迭代复杂度；计算上，设计一整套自适应的重启与调参策略，在不同的停机精度下，使用NVIDIA A100-SXM4-80GB GPU对各类LP基准数据集进行了大量的数值实验。实验结果表明，在高精度要求下，与近期荣获国际奖项（Beale- Orchard-Hays Prize）的PDLP求解器（Google开发）相比，HPR-LP求解器（Julia版）对于预处理的问题上达到了SGM10意义下2.39倍至5.70倍的加速（对于未预处理的问题能够达到2.03倍至4.06倍的加速）。

孙德锋教授的报告深入浅出，由理论研究到软件开发，不但体现了数学研究之美，而且展示了数学应用的魅力，激励在场师生们不断探索、续写华章。

本活动受 2024年书香校园精品立项支持