TY - JOUR
T1 - A DRS-Based Path-Following Algorithm for Linear Programming
AU - Liu , Yiyang
AU - Liu , Haoyang
AU - Nie , Hantao
AU - Wen , Zaiwen
JO - Journal of Computational Mathematics
VL - 5
SP - 1141
EP - 1168
PY - 2025
DA - 2025/09
SN - 43
DO - http://doi.org/10.4208/jcm.2508-m2023-0134
UR - https://global-sci.org/intro/article_detail/jcm/24475.html
KW - Linear programming, Douglas-Rachford splitting, Second-order method, Path-following.
AB - <p style="text-align: justify;">In this paper, we present a novel Douglas-Rachford-splitting-based path following
(DRS-PF) method that rapidly obtains the solution of linear programming (LP) with
high accuracy. It originates from the fixed-point mapping associated with DRS on the
log-barrier penalized LP. A path-following scheme is then proposed to simultaneously update the iterates and the penalty parameter for accelerating the overall procedure. Its
global convergence towards an optimal solution to the original problem is established under mild assumptions. Numerical experiments show that DRS-PF outperforms the simplex
and interior point methods implemented in the academic software (CLP, HiGHS, etc.) in
terms of the geometric mean of the running time on a few typical benchmark data sets. In
some cases, it is even reasonably competitive to the interior point method implemented in
Gurobi, one of the most powerful software for LP.</p>