A primal projective interior point method for linear programming (Q1176804): Difference between revisions

The authors present a new projective interior point algorithm [cf. \textit{N. Karmarkar}, Combinatorica 4, No. 4, 373-395 (1984; Zbl 0557.90065)] which solves linear programming problems in polynomial time without requiring knowledge of the optimal value of the objective function, or a lower bound for this value. To start with, the algorithm requires only that an interior feasible point be provided. In the absence of degeneracy it generates a monotonically decreasing sequence of objective values which converges to the optimal objective value, if it exists, or proves that the problem is unbounded. No computational results for the algorithm are given.