Ellipsoid method

From Wikipedia, the free encyclopedia

The ellipsoid method is an algorithm for solving convex optimization problems. It was introduced by Shor, Nemirovsky, and 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. In practice, however, variations of the simplex algorithm are much faster, and interior-point methods 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.

1 Description
2 Unconstrained Minimization
3 Inequality-Constrained Minimization
- 3.1 Application to Linear Programming
4 Performance
5 External links

Main article: Convex optimization

A convex optimization problem consists of a convex function $f_0(x): \mathbb{R}^n \to \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 \right \}$

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 \$ .

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 \right \}$ . 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+1)} ) \leq 0$ . We therefore conclude that

$x^* \in \mathcal{E}^{(k)} \cap \{z: g^{(k+1)T} (z - x^{(k+1)} ) \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)} \tilde{g}^{(k+1)}$

$P_{(k+1)} = \frac{n^2}{n^2-1} \left(P_{(k)} - \frac{2}{n+1} P_{(k)} \tilde{g}^{(k+1)} \tilde{g}^{(k+1)T} P_{(k)} \right )$

where $\tilde{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$

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_{\rm{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_{\rm{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 \$ .

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.