Unified complexity analysis for Newton LP methods

DOI10.1007/BF01585691MaRDI QIDQ1184332zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A unified view of interior point methods for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Complexity analysis for certain convex programming problems
• Linear programming, complexity theory and elementary functional analysis
• A new polynomial-time algorithm for linear programming

Cites work

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

Cited in

(17)

• A continuation algorithm for a class of linear complementarity problems using an extrapolation technique
• A new linesearch method for quadratically constrained convex programming
• Fast convergence of the simplified largest step path following algorithm
• Modified barrier functions (theory and methods)
• The implementation of linear programming algorithms based on homotopies
• The modified barrier function method for linear programming and its extensions
• Zonotopes and the LP-Newton method
• The Kantorovich theorem and interior point methods
• A long-step barrier method for convex quadratic programming
• Newtonian program analysis via tensor product
• Methods of centers for variational inequalities and linear programming
• Improving the rate of convergence of interior point methods for linear programming
• scientific article; zbMATH DE number 7705687 (Why is no real title available?)
• The Newton modified barrier method for QP problems
• Linear programming, complexity theory and elementary functional analysis
• Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
• Complexity analysis for certain convex programming problems

This page was built for publication: Unified complexity analysis for Newton LP methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1184332)