The Ellipsoid Method: A Survey

By Robert G. Bland, Donald Goldfarb, Michael J. Todd. 1980

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “Indeed, there are (typically impractical) algorithms such as center-of-mass methods [7], which might use the dimension in order to signiﬁcantly reduce the oracle complexity, but at a potentially huge computational cost.”
The Design of Approximation Algorithms (2011, background): “An extended treatment of the topic can be found in the book of Grötschel, Lovász, and Schrijver [145]; a survey-level treatment can be found in Bland, Goldfarb, and Todd [50].”
Dynamic Resource Allocation in Cognitive Radio Networks (2010, methodology): “veloped to solve (P1-D) by alternating between solvingd(η) for a given ηand updating η to minimize d(η). At each iteration, η can be updated by a subgradient-based method such as the ellipsoid method [16], according to the subgradients of d(η), which can be shown equal to P −Tr(S⋆) and Γj −Tr GjS⋆GH”
Wiley‐Interscience Series in Discrete Mathematics and Optimization (2011, methodology): “In any case, computational experience with Khachiyan's algorithm has shown that it is not a practical alternative to the simplex method [10].”
Optimum Co-Design for Spectrum Sharing between Matrix Completion Based MIMO Radars and a MIMO Communication System (2015, methodology): “The convergence of Algorithm 1 is guaranteed by the convergence of the ellipsoid method [56].”
Wiley‐Interscience Series in Discrete Mathematics and Optimization (2011, methodology): “In any case, computational experience with Khachiyan's algorithm has shown that it is not a practical alternative to the simplex method [10].”
Design of Experiments in Nonlinear Models: Asymptotic Normality, Optimality Criteria and Small-Sample Properties (2013, methodology): “(1980) and Bland et al. (1981) for a general exposition on the ellipsoid method for combinatorial and LP problems. The method, initially proposed by Shor (1977), has been used by Khachiyan (1979) to prove the polynomial complexity of LP.”
Metaheuristic design of feedforward neural networks: A review of two decades of research (2017, methodology): “However, this was an expensive approach, which does not use any Paretobased multiobjective algorithm to compute Pareto set; rather, an ellipsoid method [290] was applied to train FNN for each scalar objective vci ∈ vc sequentially.”
Graph Implementations for Nonsmooth Convex Programs (2008, methodology): “Methods that are theoretically efficient for general nondifferentiable problems, such as the ellipsoid method [BGT81], are notoriously slow in practice.”