Normal Solutions of Linear Programs.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1983
- Accession Number
- ADA129073
Entities
People
- Olvi L. Mangasarian
Organizations
- University of Wisconsin–Madison