Unified complexity analysis for Newton LP methods (Q1184332): Difference between revisions

The authors show that a theorem of S. Smale can be applied to unify the polynomial-time bound proofs of several of the recent interior algorithms. They consider, in particular, \textit{C. C. Gonzaga's} linear programming barrier method [in: Progress in mathematical programming, Interior-point and related methods, Proc. Conf., Pacific Grove/Calif. 1987, 1-28 (1989; Zbl 0691.90053)], the barrier method applied to convex quadratic programming, a primal linear programming method, a primal-dual linear programming method, and a primal-dual method applied to convex quadratic programming. A good reference for all this material is the collection of papers mentioned above.