An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization

Qi Deng (), Qing Feng (), Wenzhi Gao (), Dongdong Ge (), Bo Jiang (), Yuntian Jiang (), Jingsong Liu (), Tianhao Liu (), Chenyu Xue (), Yinyu Ye () and Chuwen Zhang ()
Additional contact information
Qi Deng: Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China
Qing Feng: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
Wenzhi Gao: Institute of Computational and Mathematical Engineering, Stanford University, Palo Alto, California 94305
Dongdong Ge: Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China
Bo Jiang: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China; and Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics, Shanghai 200433, China; and Dishui Lake Advanced Finance Institute, Shanghai University of Finance and Economics, Shanghai 200120, China
Yuntian Jiang: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
Jingsong Liu: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
Tianhao Liu: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
Chenyu Xue: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China
Yinyu Ye: Institute of Computational and Mathematical Engineering, Stanford University, Palo Alto, California 94305
Chuwen Zhang: Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China

INFORMS Journal on Computing, 2025, vol. 37, issue 2, 338-359

Abstract: The alternating-direction-method-of-multipliers-based (ADMM-based) interior point method, or ABIP method, is a hybrid algorithm that effectively combines interior point method (IPM) and first-order methods to achieve a performance boost in large-scale linear optimization. Different from traditional IPM that relies on computationally intensive Newton steps, the ABIP method applies ADMM to approximately solve the barrier penalized problem. However, similar to other first-order methods, this technique remains sensitive to condition number and inverse precision. In this paper, we provide an enhanced ABIP method with multiple improvements. First, we develop an ABIP method to solve the general linear conic optimization and establish the associated iteration complexity. Second, inspired by some existing methods, we develop different implementation strategies for the ABIP method, which substantially improve its performance in linear optimization. Finally, we conduct extensive numerical experiments in both synthetic and real-world data sets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8× reduction in the geometric mean of run time on 105 selected linear optimization instances from Netlib, and it exhibits advantages in certain structured problems, such as support vector machine and PageRank. However, the enhanced ABIP method still falls behind commercial solvers in many benchmarks, especially when high accuracy is desired. We posit that it can serve as a complementary tool alongside well-established solvers.

Keywords: linear optimization; conic optimization; ADMM; interior point method; implementation improvement; iteration complexity (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0017 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:2:p:338-359

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().