A polynomial method of approximate centers for linear programming

DOI10.1007/BF01586056zbMath0771.90067OpenAlexW2013162809MaRDI QIDQ1196720

Jean-Philippe Vial, Cornelis Roos

Publication date: 16 January 1993

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

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

zbMATH Keywords

convergence analysisinterior point methodspath following methods

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (31)

Interior-point algorithms for semi-infinite programming ⋮ A feasible descent cone method for linearly constrained minimization problems ⋮ Primal-dual algorithms for linear programming based on the logarithmic barrier method ⋮ A generalized interior-point barrier function approach for smooth convex programming with linear constraints ⋮ Fast convergence of the simplified largest step path following algorithm ⋮ Volumetric path following algorithms for linear programming ⋮ The curvature integral and the complexity of linear complementarity problems ⋮ A logarithmic barrier cutting plane method for convex programming ⋮ The largest step path following algorithm for monotone linear complementarity problems ⋮ An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution ⋮ Primal-dual target-following algorithms for linear programming ⋮ Solving real-world linear ordering problems using a primal-dual interior point cutting plane method ⋮ A cutting plane method from analytic centers for stochastic programming ⋮ Method of approximate centers for semi-definite programming ⋮ Unnamed Item ⋮ Properties Of Primal Interior Point Methods For QP^∗ ⋮ A survey of search directions in interior point methods for linear programming ⋮ On the complexity of following the central path of linear programs by linear extrapolation. II ⋮ Todd's low-complexity algorithm is a predictor-corrector path-following method ⋮ A build-up variant of the logarithmic barrier method for LP ⋮ A long-step barrier method for convex quadratic programming ⋮ Convergence behavior of interior-point algorithms ⋮ On the convergence of the method of analytic centers when applied to convex quadratic programs ⋮ A new full-Newton step interior-point method for \(P_*(\kappa)\)-LCP based on a positive-asymptotic kernel function ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ A circular cone relaxation primal interior point algorithm for LP ⋮ Combined entropic regularization and path-following method for solving finite convex min-max problems subject to infinitely many linear constraints ⋮ Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming ⋮ Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization ⋮ A long-step primal-dual path-following method for semidefinite programming ⋮ Degeneracy in interior point methods for linear programming: A survey

Cites Work

• Unnamed Item
• Unnamed Item
• A monotonic projective algorithm for fractional linear programming
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• An extension of Karmarkar's algorithm for linear programming using dual variables
• A polynomial Newton method for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• New trajectory-following polynomial-time algorithm for linear programming problems
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• Long steps in an \(O(n^ 3L)\) algorithm for linear programming
• Polynomial affine algorithms for linear programming
• An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Centered Projective Algorithm for Linear Programming
• How Can We Speed Up Matrix Multiplication?

This page was built for publication: A polynomial method of approximate centers for linear programming