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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA453840

Entities

People

  • A. M. Morshedi
  • J. E. Dennis Jr.
  • Kathryn Turner

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Heuristic Methods
  • Information Operations
  • Linear Programming
  • Mathematics
  • Scientific Research
  • Standards

Fields of Study

  • Mathematics

Readers

  • Linear Algebra
  • Operations Research