The simplex algorithm is quite fast in practice, but no variant of it is known to be polynomial time. The Ellipsoid Algorithm is a first known to be polynomial time algorithm for linear programming,
i.e., find a feasible solution, or in other words, given a convex set , written as , find a point in .
We start with a big enough ball, which is guaranteed to contain . The sphere is defined , where is sufficiently large. (Here, and )
- check if is feasible
- if not, find a violated constraint s.t. , and compute minimum volume Ellipsoid containing is where
Now let’s prove the correctness and polynomiality of the algorithm. We will use the following lemmas.
Lemma 1. where denotes the number of bits required.
Lemma 3. Given , the minimum volume ellipsoid containing has center and matrix given as
Now the theorem we want to prove:
Theorem 4. The algorithm either finds a feasible solution or we can go to a lower dimensional space in iterations.
Proof of Lemma 2,3:
Without loss of generality, assume
By symmetry, , center moves only along e, and it has axes length for some is on boundary of .
, where is a unit n-ball, and is axis length
Minimizing we get (by setting and solve for )
and therefore the axes lengths are:
and the volume is:
and we can derive the inequality:
Each iteration of Ellipsoid algorithm only needs a violated inequality for the current query point. It does not need any other information from the feasible set. So in fact, the algorithm can be used much more generally, for convex programming.
Separation Oracle: a procedure, which answers as YES or NO, and in the latter case outputs a separating hyperplane.
Theorem 5. Given s.t. and access to a separation oracle for K, the Ellipsoid Algorithm finds a point in in at most queries.
queries to halve the volume of current ellipsoid takes halvings .