First, let’s look at using the ellipsoid method to solve LP feasibility (recall that we’ve shown that finding the optimal solution to an LP reduces to solving feasibility). Given constraints , we want to output or indicate that the set of constraints is infeasible.

The algorithm maintains an ellipsoid, which we can describe by

*Example 1.*

*Example 2.*

**Algorithm**

- Initialize for sufficiently large
- Repeat:
- – check if is feasible

- – if not, violated constraint

- – compute minimum volume ellipsoid containing

*Lemma 1.*

*Lemma 2.*

*Lemma 3.*

Given , the minimum value ellipsoid containing is where

For example, for this is

*Theorem 1.*

For a linear program, the ellipsoid algorithm either finds a feasible or we can go to a lower-dimensional subspace after a polynomial number of iterations.

*Proof. (Lemmas 2 and 3)*

Consider the equality . It suffices to understand the minimum half-ball and smallest ellipsoid containing it. Without loss of generality, assume . Then, by symmetry, center moves only along and it has axes lengths for some . By minimality, is on the boundary of .

So,

or

The volume of

Minimizing we get and therefore the axes lengths are

and the volume is . Using the bound , we get volume

To prove the theorem, we observe in addition that if is feasible and bounded, it contains linearly independent vertices, . The simplex formed by them has volume

Each where is the solution of for some subset of inequalities.