# Ellipsoid method

This algorithm seeks to solve $LaTeX: Ax \le b$ by iterations that begin with $LaTeX: x=0$ and $LaTeX: Q=\mbox{diag}(2^{-L})$, where $LaTeX: L$ is a measure of the smallest datum that can be represented -- i.e., $LaTeX: x$ is a solution if, and only if, it satisfies $LaTeX: Ax \le b + 2^{-L}$. If the current iterate, $LaTeX: x$, does not satisfy this, a new pair $LaTeX: (x', Q')$ is defined by choosing one of the violated inequalities, say $LaTeX: A_{i,*}x > b_i$. Then, let $LaTeX: v = A_{i,*}^T$, and apply the following rules:
1. $LaTeX: x' = \frac{1} {(n+1)\sqrt{v'Qv}} \; (x - Qv)$
2. $LaTeX: Q' = \frac{n^2}{(n^2 - 1)(n+1) (v^T Q v)} \; (Q - 2 v v^T)$
Now $LaTeX: E(x',Q')$ defines an ellipsoid centered at $LaTeX: x'$, and it contains all the feasible points in $LaTeX: E(x,Q)$. After at most $LaTeX: O(n^2 L)$ iterations, the algorithm terminates with a solution, or with the fact that no solution exists.
By treating the objective as a constraint, say $LaTeX: c^T x \le c^Tx^* - e$ and/or $LaTeX: c^T x \ge c^Tx^* + e$, the ellipsoid method can be used to solve a linear program. Its significance is that it was the first algorithm for linear programming shown to have polynomial time complexity.