报告题目：An Efficient HPR Algorithm for the Wasserstein Barycenter Problem with $O(Dim(P)/\varepsilon)$ Computational Complexity 

报 告 人：孙德锋  香港理工大学

报告时间：2023年10月6日下午 15:00-16:00

报告地点：龙洞校区行政楼610

主 持 人：刘玉兰

报告摘要：We propose and analyze an efficient Halpern-Peaceman-Rachford (HPR) algorithm for solving the Wasserstein barycenter problem (WBP) with fixed supports. While the Peaceman-Rachford (PR) splitting method itself may not be convergent for solving the WBP, the HPR algorithm can achieve an $O(1/\varepsilon)$ non-ergodic iteration complexity with respect to the Karush–Kuhn–Tucker (KKT) residual. More interestingly, we propose an efficient procedure with linear time computational complexity to solve the linear systems involved in the subproblems of the HPR algorithm. As a consequence, the HPR algorithm enjoys an $O({\rm Dim(P)}/\varepsilon)$ non-ergodic computational complexity in terms of flops for obtaining an $\varepsilon$-optimal solution measured by the KKT residual for the WBP, where ${\rm Dim(P)}$ is the dimension of the variable of the WBP. This is better than the best-known complexity bound for the WBP. Moreover, the extensive numerical results on both the synthetic and real data sets demonstrate the superior performance of the HPR algorithm for solving the large-scale WBP. This is a joint work with Guojun Zhang and Yancheng Yuan.      

专家简介:孙德锋，香港理工大学应用数学系系主任和应用优化与运筹学讲座教授，美国工业与应用数学学会会士，中国工业与应用数学学会会士，香港数学学会会长。荣获国际数学规划Beale--Orchard-Hays奖，新加坡国立大学科学学院首届杰出科学家奖。曾任《亚太运筹学杂志》主编，现任《数学规划》、《SIAM优化杂志》、《优化理论与应用》、《中国运筹学学会期刊》、《计算数学杂志》和《中国科学：数学》副主编。2020年，他当选为CSIAM和SIAM学会会员。2022年，他获得研资局高级研究员计划奖。