A quadratically-convergent algorithm for the linear programming problem with lower and upper bounds.

*(English)*Zbl 0726.90057
Large-scale numerical optimization, Proc. Workshop, Ithaca/NY (USA) 1989, 49-57 (1990).

Summary: [For the entire collection see Zbl 0721.00030.]

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 \(\ell_ 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.

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 \(\ell_ 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.

##### MSC:

90C05 | Linear programming |

90-08 | Computational methods for problems pertaining to operations research and mathematical programming |

90C06 | Large-scale problems in mathematical programming |