CaltechAUTHORS
  A Caltech Library Service

Convergence in Karmarkar's Algorithm for Linear Programming

Franklin, Joel (1987) Convergence in Karmarkar's Algorithm for Linear Programming. SIAM Journal on Numerical Analysis, 24 (4). pp. 928-945. ISSN 0036-1429. http://resolver.caltech.edu/CaltechAUTHORS:FRAsiamjna87

[img]
Preview
PDF - Published Version
See Usage Policy.

1518Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:FRAsiamjna87

Abstract

Karmarkar’s algorithm is formulated so as to avoid the possibility of failure because of unbounded solutions. A general inequality gives an easy proof of the convergence of the iterations. It is shown that the parameter value α = 0.5 more than doubles the originally predicted rate of convergence. To go from the last iterate to an exact optimal solution, an O(n^3) termination algorithm is prescribed. If the data have maximum bit length independent of n, the composite algorithm is shown to have complexity 0(n^4.5 log n).


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/0724060DOIUNSPECIFIED
Additional Information:©1987 Society for Industrial and Applied Mathematics. Received by the editors April 14, 1986; accepted for publication (in revised form) September 25, 1986.
Subject Keywords:linear programming; Karmarkar’s algorithm; projective-iterative method
Record Number:CaltechAUTHORS:FRAsiamjna87
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:FRAsiamjna87
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13073
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:05 Feb 2009 21:48
Last Modified:26 Dec 2012 10:44

Repository Staff Only: item control page