In mathematics, the John ellipsoid or Löwner–John ellipsoid E(K) associated to a convex body K in n-dimensional Euclidean space R n {\displaystyle \mathbb {R} ^{n}} can refer to the n-dimensional ellipsoid of maximal volume contained within K or the ellipsoid of minimal volume that contains K. Often, the minimal volume ellipsoid is called the Löwner ellipsoid, and the maximal volume ellipsoid is called the John ellipsoid (although John worked with the minimal volume ellipsoid in his original paper). One can also refer to the minimal volume circumscribed ellipsoid as the outer Löwner–John ellipsoid, and the maximum volume inscribed ellipsoid as the inner Löwner–John ellipsoid. The German-American mathematician Fritz John proved in 1948 that each convex body in R n {\displaystyle \mathbb {R} ^{n}} is circumscribed by a unique ellipsoid of minimal volume, and that the dilation of this ellipsoid by factor 1/n is contained inside the convex body. That is, the outer Lowner-John ellipsoid is larger than the inner one by a factor of at most n. For a balanced body, this factor can be reduced to n . {\displaystyle {\sqrt {n}}.}
Properties The inner Löwner–John ellipsoid E(K) of a convex body K ⊂ R n {\displaystyle K\subset \mathbb {R} ^{n}} is a closed unit ball B in R n {\displaystyle \mathbb {R} ^{n}} if and only if B ⊆ K and there exists an integer m ≥ n and, for i = 1, ..., m, real numbers ci > 0 and unit vectors u i ∈ S n − 1 ∩ ∂ K {\displaystyle u_{i}\in S^{n-1}\cap \partial K} (where S is the unit n-sphere) such that
∑ i = 1 m c i u i = 0 {\displaystyle \sum _{i=1}^{m}c_{i}u_{i}=0}
and, for all x ∈ R n : {\displaystyle x\in \mathbb {R} ^{n}:}
x = ∑ i = 1 m c i ( x ⋅ u i ) u i . {\displaystyle x=\sum _{i=1}^{m}c_{i}(x\cdot u_{i})u_{i}.}
Computation In general, computing the John ellipsoid of a given convex body is a hard problem. However, for some specific cases, explicit formulas are known. Some cases are particularly important for the ellipsoid method. Let E(A, a) be an ellipsoid in R n , {\displaystyle \mathbb {R} ^{n},} defined by a matrix A and center a. Let c be a nonzero vector in R n . {\displaystyle \mathbb {R} ^{n}.} Let E'(A, a, c) be the half-ellipsoid derived by cutting E(A, a) at its center using the hyperplane defined by c. Then, the Lowner-John ellipsoid of E'(A, a, c) is an ellipsoid E(A', a') defined by:
… excerpt ends here. Continue reading the full article.
