John ellipsoid

In mathematics, the John ellipsoid or Löwner–John ellipsoid E(K) associated to a convex body K in n-dimensional Euclidean space ⁠${\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.

Outer Löwner–John ellipsoid containing a set of a points in ⁠${\displaystyle \mathbb {R} ^{2}}$⁠

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).^[1] 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.^[2]

The German-American mathematician Fritz John proved in 1948 that each convex body in ⁠${\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.^[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

The inner Löwner–John ellipsoid E(K) of a convex body ${\displaystyle K\subset \mathbb {R} ^{n}}$ is a closed unit ball B in ⁠${\displaystyle \mathbb {R} ^{n}}$⁠ 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 ${\displaystyle u_{i}\in S^{n-1}\cap \partial K}$ (where S is the unit n-sphere) such that^[4]

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

and, for all ${\displaystyle x\in \mathbb {R} ^{n}:}$

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

Let E(A, a) be an ellipsoid in ⁠${\displaystyle \mathbb {R} ^{n},}$⁠ defined by a matrix A and center a. Let c be a nonzero vector in ⁠${\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: $${\displaystyle {\begin{aligned}\mathbf {a'} &=\mathbf {a} -{\frac {1}{n+1}}\mathbf {b} \\\mathbf {A'} &={\frac {n^{2}}{n^{2}-1}}\left(\mathbf {A} -{\frac {2}{n+1}}\mathbf {bb} ^{\mathrm {T} }\right)\end{aligned}}}$$ where b is a vector defined by: $${\displaystyle \mathbf {b} ={\frac {1}{\sqrt {\mathbf {c} ^{\mathrm {T} }\mathbf {Ac} }}}\mathbf {Ac} }$$ 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.^[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

• 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

1. Güler, Osman; Gürtuna, Filiz (2012). "Symmetry of convex sets and its applications to the extremal ellipsoids of convex bodies". Optimization Methods and Software. 27 (4–5): 735–759. CiteSeerX 10.1.1.664.6067. doi:10.1080/10556788.2011.626037. ISSN 1055-6788. S2CID 2971340.
2. Ben-Tal, A. (2001). Lectures on modern convex optimization : analysis, algorithms, and engineering applications. Nemirovskiĭ, Arkadiĭ Semenovich. Philadelphia, PA: Society for Industrial and Applied Mathematics. ISBN 0-89871-491-5. OCLC 46538510.
3. John, Fritz. "Extremum problems with inequalities as subsidiary conditions". Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, 187—204. Interscience Publishers, Inc., New York, N. Y., 1948. OCLC 1871554 MR30135
4. Ball, Keith M. (1992). "Ellipsoids of maximal volume in convex bodies". Geom. Dedicata. 41 (2): 241–250. arXiv:math/9201217. doi:10.1007/BF00182424. ISSN 0046-5755. S2CID 18330466.
5. Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419
6. Dabbene, Fabrizio; Henrion, Didier; Lagoa, Constantino M. (2017). "Simple approximations of semialgebraic sets and their applications to control". Automatica. 78: 110–118. arXiv:1509.04200. doi:10.1016/j.automatica.2016.11.021. S2CID 5778355.
7. Rimon, Elon; Boyd, Stephen (1997). "Obstacle Collision Detection Using Best Ellipsoid Fit". Journal of Intelligent and Robotic Systems. 18 (2): 105–126. doi:10.1023/A:1007960531949. S2CID 10505238.
8. Shen, Weiwei; Wang, Jun (2015). "Transaction Costs-Aware Portfolio Optimization via Fast Lowner-John Ellipsoid Approximation" (PDF). Proceedings of the AAAI Conference on Artificial Intelligence. 29: 1854–1860. doi:10.1609/aaai.v29i1.9453. S2CID 14746495. Archived from the original (PDF) on 2017-01-16.

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