Löwner–John Ellipsoids

Martin Henk

2010 Mathematics Subject Classification: 52XX, 90CXX

Keywords and Phrases: Löwner-John ellipsoids, volume, ellipsoid method, (reverse) isoperimetric inequality, Kalai’s 3^{n}-conjecture, norm approximation, non-negative homogeneous polynomials

1 The men behind the ellipsoids

Before giving the mathematical description of the Löwner–John ellipsoids and pointing out some of their far-ranging applications, I briefly illuminate the adventurous life of the two eminent mathematicians, by whom the ellipsoids are named: Charles Loewner (Karel Löwner) and Fritz John.

Karel Löwner (see Figure 1) was born into a Jewish family in Lány, a small town about 30 km west of Prague, in 1893. Due to his father’s liking for German

Figure 1: Charles Loewner in 1963 (Source: Wikimedia Commons) style education, Karel attended a German Gymnasium in Prague and in 1912 he began his studies at German Charles-Ferdinand University in Prague, where he not only studied mathematics, but also physics, astronomy, chemistry and meteorology. He made his Ph.D. in 1917 under supervision of Georg Pick on a distortion theorem for a class of holomorphic functions.

In 1922 he moved to the University of Berlin, where he made his Habilitation in 1923 on the solution of a special case of the famous Bieberbach conjecture. In 1928 he was appointed as non-permanent extraordinary professor at Cologne, and in 1930 he moved back to Prague where he became first an extraordinary professor and then a full professor at the German University in Prague in 1934. After the complete occupation of Czech lands in 1939 by Nazi Germany, Löwner was forced to leave his homeland with his family and emigrated to the United States. From this point on he changed his name to Charles Loewner. He worked for a couple of years at Louisville, Brown and Syracuse University, and in 1951 he moved to Stanford University. He died in Stanford in 1968 at the age of 75. Among the main research interests of Loewner were geometric function theory, fluid dynamics, partial differential equations and semigroups. Robert Finn (Stanford) wrote about Loewner’s scientific work: “Loewners Veröffentlichungen sind nach heutigen Maßstäben zwar nicht zahlreich, aber jede für sich richtungsweisend.”^{1}

Fritz John^{2} was born in Berlin in 1910 and studied mathematics in Göttingen where he was most influenced by Courant, Herglotz and Lewy. Shortly after Hitler had come to power in January 1933, he – as a Non-Aryan – lost his scholarship which gave him, in addition to the general discrimination of Non-Aryans, a very hard financial time. In July 1933, under supervision of Courant he finished his Ph.D. on a reconstructing problem of functions, which was suggested to him by Lewy. With the help of Courant he left Germany in the beginning of 1934 and stayed for one year in Cambridge. Fortunately, in 1935 he got an assistant professorship in Lexington, Kentucky, where he was promoted to associate professor in 1942. Four years later, 1946, he moved to New York University where he joined Courant, Friedrichs and Stoker in building the institute which later became the Courant Institute of Mathematical Sciences. In 1951 he was appointed full professor at NYU and remained there until his retirement 1981. He died in New Rochelle, NY, in 1994 at the age of 84. For his deep and pioneering contributions to different areas of mathematics which include partial differential equations, Radon transformations, convex geometry, numerical analysis, ill-posed problems etc., he received many awards and distinctions.

For detailed information on life and impact of Karel Löwner and Fritz John we refer to [16, 25, 27, 35, 36, 37, 39, 40].

1“Compared to today’s standards, Loewner’s publications are not many, yet each of them is far reaching.”

2For a picture see the article of Richard W. Cottle [13] in this volume.

Documenta Mathematica · Extra Volume ISMP (2012) 95–106

2 The ellipsoids

Before presenting the Löwner–John ellipsoids let me briefly fix some notations. An ellipsoid E in the n-dimensional Euclidean space ℝ^{n} is the image of the unit ball B_{n}, i.e., the ball of radius 1 centered at the origin, under a regular affine transformation. So there exist a t ∈ ℝ^{n}, the center of the ellipsoid, and a regular matrix T ∈ ℝ^{n×n} such that

