EUVIMEDEUVIMED entdecken
Crossref

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, Chuwen Zhang

INFORMS Journal on Computing · 2025-03 · 37 (2) · 338-359

DOI: 10.1287/ijoc.2023.0017 ↗

Kurz gefasst

Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2025-03. Verfasst von Qi Deng und 10 weiteren Autor:innen. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 33 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: This research was supported by the National Natural Science Foundation of China [Grants 72394360, 72394364, 72394365, 72225009, 72171141, and 72150001] and by the Program for Innovative Research Team of Shanghai University of Finance and Economics. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0017 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0017 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Zitieren

APA

Deng, Q., Feng, Q., Gao, W., Ge, D., Jiang, B., Jiang, Y., Liu, J., Liu, T., Xue, C., Ye, Y., & Zhang, C. (2025). An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization. INFORMS Journal on Computing, 37(2), 338-359. https://doi.org/10.1287/ijoc.2023.0017

Vancouver

Deng Q, Feng Q, Gao W, Ge D, Jiang B, Jiang Y, et al. An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization. INFORMS Journal on Computing. 2025;37(2):338-359. doi:10.1287/ijoc.2023.0017

BibTeX
@article{Deng2025,
  author = {Deng, Qi and Feng, Qing and Gao, Wenzhi and Ge, Dongdong and Jiang, Bo and Jiang, Yuntian and Liu, Jingsong and Liu, Tianhao and Xue, Chenyu and Ye, Yinyu and Zhang, Chuwen},
  title = {An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for Linear and Conic Optimization},
  journal = {INFORMS Journal on Computing},
  year = {2025},
  volume = {37},
  number = {2},
  pages = {338--359},
  doi = {10.1287/ijoc.2023.0017}
}
Kostenlos starten →