Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
From MaRDI portal
Publication:1361107
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
interior-point algorithmcorrector stepsprimal-dual Dikin affine scaling algorithmsemi-definite linear complementarity
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
