Modifications and implementation of the ellipsoid algorithm for linear programming

DOI10.1007/BF01583776MaRDI QIDQ3934131zbMATH OpenOpenAlexFDO

Authors 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 algorithmKhachiyan algorithmlinear inequalitiesmodificationsnumerically stable implementationpolynomial boundedness

Mathematics Subject Classification ID

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

Cites work

• Convergence rate of the gradient descent method with dilatation of the space
• Extension of Davidon’s Variable Metric Method to Maximization Under Linear Inequality and Equality Constraints
• Feature Article—The Ellipsoid Method: A Survey
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3508265 (Why is no real title available?)
• scientific article; zbMATH DE number 3516928 (Why is no real title available?)
• scientific article; zbMATH DE number 3523479 (Why is no real title available?)
• scientific article; zbMATH DE number 3797099 (Why is no real title available?)
• scientific article; zbMATH DE number 3215568 (Why is no real title available?)
• scientific article; zbMATH DE number 3282977 (Why is no real title available?)
• scientific article; zbMATH DE number 3385445 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• Khachiyan’s algorithm for linear programming
• Least Squares Computations by Givens Transformations Without Square Roots
• Location of the Maximum on Unimodal Surfaces
• Methods for Computing and Modifying the LDV Factors of a Matrix
• Methods for Modifying Matrix Factorizations
• The Gradient Projection Method for Nonlinear Programming. Part I. Linear Constraints
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• Triangular factors of modified matrices

Cited in

(16)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3934131)