Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 2, 163-171.

Embedded Maximal Ellipsoids and Semi-Infinite Optimization

Friedrich Juhnke

Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg Postfach 4120, 39016 Magdeburg friedrich.juhnke@mathematik.uni-magdeburg.d400.de

Abstract. The ellipsoid of maximal volume contained in a given convex body K ⊆ R^{n} will be described as solution of a nonlinear semi-infinite optimization problem using the Minkowski support function. The corresponding necessary optimality conditions of the John-Kuhn/Tucker-type turn out to be sufficient ones too. Using these conditions only we show the uniqueness of the maximal ellipsoid. The maximal ellipsoid of K also proves to be the maximal ellipsoid of the intersection of at most n(n + 3)/2 supporting halfspaces of K. Furthermore it will be shown that the uniqueness of the maximal ellipsoid turns out to be a consequence of certain generalized convexity properties of the optimization problem investigated.

1. Introduction

Let K be an arbitrarily given convex body (convex compact set with non-empty interior) of the n-dimensional euclidean vector space R^{n}. We shall consider the ellipsoid of maximal volume contained in K. The existence of such a maximal ellipsoid follows by continuity and compactness reasons. The uniqueness of it was first proved by Danzer, Laugwitz, Lenz [2] using geometrical means. A further uniqueness proof was recently given in [1], where John’s optimality conditions are used in connection with geometrical details (principal axes).

In this paper we are concerned with the maximal ellipsoid as the solution of a certain semi-infinite optimization problem. The optimization model used by John [4] to describe (minimal) covering ellipsoids cannot immediately be transferred to the case of (maximal) inscribed ones. Therefore we choose here another way to state the required set inclusions by using the Minkowski support function. We give corresponding necessary optimality conditions and shall prove their sufficiency. Furtheron we shall show that the uniqueness of the maximal ellipsoid is a consequence of the derived optimality conditions only. The maximal ellipsoid of K turns out to be automatically the maximal ellipsoid of a certain

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

convex (and compact) polyhedron given as the intersection of at most n(n+3)/2 supporting half-spaces of K.

Finally we shall give a proof of the uniqueness of the maximal ellipsoid based on generalized convexity properties of the corresponding optimization problem.

2. Necessary and sufficient optimality conditions

Let K ⊆ R^{n} be a given convex body with the corresponding support function

k(u) := sup_{t∈K} u^{T} t, u ∈ R^{n}.

The ellipsoid E = E(C, x) := {t ∈ R^{n} | (t − x)^{T} C(t − x) ≤ 1} ⊆ R^{n} with center x = (x_{1},…, x_{n})^{T} ∈ R^{n} and C = (c_{ik})_{n,n} ∈ P_{n} has the support function

h(u) := sup_{t∈E} u^{T} t = u^{T} x + \sqrt{u^{T} Xu}, u ∈ R^{n},

where X = (x_{ik})_{n,n} := C^{−1} ∈ P_{n}. In what follows P_{n} denotes the set of all positively definite real symmetric (n, n)-matrices. The volume of E(C, x) is given by

V (E) = \frac{ω_{n}}{\sqrt{detC}} = ω_{n}\sqrt{detX},

where ω_{n} := π^{n/2}/Γ(\frac{n}{2} + 1) denotes the volume of the unit ball

B := {t ∈ R^{n} | ∥t∥ ≤ 1}.

Among all ellipsoids E embedded in K we look for that one with maximal volume. This problem

max{V (E) | E = E(C, x) ⊆ K}

is equivalent to