\begin{aligned}E = t + T B_{n} & = \{t + T y : y ∈ B_{n}\} \\ & = \{x ∈ ℝ^{n} : ||T^{−1}(x − t)|| ≤ 1\}, \end{aligned}  (1)

where || · || denotes the Euclidean norm.

By standard compactness arguments it can be easily seen that every convex body K ⊂ ℝ^{n}, i.e., convex compact set with interior points, has an inscribed and circumscribed ellipsoid of maximal and minimal volume, respectively.

Figure 2: Maximal inscribed ellipse of a flat diamond, and minimal circumscribed ellipse (circle) of a regular triangle

To prove, however, that these extremal volume ellipsoids are uniquely determined requires some work. In the planar case n = 2, this was shown by F. Behrend^{3} in 1937/38 [7, 8]. O.B. Ader, a student of Fritz John in Kentucky, treated a special 3-dimensional case [1], and the first proof of uniqueness of these ellipsoids in general seems to have been given by Danzer, Laugwitz and Lenz in 1957 [14] and independently by Zaguskin [45].

In his seminal paper Extremum problems with inequalities as subsidiary conditions [26], Fritz John extends the Lagrange multiplier rule to the case of (possibly infinitely many) inequalities as side constraints. As an application of his optimality criterion he shows that for the minimal volume ellipsoid t+T B_{n}, say, containing K it holds

t + \frac{1}{n}T B_{n} ⊂ K ⊆ t + T B_{n}.  (2)

In other words, K can be sandwiched between two concentric ellipsoids of ratio n. According to Harold W. Kuhn [30], the geometric problem (2) and related questions from convex geometry were John’s main motivation for his paper [26]. John also pointed out that for convex bodies having a center of symmetry, i.e., Figure 3: Minimal volume ellipses together with their concentric copies scaled by \frac{1}{2} for the triangle and by \frac{1}{\sqrt{2}} for the square

3Felix Adalbert Behrend was awarded a Doctor of Science at German University in Prague in 1938 and most likely, he discussed and collaborated with Karel Löwner on the ellipsoids.

Documenta Mathematica · Extra Volume ISMP (2012) 95–106

there exists a c ∈ ℝ^{n} such that K = c − K = {c − y : y ∈ K}, the factor 1/n can be replaced by 1/\sqrt{n} and that both bounds are best possible as a simplex and a cube show (see Figure 3).

Actually, his optimality criterion gives more information about the geometry of minimal (or maximal) volume ellipsoids and together with a refinement/supplement by Keith Ball from 1992 [3] (see also Pełczyński [38] and [4, 21, 29]) we have the following beautiful characterization:

Theorem 2.1 (John). Let K ⊂ ℝ^{n} be a convex body and let K ⊆ B_{n}. Then the following statements are equivalent:

i) B_{n} is the unique minimal volume ellipsoid containing K.

ii) There exist contact points u_{1}, …, u_{m} ∈ bdK ∩ bdB_{n}, i.e., lying in the boundary of K and B_{n}, and positive numbers λ_{1}, …, λ_{m}, m ≥ n, such that

∑_{i=1}^{m} λ_{i} u_{i} = 0 and I_{n} = ∑_{i=1}^{m} λ_{i}(u_{i} u_{i}^{⊺}),

where I_{n} is the (n × n)- identity matrix.

