Ellipsoid Algorithm.pdf

The Ellipsoid algorithm, designed by KHACHIAN (1979), is a polynomial running time algorithm for solving a general system of linear inequalities. A simplified version by Yamnitsky and Levin utilizes the Simplex construct. The algorithm finds a feasible solution, implying the existence of an optimum solution. It starts with a Simplex S that encloses all polytope vertices and checks if the midpoint of S is a feasible solution. If not, it finds another S with smaller volume that still encloses the polytope, eventually leading to a feasible solution or concluding that there is no solution. The algorithm assumes rational input and defines the size of the input in bits as L, where 2L ≥ nn+1B^n+1*m. The goal is to find a point in the polytope P = {x|Ax ≤ b}, with all vertices x ∈ P written as x = (d1/d, d2/d, ..., dn/d), where 0 ≤ |di| ≤ 2L and 0 < |d| ≤ 2L. The algorithm also considers Linear Strict Inequalities (LSI) and defines a Half-Simplex as the intersection of a Simplex with a half-space. The prerequisites for the algorithm include the existence of a simplex S ⊂ P with Vol(S) > 0, which is guaranteed by Theorem D, stating that each vertex x ∈ P can be described as a convex combination of at most n + 1 vertices of P.