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

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