北洋数学讲堂预告丨《求解大规模线性规划问题的HPR方法》-孙德锋

线性规划（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倍的加速）。

孙德锋，香港理工大学应用数学系系主任和应用优化与运筹学讲座教授。分别于1989年和1992年获南京大学数学系学士和硕士学位，1995年获中国科学院应用数学所博士学位。2020年，当选为美国工业与应用数学学会会士、中国工业与应用数学学会会士；2020年至2024年任香港数学学会会长；2022年获香港研究资助局高级研究学者奖；2024年当选为中国运筹学会会士及首届美国运筹学和管理学研究协会高级会员。

主要研究领域为连续优化和机器学习，涵盖基础理论、算法及应用。在锥规划扰动性分析、非光滑分析、矩阵优化软件开发、光滑化牛顿算法、外梯度算法、对称高斯-赛德尔方法及应用等方面做出了系列领先成果。2002年，与孙捷教授合作证明了半正定锥上投影算子的强半光滑性。2006年，独立解决了非线性半正定规划的强正则性公开问题；与戚厚铎教授合作开发的最邻近相关矩阵牛顿方法被纳入数值与统计算法库NAG库，广泛应用于学术界和工业界。与Toh Kim-Chuan教授及学生合作研发的大规模半正定问题求解器SDPNAL+，于2018年获得国际优化学会 “Beale–Orchard-Hays” 奖。自1998年起，与合作者设计了求解非光滑方程的光滑化牛顿算法；并利用对称高斯-赛德尔方法开发了用于求解大规模凸锥优化问题的多块交替方向乘子法。曾获新加坡国立大学科学学院首届杰出科学家奖（2007年）；因在排产优化求解器方面的贡献，获华为香港研究所和诺亚方舟实验室分别颁发的杰出合作奖（2021年）；作为成员荣获中国运筹学会运筹应用奖（2022年）。