Unified complexity analysis for Newton LP methods

James Renegar; Michael Shub

doi:10.1007/BF01585691

Mathematical Programming

Paper

01 Jan 1992

Unified complexity analysis for Newton LP methods

View publication

Abstract

We show that a theorem of Smale can be used to unify the polynomial-time bound proofs of several of the recent interior algorithms for linear programming and convex quadratic programming. © 1992 The Mathematical Programming Society, Inc.

Paper

Stably ergodic skew products

Roy Adler, Bruce Kitchens, et al.

Discrete and Continuous Dynamical Systems

Paper

Complexity of Bezout’s Theorem. III. Condition Number and Packing

Michael Shub, Steve Smale

Journal of Complexity

Paper

Implicit gamma theorems (I): Pseudoroots and pseudospectra

Jean-Pierre Dedieu, Myong-Hi Kim, et al.

Foundations of Computational Mathematics

Paper

Test complexity of generic polynomials

Peter Bürgisser, Thomas Lickteig, et al.

Journal of Complexity

View all publications

Abstract

Related

Stably ergodic skew products

Complexity of Bezout’s Theorem. III. Condition Number and Packing

Implicit gamma theorems (I): Pseudoroots and pseudospectra

Test complexity of generic polynomials