Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
From MaRDI portal
Publication:1361107
DOI10.1007/BF02614380zbMath0884.90112MaRDI QIDQ1361107
Cornelis Roos, Tamás Terlaky, Yinyu Ye, Benjamin Jansen
Publication date: 5 April 1998
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
interior-point algorithm; corrector steps; primal-dual Dikin affine scaling algorithm; semi-definite linear complementarity
90C60: Abstract computational complexity for mathematical programming problems
90C05: Linear programming
90C33: Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Related Items
Polynomial primal-dual cone affine scaling for semidefinite programming, On self-regular IPMs (with comments and rejoinder), A new class of polynomial primal-dual methods for linear and semidefinite optimization
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