Normal Solutions of Linear Programs.
Technical summary rept.,
WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER
Pagination or Media Count:
The solvability of a linear program is charcterized in terms of the existence of a fixed projection on the feasible region, of all sufficiently large positive multiples of the gradient of the objective function. This projection turns out to be the noraml solution obtained by projecting the origin on the optimal solution set. By seeking the solution with least 2-norm which minimizes the 1-norm infeasibility measure of a system of linear inequalities or of the optimality conditions of a linear program one is led to a simple minimization problem of a convex quadratic function on the nonegative orthant which is guaranteed to be solvable by a succesiveoverrelaxation SOR method. This normal solution is an exact solution if the ogriginal system is solvable, otherwise it is an error-minimizing solution. New computational results results are given to indicate that SOR methods can solve very large sparse linear programs that cannot be handled by an ordinary linear programming package.
- Theoretical Mathematics