A Quadratically-Convergent Algorithm for the Linear Programming Problem with Lower and Upper Bounds

Abstract

We present a new algorithm to solve linear programming problems with finite lower and upper bounds. This algorithm generates an infinite sequence of points guaranteed to converge to the solution; the ultimate convergence rate is quadratic. The algorithm requires the solution of a linear least squares problem at each iteration - it is similar in this respect to recent interior point and "Karmarkar-like" methods. However, the algorithm does not require feasibility of the iterates; instead, monotonic decrease of an augmented linear $l_{1}$ function is maintained. A penalty parameter is not required. This method is particularly attractive for large-scale problems in that the number of iterations required to obtain high accuracy is relatively insensitive to problem size and is typically quite small. We provide results of numerical experiments.