4.5 Article

An ADMM-based interior-point method for large-scale linear programming

期刊

OPTIMIZATION METHODS & SOFTWARE
卷 36, 期 2-3, 页码 389-424

出版社

TAYLOR & FRANCIS LTD
DOI: 10.1080/10556788.2020.1821200

关键词

Linear programming; homogeneous self-dual embedding; interior-point method; central path following; ADMM; iteration complexity

资金

  1. NSF grant Division of Mathematical Sciences [PDMS-1953210]
  2. NSF grant Division of Computing and Communication Foundations [CCF-2007797]
  3. UC Davis CeDAR (Center for Data Science and Artificial Intelligence Research) Innovative Data Science Seed Funding Program

向作者/读者索取更多资源

In this paper, a new method named ABIP based on Alternating Direction Method of Multipliers (ADMM) is proposed, which inherits stability from IPM and scalability from ADMM. ABIP approximates the minimization of the log-barrier penalty function using ADMM in the framework, solving large-scale LP problems.
In this paper, we propose a new framework to implement interior point method (IPM) in order to solve some very large-scale linear programs (LPs). Traditional IPMs typically use Newton's method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton's method, IPM is often classified assecond-order method- a genre that is attached with stability and accuracy at the expense of scalability. Indeed, computing a Newton step amounts to solving a large system of linear equations, which can be efficiently implemented if the input data are reasonably sized and/or sparse and/or well-structured. However, in case the above premises fail, then the challenge still stands on the way for a traditional IPM. To deal with this challenge, one approach is to apply the iterative procedure, such as preconditioned conjugate gradient method, to solve the system of linear equations. Since the linear system is different in each iteration, it is difficult to find good pre-conditioner to achieve the overall solution efficiency. In this paper, an alternative approach is proposed. Instead of applying Newton's method, we resort to the alternating direction method of multipliers (ADMM) to approximately minimize the log-barrier penalty function at each iteration, under the framework of primal-dual path-following for a homogeneous self-dual embedded LP model. The resulting algorithm is an ADMM-Based Interior Point Method, abbreviated asABIPin this paper. The new method inherits stability from IPM and scalability from ADMM. Because of its self-dual embedding structure,ABIPis set to solve any LP without requiring prior knowledge about its feasibility. We conduct extensive numerical experiments testingABIPwith large-scale LPs from NETLIB and machine learning applications. The results demonstrate thatABIPcompares favourably with other LP solvers includingSDPT3,MOSEK,DSDP-CGandSCS.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.5
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据