.

# 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(n^{4}L), 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

.