Ellipsoid Method

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,

find x

subject to Ax \leq b

i.e., find a feasible solution, or in other words, given a convex set P, written as Ax \leq b, find a point in P.

We start with a big enough ball, which is guaranteed to contain P. The sphere is defined E_0(0, R^2I) = \{ x: (x-z)^\top A^{-1}(x-z) \leq 1 \}, where R is sufficiently large. (Here, z =0 and A = R^2I)

Repeat:

  1. check if z is feasible
  2. if not, find a violated constraint a s.t. a \cdot x \leq a \cdot z, and compute minimum volume Ellipsoid E_{t+1} containing E_t \cap \{x: a\cdot x \leq a\cdot z \} is E'(z', A') where z' = z - \frac{1}{n+1} \frac{Aa}{\sqrt{a^\top Aa}}, A' = \frac{n^2}{n^2-1}(A - \frac{2}{n+1}\frac{Aaa^\top A^\top}{a^\top Aa})

Now let’s prove the correctness and polynomiality of the algorithm. We will use the following lemmas.

Lemma 1. \langle R \rangle \leq poly(n,\langle A \rangle, \langle b\rangle) where \langle \cdot \rangle denotes the number of bits required.

Lemma 2. vol(E_{t+1}) \leq e^\frac{-1}{2n+2} vol(E_t)

Lemma 3. Given E(z, A), the minimum volume ellipsoid containing E(z, A) \cap \{x : a\cdot x \leq a\cdot z\} has center z' and matrix A' given as

z' = z - \frac{1}{n+1} \frac{Aa}{\sqrt{a^\top Aa}}          A' = \frac{n^2}{n^2-1}(A - \frac{2}{n+1}\frac{Aaa^\top A^\top}{a^\top Aa})

Now the theorem we want to prove:

Theorem 4. The algorithm either finds a feasible solution x or we can go to a lower dimensional space in O(n^2 log R) iterations.

Proof of Lemma 2,3:

Without loss of generality, assume a=(1,0,0,...0)^\top

Screen Shot 2018-11-12 at 4.07.59 AM

By symmetry, E', center moves only along e, and it has axes length (1-z), r, r, ...., r for some r \cdot (0,1,0,0,....,0) is on boundary of E'.

i.e. ((0,1) - (z, 0))\begin{pmatrix} \frac{1}{(1-z)^2} & 0 \\0 & \frac{1}{r^2}  \end{pmatrix} \left ( \begin{pmatrix} 0 \\ 1 \end{pmatrix} - \begin{pmatrix} z \\ 0 \end{pmatrix} \right ) or

\frac{z^2}{(1-z)^2}+\frac{1}{r^2}=1 \Longrightarrow r = \frac{1-z}{\sqrt{1-2z}}

vol(E') = vol(B_n) \cdot \prod_i a_i, where B_n is a unit n-ball, and a is axis length

\begin{aligned} vol(E') &= vol(B_n) \cdot \prod_i a_i \\ &= vol(B_n) \cdot (1-z)\cdot r^{n-1} \\ &=vol(B_n) \cdot \frac{(1-z)^n}{(1-2z)^\frac{n-1}{2}}\end{aligned}

Minimizing f(z) = \frac{(1-z)^n}{1-2z^\frac{n-1}{2}} we get z=\frac{1}{n+1} (by setting \nabla f(z) = 0 and solve for z)

and therefore the axes lengths are:

\frac{n}{n+1}\frac{\frac{n}{n+1}}{\sqrt{\frac{n-1}{n+1}}} = \frac{n}{\sqrt{n^2-1}} \cdot

and the volume is:

\frac{n^n}{(n+1)(n^2-1)^\frac{n-1}{2}}

and we can derive the inequality:

\begin{aligned} \frac{n^n}{(n+1)(n^2-1)^\frac{n-1}{2}} &= \left (\frac{n}{n+1}\right )\cdot\left ( \frac{n^2}{n^2-1}\right )^\frac{n-1}{2} \\ &= \left( 1-\frac{1}{n+1}\right )\left ( 1+\frac{1}{n^2-1}\right )^\frac{n-1}{2} \\&\leq e^\frac{-1}{n+1} \cdot e^\frac{1}{2(n+1)} = e^{-\frac{1}{2n+2}}\end{aligned}.

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 z \in P as YES or NO, and in the latter case outputs a separating hyperplane.

Theorem 5. Given r, R s.t. \exists x_0 ~~ x_0+rB_n \subset K \subset RB_n and access to a separation oracle for K, the Ellipsoid Algorithm finds a point in K in at most O(n^2 log(\frac{R}{r})) queries.

O(n) queries to halve the volume of current ellipsoid R^n \rightarrow r^n takes n\cdot log\frac{R}{r} halvings \rightarrow O(n^2 log\frac{R}{r}).