# Ellipsoid method

An iteration of the ellipsoid method

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size.

The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

## History

The ellipsoid method has a long history. As an iterative method, a preliminary version was introduced by Naum Z. Shor. In 1972, an approximation algorithm for real convex minimization was studied by Arkadi Nemirovski and David B. Yudin (Judin). As an algorithm for solving linear programming problems with rational data, the ellipsoid algorithm was studied by Leonid Khachiyan; Khachiyan's achievement was to prove the polynomial-time solvability of linear programs. This was a notable step from a theoretical perspective: The standard algorithm for solving linear problems at the time was the simplex algorithm, which has a run time that *typically* is linear in the size of the problem, but for which examples exist for which it is *exponential* in the size of the problem. As such, having an algorithm that is *guaranteed* to be polynomial for all cases seemed like a theoretical breakthrough.

Khachiyan's work showed, for the first time, that there can be algorithms for solving linear programs whose runtime can be proven to be polynomial. In practice, however, the algorithm is fairly slow and of little practical interest, though it provided inspiration for later work that turned out to be of much greater practical use. Specifically, Karmarkar's algorithm, an interior-point method, is much faster than the ellipsoid method in practice. Karmarkar's algorithm is also faster in the worst case.

The ellipsoidal algorithm allows complexity theorists to achieve (worst-case) bounds that depend on the dimension of the problem and on the size of the data, but not on the number of rows, so it remained important in combinatorial optimization theory for many years.[1][2][3][4] Only in the 21st century have interior-point algorithms with similar complexity properties appeared.[citation needed]

## Description

A convex minimization problem consists of the following ingredients.

• A convex function ${\displaystyle f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R} }$ to be minimized over the vector ${\displaystyle x}$ (containing n variables);
• Convex inequality constraints of the form ${\displaystyle f_{i}(x)\leqslant 0}$, where the functions ${\displaystyle f_{i}}$ are convex; these constraints define a convex set ${\displaystyle Q}$.
• Linear equality constraints of the form ${\displaystyle h_{i}(x)=0}$.

We are also given an initial ellipsoid ${\displaystyle {\mathcal {E}}^{(0)}\subset \mathbb {R} ^{n}}$ defined as

${\displaystyle {\mathcal {E}}^{(0)}=\left\{z\in \mathbb {R} ^{n}\ :\ (z-x_{0})^{T}P_{(0)}^{-1}(z-x_{0})\leqslant 1\right\}}$

containing a minimizer ${\displaystyle x^{*}}$, where ${\displaystyle P_{(0)}\succ 0}$ and ${\displaystyle x_{0}}$ is the center of ${\displaystyle {\mathcal {E}}}$.

Finally, we require the existence of a cutting-plane oracle (also called a separation oracle) for the convex set ${\displaystyle Q}$. Given a point ${\displaystyle x\in \mathbb {R} ^{n}}$, the oracle should return one of two answers:[5]