For instance, let C_{n} = [−1, 1]^{n} be the cube of edge length 2 centered at the origin. C_{n} is contained in the ball of radius \sqrt{n} centered at the origin, i.e., \sqrt{n}B_{n}, which is the minimal volume ellipsoid containing C_{n}. To see this, we observe that the statement above is invariant with respect to scalings of B_{n}. Thus it suffices to look for contact points in bdC_{n} ∩ bd\sqrt{n}B_{n} satisfying ii). Obviously, all the 2^{n} vertices u_{i} of C_{n} are contact points and since ∑ u_{i} = 0 and ∑(u_{i} u_{i}^{⊺}) = 2^{n} I_{n} we are done. But do we need all of them? Or, in general, are there upper bounds on the number of contact points needed for the decomposition of the identity matrix in Theorem 2.1 ii)? There are! In the general case the upper bound is n(n + 3)/2 as it was pointed out by John. For symmetric bodies we can replace it by n(n + 1)/2. Hence we can find at most n(n + 1)/2 vertices of the cube such that the unit ball is also the minimal volume ellipsoid of the convex hull of these vertices. For the number of contact points for “typical” convex bodies we refer to Gruber [22, 23].

For maximal volume inscribed ellipsoids we have the same characterization as in the theorem above. Hence we also see that B_{n} is the maximal volume ellipsoid contained in C_{n}. Here we take as contact points the unit vectors (see Figure 3).

According to Busemann [11], Löwner discovered the uniqueness of the minimal volume ellipsoid but “did not publish his result” (see also [12, p. 90]), and in honor of Karel Löwner and Fritz John these extremal volume ellipsoids are called Löwner–John ellipsoids.

Sometimes they are also called John-Löwner ellipsoids (see, e.g., [9]), just John-ellipsoids, when the emphasis is more on the decomposition property ii) in Theorem 2.1 (see, e.g., [19, 4]), or it also happens that the maximal inscribed ellipsoids are called John-ellipsoids and the Löwner-ellipsoids are the circumscribed ones (see, e.g., [24]).

3 Ellipsoids in action

From my point of view the applications can be roughly divided into two classes, either the Löwner–John ellipsoids are used in order to bring the body into a “good position” by an affine transformation or they serve as a “good&easy” approximation of a given convex body.

I start with some instances of the first class, since problems from this class were the main motivation to investigate these ellipsoids. To simplify the language, we call a convex body K in Löwner–John-position, if the unit ball B_{n} is the minimal volume ellipsoid containing K.

Reverse geometric inequalities. For a convex body K ⊂ ℝ^{n} let r(K) be the radius of a largest ball contained in K, and let R(K) be the radius of the smallest ball containing K. Then we obviously have R(K)/r(K) ≥ 1 and, in general, we cannot bound that ratio from above, as, e.g., flat or needle-like bodies show (see Figure 2). If we allow, however, to apply affine transformations to K, the situation changes. Assuming that K is in its Löwner–John-position, by (2) we get R(K)/r(K) ≤ n and so (cf. [33])

1 ≤ max_{K convex body} min_{α regular affine transf.} \frac{R(α(K))}{r(α(K))} ≤ n.

The lower bound is attained for ellipsoids and the upper bound for simplices. The study of this type of reverse inequalities or “affine invariant inequalities” goes back to the already mentioned work of Behrend [7] (see also the paper of John [26, Section 3]) and is of great importance in convex geometry.

Another, and more involved, example of this type is a reverse isoperimetric inequality. Here the ratio of the surface area F(K) to the volume V(K) of a convex body K is studied. The classical isoperimetric inequality states that among all bodies of a given fixed volume, the ball has minimal surface area, and, again, flat bodies show that there is no upper bound. Based on John’s Theorem 2.1, however, Ball [2] proved that simplices give an upper bound, provided we allow affine transformations. More precisely, we have

\frac{F(B_{n})^{\frac{1}{n−1}}}{V(B_{n})^{\frac{1}{n}}} ≤ max_{K convex body} min_{α regular affine transf.} \frac{F(α(K))^{\frac{1}{n−1}}}{V(α(K))^{\frac{1}{n}}} ≤ \frac{F(S_{n})^{\frac{1}{n−1}}}{V(S_{n})^{\frac{1}{n}}} ,

