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

linear inequalitiesmodificationspolynomial boundednessellipsoid algorithmKhachiyan algorithmnumerically stable implementation

Mathematics Subject Classification ID

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

Cites work

• 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?)
• 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
• 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)

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