Modifications and implementation of the ellipsoid algorithm for linear programming

DOI10.1007/BF01583776zbMath0477.90038OpenAlexW2050434204MaRDI QIDQ3934131

Donald Goldfarb, Michael J. Todd

Publication date: 1982

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

ellipsoid algorithmlinear inequalitiesmodificationspolynomial boundednessKhachiyan algorithmnumerically stable implementation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (15)

A Fast and Practical Method to Estimate Volumes of Convex Polytopes ⋮ Block-iterative surrogate projection methods for convex feasibility problems ⋮ Objective functions and the complexity of policy design ⋮ On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids ⋮ Kan extensions are partial colimits ⋮ Simplices by point-sliding and the Yamnitsky-Levin algorithm ⋮ Stochastic ellipsoid methods for robust control: Multiple updates and multiple cuts ⋮ The ellipsoid method in linear programming ⋮ Monotone Gram matrices and deepest surrogate inequalities in accelerated relaxation methods for convex feasibility problems ⋮ A class of rank-two ellipsoid algorithms for convex programming ⋮ An ellipsoid algorithm for nonlinear programming ⋮ Iterant recombination with one-norm minimization for multilevel Markov chain algorithms via the ellipsoid method ⋮ A class of methods for solving large convex systems ⋮ The ellipsoid method and its implications ⋮ A probabilistic ellipsoid algorithm for linear optimization problems with uncertain LMI constraints

Cites Work

• Triangular factors of modified matrices
• The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints
• Khachiyan’s algorithm for linear programming
• Feature Article—The Ellipsoid Method: A Survey
• Methods for Computing and Modifying the LDV Factors of a Matrix
• Least Squares Computations by Givens Transformations Without Square Roots
• Methods for Modifying Matrix Factorizations
• Location of the Maximum on Unimodal Surfaces
• Extension of Davidon’s Variable Metric Method to Maximization Under Linear Inequality and Equality Constraints
• Convergence rate of the gradient descent method with dilatation of the space
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Modifications and implementation of the ellipsoid algorithm for linear programming