Faster first-order primal-dual methods for linear programming using restarts and sharpness
First-order primal-dual methods are appealing for their low memory overhead, fast iterations,
and effective parallelization. However, they are often slow at finding high accuracy solutions …
and effective parallelization. However, they are often slow at finding high accuracy solutions …
Global linear and local superlinear convergence of IRLS for non-smooth robust regression
We advance both the theory and practice of robust $\ell_p $-quasinorm regression for $ p\in
(0, 1] $ by using novel variants of iteratively reweighted least-squares (IRLS) to solve the …
(0, 1] $ by using novel variants of iteratively reweighted least-squares (IRLS) to solve the …
Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
Optimal Transport (OT) is a mathematical framework that first emerged in the eighteenth
century and has led to a plethora of methods for answering many theoretical and applied …
century and has led to a plethora of methods for answering many theoretical and applied …
On the geometry and refined rate of primal–dual hybrid gradient for linear programming
H Lu, J Yang - Mathematical Programming, 2024 - Springer
We study the convergence behaviors of primal–dual hybrid gradient (PDHG) for solving
linear programming (LP). PDHG is the base algorithm of a new general-purpose first-order …
linear programming (LP). PDHG is the base algorithm of a new general-purpose first-order …
cuPDLP. jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia
H Lu, J Yang - arXiv preprint arXiv:2311.12180, 2023 - arxiv.org
In this paper, we provide an affirmative answer to the long-standing question: Are GPUs
useful in solving linear programming? We present cuPDLP. jl, a GPU implementation of …
useful in solving linear programming? We present cuPDLP. jl, a GPU implementation of …
Restarted Halpern PDHG for linear programming
H Lu, J Yang - arXiv preprint arXiv:2407.16144, 2024 - arxiv.org
In this paper, we propose and analyze a new matrix-free primal-dual algorithm, called
restarted Halpern primal-dual hybrid gradient (rHPDHG), for solving linear programming …
restarted Halpern primal-dual hybrid gradient (rHPDHG), for solving linear programming …
Learning to Pivot as a Smart Expert
Linear programming has been practically solved mainly by simplex and interior point
methods. Compared with the weakly polynomial complexity obtained by the interior point …
methods. Compared with the weakly polynomial complexity obtained by the interior point …
New developments of ADMM-based interior point methods for linear programming and conic programming
The ADMM-based interior point method (ABIP, Lin et al.\2021) is a hybrid algorithm which
effectively combines the iterior point method and the first-order method to achieve …
effectively combines the iterior point method and the first-order method to achieve …
[HTML][HTML] Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs
O Hinder - Operations Research Letters, 2024 - Elsevier
We analyze restarted PDHG on totally unimodular linear programs. In particular, we show
that restarted PDHG finds an ϵ-optimal solution in O (H m 1 2.5 nnz (A) log(H m 2/ϵ)) …
that restarted PDHG finds an ϵ-optimal solution in O (H m 1 2.5 nnz (A) log(H m 2/ϵ)) …
An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization
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) …
or ABIP method, is a hybrid algorithm that effectively combines interior point method (IPM) …