Unified complexity analysis for Newton LP methods
The authors show that a theorem of S. Smale can be applied to unify the polynomial-time bound proofs of several of the recent interior algorithms. They consider, in particular, \textit{C. C. Gonzaga's} linear programming barrier method [in: Progress in mathematical programming, Interior-point and related methods, Proc. Conf., Pacific Grove/Calif. 1987, 1-28 (1989; Zbl 0691.90053)], the barrier method applied to convex quadratic programming, a primal linear programming method, a primal-dual linear programming method, and a primal-dual method applied to convex quadratic programming. A good reference for all this material is the collection of papers mentioned above.
- 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
- 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
- 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?)
- Interior path following primal-dual algorithms. I: Linear programming
- On a theorem of S. Smale about Newton's method for analytic mappings
- On Approximate Zeros and Rootfinding Algorithms for a Complex Polynomial
- 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
- Improving the rate of convergence of interior point methods for linear programming
- Modified barrier functions (theory and methods)
- Methods of centers for variational inequalities and linear programming
- A new linesearch method for quadratically constrained convex programming
- Fast convergence of the simplified largest step path following algorithm
- The Kantorovich theorem and interior point methods
- A continuation algorithm for a class of linear complementarity problems using an extrapolation technique
- 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
- Complexity analysis for certain convex programming problems
- Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration.
- Newtonian program analysis via tensor product
- scientific article; zbMATH DE number 7705687 (Why is no real title available?)
- A long-step barrier method for convex quadratic programming
- Zonotopes and the LP-Newton method
- The modified barrier function method for linear programming and its extensions
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)
