On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms

DOI10.1137/0802015zbMath0763.90066MaRDI QIDQ4018396

John E. jun. Dennis, Yin Zhang, Richard A. Tapia

Publication date: 16 January 1993

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1911/101672

zbMATH Keywords

Newton's method; duality gap; nondegeneracy; convergence rate analysis; \(Q\)-superlinear convergence; interior point primal-dual linear programming algorithms

Mathematics Subject Classification ID

90C05: Linear programming

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

Polynomial Interior Point Cutting Plane Methods, A quadratically convergent scaling newton’s method for nonlinear complementarity problems, Convergence behavior of interior-point algorithms, Primal-dual nonlinear rescaling method for convex optimization, A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming, Improving the rate of convergence of interior point methods for linear programming, Quadratic convergence of a long-step interior-point method for nonlinear monotone variational inequality problems, Degeneracy in interior point methods for linear programming: A survey, On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP, Interior point methods for optimal control of discrete time systems, Superlinear convergence of infeasible-interior-point methods for linear programming, Superlinear and quadratic convergence of some primal - dual interior point methods for constrained optimization, Linear programming with stochastic elements: An on-line approach, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, On the convergence of primal-dual interior-point methods with wide neighborhoods, On the convergence rate of Newton interior-point methods in the absence of strict complementarity, Primal-dual Newton-type interior-point method for topology optimization, Inexact primal-dual interior point iteration for linear programs in function spaces, A primal-dual interior-point method for linear programming based on a weighted barrier function, On the formulation and theory of the Newton interior-point method for nonlinear programming, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming, Primal-dual nonlinear rescaling method with dynamic scaling parameter update, On interior-point Newton algorithms for discretized optimal control problems with state constraints^∗