An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution

DOI10.1007/BF02206810zbMath0848.90081OpenAlexW2000930544MaRDI QIDQ1915904

Robert M. Freund

Publication date: 24 October 1996

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

Newton methodbarrier functioninterior-pointmeasures of infeasibilitynonoptimality

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items

A predictor-corrector infeasible-interior-point algorithm for linear programming, A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization, Linear programming, complexity theory and elementary functional analysis, A new infeasible interior-point method based on Darvay's technique for symmetric optimization, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, Active-set prediction for interior point methods using controlled perturbations

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• A polynomial Newton method for linear programming
• A combined phase I-phase II projective algorithm 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
• Modified barrier functions (theory and methods)
• On Anstreicher's combined phase I-phase II projective algorithm for linear programming
• A polynomial method of approximate centers for linear programming
• On interior algorithms for linear programming with no regularity assumptions
• A projective algorithm for linear programming with no regularity condition
• On combined phase 1-phase 2 projective methods for linear programming
• A primal-dual infeasible-interior-point algorithm for linear programming
• Superlinear convergence of infeasible-interior-point methods for linear programming
• Polynomiality of infeasible-interior-point algorithms for linear programming
• A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
• A simple complexity proof for a polynomial-time linear programming algorithm
• Combining phase I and phase II in a potential reduction algorithm for linear programming
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• An Interior Point Column Generation Method for Linear Programming Using Shifted Barriers
• Following a “Balanced” Trajectory from an Infeasible Point to an Optimal Linear Programming Solution with a Polynomial-Time Algorithm
• Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming
• A Surface of Analytic Centers and Primal-Dual Infeasible-Interior-Point Algorithms for Linear Programming
• A Potential Reduction Algorithm with User-Specified Phase I–Phase II Balance for Solving a Linear Program from an Infeasible Warm Start
• An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming