A Finite Algorithm for the Least Two-Norm Solution of a Linear Program.
Technical summary rept.,
WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
By perturbing properly a linear program to a separable quadratic program it is possible to solve the latter in its dual variable space by iterative techniques such as sparsity-preserving SOR successive over relaxations. In this way large sparse linear programs can be handled. This paper gives a new computational criterion to check whether the solution of the perturbed quadratic programs provide the least 2-norm solution of the original linear program. This criterion improves on the criterion proposed in an earlier paper. The author also describes an algorithm for solving linear programs which is based on the SOR methods. The main property of this algorithm is that, under mild assumptions, it finds the least 2-norm solution of a linear program in a finite number of iterations.
- Theoretical Mathematics