where S_{n} is a regular n-simplex. For more applications of this type we refer to the survey [17].

Faces of symmetric polytopes. One of my favorite and most surprising applications is a result on the number of vertices f_{0}(P) and facets f_{n−1}(P), i.e., (n − 1)-dimensional faces, of a polytope P ⊂ ℝ^{n} which is symmetric with respect to the origin. For this class of polytopes, it is conjectured by Kalai that the total number of all faces (vertices, edges, …, facets) is at least 3^{n} − 1, as for instance in the case of the cube C_{n} = [−1, 1]^{n}. So far this has been verified in dimensions n ≤ 4 [41], and not much is known about the number of faces of symmetric polytopes in arbitrary dimensions. One of the very few exceptions is a result by Figiel, Lindenstrauss and Milman [15], where they show

ln(f_{0}(P)) ln(f_{n−1}(P)) ≥ \frac{1}{16}n.

In particular, either f_{0}(P) or f_{n−1}(P) has to be of size ∼ e^{\sqrt{n}}. For the proof it is essential that in the case of symmetric polytopes the factor n in (2) can be replaced by \sqrt{n}. For more details we refer to [5, pp. 274].

Preprocessing in algorithms. Also in various algorithmic related problems in optimization, computational geometry, etc., it is of advantage to bring first the convex body in question close to its Löwner–John-position, in order to avoid almost degenerate, i.e., needle-like, flat bodies. A famous example in this context is the celebrated algorithm of Lenstra [34] for solving integer programming problems in polynomial time in fixed dimension. Given a rational polytope P ⊂ ℝ^{n}, in a preprocessing step an affine transformation α is constructed such that α(P) has a “spherical appearance”, which means that R(α(P))/r(α(P)) is bounded from above by a constant depending only on n. Of course, this could be easily done, if we could determine a Löwner–John ellipsoid (either inscribed or circumscribed) in polynomial time. In general this seems to be a hard task, but there are polynomial time algorithms which compute a (1 + ϵ)-approximation of a Löwner–John ellipsoid for fixed ϵ. For more references and for an overview of the current state of the art of computing Löwner–John ellipsoids we refer to [44] and the references therein.

In some special cases, however, we can give an explicit formula for the minimal volume ellipsoid containing a body K, and so we obtain a “good&easy” approximation of K. This brings me to my second class of applications of Löwner–John ellipsoids.

Figure 4: The Löwner–John ellipse of a half-ellipse

Khachiyan’s ellipsoid allgorithm. The famous polynomial time algorithm of Khachiyan for solving linear programming problems is based on the idea to construct a sequence of ellipsoids of strictly decreasing volume containing the given polytope until either the center of an ellipsoid lies inside our given polytope or the volume of the ellipsoids is so small that we can conclude that the polytope must be empty (roughly speaking). This “ellipsoid method” goes back to works of N. Z. Shor [43] and Judin and Nemirovskiĭ [28] (see also the articles of Robert E. Bixby [10] and David Shanno [42] in this volume).

Assuming that our polytope P is contained in an ellipsoid t + T B_{n}, say, we are faced with the question what to do if t ∉ P. But then we know that one of the inequalities describing our polytope P induces a hyperplane H passing through the center t, such that P is entirely contained in one of the halfspaces H^{+}, say, associated to H. Hence we know

P ⊂ (t + T B_{n}) ∩ H^{+},

and in order to iterate this process we have to find a “small” ellipsoid containing the half-ellipsoid (t + T B_{n}) ∩ H^{+}. Here it turns out that the Löwner–John ellipsoid of minimal volume containing (t + T B_{n}) ∩ H^{+} (see Figure 4) can be explicitly calculated by a formula (see, e.g., [20, p. 70]) and the ratio of the volumes of two consecutive ellipsoids in the sequence is less than e^{−1/(2n)}. To turn this theoretic idea into a polynomial time algorithm, however, needs more work. In this context, we refer to [20, Chapter 3], where also variants of this basic ellipsoid method are discussed.

