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 approximation: Two examples

Michael Shub, Amie Wilkinson

Ergodic Theory and Dynamical Systems

Paper

On the asymptotic behavior of the projective rescaling algorithm for linear programming

Michael Shub

Journal of Complexity

Paper

On the intractability of hilbert’s nullstellensatz and an algebraic version of "NP ≠ p?"

Michael Shub, Steve Smale

Duke Mathematical Journal

Paper

On the distance to the zero set of a homogeneous polynomial

Michael Shub

Journal of Complexity

View all publications

Abstract

Related

Stably ergodic approximation: Two examples

On the asymptotic behavior of the projective rescaling algorithm for linear programming

On the intractability of hilbert’s nullstellensatz and an algebraic version of "NP ≠ p?"

On the distance to the zero set of a homogeneous polynomial