A Complexity Analysis for Interior-Point Algorithms Based on Karmarkar’s Potential Function
Authors:
- Jun JiJJJun Ji
- Ye YinyuYYYe Yinyu
- 1 August 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 4 (3) , 512-520
Abstract
A new complexity analysis for constant potential reduction algorithms for linear programming is considered. Using Karmarkar’s primal-based potential function, it is shown that for a class of linear programs the number of iterations required is at most $O( mt + n\log ( n ) )$, where m is the number of equations and n is the number of variables in the standard linear programming form, and t can be interpreted as the number of significant figures required in the final solution. It is also shown that this result holds in expectation for some randomly generated problems. At the same time, it is shown that Karmarkar’s algorithm requires at least $\Omega ( n )$ iterations to solve Anstreicher’s linear program, if the initial solution is poor but valid.
Keywords
This publication has 18 references indexed in Scilit:
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential functionMathematical Programming, 1991
- Karmarkar's linear programming algorithm and Newton's methodMathematical Programming, 1991
- On the Performance of Karmarkar’s Algorithm over a Sequence of IterationsSIAM Journal on Optimization, 1991
- Polynomial affine algorithms for linear programmingMathematical Programming, 1990
- The Worst-Case Step in Karmarkar's AlgorithmMathematics of Operations Research, 1989
- Conical projection algorithms for linear programmingMathematical Programming, 1989
- A variant of Karmarkar's linear programming algorithm for problems in standard formMathematical Programming, 1987
- A monotonic projective algorithm for fractional linear programmingAlgorithmica, 1986
- A polynomial newton method for linear programmingAlgorithmica, 1986
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984