EP : \{ \begin{matrix}max\{f(X, x) = detX | (X, x) ∈ M\} \\ M := \{(X, x) | X ∈ P_{n}, x ∈ R^{n}, ∀u ∈ ∂B : u^{T} x + \sqrt{u^{T} Xu} ≤ k(u)\}, \end{matrix}  (1)

since the inclusion E ⊆ K is fulfilled iff h(u) ≤ k(u) holds for every u ∈ R^{n}. (The support functions are positively homogeneous ones, therefore the argument u can be restricted to the boundary ∂B of the unit ball.) (1) is a semi-infinite optimization problem with the m := n(n+3)/2 variables x_{i} and x_{ik}, i, k = 1,…, n, i ≤ k. In what follows the pair (X, x) ∈ M will be regarded both as point ξ = (x_{11},…, x_{1n}, x_{22},…, x_{2n},…, x_{nn}, x_{1},…, x_{n}) ∈ R^{m}, and as ellipsoid E(X^{−1}, x) ⊆ R^{n}.

Let (X^{0}, x^{0}) be an optimal solution of the embedding problem EP. Then according to John [4] there exist directions u^{1},…, u^{r} ∈ ∂B, 0 ≤ r ≤ n(n + 3)/2, which correspond to active restrictions of M, and nonnegative multipliers

(λ_{0},…, λ_{r}) ≠ (0,…, 0); λ_{0} ≥ 0, λ_{1} > 0,…, λ_{r} > 0

in such a way that the gradient of the Lagrangian function

L(X, x, λ) := λ_{0}(−f(X, x)) + ∑_{j=1}^{r} λ_{j}[u^{j}^{T} x + \sqrt{u^{j}^{T} Xu^{j}} − k(u^{j})]

vanishes at the point (X^{0}, x^{0}). This leads to the following

Theorem 1. If E_{0} = E(X^{0}^{−1}, x^{0}) is the maximal ellipsoid of the convex body K ⊆ R^{n}, then there exist vectors

u^{1},…, u^{r} ∈ ∂B, 0 ≤ r ≤ \frac{n(n + 3)}{2},  (2)

and scalars

λ^{T} = (λ_{0}, λ_{1},…, λ_{r}) ≠ (0,…, 0); λ_{0} ≥ 0, λ_{1} > 0,…, λ_{r} > 0  (3)

such that

u^{j}^{T} x^{0} + \sqrt{u^{j}^{T} X^{0}u^{j}} = k(u^{j}), j = 1,…, r  (4)
∑_{j=1}^{r} λ_{j}u^{j} = 0  (5)

(2λ_{0}detX^{0})I = ∑_{j=1}^{r} λ_{j} \frac{X^{0}u^{j}u^{j}^{T}}{\sqrt{u^{j}^{T} X^{0}u^{j}}}  (6)

(I denotes the (n, n)-unit matrix).

The hyperplane

H_{j} := {t ∈ R^{n} | u^{j}^{T} t = h(u^{j})}, j = 1,…, r

supports both the ellipsoid E_{0} and the convex body K due to (4).

y_{j} = x^{0} + \frac{X^{0}u^{j}}{\sqrt{u^{j}^{T} X^{0}u^{j}}} ∈ ∂E_{0} ∩ ∂K  (7)

is the unique supporting point of H_{j} with respect to E_{0}. (In addition to y^{j} there may exist also other supporting points of H_{j} with respect to K.) In what follows, these points y^{1},…, y^{r} are referred to as characteristic boundary points of K, analogously we denote u^{1},…, u^{r} as characteristic directions and HR_{1},…, HR_{r} as characteristic supporting halfspaces of K,

HR_{j} := {t ∈ R^{n}|u^{j}^{T} t ≤ h(u^{j})}, j = 1,…, r.

P := ⋂_{j=1}^{r} HR_{j} is referred to as characteristic supporting polyhedron of K. The center

x^{0} of the maximal ellipsoid lies in the convex hull conv{y^{1},…, y^{r}} of the characteristic boundary points since

∑_{j=1}^{r} λ_{j}\sqrt{u^{j}^{T} X^{0}u^{j}}y^{j} = (∑_{j=1}^{r} λ_{j}\sqrt{u^{j}^{T} X^{0}u^{j}})x^{0}  (8)

on account to (5), (7). The optimality conditions (2,…,6) imply r > 1: If r = 0 then λ_{0} > 0 according to (3) and therefore detX^{0} = 0 from (6) contrary to X^{0} ∈ P_{n}. The case r = 1 would lead to y^{1} = x^{0} from (8) contrary to (7). Setting up the trace of the matrices in (6) we get

2nλ_{0}detX^{0} = ∑_{j=1}^{r} λ_{j}\sqrt{u^{j}^{T} X^{0}u^{j}}  (9)

and hence λ_{0} > 0 is always fulfilled. The conditions (2,…,6) therefore turn out to be automatically Kuhn-Tucker-type conditions, without examination of any constraint qualification of (1).

Theorem 2.

a) The maximal ellipsoid of the convex body K ⊆ R^{n} is also the maximal ellipsoid of the characteristic supporting polyhedron

P = {t ∈ R^{n} | u^{j}^{T} t ≤ h(u^{j}), j = 1,…, r} ⊇ K

and n + 1 ≤ r ≤ n(n + 3)/2 holds.

b) The maximal ellipsoid of K is unique.

c) The necessary optimality conditions (2,…,6) are also sufficient ones: E(X^{0}^{−1}, x^{0}) is maximal ellipsoid of K iff E(X^{0}^{−1}, x^{0}) ⊆ K and (2,…,6) are fulfilled.

