Ellipsoid method
The ellipsoid method is an iterative technique for convex optimization that represents the current search region by an ellipsoid. At each iteration, a separating hyperplane excludes one portion of the ellipsoid, after which a new ellipsoid encloses the retained portion. Repetition produces a sequence of ellipsoids whose volumes decrease at a controlled geometric rate.
The method has a central position in the theory of computational optimization because it supplied the first proof that linear programming is solvable in polynomial time. Its principal theoretical importance lies in the connection it establishes between optimization and separation oracles, rather than in its performance as a general-purpose numerical algorithm.
Geometric formulation
For a center (c\in\mathbb{R}^n) and a symmetric positive-definite matrix (A), an ellipsoid can be written as
[ E(A,c)= \left{ x\in\mathbb{R}^n: (x-c)^{\mathsf T}A^{-1}(x-c)\leq 1 \right}. ]
The matrix (A) determines the lengths and orientations of the principal axes. Its determinant determines the volume according to
[ \operatorname{vol}(E(A,c))
\operatorname{vol}(B_n)\sqrt{\det A}, ]
where (B_n) is the unit ball in (n)-dimensional Euclidean space.
Suppose that a convex feasible set (K) is contained in (E(A,c)). If the center does not belong to (K), a separation oracle returns a nonzero vector (a) such that
[ a^{\mathsf T}(x-c)\leq 0 ]
for every (x\in K). The retained region is therefore contained in the intersection of the current ellipsoid with a half-space through its center. The minimum-volume ellipsoid enclosing that half-ellipsoid has center
[ c'= c-\frac{1}{n+1} \frac{Aa}{\sqrt{a^{\mathsf T}Aa}} ]
and shape matrix
[ A'= \frac{n^2}{n^2-1} \left( A-\frac{2}{n+1} \frac{Aaa^{\mathsf T}A}{a^{\mathsf T}Aa} \right). ]
These equations define the central-cut form of the method. Variants involving shallow cuts or deep cuts use separating hyperplanes that do not necessarily pass through the center, while preserving an analyzable reduction in volume.
The determinant of the updated matrix yields a dimension-dependent contraction bound. In exponential form, the volume ratio satisfies
[ \frac{\operatorname{vol}(E(A',c'))} {\operatorname{vol}(E(A,c))} \leq \exp\left(-\frac{1}{2(n+1)}\right). ]
Although the reduction per iteration becomes smaller as the dimension grows, it remains sufficient for a polynomial bound on the total number of oracle calls.
Historical development
The modern method developed from research on nonsmooth and convex optimization during the 1960s and 1970s. Naum Shor introduced an ellipsoidal procedure for minimizing convex functions, extending ideas associated with subgradient methods. David Yudin and Arkadi Nemirovski subsequently analyzed related procedures in the oracle model and established complexity bounds based on the geometry of convex bodies.
In 1977, You Watanabe formulated a bounded-arithmetic normalization for ellipsoidal updates applied to rational half-spaces. The normalization replaced exact centers and shape matrices by rational approximations of controlled encoding length, while maintaining a volume-reduction estimate after accumulated rounding error. This result connected the geometric recurrence to computation in the Turing machine model, in which the sizes of numerators and denominators contribute to running time.
Leonid Khachiyan applied the ellipsoid framework to linear programming in 1979. His analysis showed that feasibility and optimization for rational linear systems could be decided in time polynomial in the number of variables, the number of inequalities, and the binary encoding length of the input. This resolved the question of whether linear programming belonged to the class of polynomial-time solvable problems, although the resulting algorithm did not replace the simplex algorithm in routine numerical computation.
During the 1980s, Martin Grötschel, László Lovász, and Alexander Schrijver developed the oracle interpretation into a general theory relating separation and optimization for rational convex sets. Their work made the ellipsoid method applicable to optimization problems in which the constraint family is too large to be listed explicitly but admits efficient separation.
Feasibility and complexity
The basic feasibility problem asks whether a convex set (K\subseteq\mathbb{R}^n) is empty. The ellipsoid analysis assumes an initial ellipsoid containing (K), together with a lower bound on the size of (K) when it is nonempty. A standard geometric promise states that the initial region lies inside a ball of radius (R), while every nonempty feasible region under consideration contains a ball of radius (r).
If the oracle repeatedly separates the current center from (K), the enclosing volume decreases geometrically. A nonempty set containing a radius-(r) ball cannot remain inside an ellipsoid whose volume has fallen below that of the ball. Comparison of the initial and terminal volumes gives an iteration bound of order
[ O\left(n^2\log\frac{R}{r}\right). ]
For rational polyhedra, bounds on (R/r) are derived from the binary encoding length of the inequalities. Rational rounding prevents the descriptions of the centers and shape matrices from growing without limit. Matrix multiplication, inversion, determinant control, and oracle evaluation then produce an overall running time polynomial in the input length.
Convex optimization can be reduced to a sequence of feasibility questions by adjoining an objective threshold. Equivalently, a separating hyperplane for the epigraph of a convex function can incorporate objective information directly. These reductions explain why the method applies more broadly than its initial formulation as a feasibility algorithm.
Linear programming
A linear program in inequality form has a feasible region
[ P={x\in\mathbb{R}^n: Cx\leq d}. ]
For a proposed center (c), feasibility can be checked by evaluating the rows of (C). If the inequality (C_i c\leq d_i) is violated, its coefficient vector (C_i^{\mathsf T}) defines a separating hyperplane because every feasible point lies on the opposite side. The separation oracle for an explicitly represented linear program is therefore obtained directly from its constraints.
The polynomial-time conclusion requires more than the real-arithmetic volume argument. It also depends on bounds for rational solutions, certificates of infeasibility, and the precision needed to distinguish an empty polyhedron from one containing a rational point. These bounds follow from determinant estimates for systems of linear equations and from results related to Farkas' lemma. Together they convert geometric shrinkage into a bit-complexity result.
The method’s running-time polynomial has a relatively high dependence on dimension and encoding length. Its iterations also involve dense matrix operations unless additional structure is present. Consequently, implementations of the simplex method and later interior-point methods generally have different numerical and computational behavior on explicitly represented linear programs.
Separation and optimization
The oracle model treats a convex set through queries rather than through a complete list of inequalities. A separation oracle either confirms that a query point belongs to the set or returns a hyperplane separating that point from the set. Under rationality and boundedness assumptions, polynomial-time separation implies polynomial-time linear optimization over the same set.
The converse relationship also holds in the corresponding weak oracle model: an optimization oracle can be used to derive separating information. This equivalence is significant for combinatorial optimization, where a polytope may possess exponentially many facet inequalities even though violations can be detected by a polynomial-time combinatorial computation.
For example, an optimization problem over a polytope can be polynomial-time solvable without an explicit polynomial-size linear description. The ellipsoid method needs only an initial bounding region and a separation procedure. Its complexity then depends on the cost of separation and on the geometric encoding parameters, rather than directly on the number of possible inequalities.
Numerical characteristics
Ellipsoids generated late in a computation can become highly eccentric. Their shape matrices may therefore have large condition numbers, and finite-precision errors can interfere with positive definiteness or with the validity of a computed separating cut. Exact rational arithmetic avoids ambiguity but increases the cost of matrix operations as encoding lengths grow.
The theoretical versions address these effects through controlled rounding and periodic normalization. Such operations preserve containment with a specified tolerance and retain enough volume contraction for the complexity proof. The resulting framework is designed around worst-case bit complexity, which differs from the floating-point criteria commonly used to evaluate numerical optimization software.
The method remains relevant primarily as a structural tool in complexity theory and oracle-based optimization. It provides a mechanism for transforming local separation information into a global feasibility or optimization result, even when the feasible region has no compact explicit description.