= Ellipsoid method
The <ellipsoid method> repeatedly asks a <separation oracle> about the center of a containing ellipsoid and replaces that ellipsoid by a smaller one containing its intersection with a separating half-space. The volume decreases by a dimension-dependent factor at each iteration. For rational polyhedra, the exact feasibility theorem has polynomial bit complexity in the dimension and coefficient encoding bounds when separation is <polynomial time>. It includes lower-dimensional feasible sets through rational precision bounds or suitable relaxations; one must not declare infeasibility just because the original feasible set has zero volume.
Back to article page
