A modification of karmarkar's linear programming algorithm

Robert J. Vanderbei, Marc S. Meketon, Barry A. Freedman

Research output: Contribution to journalArticlepeer-review

128 Scopus citations


We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.

Original languageEnglish (US)
Pages (from-to)395-407
Number of pages13
Issue number1-4
StatePublished - Nov 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Applied Mathematics
  • Computer Science Applications


  • Karmarkar's algorithm
  • Least squares
  • Linear programming
  • Projected gradient methods


Dive into the research topics of 'A modification of karmarkar's linear programming algorithm'. Together they form a unique fingerprint.

Cite this