Accession Number:

ADA129073

Title:

Normal Solutions of Linear Programs.

Descriptive Note:

Technical summary rept.,

Corporate Author:

WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s):

Report Date:

1983-03-01

Pagination or Media Count:

23.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE