The ellipsoid method

The ellipsoid method can be used to find a solution of a system of linear inequalities in polynomial time. It implies the polynomial time solvability of any linear program. This is a self-contained explanation of Khachiyan’s algorithm. First there is the definition and the fundamental properties of ellipsoids; then the algorithm to find a point in a full dimensional polytope and the proof of its correctness; finally the application of the ellipsoid method to the problem of finding a point in any polyhedron.