A modification of karmarkar's linear programming algorithm

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

doi:10.1007/BF01840454

A modification of karmarkar's linear programming algorithm

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

Research output: Contribution to journal › Article › peer-review

130 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	395-407
Number of pages	13
Journal	Algorithmica
Volume	1
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01840454
State	Published - Nov 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
Applied Mathematics
Computer Science Applications

Keywords

Karmarkar's algorithm
Least squares
Linear programming
Projected gradient methods

Access to Document

10.1007/BF01840454

Cite this

@article{45e8d06ae540406e87e9039ef0e2772a,

title = "A modification of karmarkar's linear programming algorithm",

abstract = "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.",

keywords = "Karmarkar's algorithm, Least squares, Linear programming, Projected gradient methods",

author = "Vanderbei, {Robert J.} and Meketon, {Marc S.} and Freedman, {Barry A.}",

year = "1986",

month = nov,

doi = "10.1007/BF01840454",

language = "English (US)",

volume = "1",

pages = "395--407",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

T1 - A modification of karmarkar's linear programming algorithm

AU - Vanderbei, Robert J.

AU - Meketon, Marc S.

AU - Freedman, Barry A.

PY - 1986/11

Y1 - 1986/11

N2 - 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.

AB - 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.

KW - Karmarkar's algorithm

KW - Least squares

KW - Linear programming

KW - Projected gradient methods

UR - http://www.scopus.com/inward/record.url?scp=33746951751&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746951751&partnerID=8YFLogxK

U2 - 10.1007/BF01840454

DO - 10.1007/BF01840454

M3 - Article

AN - SCOPUS:33746951751

SN - 0178-4617

VL - 1

SP - 395

EP - 407

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

A modification of karmarkar's linear programming algorithm

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this