Extremal geometric problems. In geometric inequalities, where one is interested in maximizing or minimizing a certain functional among all convex bodies, the approximation of the convex body by (one of) its Löwner–John ellipsoids gives a reasonable first (and sometimes optimal) bound. As an example we consider the Banach–Mazur distance d(K, M) between two convex bodies K, M ⊂ ℝ^{n}. Here, d(K, M) is the smallest factor δ such that there exist an affine transformation α and a point x ∈ ℝ^{n} with K ⊆ α(M) ⊆ δ K + x. This distance is symmetric and multiplicative, i.e.,

d(K, M) = d(M, K) ≤ d(M, L) d(L, K).

Of course, this distance perfectly fits to Löwner–John ellipsoids and by (2) we have d(B_{n}, K) ≤ n for every convex body K. So we immediately get that the Banach-Mazur distance between any pair of convex bodies is bounded, namely

d(K, M) ≤ d(B_{n}, K) d(B_{n}, M) ≤ n^{2}.

But how good is this bound? This is still an open problem and for the current best lower and upper bounds as well as related questions on the Banach-Mazur distance we refer to [19, Sec. 7.2].

4 Beyond Ellipsoids

Looking at (2) and Theorem 2.1, it is quite natural to ask, what happens if we replace the class of ellipsoids, i.e., the affine images of B_{n}, by parallelepipeds, i.e., the affine images of the cube C_{n}, or, in general, by the affine images of a given convex body L. This question was studied by Giannopoulos, Perissinaki and Tsolomitis in their paper John’s theorem for an arbitrary pair of convex bodies [18]. They give necessary and sufficient conditions when a convex body L has minimal volume among all its affine images containing a given body K which nicely generalize Theorem 2.1. One consequence is that for every convex body K, there exists a parallelepiped t + T C_{n} such that (cf. (2) and see also Lassak [31])

t + \frac{1}{2 n − 1}T C_{n} ⊂ K ⊂ t + T C_{n}.

Observe, that in this more general setting we lose the uniqueness of an optimal solution. Another obvious question is: what can be said about minimal circumscribed and maximal inscribed ellipsoids when we replace the volume functional by the surface area, or, in general, by so the called intrinsic volumes? For answers in this context we refer to Gruber [23].

In view of (2), ellipsoids E = T B_{n} with center 0 may be described by an inequality of the form E = {x ∈ ℝ^{n} : p_{2}(x) ≤ 1}, where p_{2}(x) = x^{⊺}T^{−⊺} T^{−1}x ∈ ℝ[x] is a homogeneous non-negative polynomial of degree 2. Given a convex body K symmetric with respect to the origin, the center t in (2) of the minimal volume ellipsoid is the origin and so we can restate (2) as follows: for any 0symmetric convex body K there exists a non-negative homogeneous polynomial p_{2}(x) of degree 2 such that

(\frac{1}{n} p_{2}(x))^{\frac{1}{2}} ≤ |x|_{K} ≤ p_{2}(x)^{\frac{1}{2}} for all x ∈ ℝ^{n},  (3)

where |x|_{K} = min{λ ≥ 0 : x ∈ λ K} is the gauge or Minkowski function of K. In fact, this formulation can also be found at the end of John’s paper [26].

Since | · |_{K} defines a norm on ℝ^{n} and any norm can be described in this way, (3) tells us, how well a given arbitrary norm can be approximated by a homogeneous polynomial of degree 2, i.e., by the Euclidean norm. So what can we gain if we allow higher degree non-negative homogeneous polynomials? In [6], Barvinok studied this question and proved that for any norm |·| on ℝ^{n} and any odd integer d there exists a non-negative homogeneous polynomial p_{2d}(x) of degree 2d such that

(\frac{1}{\binom{d+n−1}{d}} p_{2d}(x))^{\frac{1}{2d}} ≤ |x| ≤ p_{2d}(x)^{\frac{1}{2d}} for all x ∈ ℝ^{n}.

