Unified complexity analysis for Newton LP methods

DOI10.1007/BF01585691zbMath0751.90048OpenAlexW2016205992MaRDI QIDQ1184332

James Renegar, Michael Shub

Publication date: 28 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585691

zbMATH Keywords

Newton's methodbarrier methodinterior algorithms

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A new linesearch method for quadratically constrained convex programming, Fast convergence of the simplified largest step path following algorithm, The implementation of linear programming algorithms based on homotopies, The Newton modified barrier method for QP problems, Linear programming, complexity theory and elementary functional analysis, Unnamed Item, The modified barrier function method for linear programming and its extensions, Complexity analysis for certain convex programming problems, Improving the rate of convergence of interior point methods for linear programming, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration., Modified barrier functions (theory and methods), A long-step barrier method for convex quadratic programming, The Kantorovich theorem and interior point methods, A continuation algorithm for a class of linear complementarity problems using an extrapolation technique, Methods of centers for variational inequalities and linear programming

Cites Work

• On a theorem of S. Smale about Newton's method for analytic mappings
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On zero finding methods of higher order from data at one point
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
• On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
• On the efficiency of algorithms of analysis
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Affine Invariant Convergence Theorems for Newton’s Method and Extensions to Related Methods
• Unnamed Item
• Unnamed Item
• Unnamed Item