An Investigation of Karmarkar's Algorithm for Linear Programming.

Abstract

During this contract period DSA has concentrated on achieving a geometrical rather than an algebraic understanding of Karmarkar's algorithm, and on the formulation of alternative approaches that retain the main advantages of Karmarkar's approach while avoiding the undesireable computational aspects of his specific algorithm. From a geometric perspective, we have asked why does the algorithm work, when it works? How can one understand the convergence process, which occurs in the shifting coordinates of Karmarkar's simplex, in terms of an orderly convergence process in the original space? This has led to a number of non-obvious insights concerning the essence of the Karmarkar algorithm. The findings of this part of the study are contained in a separate report that has been distributed, and is being prepared for publication. Keywords: Optimization; non-linear programming; quadratic programming; numerical stability.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 10, 1986
Accession Number
ADA172679

Entities

People

  • George E. Pugh
  • J. Danskin

Tags

Communities of Interest

  • C4I
  • Cyber
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Applied Mathematics
  • Computational Science
  • Computer Programs
  • Computers
  • Contracts
  • Evolutionary Algorithms
  • Game Theory
  • Geometry
  • Heuristic Methods
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Optimization
  • Quadratic Programming
  • Simplex Method

Readers

  • Operations Research
  • Systems Analysis and Design

Technology Areas

  • Space