An algorithm of the Karmarkar type. (English. Russian original) Zbl 0654.90048

Nemirovskij, A. S.

Sov. J. Comput. Syst. Sci. 25, No. 5, 61-74 (1987); translation from Izv. Akad. Nauk SSSR, Tekh. Kibern. 1987, No. 1, 105-118 (1987).

A description is given of a polynomial algorithm for solving linear programming problems that, like Karmarkar’s algorithm, is based on the use of projective transformations of the condition polyhedron. This algorithm has the same estimates of the rate of convergence as Karmarkar’s method but does not require a priori knowledge of an admissible plan or the optimal value of the objective functional.

MSC:

90C05	Linear programming
68Q25	Analysis of algorithms and problem complexity
65K05	Numerical mathematical programming methods

Keywords:

polynomial algorithm; Karmarkar’s algorithm; projective transformations; rate of convergence