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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1986
Accession Number
ADA172588

Entities

People

  • Stefano Lucidi

Organizations

  • University of Wisconsin–Madison

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computations
  • Computer Programming
  • Determinants (Mathematics)
  • Evolutionary Algorithms
  • Identities
  • Iterations
  • Linear Programming
  • Mathematical Analysis
  • Mathematics
  • North Carolina
  • Perturbations
  • Quadratic Programming
  • Sequences
  • Simplex Method
  • United States

Readers

  • Operations Research

Technology Areas

  • Space