John ellipsoid

Template:Short description File:Lowner Ellipse.webm

In mathematics, the John ellipsoid or Löwner–John ellipsoid Template:Math associated to a convex body Template:Mvar in Template:Mvar-dimensional Euclidean space Template:Tmath can refer to the Template:Mvar-dimensional ellipsoid of maximal volume contained within Template:Mvar or the ellipsoid of minimal volume that contains Template:Mvar.

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 Template:Tmath is circumscribed by a unique ellipsoid of minimal volume, and that the dilation of this ellipsoid by factor Template:Math 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 Template:Mvar. For a balanced body, this factor can be reduced to $\sqrt{n}.$

Properties

The inner Löwner–John ellipsoid Template:Math of a convex body $K\subset {ℝ}^n$ is a closed unit ball Template:Mvar in Template:Tmath if and only if Template:Math and there exists an integer Template:Math and, for Template:Math, real numbers Template:Math and unit vectors $u_i\in S^{n-1}\cap \partial K$ (where Template:Mvar is the unit n-sphere) such that

$$\sum _{i=1}^m{c}_i{u}_i=0$$

and, for all $x\in {ℝ}^n:$

$$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.Template:Rp

Let Template:Math be an ellipsoid in Template:Tmath defined by a matrix Template:Math and center Template:Math. Let Template:Math be a nonzero vector in Template:Tmath Let Template:Math be the half-ellipsoid derived by cutting Template:Math at its center using the hyperplane defined by Template:Math. Then, the Lowner-John ellipsoid of Template:Math is an ellipsoid Template:Math defined by: $$\begin{array}{cc}{𝐚}^{\prime }& =𝐚-\frac{1}{n+1}𝐛\\ {𝐀}^{\prime }& =\frac{n^2}{n^2-1}(𝐀-\frac{2}{n+1}{𝐛𝐛}^{\mathrm{T}})\end{array}$$ where Template:Math is a vector defined by: $$𝐛=\frac{1}{\sqrt{{𝐜}^{\mathrm{T}}𝐀𝐜}}𝐀𝐜$$ Similarly, there are formulas for other sections of ellipsoids, not necessarily through its center.

Applications

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. 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.

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

See also

• Template:Annotated link
• 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

• Template:Cite journal