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
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:FRAsiamjna87
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).
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Kristin Buxton|
|Deposited On:||05 Feb 2009 21:48|
|Last Modified:||26 Dec 2012 10:44|
Repository Staff Only: item control page