Proof. We can assume the maximal ellipsoid to be the unit ball after a suitable affine transformation , X^{0} = I, x^{0} = 0, E(X^{0}^{−1}, x^{0}) = B. Then the characteristic directions and the characteristic boundary points coincide, y^{j} = u^{j} ∈ ∂B, j = 1,…, r. The optimality conditions (4,5,6) and (9) become

k(u^{j}) = 1; j = 1,…, r  (4′)
∑_{j=1}^{r} λ_{j}u^{j} = 0  (5′)

2λ_{0}I = ∑_{j=1}^{r} λ_{j}u^{j}u^{j}^{T}  (6′)

and

2nλ_{0} = ∑_{j=1}^{r} λ_{j}.  (9′)

Furtheron in what follows we need the fact: The trace of an arbitrarily chosen (n, n)-matrix A = (a_{ik}) can be expressed by using the optimality conditions in the form

∑_{i=1}^{n} a_{ii} = \frac{1}{2λ_{0}} ∑_{j=1}^{r} λ_{j}u^{j}^{T} Au^{j}  (10)

since

∑_{j=1}^{r} λ_{j}u^{j}^{T} Au^{j} = ∑_{i,k=1}^{n} a_{ik} ∑_{j=1}^{r} λ_{j}u_{i}^{j}u_{k}^{j} = 2λ_{0} ∑_{i,k=1}^{n} a_{ik}δ_{ik} = 2λ_{0} ∑_{i=1}^{n} a_{ii}

with the Kronecker δ_{ik} according to (6’).

(a) Let E = E(X^{−1}, x) ⊆ P = {t ∈ R^{n} | u^{j}t ≤ 1, j = 1,…, r} be any ellipsoid embedded in the characteristic supporting polyhedron P. The support function h_{E} of E satisfies

h_{E}(u^{j}) = u^{j}^{T} x + \sqrt{u^{j}^{T} Xu^{j}} ≤ 1, j = 1,…, r  (11)

which involves

∑_{j=1}^{r} λ_{j}\sqrt{u^{j}^{T} Xu^{j}} ≤ ∑_{j=1}^{r} λ_{j} = 2λ_{0}n  (12)

due to (5) and (9’). To X ∈ P_{n} there exists a uniquely determined R = (r_{ik})_{n,n} ∈ P_{n} with X = RR (cf. remark before Lemma 1). Using this we obtain

(detR)^{1/n} ≤ \frac{1}{n} ∑_{i=1}^{n} r_{ii}  (13)

= \frac{1}{2λ_{0}n} ∑_{j=1}^{r} λ_{j}u^{j}^{T} Ru^{j}

≤ \frac{1}{2λ_{0}n} ∑_{j=1}^{r} λ_{j}∥u^{j}^{T} ∥ ∥Ru^{j}∥  (14)

= \frac{1}{2λ_{0}n} ∑_{j=1}^{r} λ_{j}\sqrt{u^{j}^{T} Xu^{j}}

≤ 1  (15)

on account of (10),(12) and the arithmetic-geometric-mean-inequality (applied to the eigenvalues of R whose product equals detR and whose sum equals the trace of R). This results in

V (E) = ω_{n}\sqrt{detX} = ω_{n}detR ≤ ω_{n} = V (E_{0})  (16)

which shows that E_{0} has the greatest volume among all ellipsoids E inscribed in P. Assuming r ≤ n we can find a vector v ∈ R^{n}, v ≠ 0, with

u^{j}^{T} v = 0, j = 1,…, r

since the characteristic directions are linearely dependent in view of (5). Therefore the convex set P is unbounded, P is a polyhedral cylinder with the recession direction v ≠ 0 and contains ellipsoids with arbitrarily great volume in contradiction to (16). Hence r ≥ n + 1 is fulfilled.

(b) Suppose there exists a further maximal ellipsoid E_{1}(X^{1}^{−1}, x^{1}) besides E_{0}. Then (11), (12) hold for (X, x) = (X^{1}, x^{1}) and (13,14,15,16) are fulfilled as equalities for X^{1} = R^{1}R^{1}. The equality (13) shows that all eigenvalues of R^{1} coincide; due to (16) they are equal to 1 such that R^{1} = I and X^{1} = I = X^{0}.

From (11) and (5’) we get

u^{j}^{T} x^{1} = 0, j = 1,…, r

and with (6’)

x^{1} = \frac{1}{2λ_{0}} ∑_{j=1}^{r} λ_{j}u^{j}u^{j}^{T} x^{1} = 0