Observe, for d = 1 we get (3) and thus (2) for symmetric bodies, but in general it is not known whether the factor \binom{d+n−1}{d} is best possible. Barvinok’s proof is to some extent also an application of John’s theorem as in one step it uses (2) in a certain \binom{d+n−1}{d}-dimensional vector space. In [6] there is also a variant for non-symmetric gauge functions (non-symmetric convex bodies) which, in particular, implies (2) in the case d = 1.

In a recent paper Jean B. Lasserre [32] studied the following even more general problem: Given a compact set U ⊂ ℝ^{n} and d ∈ ℕ, find a homogeneous polynomial g of degree 2d such that its sublevel set G = {x ∈ ℝ^{n} : g(x) ≤ 1} contains U and has minimum volume among all such sublevel sets containing U. It turns out that this is a finite-dimensional convex optimization problem and in [32, Theorem 3.2] a characterization of the optimal solutions is given which “perfectly” generalizes Theorem 2.1. In particular, the optimal solutions are also determined by finitely many “contact points”.

Acknowledgements. I would like to thank very much Peter M. Gruber, Jaroslav Nesetril and Ivan Netuka for all their help and information regarding the history of the Löwner–John ellipsoids. For many helpful comments on earlier drafts I want to thank Matthias Henze, María Hernández Cifre, Eva Linke and Carsten Thiel.

References

[1] O.B. Ader. An affine invariant of convex bodies. Duke Math. J., 4(2):291– 299, 1938.

[2] K. Ball. Volume ratios and a reverse isoperimetric inequality. J. London Math. Soc. (2), 44(2):351–359, 1991.

[3] K. Ball. Ellipsoids of maximal volume in convex bodies. Geom. Dedicata, 41:241–250, 1992.

[4] K. Ball. An Elementary Introduction to Modern Convex Geometry. Cambridge University Press. Math. Sci. Res. Inst. Publ., 31:1–58, 1997.

[5] A. Barvinok. A course in convexity, volume 54 of Graduate Studies in Mathematics. AMS, 2002.

[6] A. Barvinok. Approximating a norm by a polynomial. GAFA seminar notes (Springer Lect. Notes Math.), 1807:20–26, 2003.

[7] F. Behrend. Über einige Affininvarianten konvexer Bereiche. Math. Annalen, 113:713–747, 1937.

[8] F. Behrend. Über die kleinste umbeschriebene und die größte einbeschriebene Ellipse eines konvexen Bereichs. Math. Annalen, 115(1):379– 411, 1938.

[9] M. Berger. Geometry Revealed. Springer book, pages 1–840, 2010.

[10] R. E. Bixby A Brief History of Linear and Mixed-Integer Programming Computation, this volume.

[11] H. Busemann. The Foundations of Minkowskian Geometry. Comment. Math. Helv., 24:156–187, 1950.

[12] H. Busemann. The geometry of geodesics. Academic Press Inc., New York, N. Y., 1955.

[13] R.W. Cottle William Karush and the KKT theorem, this volume.

[14] L. Danzer, D. Laugwitz, and H. Lenz. Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden. Arch. Math., 8:214–219, 1957.

[15] T. Figiel, J. Lindenstrauss, and V.D. Milman. The dimension of almost spherical sections of convex bodies. Acta Mathematica, 139:53–94, 1977.

[16] R. Finn. Nachlass von Charles Loewner. DMV Mitteilungen, 17(1):58, 2009.

[17] R.J. Gardner. The Brunn-Minkowski inequality. Bull. Am. Math. Soc., New Ser., 39(3):355–405, 2002.

[18] A. Giannopoulos, I. Perissinaki, and A. Tsolomitis. John’s theorem for an arbitrary pair of convex bodies. Geom. Dedicata, 84(1-3):63–79, 2001.

