In mathematics, the John ellipsoid or LöwnerâÂÂJohn ellipsoid associated to a convex body in -dimensional Euclidean space can refer to the -dimensional ellipsoid of maximal volume contained within or the ellipsoid of minimal volume that contains .
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 is circumscribed by a unique ellipsoid of minimal volume, and that the dilation of this ellipsoid by factor 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 . For a balanced body, this factor can be reduced to
The inner LöwnerâÂÂJohn ellipsoid of a convex body is a closed unit ball in if and only if and there exists an integer and, for , real numbers and unit vectors (where is the unit n-sphere) such that
and, for all
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 be an ellipsoid in defined by a matrix and center . Let be a nonzero vector in Let be the half-ellipsoid derived by cutting at its center using the hyperplane defined by . Then, the Lowner-John ellipsoid of is an ellipsoid defined by:
where is a vector defined by:
Similarly, there are formulas for other sections of ellipsoids, not necessarily through its center.
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.