报告题目 (Title)：An Enhanced ADMM-based Interior Point Method for Linear and Conic Optimization （基于改进admm的线性和二次优化内点法）

报告人 (Speaker)：邓琪 副教授（上海财经大学）

报告时间 (Time)：2023年11月7日 (周二) 14:40

报告地点 (Place)：校本部GJ303

邀请人(Inviter)：徐姿 教授

主办部门：理学院数学系

报告摘要：The ADMM-based interior point (ABIP, Lin et al. 2021) method is a hybrid algorithm that effectively combines the interior point method and the first-order method to achieve a performance boost in large-scale linear programming. Different from traditional interior point methods which rely on computationally intensive Newton steps, the ABIP method applies the alternating direction method of multipliers (ADMM) to approximately solve the barrier penalized problem. In this paper, we provide an enhanced ABIP method with multiple improvements. Firstly, we extend the ABIP method to solve more general linear conic programming and establish the associated iteration complexity of the enhanced algorithm. Secondly, we develop multiple new implementation strategies for ABIP, which substantially improve its performance for linear programming. Finally, we conduct extensive numerical experiments in both synthetic and real-world datasets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8x reduction in the geometric mean of run time on $105$ LP instances from Netlib and it compares favorably against state-of-the-art open-source solvers in a wide range of large-scale problems. Moreover, it is even comparable to commercial solvers in some particular datasets.