Ellipsoid Algorithm

First known to be polynomial time algorithm with regard to linear programming.


find x
subject to Ax ≤ b
i.e., find a feasible solution

Run Time:

O(n4L), where L = #bits to represent A and b

Ellipsoid Algorithm

Consider a sequence associated with smaller and smaller ellipsoids each with the feasible region inside.

For iteration k:
ck = center of Ek

Eventually ck has to be inside of F, and we aredone.

ellipsoid feasible region

To obtain the next smaller ellipsoid:

  • find most violated constraint ak
  • find smallest ellipsoid which includes constraint
smaller ellipsoid