Ellipsoid Method

First, let’s look at using the ellipsoid method to solve LP feasibility (recall that we’ve shown that finding the optimal solution to an LP reduces to solving feasibility). Given constraints Ax \leq b, we want to output x : Ax \leq b or indicate that the set of constraints is infeasible.

The algorithm maintains an ellipsoid, which we can describe by

E(z, A) = \{ x : (x-z)^T A^{-1} (x-z) \leq 1\}

Example 1.
A = I, z = 0 \implies E(0, I) = \{x : \|x\|^2 \leq 1\}

Example 2.
A = \begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}, z=(1, 1) \implies E(z, A) = \frac{(x_1 - 1)^2}{a^2} + \frac{(x_2 - 1)^2}{b^2} \leq 1

Algorithm

  • Initialize E_0 = (0, R^2 I) for sufficiently large R
  • Repeat:
      – check if z is feasible
      – if not, violated constraint a \cdot x \leq a \cdot z
      – compute minimum volume ellipsoid E_{t+1} containing E_t \cap \{x : a \cdot x \leq a \cdot z\}

Lemma 1.
bits(R) \leq poly(n, bits(A), bits(b))

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

Lemma 3.
Given E(z, A), the minimum value ellipsoid containing E(z, A) \cap \{x : a \cdot x \leq a \cdot z\} is E'(z', A') where

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

For example, for A = I, z = 0, a = e_1 = (1, 0, ..., 0)^T this is

z' = -\frac{1}{n+1} (1, 0, ..., 0)^T
A' = \frac{n^2}{n^2 - 1} (I - \frac{2}{n+1} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}) = \frac{n^2}{n^2 - 1} \begin{pmatrix} \frac{n-1}{n+1} & 0 & 0 \\ 0 & \ddots & \vdots \\ 0 & \dots & \ddots \end{pmatrix}

Theorem 1.
For a linear program, the ellipsoid algorithm either finds a feasible x or we can go to a lower-dimensional subspace after a polynomial number of iterations.

Proof. (Lemmas 2 and 3)
Consider the equality E(z, A) = z + A^{\frac{1}{2}}E(0, I). It suffices to understand the minimum half-ball and smallest ellipsoid containing it. Without loss of generality, assume a = (1, 0, ..., 0)^T. Then, by symmetry, E' center moves only along e_1 and it has axes lengths (1-z), r, ..., r for some r. By minimality, (0, 1, 0, ..., 0) is on the boundary of E'.

So,
((0, 1) - (z, 0)) \begin{pmatrix} \frac{1}{(1-z)^2} & 0 \\ 0 & \frac{1}{r^2} \end{pmatrix} (\begin{pmatrix}0 \\ 1 \end{pmatrix} - \begin{pmatrix} z \\ 0 \end{pmatrix}) = 1
or
\frac{z^2}{(1-z)^2} + \frac{1}{r^2} = 1 \implies r = \frac{1-z}{\sqrt{1-2z}}

The volume of E' = Vol(B_n) \cdot \prod_i axislength_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}}}

Minimizing f(z) = \frac{(1-z)^n}{(1-2z)^{\frac{n-1}{2}}} we get z = \frac{1}{n+1} 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}}, ...

and the volume is \frac{n^n}{(n+1)(n^2 - 1)^{\frac{n-1}{2}}} = (\frac{n}{n+1})(\frac{n^2}{n^2 - 1})^{\frac{n-1}{2}} = (1 - \frac{1}{n+1})(1 + \frac{1}{n^2 - 1})^{\frac{n-1}{2}}. Using the bound 1+x \leq e^x, we get volume \leq e^{-\frac{1}{n+1}} \cdot e^{\frac{1}{2(n+1)}} = e^{-\frac{1}{2n+2}}

To prove the theorem, we observe in addition that if P is feasible and bounded, it contains n+1 linearly independent vertices, x^0, ..., x^n. The simplex formed by them has volume

V = \frac{1}{n!} \begin{vmatrix} 1 & 1 & \dots & 1 \\ x^0 & x^1 & \dots & x^n \\ \vdots & \vdots & \vdots & \vdots \end{vmatrix}

Each x_i^j = \frac{\det(C_i^j)}{\det(C^j)} where x^j is the solution of C^j x = d^j for some subset of inequalities.

V = \frac{1}{n!} \begin{vmatrix} 1 & \dots & 1 \\ & \vdots & \\ \dots & \frac{\det(C_i^j)}{\det(C^j)} & \dots \end{vmatrix} = \frac{1}{n!} \det \begin{pmatrix} \det(C^0) & \dots & \det(C^n) \\ \det(C^0_1) & \dots \\ \vdots \\ & & \det(C^n_n) \end{pmatrix} \begin{pmatrix} \frac{1}{\det(C^0)} & & \\ & \ddots & \\ & & \frac{1}{\det(C^n)} \end{pmatrix} \geq \frac{1}{n!} \prod_j \frac{1}{\det(C^j)} \geq 2^{-poly(n, bits(A, b))} \square

Advertisement