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. doi:10.1137/0724060.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
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
Issue or Number:4
Record Number:CaltechAUTHORS:FRAsiamjna87
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13073
Deposited On:05 Feb 2009 21:48
Last Modified:08 Nov 2021 22:35

Repository Staff Only: item control page