Papers › Solving a linear program via a single unconstrained minimization
Solving a linear program via a single unconstrained minimization
Adilet Otemissov, Alina Abdikarimova
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
This paper proposes a novel approach for solving linear programs. We reformulate a primal-dual linear program as an unconstrained minimization of a convex and twice continuously differentiable merit function. When the optimal set of the primal-dual pair is nonempty, its optimal set is equal to the optimal set of the proposed merit function. Minimizing this merit function poses some challenges due to its Hessian being singular at some points in the domain, including the optimal solutions. We handle singular Hessians using the Newton method with Levenberg-Marquardt regularization. We show that the Newton method with Levenberg-Marquardt regularization yields global convergence to a solution of the primal-dual linear program in at most O(ϵ^(-3/2)) iterations requiring only the assumption that the optimal set of the primal-dual linear program is bounded. Testing on random synthetic problems demonstrates convergence to optimal solutions to very high accuracy significantly faster than the derived worst-case bound. We further introduce a modified merit function that depends on a scalar parameter ν> 0, whose Hessian is nonsingular for all ν> 0 and which reduces exactly to the original merit function when ν= 0. Based on this formulation, we propose a heuristic scheme that performs Newton steps while gradually decreasing ν toward zero. Numerical experiments indicate that this approach achieves faster convergence, particularly on higher-dimensional problems.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections