Accession Number:

ADA453840

Title:

A Variable-Metric Variant of the Karmarkar Algorithm for Linear Programming

Descriptive Note:

Technical rept.

Corporate Author:

RICE UNIV HOUSTON TX DEPT OF MATHEMATICAL SCIENCES

Report Date:

1987-01-01

Pagination or Media Count:

33.0

Abstract:

The most time-consuming part of the Karmarkar algorithm for linear programming is the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variable-metric techniques in an innovative way to approximate this projection. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems.

Subject Categories:

  • Numerical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE