A polynomial arc-search interior-point algorithm for linear programming

DOI10.1007/s10957-013-0281-0zbMath1274.90494arXiv1406.4539MaRDI QIDQ378268

Ya-Guang Yang

Publication date: 11 November 2013

Published in: Numerical Algorithms, Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.4539

zbMATH Keywords

linear programming; interior-point method; polynomial algorithm; arc-search; infeasible interior-point algorithm; Mehrotra's algorithm; Netlib problems

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C05: Linear programming

90C51: Interior-point methods

Related Items

A wide neighborhood infeasible-interior-point method with arc-search for -SCLCPs, An Arc Search Interior-Point Algorithm for Monotone Linear Complementarity Problems over Symmetric Cones, A New Predictor-corrector Infeasible Interior-point Algorithm for Linear Optimization in aWide Neighborhood, A polynomial time infeasible interior-point arc-search algorithm for convex optimization, A wide neighborhood infeasible-interior-point method with arc-search for linear programming, A polynomial arc-search interior-point algorithm for linear programming, A wide neighborhood interior-point algorithm with arc-search for \(P_{\ast}(\kappa)\) linear complementarity problem, An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming, A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy, On the extension of an arc-search interior-point algorithm for semidefinite optimization, An arc search infeasible interior-point algorithm for symmetric optimization using a new wide neighborhood, Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming, 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, An interior-point algorithm for linear programming with optimal selection of centering parameter and step size, An infeasible interior-point arc-search algorithm for nonlinear constrained optimization, A wide neighborhood arc-search interior-point algorithm for convex quadratic programming with box constraints and linear constraints, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, A primal-dual interior-point algorithm with arc-search for semidefinite programming, A corrector-predictor arc search interior-point algorithm for symmetric optimization, On the convergence analysis of arc search interior point methods for LCPs, An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path, An \(\ell_{2}\)-neighborhood infeasible interior-point algorithm for linear complementarity problems, An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints, A wide neighborhood arc-search interior-point algorithm for convex quadratic programming, An arc-search infeasible interior-point algorithm for horizontal linear complementarity problem in the N∞− neighbourhood of the central path

Uses Software

• Matlab
• LOQO
• Netlib
• LIPSOL
• PCx

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial arc-search interior-point algorithm for linear programming
• A polynomial arc-search interior-point algorithm for convex quadratic programming
• Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods
• A new polynomial-time algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Degeneracy in interior point methods for linear programming: A survey
• Polynomiality of infeasible-interior-point algorithms for linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Long-step strategies in interior-point primal-dual methods
• An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming
• Multiple centrality corrections in a primal-dual method for linear programming
• The many facets of linear programming
• Presolving in linear programming
• Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization
• A MODIFIED FULL-NEWTON STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR LINEAR OPTIMIZATION
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
• On Mehrotra-Type Predictor-Corrector Algorithms
• Modification of the minimum-degree algorithm by multiple elimination
• Feature Article—The Ellipsoid Method: A Survey
• On the Implementation of a Primal-Dual Interior Point Method
• On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
• LOQO:an interior point code for quadratic programming
• Two Infeasible Interior-Point Predictor-Corrector Algorithms for Linear Programming
• A Full-Newton Step O(n) Infeasible Interior-Point Algorithm for Linear Optimization
• On the Automatic Scaling of Matrices for Gaussian Elimination
• Globally convergent algorithms for robust pole assignment by state feedback
• Benchmarking optimization software with performance profiles.