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

Stable ergodicity

Charles Pugh, Michael Shub, et al.

Bulletin of the American Mathematical Society

Paper

Implicit gamma theorems (I): Pseudoroots and pseudospectra

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

Foundations of Computational Mathematics

Paper

Stable ergodicity in homogeneous spaces

Jonathan Brezin, Michael Shub

Bulletin of the Brazilian Mathematical Society

Paper

Complexity of Bezout's theorem IV: Probability of success; extensions

Michael Shub, Steve Smale

SIAM Journal on Numerical Analysis

View all publications

Abstract

Related

Stable ergodicity

Implicit gamma theorems (I): Pseudoroots and pseudospectra

Stable ergodicity in homogeneous spaces

Complexity of Bezout's theorem IV: Probability of success; extensions