Improved complexity using higher-order correctors for primal-dual Dikin affine scaling

DOI10.1007/BF02614380zbMath0884.90112OpenAlexW2057898847MaRDI QIDQ1361107

Benjamin Jansen, Yinyu Ye, Cornelis Roos, Tamás Terlaky

Publication date: 5 April 1998

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

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

zbMATH Keywords

interior-point algorithmcorrector stepsprimal-dual Dikin affine scaling algorithmsemi-definite linear complementarity

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path ⋮ A wide neighborhood infeasible-interior-point method with arc-search for linear programming ⋮ A wide neighborhood arc-search interior-point algorithm for convex quadratic programming ⋮ On self-regular IPMs (with comments and rejoinder) ⋮ An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood ⋮ A polynomial-iteration infeasible interior-point algorithm with arc-search for semidefinite optimization ⋮ A primal-dual interior-point algorithm with arc-search for semidefinite programming ⋮ Polynomial primal-dual cone affine scaling for semidefinite programming ⋮ A new class of polynomial primal-dual methods for linear and semidefinite optimization ⋮ On the convergence analysis of arc search interior point methods for LCPs ⋮ A predictor-corrector algorithm for \(P_{\ast}(\kappa)\)-linear complementarity problems based on a specific self-regular proximity function ⋮ A class of path-following interior-point methods for \(P_*(\kappa)\)-horizontal linear complementarity problems

Cites Work

• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• Computational experience with a primal-dual interior point method for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Family of Polynomial Affine Scaling Algorithms for Positive SemiDefinite Linear Complementarity Problems
• A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• On the Implementation of a Primal-Dual Interior Point Method
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• A Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming