An \(O(n^ 3L)\) potential reduction algorithm for linear programming

DOI10.1007/BF01594937zbMath0734.90057OpenAlexW2599168675MaRDI QIDQ811360

Publication date: 1991

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

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

zbMATH Keywords

interior point algorithm primal-dual potential function

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 (69)

A globally convergent primal-dual interior point algorithm for convex programming ⋮ Interior-point algorithms for semi-infinite programming ⋮ Convergence property of the Iri-Imai algorithm for some smooth convex programming problems ⋮ Theoretical convergence of large-step primal-dual interior point algorithms for linear programming ⋮ Determination of optimal vertices from feasible solutions in unimodular linear programming ⋮ Extensions of the potential reduction algorithm for linear programming ⋮ Combining phase I and phase II in a potential reduction algorithm for linear programming ⋮ Limiting behavior of weighted central paths in linear programming ⋮ Interior-point solver for large-scale quadratic programming problems with bound constraints ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones ⋮ Potential reduction method for harmonically convex programming ⋮ Asymptotic convergence in a generalized predictor-corrector method ⋮ Potential-reduction methods in mathematical programming ⋮ Long-step strategies in interior-point primal-dual methods ⋮ Some variants of the Todd low-complexity algorithm ⋮ An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming ⋮ Large step volumetric potential reduction algorithms for linear programming ⋮ New complexity results for the Iri-Imai method ⋮ An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming ⋮ Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems ⋮ An Interior-Point Differentiable Path-Following Method to Compute Stationary Equilibria in Stochastic Games ⋮ Applications of second-order cone programming ⋮ A primal-dual potential reduction method for problems involving matrix inequalities ⋮ A Simple Efficient Interior Point Method for Min-Cost Flow ⋮ On inverse traveling salesman problems ⋮ A constraint-reduced variant of Mehrotra's predictor-corrector algorithm ⋮ Adaptive constraint reduction for convex quadratic programming ⋮ Theoretical treatment of target coverage in wireless sensor networks ⋮ On the length of primal-dual projection of potential reduction algorithm ⋮ A potential-reduction algorithm for linear complementarity problems ⋮ A unified approach to interior point algorithms for linear complementarity problems: A summary ⋮ Comparative analysis of affine scaling algorithms based on simplifying assumptions ⋮ On lower bound updates in primal potential reduction methods for linear programming ⋮ A combined phase I-phase II scaled potential algorithm for linear programming ⋮ A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start ⋮ An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem ⋮ A note on a potential reduction algorithm for LP with simultaneous primal-dual updating ⋮ On the convergence of the affine-scaling algorithm ⋮ Long steps in an \(O(n^ 3L)\) algorithm for linear programming ⋮ An interior point potential reduction algorithm for the linear complementarity problem ⋮ A polynomial method of approximate centers for linear programming ⋮ Todd's low-complexity algorithm is a predictor-corrector path-following method ⋮ On interior algorithms for linear programming with no regularity assumptions ⋮ An active-set strategy in an interior point method for linear programming ⋮ Strict monotonicity in Todd's low-complexity algorithm for linear programming ⋮ A build-up variant of the logarithmic barrier method for LP ⋮ On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm ⋮ Convergence behavior of interior-point algorithms ⋮ On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise ⋮ A new polynomial time method for a linear complementarity problem ⋮ A new potential reduction algorithm for smooth convex programming ⋮ Computational experience with a modified potential reduction algorithm for linear programming ⋮ An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization ⋮ Near boundary behavior of primal-dual potential reduction algorithms for linear programming ⋮ Exploiting special structure in a primal-dual path-following algorithm ⋮ An interior point potential reduction method for constrained equations ⋮ A corrector-predictor arc search interior-point algorithm for symmetric optimization ⋮ An interior point method, based on rank-1 updates, for linear programming ⋮ Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs ⋮ Differential-algebraic approach to linear programming ⋮ An extension of the potential reduction algorithm for linear complementarity problems with some priority goals ⋮ Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming ⋮ Updating lower bounds when using Karmarkar's projective algorithm for linear programming ⋮ On solution-containing ellipsoids in linear programming ⋮ A primal-dual affine-scaling potential-reduction algorithm for linear programming ⋮ Interior-point methods for linear programming: a review

Cites Work

This page was built for publication: An \(O(n^ 3L)\) potential reduction algorithm for linear programming