# zbMATH — the first resource for mathematics

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.

##### MSC:
 90C05 Linear programming 90-08 Computational methods for problems pertaining to operations research and mathematical programming 90C06 Large-scale problems in mathematical programming
MINOS