• "The point ${\displaystyle x}$ is in ${\displaystyle Q}$", or -
• "The point ${\displaystyle x}$ is in not in ${\displaystyle Q}$, and moreover, here is a hyperplane that separates ${\displaystyle x}$ from ${\displaystyle Q}$", that is, a vector ${\displaystyle c}$ such that ${\displaystyle c\cdot x for all ${\displaystyle y\in Q}$.

One example of a cutting-plane oracle is given by a subgradient g of f.[clarification needed]

### Application to linear programming

In the context of linear programming, the constraints are all linear, and ${\displaystyle Q}$ is a convex polytope. Then, the separation oracle can be easily implemented as follows.[5] Given the constraints ${\displaystyle Q=\{x|Ax\leq b\}}$ and a point ${\displaystyle x\in \mathbb {R} ^{n}}$, the oracle just computes ${\displaystyle Ax}$:

• If the outcome is at most ${\displaystyle b}$, then ${\displaystyle x}$ is in ${\displaystyle Q}$;
• Otherwise, there is at least one row ${\displaystyle c}$ of A, such that ${\displaystyle c\cdot x}$ is larger than the corresponding value in ${\displaystyle b}$; this row ${\displaystyle c}$ gives us the separating hyperplane.

This oracle runs in polynomial time as long as the number of constraints is polynomial. In some linear optimization problems, even though the number of constraints is exponential, one can still write a custom separation oracle that works in polynomial time. Two examples are:[6]

• The minimum-cost arborescence problem: given a weighted directed graph and a vertex r in it, find a subgraph of minimum cost that contains a directed path from r to any other vertex. The problem can be presented as an LP with a constraint for each subset of vertices, which is an exponential number of constraints. However, a separation oracle can be implemented using n-1 applications of the minimum cut procedure.
• The maximum independent set problem. It can be approximated by an LP with a constraint for every odd-length cycle. While there are exponentially-many such cycles, a separation oracle that works in polynomial time can be implemented by just finding an odd cycle of minimum length.

The output of the ellipsoid method is either:

• Any point in the polytope ${\displaystyle Q}$ (i.e., any feasible point), or -
• A proof that ${\displaystyle Q}$ is empty.

Inequality-constrained minimization of a function that is zero everywhere corresponds to the problem of simply identifying any feasible point. It turns out that any linear programming problem can be reduced to a linear feasibility problem (e.g. minimize the zero function subject to some linear inequality and equality constraints). One way to do this is by combining the primal and dual linear programs together into one program, and adding the additional (linear) constraint that the value of the primal solution is no worse than the value of the dual solution. Another way is to treat the objective of the linear program as an additional constraint, and use binary search to find the optimum value.[citation needed]

## Unconstrained minimization

At the k-th iteration of the algorithm, we have a point ${\displaystyle x^{(k)}}$ at the center of an ellipsoid

${\displaystyle {\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\ :\ \left(x-x^{(k)}\right)^{T}P_{(k)}^{-1}\left(x-x^{(k)}\right)\leqslant 1\right\}.}$

We query the cutting-plane oracle to obtain a vector ${\displaystyle g^{(k+1)}\in \mathbb {R} ^{n}}$ such that

${\displaystyle g^{(k+1)T}\left(x^{*}-x^{(k)}\right)\leqslant 0.}$

We therefore conclude that

${\displaystyle x^{*}\in {\mathcal {E}}^{(k)}\cap \left\{z\ :\ g^{(k+1)T}\left(z-x^{(k)}\right)\leqslant 0\right\}.}$

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

{\displaystyle {\begin{aligned}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)\end{aligned}}}

where

${\displaystyle {\tilde {g}}^{(k+1)}=\left({\frac {1}{\sqrt {g^{(k+1)T}P_{(k)}g^{(k+1)}}}}\right)g^{(k+1)}.}$

The stopping criterion is given by the property that

${\displaystyle {\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f\left(x^{(k)}\right)-f\left(x^{*}\right)\leqslant \epsilon .}$
 ${\displaystyle k=0}$ ${\displaystyle k=1}$ ${\displaystyle k=2}$ ${\displaystyle k=3}$ ${\displaystyle k=4}$ ${\displaystyle k=5}$

## Inequality-constrained minimization

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

• If ${\displaystyle x^{(k)}}$ is feasible, perform essentially the same update as in the unconstrained case, by choosing a subgradient ${\displaystyle g_{0}}$ that satisfies
${\displaystyle g_{0}^{T}\left(x^{*}-x^{(k)}\right)+f_{0}\left(x^{(k)}\right)-f_{\rm {best}}^{(k)}\leqslant 0}$
• If ${\displaystyle x^{(k)}}$ is infeasible and violates the j-th constraint, update the ellipsoid with a feasibility cut. Our feasibility cut may be a subgradient ${\displaystyle g_{j}}$ of ${\displaystyle f_{j}}$ which must satisfy
${\displaystyle g_{j}^{T}\left(z-x^{(k)}\right)+f_{j}\left(x^{(k)}\right)\leqslant 0}$

for all feasible z.

## Performance

The ellipsoid method is used on low-dimensional problems, such as planar location problems, where it is numerically stable. On even "small"-sized problems, it suffers from numerical instability and poor performance in practice.

However, the ellipsoid method is an important theoretical technique in combinatorial optimization. In computational complexity theory, the ellipsoid algorithm is attractive because its complexity depends on the number of columns and the digital size of the coefficients, but not on the number of rows. In the 21st century, interior-point algorithms with similar properties have appeared[citation needed].

## Notes

1. ^ M. Grötschel, L. Lovász, A. Schrijver: Geometric Algorithms and Combinatorial Optimization, Springer, 1988.
2. ^ L. Lovász: An Algorithmic Theory of Numbers, Graphs, and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986.
3. ^ V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M. J. Atallah, CRC Press 1999, 31-1 to 31-37.
4. ^ V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.
5. ^ a b "MIT 6.854 Spring 2016 Lecture 12: From Separation to Optimization and Back; Ellipsoid Method - YouTube". www.youtube.com. Retrieved 2021-01-03.
6. ^ Vempala, Santosh (2016). "Separation oracle" (PDF).