such that in all (X^{1}, x^{1}) = (X^{0}, x^{0}).

(c) Let E_{0} = E(X^{0}^{−1}, x^{0}) be an ellipsoid embedded in K with the properties (2,…,6) respective (4’, 6’) (after a suitable affine transformation such that (X^{0}, x^{0}) = (I, 0)). Suppose E(X^{−1}, x) ⊆ K. Then the inequalities (11),(12) hold and, using the conditions (2,…,6) only, the relations (13,14,15) are fulfilled, which shows V (E) ≤ V (E_{0}). Thus E_{0} is the maximal ellipsoid of K.

3. A uniqueness proof based on generalized convexity

In general the corresponding feasible region of EP is not convex, regarded as point set of R^{m}, m = n(n+3)/2. Methods of convex analysis which are based on straight line segments therefore are of no help for the investigation of M. In what follows we will use generalized convexity (polynomial connecting curves) as indicator of uniqueness.

There exists a regular affine map for two given points (A, a), (B, b) ∈ P_{n} × R^{n}, which transforms simultaneously the two corresponding ellipsoids into diagonal form, i.e. a regular (n, n)-matrix H exists with

H^{T} AH = diag(α_{1}^{2},…, α_{n}^{2}) = D_{A}D_{A}  (17)

and

H^{T} BH = diag(β_{1}^{2},…, β_{n}^{2}) = D_{B}D_{B},  (18)

where

α_{i}, β_{i} > 0, i = 1,…, n, D_{A} := diag(α_{1},…, α_{n}), D_{B} := diag(β_{1},…, β_{n}).  (19)

With

R = R(λ) := (1 − λ)D_{A}H^{−1} + λD_{B}H^{−1}, 0 ≤ λ ≤ 1,

we have the positive definite matrix

X = X(λ) := R(λ)^{T} R(λ)
= (1 − λ)^{2}A + λ^{2}B + 2λ(1 − λ)H^{−1}^{T} D_{A}D_{B}H^{−1},  (20)

which does not depend on the special choice of the transformation matrix H since

G := H^{−1}^{T} D_{A}D_{B}H^{−1}  (21)

doesn’t: Let H_{1}, H_{2} be two regular (n, n)-matrices with the properties (17),(18) and (19); let G_{1}, G_{2} be the corresponding matrices according to (21). Then B = G_{1}A^{−1}G_{1} = G_{2}A^{−1}G_{2} holds and similar simultaneous transformations as (17), (18) applied to G_{1}^{−1}, G_{2}^{−1} verify G_{1} = G_{2}. (Remark: In the special case A = I this leads to the well known fact that for each B ∈ P_{n} there exists a uniquely determined square root G ∈ P_{n} with GG = B.)

By setting x(λ) := (1 − λ)a + λb a continuous (quadratic) curve

{ξ(λ) := (X(λ), x(λ)) | 0 ≤ λ ≤ 1}  (22)

is defined that connects any two points (A, a), (B, b) ∈ P_{n} × R^{n} and is contained in P_{n} × R^{n}. This curve has the following properties:

Lemma 1. Let (A, a), (B, b) ∈ M, (A, a) ≠ (B, b). Then {ξ(λ) := (X(λ), x(λ)) | 0 ≤ λ ≤ 1} ∈ P_{n} × R^{n} is a segment of a continuous curve without double points that connects the points (A, a) and (B, b) and is completely contained in the feasible region M. For A ≠ B and 0 < λ < 1 the objective function f of the embedding problem EP fulfills the inequality

f(X(λ), x(λ)) > (f(A, a))^{1−λ}(f(B, b))^{λ} ≥ min{f(A, a), f(B, b)}  (23)

i.e. with respect to the curve segment (22) the function f is strongly quasi concave in X and the logarithm ln f is strongly concave in X.

