聆听大师声音，感悟数学情怀。
主讲人
孙德锋
香港理工大学应用数学系系主任和应用优化与运筹学讲座教授。
美国工业与应用数学学会会士，中国工业与应用数学学会会士，香港研究资助局高级研究学者。
求解大规模线性规划
问题的HPR方法
2024年11月16日（周六）
上午10：00
北洋园校区58号楼414
线性规划（Linear Programming，LP）是一种在满足一系列线性约束条件下，最大化（或最小化）线性目标函数的数学方法。自1947年美国数学家乔治·丹齐格（George Dantzig）为解决军队资源分配问题而发明单纯形法（Simplex Method）后，LP已成为运筹学领域的基石。目前，最常用的求解LP方法是单纯形法和内点法。对于中小规模的LP问题，基于这两种算法的商用LP求解器能够快速提供高精度解决方案。然而，随着大数据时代的到来，很多实际问题（如电力系统优化、供应链管理和金融投资组合优化）的数据量急剧增加，模型规模庞大且对实时性要求较高，这超出了传统算法的处理能力。因此，如何高效解决超大规模LP问题成为了一个重要挑战。
为此，我们基于Halpern迭代以及半邻近Peaceman-Rachford分裂算子的思想，设计了一种求解超大规模LP问题的一阶加速方法——Halpern Peaceman-Rachford（HPR）方法。HPR方法以易于并行的矩阵-向量乘法为核心运算，结合松弛技术带来的大步长优势，能够高效地为超大规模LP问题提供高精度解决方案。理论上，我们证明了HPR方法在Karush-Kuhn-Tucker残差和目标误差方面具有O(1/k)的迭代复杂度。并基于这一复杂度，我们还设计一整套自适应的重启与调参策略，以进一步提升HPR方法的求解效率和鲁棒性。在不同的停机精度下，我们使用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年11月13日12:00
