Accession Number:

ADA172588

Title:

A Finite Algorithm for the Least Two-Norm Solution of a Linear Program.

Descriptive Note:

Technical summary rept.,

Corporate Author:

WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER

Personal Author(s):

• Lucidi,Stefano

Report Date:

1986-07-01

Pagination or Media Count:

31.0

Abstract:

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.

Descriptors:

• *LINEAR PROGRAMMING
• ALGORITHMS
• COMPUTATIONS
• PROBLEM SOLVING
• QUADRATIC PROGRAMMING
• PERTURBATIONS
• ITERATIONS

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE