.
Ellipsoid Algorithm
First known to be polynomial time algorithm with regard to linear programming.
Solves
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.
To obtain the next smaller ellipsoid:
- find most violated constraint ak
- find smallest ellipsoid which includes constraint
.
