Ellipsoid method

Encyclopedia : E : EL : ELL : Ellipsoid method

The ellipsoid method is an algorithm for solving linear programs. It works by first reducing the problem of optimization to a problem of feasibility. To check whether the resulting polytope is empty, it is bounded by an ellipsoid. Then, in successive steps, the ellipsoid is reduced in size until the center of the ellipsoid is in the polytope, or until the ellipsoid is too small.

The algorithm was introduced by Leonid Khachiyan and was further developed by M. Grötschel, L. Lovász and A. Schrijver in 1981. At the time, the ellipsoid method was the only algorithm for solving linear program whose runtime was provably polynomial. In practice however, variations of the simplex algorithm are much faster. Karmarkar's algorithm (1984) solves the linear program in provably polynomial time, and is much faster than the ellipsoid method in both theory and practice.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.