[19] A. Giannopoulos and V.D. Milman. Euclidean structure in finite dimensional normed spaces. In Handbook of the Geometry of Banach Spaces, pages 709–777. North-Holland, 2001.

[20] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics. Springer, 2nd edition, 1993.

[21] P.M. Gruber and F.E. Schuster. An arithmetic proof of John’s ellipsoid theorem. Arch. Math., 85:82–88, 2005.

[22] P.M. Gruber. Minimal ellipsoids and their duals Rend. Circ. Mat. Palermo (2), 37(1):35–64, 1988.

[23] P.M. Gruber. Application of an idea of Voronoi to John type poblems. Adv. Math., 218(2):309–351, 2008.

[24] P.M. Gruber. John and Loewner Ellipsoids. Discrete Comp. Geom., 46(4):776–788, 2011.

[25] S. Hildebrandt. Remarks on the life and work of Fritz John. Commun. Pure Appl. Math., 51(9-10):971–989, 1998.

[26] F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays presented to R. Courant on his 60th Birthday, pages 187–204. Interscience Publishers, 1948.

[27] F. John. Collected Papers. Volumes 1,2. Birkhäuser, 1985.

[28] D.B. Judin and A.S. Nemirovskiĭ. Estimation of the informational complexity of mathematical programming problems. Èkonom. i Mat. Metody, 12(1):128–142, 1976.

[29] F. Juhnke. Embedded maximal ellipsoids and semi-infinite optimization. Beitr. Algebra Geom., 35:163–171, 1994.

[30] H. W. Kuhn. Nonlinear Programming: A Historical Note. In History of mathematical programming, pages 82–96. North-Holland, 1991.

[31] M. Lassak. Approximation of Convex Bodies by Centrally Symmetric Bodies. Geom. Dedicata, 72:1–6, 1998.

[32] J. B. Lasserre. Level sets and non Gaussian integrals of positively homogeneous functions. arXiv:1110.6632v3, 2011.

[33] K. Leichtweiss. Über die affine Exzentrizität konvexer Körper. Arch. Math., 10:187–198, 1958.

[34] H.W. Lenstra, jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538–548, 1983.

[35] Ch.Loewner. Collected papers. Birkhäuser, 1988.

[36] J. Moser. Obituaries – Fritz John. Notices of the AMS, 42(2):256–257, 1995.

[37] I. Netuka. Charles Loewner and the Löwner ellipsoid. Pokroky Mat. Fyz. Astronom. (Czech), 38(4):212–218, 1993.

[38] A. Pełczyński. Remarks on John’s theorem on the ellipsoid of maximal volume inscribed into a convex symmetric body in R^{n}. Note di Matematica, 10(suppl. 2):395–410, 1990.

[39] M. Pinl. Kollegen in einer dunklen Zeit. Jber. Deutsch. Math.-Verein, 72:176, 1970.

[40] M. Pinl. Kollegen in einer dunklen Zeit. Schluss. Jber. Deutsch. Math.- Verein, 75:166–208, 1973.

[41] R. Sanyal, A. Werner, and G.M. Ziegler. On Kalai’s Conjectures Concerning Centrally Symmetric Polytopes. Discrete Comp. Geom., 41(2):183– 198, 2008.

[42] D. Shanno Who invented the interior-point method?, this volume.

[43] N.Z. Šhor. Use of the space expansion operation in problems of convex function minimalization, Kibernetika,1:6–12, 1970.

[44] M.J. Todd and E.A. Yildirim. On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids. Discrete Appl. Math., 155(13):1731–1744, 2007.

[45] V.L. Zaguskin. Circumscribed and inscribed ellipsoids of extremal volume. Usp. Mat. Nauk, 13(6 (84)):89–93, 1958.

Martin Henk

Fakultät für Mathematik Otto-von-Guericke-Universität Magdeburg Universitätsplatz 2 39106 Magdeburg Germany

                       martin.henk@ovgu.de