Abstract | ||
---|---|---|
This paper describes a full-dimensional version of Karmarkar's linear programming algorithm, theprojective scaling algorithm, which is defined for any linear program in Rn having a bounded, full-dimensional polytope of feasible solutions. If such a linear program hasm inequality constraints, then it is equivalent under an injective affine mappingJ:Rn?Rm to Karmarkar's original algorithm for a linear program in Rm havingm—n equality constraints andm inequality constraints. Karmarkar's original algorithm minimizes a potential functiong(x), and the projective scaling algorithm is equivalent to that version of Karmarkar's algorithm whose step size minimizes the potential function in the step direction. |
Year | DOI | Venue |
---|---|---|
1991 | 10.1007/BF01594941 | Math. Program. |
Keywords | Field | DocType |
linear programming algorithm,logarithmic barrier function,projective transformation,modified newton's method,nonlinear optimization.,karmarkar's algorithm,global newton's method,barrier function,linear program,nonlinear optimization | Affine transformation,Discrete mathematics,Mathematical optimization,Simplex algorithm,Nonlinear programming,Polytope,Linear programming,Karmarkar's algorithm,Criss-cross algorithm,Interior point method,Mathematics | Journal |
Volume | Issue | ISSN |
50 | 3 | 0025-5610 |
Citations | PageRank | References |
11 | 1.01 | 9 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
D. A. Bayer | 1 | 11 | 1.01 |
J. C. Lagarias | 2 | 563 | 235.61 |