Contents

John ellipsoid

The German-American mathematician Fritz John proved in 1948 that each convex body in Rⁿ 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.^[3] 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 ${\displaystyle {\sqrt {n}}}$.

Properties[edit]

The inner Löwner–John ellipsoid E(K) of a convex body K ⊂ Rⁿ is a closed unit ball BinRⁿ if and only if B ⊆ K and there exists an integer m ≥ n and, for i = 1, ..., m, real numbers c_i > 0 and unit vectors u_i ∈ Sⁿ⁻¹ ∩ ∂K such that^[4]

${\displaystyle \sum _{i=1}^{m}c_{i}u_{i}=0}$

and, for all x ∈ Rⁿ

${\displaystyle x=\sum _{i=1}^{m}c_{i}(x\cdot u_{i})u_{i}.}$

Computation[edit]

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.^{[5]: 70–73}

Let E(A,a) be an ellipsoid in Rⁿ, defined by a matrix A and center a. Let c be a nonzero vector in Rⁿ. 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:

${\displaystyle a'=a-{\frac {1}{n+1}}b}$ ${\displaystyle A'={\frac {n^{2}}{n^{2}-1}}\left(A-{\frac {2}{n+1}}bb^{T}\right)}$

where b is a vector defined by:

${\displaystyle b={\frac {1}{\sqrt {c^{T}Ac}}}Ac}$

Similarly, there are formulas for other sections of ellipsoids, not necessarily through its center.

Applications[edit]

The computation of Löwner–John ellipsoids (and in more general, the computation of minimal-volume polynomial level sets enclosing a set) has found many applications in control and robotics.^[6] In particular, computing Löwner–John ellipsoids has applications in obstacle collision detection for robotic systems, where the distance between a robot and its surrounding environment is estimated using a best ellipsoid fit.^[7]

Löwner–John ellipsoids has also been used to approximate the optimal policy in portfolio optimization problems with transaction costs.^[8]

See also[edit]

• Banach–Mazur compactum – Concept in functional analysis
• Ellipsoid method
• Steiner inellipse, the special case of the inner Löwner–John ellipsoid for a triangle.
• Fat object, related to radius of largest contained ball.

References[edit]

• Gardner, Richard J. (2002). "The Brunn-Minkowski inequality". Bull. Amer. Math. Soc. (N.S.). 39 (3): 355–405 (electronic). doi:10.1090/S0273-0979-02-00941-2. ISSN 0273-0979.