# Jing Jian: Ellipsoid algorithm

My favorite algorithm is the ellipsoid algorithm in solving linear program-

ming problems. The algorithm uses the duality theorem to first transform a min-

imization/maximization linear programming problem into a problem of finding

a feasible solution for a linear system. Let P = {ax = b} be a system of linear

inequalities (x and b are vectors). Let the point set E = {(x-z)^T D^{-1} (x-z)} be

a generalized ellipsoid containing the polytope defined by P centered at point

z. The algorithm is as follows:

We start with E and test to see if z satises P: if it does, the algorithm ter-

minates; if it does not, we find the hyperplane defined by the violated constraint

and nd ellipsoid that contains the half of E on the other side of the hyperplane.

We substitute the smaller ellipsoid for E and repeat the above procedure until

the ellipsoid’s center is a feasible point.

The algorithm terminates in O(n^6). The analysis of the algorithm bases on

upper bounding the size of the original ellipsoid and lower bounding the size of

the nal ellipsoid using the fact that our input is polynomial sized. Combined

with the fact that with each iteration of the loop the size of the ellipsoid shrinks

by a constant ratio.