Ellipsoid method

Definition

Let $n \ge 2$ and let $K \subseteq \R^n$ be a convex set. Assume that $K$ is given by a separation oracle: for each $c \in \R^n$ it either states $c \in K$, or returns $a \in \R^n \setminus \set{0}$ with $a^T x \le a^T c$ for all $x \in K$. For $c \in \R^n$ and a positive definite matrix $P$ of size $n \times n$, let $E(c, P) = \set{x \in \R^n : (x - c)^T P^{-1} (x - c) \le 1}$. Assume that $K \subseteq E(c_0, P_0)$ for a given ellipsoid. The ellipsoid method is the algorithm that, for $k = 0, 1, 2, \dots$, runs these steps.

1. Query the oracle at $c_k$; if $c_k \in K$, stop and return $c_k$.
2. Otherwise, take the returned vector $a$ and set $b = P_k a / \sqrt{a^T P_k a}$.
3. Set $c_{k+1} = c_k - \frac{1}{n + 1} b$ and $P_{k+1} = \frac{n^2}{n^2 - 1} \bigl(P_k - \frac{2}{n + 1} b b^T\bigr)$.

Then $E(c_{k+1}, P_{k+1})$ is the ellipsoid of least volume containing the half-ellipsoid $E(c_k, P_k) \cap \set{x : a^T x \le a^T c_k}$, and so it contains $K$.