An \(O(\sqrt nL)\) iteration primal-dual second-order corrector algorithm for linear programming

DOI10.1007/s11590-010-0242-6zbMath1269.90058OpenAlexW2085309471MaRDI QIDQ644523

Wei-jie Cong, Hong-Wei Liu, Chang-He Liu

Publication date: 4 November 2011

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-010-0242-6

zbMATH Keywords

polynomial complexitysecond-order methods

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)

Related Items

An \(O(\sqrt{n}L)\) iteration Mehrotra-type predictor-corrector algorithm for monotone linear complementarity problem, An O(r(cond(G))1/4log¼ϵ−1) iteration predictor–corrector interior-point method with a new one-norm neighbourhood for symmetric cone optimization, A new primal-dual predictor-corrector interior-point method for linear programming based on a wide neighbourhood, A wide neighborhood primal-dual predictor-corrector interior-point method for symmetric cone optimization, A New Wide Neighborhood Primal-Dual Predictor-Corrector Interior-Point Method for Linear Programming, Two wide neighborhood interior-point methods for symmetric cone optimization, A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming, A step-truncated method in a wide neighborhood interior-point algorithm for linear programming, A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation, A long-step feasible predictor–corrector interior-point algorithm for symmetric cone optimization, A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization, Large-step interior-point algorithm for linear optimization based on a new wide neighbourhood, A wide neighborhood interior-point algorithm based on the trigonometric kernel function, New complexity analysis of a Mehrotra-type predictor–corrector algorithm for semidefinite programming, A new second-order corrector interior-point algorithm for P*(k)-LCP

Uses Software

• NETLIB LP Test Set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial time second order mehrotra-type predictor--corrector algorithms
• Postponing the choice of the barrier parameter in Mehrotra-type predictor-corrector algorithms
• A simpler and tighter redundant Klee-Minty construction
• Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming
• On finding a vertex solution using interior point methods
• A primal-dual infeasible-interior-point algorithm for linear programming
• Topics in semidefinite and interior-point methods
• Interior-point methods
• Multiple centrality corrections in a primal-dual method for linear programming
• On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms
• Neighborhood-following algorithms for linear programming
• Encyclopedia of Optimization
• On Mehrotra-Type Predictor-Corrector Algorithms
• On the Implementation of a Primal-Dual Interior Point Method
• Path-Following Methods for Linear Programming
• Numerical Optimization
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• An O$(\sqrtn L)$ Iteration Primal-dual Path-following Method, Based on Wide Neighborhoods and Large Updates, for Monotone LCP