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.

A nonempty linear polyhedron can have no extreme point. Intersect it with an orthant containing one feasible point, and minimize the sum of the signed coordinates there. The relevant sublevel sets are compact, so the minimum face has an extreme point, which is also extreme in the orthant intersection. The added signed-coordinate rows are integer rows with entries at most one. The integer-matrix vertex coordinate bound gives $R=n!\max (1,U{)}^n$. This supplies a bounded feasibility search even when the original polyhedron contains lines.

For an integer linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\ge b\}$ with coefficients bounded by $U\ge 1$, put $D=[(n+1)U{]}^{n+1}$ and $0<\epsilon <1/D$. If $x_0\in P$, every $h$ with $\Vert h{\Vert }_2\le \epsilon /(nU)$ satisfies $A_{i}h\ge -\sqrt{n}U\Vert h{\Vert }_2\ge -\epsilon$. Thus $P_{\epsilon }$ contains a positive-radius Euclidean ball and is a full-dimensional linear polyhedron. If $P$ is empty, the normalized integer Farkas infeasibility gap gives $\lambda \ge 0$, $A^T\lambda =0$, $1^T\lambda =1$ and $b^T\lambda \ge 1/D$. A point of $P_{\epsilon }$ would give $0={\lambda }^{T}Ax\ge b^T\lambda -\epsilon >0$, a contradiction. Consequently this relaxation preserves emptiness and supplies the inner-volume bound needed by the ellipsoid method, even when $P$ has empty interior.

A polynomial-time algorithm for integer linear feasibility gives exact rational linear programming optimization. Rational vertex bounds give a polynomial-bit bound on every finite optimal value and its denominator. An objective threshold below that bound detects unboundedness after feasibility is established. Binary search with the additional inequality $c^{T}x\le t$ localizes the finite optimum to an interval containing a unique rational of bounded denominator; continued fractions recover it exactly. A feasible optimizer can then be found by successive coordinate minimizations on a bounded optimal face. These produce faces of one fixed rational polytope, so one uniform vertex-denominator bound works throughout, avoiding exponential growth of precision requirements.

For $n\ge 2$, the standard ellipsoid covering a centrally cut half of the unit ball has center $e_1/(n+1)$ and shape matrix $D^{\prime }=\frac{n^2}{n^2-1}(I-\frac{2}{n+1}{e}_1{e}_1^T)$. Its eigenvalues are $n^2/(n+1{)}^2$ along $e_1$ and $n^2/(n^2-1)$ in the other directions. Hence its volume ratio is $R=\frac{n}{n+1}(\frac{n^2}{n^2-1}{)}^{(n-1)/2}$. Using $\log (1-a)<-a$ and $\log (1+b)<b$ gives $\log R<-1/(2(n+1))$. Affine changes of coordinates preserve the volume ratio. The resulting geometric convergence underlies the ellipsoid method; exact rational feasibility additionally needs input-dependent size, precision and lower-dimensional feasibility bounds.