Ellipsoid method

The ellipsoid method is an algorithm for solving convex optimization problems. It was introduced by Naum Z. Shor, Arkady Nemirovsky, and David B. Yudin in 1972, and used by Leonid Khachiyan to prove the polynomial-time solvability of linear programs. At the time, the ellipsoid method was the only algorithm for solving linear programs whose runtime was provably polynomial. However, the interior-point method and variants of the simplex algorithm are much faster than the ellipsoid method, in both theory and practice. The algorithm works by enclosing the minimizer of a convex function in a sequence of ellipsoids whose volume decreases at each iteration.

Description

A convex optimization problem consists of a convex function $f\_0(x):\; mathbb\{R\}^n\; o\; mathbb\{R\}$ to be minimized over the variable $x$, convex inequality constraints of the form $f\_i(x)\; leq\; 0$, where the functions $f\_i$ are convex, and linear equality constraints of the form $h\_i(x)\; =\; 0$. We are also given an initial ellipsoid $mathcal\{E\}^\{(0)\}\; subset\; mathbb\{R\}^n$ defined as

:$mathcal\{E\}^\{(0)\}\; =\; left\; \{z\; in\; mathbb\{R\}^n\; :\; (z\; -\; x\_0)^T\; P\_\{(0)\}^\{-1\}\; (z-x\_0)\; leq\; 1\; ight\; \}$

containing the minimizer $x^*$, where $P\; succ\; 0$ and $x\_0$ is the center of $mathcal\{E\}$. Finally, we require the existence of a cutting-plane oracle for the function $f$. One example of a cutting-plane is given by the subgradient $g$ of $f$.

Unconstrained Minimization

At the $k$-th iteration of the algorithm, we have a point $x^\{(k)\}$ at the center of an ellipsoid $mathcal\{E\}^\{(k)\}\; =\; left\; \{x\; in\; mathbb\{R\}^n\; :\; x^T\; P\_\{(k)\}^\{-1\}\; x\; leq\; 1\; ight\; \}$. We query the cutting-plane oracle to obtain a vector $g^\{(k+1)\}\; in\; mathbb\{R\}^n$ such that $g^\{(k+1)T\}\; (x^*\; -\; x^\{(k)\}\; )\; leq\; 0$. We therefore conclude that

:$x^*\; in\; mathcal\{E\}^\{(k)\}\; cap\; \{z:\; g^\{(k+1)T\}\; (z\; -\; x^\{(k)\}\; )\; leq\; 0\; \}.$

We set $mathcal\{E\}^\{(k+1)\}$ to be the ellipsoid of minimal volume containing the half-ellipsoid described above and compute $x^\{(k+1)\}$. The update is given by

:$x^\{(k+1)\}\; =\; x^\{(k)\}\; -\; frac\{1\}\{n+1\}\; P\_\{(k)\}\; ilde\{g\}^\{(k+1)\}$:$P\_\{(k+1)\}\; =\; frac\{n^2\}\{n^2-1\}\; left(P\_\{(k)\}\; -\; frac\{2\}\{n+1\}\; P\_\{(k)\}\; ilde\{g\}^\{(k+1)\}\; ilde\{g\}^\{(k+1)T\}\; P\_\{(k)\}\; ight\; )$

where $ilde\{g\}^\{(k+1)\}\; =\; (1/sqrt\{g^\{(k+1)T\}\; P\; g^\{(k+1))g^\{(k+1)\}$. The stopping criterion is given by the property that

$sqrt\{g^\{(k)T\}P\_\{(k)\}g^\{(k)\; leq\; epsilon\; Rightarrow\; f(x^\{(k)\})\; -\; f(x^*)\; leq\; epsilon.$

Inequality-Constrained Minimization

At the $k$-th iteration of the algorithm for constrained minimization, we have a point $x^\{(k)\}$ at the center of an ellipsoid $mathcal\{E\}^\{(k)\}$ as before. We also must maintain a list of values $f\_\{\; m\{best^\{(k)\}$ recording the smallest objective value of feasible iterates so far. Depending on whether or not the point $x^\{(k)\}$ is feasible, we perform one of two tasks:

*If $x^\{(k)\}$ is feasible, perform essentially the same update as in the unconstrained case, by choosing a subgradient $g\_0$ that satisfies

:$g\_0^T(x^*-x^\{(k)\}\; )\; +\; f\_0(x^\{(k)\})\; -\; f\_\{\; m\{best^\{(k)\}\; leq\; 0$

*If $x^\{(k)\}$ is infeasible and violates the $j$-th constraint, update the ellipsoid with a feasibility cut. Our feasibility cut may be a subgradient $g\_j$ of $f\_j$ which must satisfy

:$g\_j^T(z-x^\{(k)\})\; +\; f\_j(x^\{(k)\})leq\; 0$

for all feasible $z$.

Application to Linear Programming

Performance

The ellipsoid method is rarely used in practice due to poor practical performance and is used almost exclusively as an educational tool to prove the polynomial complexity of linear programs.

External links

* [http://www.stanford.edu/class/ee364/ EE364] and [http://www.stanford.edu/class/ee364b/ EE364b] , a Stanford course homepage