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
- Initialize for sufficiently large
- – check if is feasible
- – if not, violated constraint
- – compute minimum volume ellipsoid containing
Given , the minimum value ellipsoid containing is where
For example, for this is
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 .
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.