Proof: The components of ξ(λ) are quadratic respecitve linear functions of λ and thus continuous everywhere. We have {(X(λ), x(λ) | 0 ≤ λ ≤ 1} ⊆ M since X(λ) ∈ P_{n} and

u^{T} x(λ) + \sqrt{u^{T} X(λ)u} = u^{T} ((1 − λ)a + λb) + ∥R(λ)u∥
≤ u^{T} ((1 − λ)a + λb) + (1 − λ)∥D_{A}H^{−1}u∥ + λ∥D_{B}H^{−1}u∥
= (1 − λ)(u^{T} a + \sqrt{u^{T} Au}) + λ(u^{T} b + \sqrt{u^{T} Bu})
≤ k(u)

for every u ∈ R^{n}, λ ∈ [0, 1].

The assumption (X(λ_{1}), x(λ_{1})) = (X(λ_{2}), x(λ_{2})), λ_{1}, λ_{2} ∈ [0, 1], leads easily to λ_{1} = λ_{2}. Let A ≠ B and 0 < λ < 1. Per definition of X(λ) we have

f(X(λ), x(λ)) = det(H^{−1}^{T} ((1 − λ)D_{A} + λD_{B})^{2}H^{−1})

= (det H^{−1})^{2} ∏_{i=1}^{n}((1 − λ)α_{i} + λβ_{i})^{2}

> (det H^{−1})^{2} ∏_{i=1}^{n}(α_{i}^{1−λ}β_{i}^{λ})^{2}  (24)

= (det H^{−1})^{2}(det D_{A})^{2(1−λ)}(det D_{B})^{2λ}

= (f(A, a))^{1−λ}(f(B, b))^{λ} ≥ min{f(A, a), f(B, b)}.

The strict estimation of (24) results from

∀u, v > 0, ∀λ ∈ (0, 1) : (1 − λ)u + λv > u^{1−λ}v^{λ}

by virtue of (α_{1},…, α_{n}) ≠ (β_{1},…, β_{n}).

The concavity property given in Lemma 1 shows the unique solvability of EP: Suppose (A, a) and (B, b) are optimal solutions of EP. Then A = B holds necessarily because otherwise every inner point of the connected curve (22) between (A, a) and (B, b) would correspond to an ellipsoid of larger volume contained in K according to (23). We choose an affine system of co-ordinates in such a way that A = B = I and a = 0, b = (2d, 0,…, 0)^{T}, where d ≥ 0. Then k(u) ≥ 1 and k(u) ≥ 2du_{1} + 1 hold for every u ∈ R^{n} due to (I, 0), (I, b) ⊆ M; thus the support function k of K fulfills

∀u ∈ ∂B : k(u) ≥ \{ \begin{matrix}1 & for u_{1} ≤ 0 \\ 2du_{1} + 1 & for u_{1} ≥ 0. \end{matrix}  (25)

Let Y (λ) := diag((1 + λd)^{2}, 1,…, 1) ∈ P_{n}, y(λ) := (λd, 0,…, 0) ∈ R^{n}. According to (25) we obtain

u^{T} y(λ) + \sqrt{u^{T} Y (λ)u} = λdu_{1} + \sqrt{1 + 2λdu_{1}^{2} + λ^{2}d^{2}u_{1}^{2}}
≤ λdu_{1} + 1 + λd|u_{1}|
≤ 1 + d(u_{1} + |u_{1}|)
≤ k(u)

for all u ∈ ∂B and all λ ∈ (0, 1) therefore (Y (λ), y(λ)) ∈ M. (The ellipsoid belonging to (Y (λ), y(λ)) is contained in the convex hull of the ellipsoids (A, a) and (B, b).) From the optimality of (A, a) we get ∀λ ∈ [0, 1] : f(Y (λ), y(λ)) = det Y (λ) = (1+λd)^{2} ≤ f(A, a) = 1 for the feasible point (Y (λ), y(λ)), such that d = 0 and (A, a) = (B, b), which proves the uniqueness of the solution of the optimization problem (EP).

References.

[1] Ball,K.: Ellipsoids of maximal volume in convex bodies, Geometriae Dedicata 41 (1992), 241-250.

[2] Danzer, L.; Laugwitz, D.; Lenz, H.: Über das Löwnersche Ellipsoid und sein Analogon unter dem einem Eikörper einbeschriebenen Ellipsoiden, Arch. Math. 8 (1957), 214-219.

[3] Gruber, P.: Minimal ellipsoids and their duals, Rendiconti del Circolo Matematico di Palermo, Serie II, Tomo XXXVII (1988), 35-64.

[4] John,F.: Extremum problems with inequalities as subsidiary conditions, Studies and essays. Courant anniversary volume, Interscience Publ. Inc., New York 1948, 187-204.

[5] Juhnke, F.: Volumenminimale Ellipsoidüberdeckungen, Beitr z. Alg. u. Geom. 30 (1990), 143-153.

[6] Juhnke, F.: Extremal circumscribed ellipsoids and generalized convexity, Approximation & Optimization, ed. Guddat, Jongen, Kummer, Nožička, Verlag Peter Lang, Frankfurt a. M. 1993, 323-340.

Received, November 29, 1993; revised version, April, 1994.