Ellipsoid method

The ellipsoid method is a polynomial algorithm for linear optimization . It was originally developed in 1976 and 1977 by David Yudin and Arkadi Nemirovski and independently by Naum Schor to solve convex optimization problems . In 1979 it was extended by the Russian mathematician Leonid Khachiyan to the first polynomial algorithm for solving linear programs. With this he proved for the first time the polynomial solvability of linear optimization problems. The ellipsoid method is not suitable for practical purposes, however, since it is numerically far inferior to the simplex method in practice.

The ellipsoid is a algorithm for deciding whether a full-dimensional polyhedron shape , wherein a real - matrix and dimensionally compatible vectors are is empty or not. If the polyhedron contains a point, then the method outputs one as well. It can be shown that this problem is equivalent to finding the optimal solution of a linear program. ${\displaystyle P=\{x\in \mathbb {R} ^{n}\;|\;Ax\leq b\}}$ ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle x,b}$

Two iterations of the ellipsoid method

The algorithm works as follows:

1. An ellipsoid (red in the picture) is determined which - if it is not empty (blue in the picture) - contains a point of the polyhedron. One can choose a sufficiently large sphere that must contain all possible corners of . Whose maximum coordinates, and so that the necessary radius of the sphere can be achieved by solving systems of linear equations from with entries and determine. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle b}$
2. Determination of a maximum number of iterations for the following steps:
3. It is tested whether the center (in the picture the red point) of the ellipsoid lies in the polyhedron (i.e. ) ${\displaystyle z}$ ${\displaystyle Az\leq b}$
4. If so, there is an output and the algorithm is ended. ${\displaystyle z}$
5. If not, one looks for an inequality (cutting plane) that separates the polyhedron. This can, for example, be a row of the matrix that satisfies. ${\displaystyle z}$ ${\displaystyle a_{i}}$ ${\displaystyle A}$ ${\displaystyle a_{i}z>b_{i}}$
6. In the half-space , if the polyhedron is not empty, there is a point of . Now one looks for an ellipsoid (green in the picture) that is as small as possible, but contains the intersection of this half-space with the original ellipsoid. ${\displaystyle \{x\in R^{n}\;|\;a_{i}(x-z)\leq 0\}}$ ${\displaystyle P}$
7. If the maximum number of iterations is reached without an ellipsoid center lying in the polyhedron, this is empty. Otherwise, go back to 3.

The maximum number of iterations is calculated polynomially from the length of the binary coding of the matrix A and the vector b. This termination criterion is based on the fact that the examined polyhedron must have a minimum size that depends on the coding length of and . If the current ellipsoid falls below this minimum size, the polyhedron must be empty. ${\displaystyle A}$ ${\displaystyle b}$

literature

• Korte, Bernhard; Vygen, Jens: combinatorial optimization , Springer Berlin Heidelberg, 2008. ISBN 978-3-540-76918-7 , pp. 79-107