Asymptotic behaviour of Karmarkar's method for linear programming (Q911987): Difference between revisions

\textit{N. Karmarkar} [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] suggested a polynomial-time algorithm for solving linear programming problems. Since 1984 many researchers have studied Karmarkar's algorithm both from the theoretical and practical point of view. In this paper an asymptotic behaviour of Karmarkar's method is studied. It is shown that the generated sequence of points approaches the boundary uniformly, in the sense that all components which tend to zero are asymptotically proportional to the objective function value. In the degenerate case Karmarkar's method generates a sequence of ill- conditioned matrices. Here the original problem can be equivalently transformed so that the corresponding matrices have well-conditioned blocks.