An ADMM-based interior-point method for large-scale linear programming
From MaRDI portal
Abstract: We propose a new framework to implement interior point method (IPM) to solve very large linear programs (LP). 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 as second-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 linear system, 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 linear system. Since the linear system is different 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 as ABIP in this paper. The new method inherits stability from IPM, and scalability from ADMM. Because of its self-dual embedding structure, ABIP is set to solve any LP without requiring prior knowledge about its feasibility. We conduct extensive numerical experiments testing ABIP with large-scale LPs from NETLIB and machine learning applications. The results demonstrate that ABIP compares favorably with existing LP solvers including SDPT3, MOSEK, DSDP-CG and SCS.
Recommendations
- Alternating direction method of multipliers for linear programming
- scientific article; zbMATH DE number 1047679
- Interior dual proximal point algorithm for linear programs
- Interior point methods for large-scale linear programming
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
Cites work
- A constrained \(\ell _{1}\) minimization approach to sparse precision matrix estimation
- A multiplicative barrier function method for linear programming
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- Advanced preprocessing techniques for linear and quadratic programming
- Algorithm 837
- Algorithm 849
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Computing the block triangular form of a sparse matrix
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Direct Methods for Sparse Linear Systems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Gradient methods with adaptive step-sizes
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3972641 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1131479 (Why is no real title available?)
- scientific article; zbMATH DE number 194636 (Why is no real title available?)
- scientific article; zbMATH DE number 3894797 (Why is no real title available?)
- Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning
- Interior point methods 25 years later
- Matrix-free interior point method
- Matrix-free interior point method for compressed sensing problems
- Numerical recipes. The art of scientific computing.
- On a Wide Region of Centers and Primal-Dual Interior Point Algorithms for Linear Programming
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the Implementation of a Primal-Dual Interior Point Method
- Parallel alternating direction multiplier decomposition of convex programs
- Parallel iterative methods for sparse linear systems
- Preprocessing for quadratic programming
- Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method
- Presolving in linear programming
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Solving semidefinite-quadratic-linear programs using SDPT3
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
- The Split Bregman Method for L1-Regularized Problems
- Two-Point Step Size Gradient Methods
Cited in
(16)- Bregman primal-dual first-order method and application to sparse semidefinite programming
- Alternating direction method of multipliers for linear programming
- ABIP
- Interior-point algorithm for linear programming based on a new descent direction
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- An interior proximal gradient method for nonconvex optimization
- A practical and optimal first-order method for large-scale convex quadratic programming
- A decomposition approach on the base of Brownian iteration for the linear programming where all basis matrices are M-matrix
- Accelerated convergence of time-splitting algorithm by relaxation method
- An ADMM-based interior point method for solving nonnegative tensor least squares problems and its applications
- On the geometry and refined rate of primal-dual hybrid gradient for linear programming
- Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs
- HPR-LP: an implementation of an HPR method for solving linear programming
- A DRS-based path-following algorithm for linear programming
- An adaptive cubic regularisation algorithm based on interior-point methods for optimization with general inequality constraints
- Managing randomization in the multi-block alternating direction method of multipliers for quadratic optimization
This page was built for publication: An ADMM-based interior-point method for large-scale linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4999335)
