Ellipsoid method

The ellipsoid method is an iterative algorithm for convex optimization that encloses the feasible region in shrinking ellipsoids. At each step, a violated constraint guides a cut that retains the feasible region while reducing the enclosing ellipsoid.

Separation oracle: An algorithm that either confirms a point belongs to a convex set or returns a hyperplane separating it from the set. It supplies the violated constraint or separating cut that determines each ellipsoid update.
Convex set: A set containing the line segment between every pair of its points. The method's cuts preserve a convex feasible region inside each enclosing ellipsoid.
Leonid Khachiyan: A Soviet mathematician who proved that linear programming has a polynomial-time algorithm using the ellipsoid method. His 1979 result established the method's landmark role in the theory of computational complexity.
Simplex algorithm: A linear-programming algorithm that moves between vertices of the feasible polytope. Unlike the ellipsoid method's polynomial worst-case bound, simplex often performs well empirically but can take exponential time.
Linear programming feasibility: The problem of finding a point satisfying a system of linear inequalities, or certifying that none exists. This is the direct feasibility task solved by applying the method to linear constraints.
Central cut: A hyperplane cut through an ellipsoid's center that retains the half containing the feasible region. The central cut is the standard update when a separating hyperplane passes through the current center.
Convex optimization: Optimization of a convex objective over a convex feasible set. The ellipsoid method applies to convex problems through their feasible regions and separating information.
Linear programming: Optimization of a linear objective subject to linear equality and inequality constraints. Khachiyan's polynomial-time result concerned linear programming, even though the method is broader.
Interior-point method: An optimization method that approaches an optimum through the interior of the feasible region. Interior-point algorithms later combined strong complexity guarantees with much better practical performance on many linear programs.
Semidefinite programming: Optimization over symmetric matrices constrained to be positive semidefinite. Oracle-based ellipsoid techniques can address semidefinite programs when suitable separation information is available.

Linked from 2 pages