Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 36 (1995), No. 1, 17-24.

Polarity of Embedded and Circumscribed Ellipsoids

Friedrich Juhnke^{1}

Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg Postfach 4120, D-39016 Magdeburg, Germany Friedrich.Juhnke@Mathematik.Uni-Magdeburg.D400.DE

Abstract. In this paper we investigate simultaneously the minimal circumscribed and the maximal inscribed ellipsoid of an n−dimensional convex body by means of optimization techniques. This approach presents necessary and sufficient optimality conditions and allows to establish polarity relations between these two extremal ellipsoids.

1. Introduction

We consider a nonempty compact set K of the n−dimensional Euclidean vectorspace R^{n}, the convex hull of which is a convex body ( int convK ≠ ∅), and ellipsoids E = E(C, x) := {t ∈ R^{n}| (t − x)^{T} C(t − x) ≤ 1} with center x = (x_{1}, …, x_{n})^{T} and C ∈ P_{n} := {P | P positive definite real symmetric (n, n)−matrix }. The volume of E(C, x) is given by V (E) = ω_{n}/\sqrt{detC}, where ω_{n} := π^{\frac{n}{2}} /Γ(\frac{n}{2} + 1) denotes the volume of the Euclidean unit ball B := {t ∈ R^{n}| ∥t∥ ≤ 1}.

Let

k(u) = sup_{t∈convK} u^{T} t and h(u) = sup_{t∈E(C,x)} u^{T} t = u^{T} x + \sqrt{u^{T} C^{−1}u}

be the corresponding support functions of convK and E respectively, u ∈ R^{n}.

The covering E(C, x) ⊇ K ( or the embedding E(C, x) ⊆ convK respectively) is fulfilled if and only if the inequality h(u) ≥ k(u) ( or h(u) ≤ k(u) respectively) holds for all u ∈ R^{n}. In what follows we investigate relationships between the optimal solutions of these two problems:

Covering Problem (UP): Among all ellipsoids covering K determine that one with minimal volume (Loewner-ellipsoid, minimal ellipsoid ).

1 The results of this paper are part of the author’s habilitation thesis at the Technical University of Magdeburg.

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

Embedding problem (EP): Among all ellipsoids contained in convK is to be found the one with maximal volume (maximal ellipsoid ).

These two problems can be formulated as semi-infinite optimization problems:

min{F (X, x) := detX| (X, x) ∈ UM} (UP) :

UM := \{(X, x)| X ∈ P_{n}, x ∈ R^{n}, ∀u ∈ ∂B : u^{T} x + \sqrt{u^{T} Xu} ≥ k(u)\},

min{f(X, x) := −detX| (X, x) ∈ EM} (EP) :

EM := \{(X, x)| X ∈ P_{n}, x ∈ R^{n}, ∀u ∈ ∂B : u^{T} x + \sqrt{u^{T} Xu} ≤ k(u)\},

where X = (x_{ik})_{n,n} := C^{−1} ∈ P_{n} and ∂B = \{u ∈ R^{n}| ∥u∥ = \sqrt{u^{T} u} = 1\}. The existence of both the minimal and the maximal ellipsoid follows from continuity and compactness reasons, the uniqueness was first proved (geometrically) in [2]. We will regard feasible solutions (X, x) of UM and EM respectively both as points

ξ = (x_{11}, …, x_{1n}, x_{22}, …, x_{2n}, …, x_{nn}, x_{1}, …, x_{n}) ∈ R^{m}

with m = n(n + 3)/2 and as ellipsoids E(X^{−1}, x) ⊆ R^{n}.

Let u ∈ ∂B be a direction which corresponds to an active restriction

u^{T} x + \sqrt{u^{T} Xu} = k(u)

for a given (X, x) ∈ UM or (X, x) ∈ EM respectively. Then u determines a supporting hyperplane

H = H(u) := {t ∈ R^{n}| u^{T} t = h(u) = k(u)}  (1)

of both the ellipsoid E(X^{−1}, x) and the convex body convK. The supporting point of H with respect to E(X^{−1}, x) is (uniquely) given by

y = y(X, x, u) := x + \frac{Xu}{\sqrt{u^{T} Xu}} ∈ ∂E(X^{−1}, x) ∩ convK.  (2)

In the case (X, x) ∈ UM we have not only y ∈ convK but even y ∈ K and there are no other supporting points of H with respect to convK: Any supporting point p ∈ H ∩convK is also a supporting point of H with respect to E(X^{−1}, x) due to K ⊆ E, hence p = y and y ∉ K would imply y = ∑_{i=1}^{N} α_{i}a^{i} ∈ convK, a^{i} ∈ K, 0 < α_{i} < 1, ∑_{i=1}^{N} α_{i} = 1 and u^{T} a^{i} < k(u) due to H ∩ convK = {y}, thus u^{T} y = ∑_{i=1}^{N} α_{i}u^{T} a^{i} < k(u) in contradiction to y ∈ H. ( In the case of (X, x) ∈ EM, there may also exist supporting points of H other than y with respect to convK ). — In what follows we obtain polarity relations between the minimal and the maximal ellipsoid only using optimality conditions of (UP) and (EP). (Concerning other approaches without optimization techniques cf. [1])

2. Optimality conditions and polarity

General necessary optimality conditions for such types of optimization problems as (UP), (EP) are given by John [4] in the following form: Let (X^{∗}, x^{∗}) be an optimal solution of (UP) or (EP) respectively. Then there exist directions u^{1}, …, u^{r} ∈ ∂B which correspond to active restrictions of UM or EM respectively, and multipliers

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

where 0 ≤ r ≤ \frac{n(n+3)}{2}, in such a way that the Lagrangian function built with these restrictions,

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

or

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

respectively, is stationary at the point (X, x) = (X^{∗}, x^{∗}). In what follows these vectors u^{1}, …, u^{r} are referred to as characteristic directions; the corresponding y^{j} := y(X^{∗}, x^{∗}, u^{j}) and H_{j} := H(u^{j}) according to (1),(2) are referred to as characteristic supporting points and characteristic supporting hyperplanes respectively, j = 1, …, r. HR_{j} := {t ∈ R^{n}|u^{j}^{T} t ≤ k(u^{j})} denotes the corresponding characteristic supporting halfspace containing K, j = 1, …, r.

Additionally, these conditions turn out to be sufficient ones and they are conditions of the Kuhn-Tucker-type, i.e. the multiplier λ_{0} of the objective function does not vanish. Further the uniqueness of the optimal ellipsoids is a consequence of these conditions. In detail we obtain the following results:

Theorem 1:

(a) E(X^{0}^{−1}, x^{0}) is a minimal ellipsoid of the set K ⊆ R^{n} iff E(X^{0}^{−1}, x^{0}) ⊇ K and the following conditions are fulfilled: There exist vectors u^{1}, …, u^{r} ∈ ∂B and scalars λ_{0}, …, λ_{r} ∈ R with

n + 1 ≤ r ≤ \frac{n(n + 3)}{2}  (5)
λ_{0} > 0, …, λ_{r} > 0  (6)

such that

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

(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}}}  (9)

(b) The minimal ellipsoid of K is unique.

(c) The minimal ellipsoid E(X^{0}^{−1}, x^{0}) of K is also the minimal ellipsoid of the finite set {y^{1}, ⋯, y^{r}} of the characteristic supporting points

y^{j} := x^{0} + \frac{X^{0}u^{j}}{\sqrt{u^{j}^{T} X^{0}u^{j}}} , j = 1, …, r.

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

Proof: Let (X^{0}, x^{0}) be an optimal solution of (UP). Then according to [4] there exist u^{j} ∈ ∂B and λ_{0}, λ_{j} ∈ R, j = 1, …, r, such that the necessary optimality conditions (7),(8),(9) are fulfilled, in the first instance with

(λ_{0}, …, λ_{r}) ≠ (0, …, 0), λ_{0} ≥ 0, λ_{1} > 0, …, λ_{r} > 0 and 0 ≤ r ≤ \frac{n(n + 3)}{2}.  (10)

(8) and (9) are the stationary conditions for the Lagrangian function UL(X, x, λ) in (X^{0}, x^{0}) according to

\frac{∂UL}{∂x_{ik}} = \{ \begin{matrix}λ_{0}X_{ii} − \frac{1}{2} ∑_{j=1}^{r} λ_{j} \begin{matrix}(u_{i}^{j}) & 2 \\ √ & \overline{u^{j}^{T} Xu^{j}} \end{matrix} , & i = k \\ 2λ_{0}X_{ik} − ∑_{j=1}^{r} λ_{j} \frac{u_{i}^{j}u_{k}^{j}}{\sqrt{u^{j}^{T} Xu^{j}}} , & i ≠ k \end{matrix}

(X_{ik} denotes the cofactor of x_{ik} in the matrix X); i, k = 1, …, n. From (9),(10) we get r > 0. Considering the traces in (9) we conclude

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

which shows λ_{0} > 0 (Kuhn-Tucker-type conditions) and thus (6) is confirmed.

A regular affine transformation has no effect on the optimization problem (UP) ( all volumes are simultaneously multiplied by a constant factor). Hence we can assume the minimal ellipsoid to be the unit ball, i.e. (X^{0}, x^{0}) = (I, 0). In this case we have y^{j} = u^{j}, j = 1, …, r; the optimality conditions (7) and (9) are simplified to k(u^{j}) = 1, j = 1, …, r, and

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

Let E = E(C, x) be any ellipsoid with y^{j} ∈ E(C, x), j = 1, …, r. Then we obtain

2nλ_{0} = ∑_{j=1}^{r} λ_{j} ≥ ∑_{j=1}^{r} λ_{j}(y^{j} − x)^{T} C(y^{j} − x)  (13)

= ∑_{j=1}^{r} λ_{j}u^{j}^{T} Cu^{j} + (∑_{j=1}^{r} λ_{j})x^{T} Cx

≥ ∑_{i=1}^{n} ∑_{k=1}^{n} c_{ik} ∑_{j=1}^{r} λ_{j}u_{i}^{j}u_{k}^{j}  (14)

= 2λ_{0} ∑_{i=1}^{n} c_{ii}

≥ 2λ_{0}n(detC)^{\frac{1}{n}}  (15)

from (11), (8) and (12). The last estimations result from the arithmetic-geometric-mean-inequality applied to the sum (trace of C) and the product (determinant of C) of the eigenvalues of C. (13),(14),(15) show

V (E) = \frac{ω_{n}}{\sqrt{detC}} ≥ ω_{n} = V (E_{0})  (16)

where E_{0} = E(I, 0), which proves the assertion (c). If r ≤ n, then all points y^{1}, …, y^{r} would lie in a certain hyperplane of R^{n} and could be covered by ellipsoids with arbitrarily small volumes; therefore dim aff{y^{1}, …, y^{r}} = n, thus r ≥ n + 1 so that (5) is confirmed.

To show the sufficiency of the conditions (5),…,(9), let E_{0} = E(X^{0}^{−1}, x^{0}) be any ellipsoid covering K and fulfilling (5),…,(9). After a suitable affine transformation we can assume (X^{0}, x^{0}) = (I, 0). Then by using the conditions (5),…,(9) only we obtain the inequalities (13),(14),(15) for each E = E(X^{−1}, x) ⊇ K; thus V (E) ≥ V (E_{0}) and E_{0} turns out to be the minimal ellipsoid.

To verify the uniqueness let E(X^{0}^{−1}, x^{0}) = E(I, 0) and E(C, x) be two minimal ellipsoids. Then the inequalities (16) and consequently also (13),(14),(15) hold with the equal sign. From (14) we obtain x^{T} Cx = 0, thus x = x^{0} = 0. (15) shows that all eigenvalues of C are identical with each other. Due to detC = 1 they all equal 1, thus C=I and E = E_{0}.

The two problems (UP) and (EP) have intentionally been designed as similar as possible, hoping to obtain common properties and connections between the two extremal ellipsoids. Particularily the two corresponding Lagrangian functions UL and EL coincide, with the exception of the sign, cf. (3),(4). Consequently the stationary conditions of these functions are exactly the same and we get results characterizing the maximal ellipsoid similar to those obtained for the minimal ellipsoid. They are summarized in the following theorem.

Theorem 2:

(a) E((X^{1})^{−1}, x^{1}) is a maximal ellipsoid of convK if and only if E((X^{1})^{−1}, x^{1}) ⊆ convK and there exist directions u^{1}, …, u^{r} ∈ ∂B and multipliers λ_{0}, …, λ_{r} ∈ R with

n + 1 ≤ r ≤ \frac{n(n + 3)}{2}  (17)
λ_{0} > 0, …, λ_{r} > 0  (18)

such that

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

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

(b) The maximal ellipsoid of convK is unique.

(c) The maximal ellipsoid of convK is also the maximal ellipsoid of the intersection

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

of the characteristic supporting halfspaces HR_{j}, j = 1, …, r.

A detailed proof of Theorem 2 is given in [6], where it is also shown that the polyhedron P is necessarily bounded and therefore a convex polytope.

The two theorems together allow to state the properties given in the following

Corollary:

(a) The maximal ellipsoid E_{1} = E(X^{1}^{−1}, x^{1}) with y^{1}, …, y^{r} ∈ ∂E_{1} ∩ convK as corresponding characteristic supporting points is automatically the minimal ellipsoid of the finite set {y^{1}, …, y^{r}}, thus of the polytope conv{y^{1}, …, y^{r}}.

(b) The minimal ellipsoid E_{0} = E(X^{0}^{−1}, x^{0}) of K with the corresponding characteristic supporting halfspaces HR_{1}, …, HR_{r} is automatically the maximal ellipsoid of the

polytope P = ⋂_{j=1}^{r} HR_{j}.

Proof: (a): According to equation (19), E_{1} covers the characteristic supporting points y^{j} = y(X^{1}, x^{1}, u^{j}), j = 1, …, r, cf. (2). The corresponding supporting normal vectors u^{1}, …, u^{r}, together with the multipliers λ_{0}, …, λ_{r} stated in Theorem 2, fulfil the conditions (5),…,(9) with (X, x) = (X^{1}, x^{1}), due to (17), …,(21). These conditions are sufficient for E_{1} to be the minimal ellipsoid of {y^{1}, …, y^{r}} according to Theorem 1.

(b): We have

E_{0} = E(X^{0}^{−1}, x^{0}) ⊆ ⋂_{j=1}^{r}{t ∈ R^{n}| u^{j}^{T} t ≤ h_{0}(u^{j})} = P

such that (X^{0}, x^{0}) is a feasible solution of the embedding problem (EP) with respect to the convex body P. (h_{0} denotes the support function of E(X^{0}^{−1}, x^{0}).) The conditions (5),…,(9) are fulfilled according to Theorem 1; with the same characteristic directions u^{1}, …, u^{r} and the same multipliers λ_{0}, …, λ_{r} these conditions coincide with (17),…,(21) of Theorem 2 which are sufficient to prove E_{0} to be the maximal ellipsoid of the polytope P.

The assertion of the corollary can be generalized to polarity properties in the following way: Let Q^{E} := {t ∈ R^{n}| ∀z ∈ Q : z^{T} Ct ≤ 1} denote the polar set of any set Q ⊆ R^{n} with respect to the ellipsoid E = E(C, 0). For convex sets Q, R ⊆ R^{n} we have the well known reciprocal inclusion Q ⊆ R ⟹ Q^{E} ⊇ R^{E} as well as

(Q ∪ R)^{E} = Q^{E} ∩ R^{E}, (Q ∩ R)^{E} = cl conv(Q^{E} ∪ R^{E}).  (22)

The polar set of a halfspace containing 0 turns out to be a closed segment with 0 as one of its endpoints and vice versa;

{z ∈ R^{n}| a^{T} z ≤ 1}^{E} = [0, C^{−1}a],  (23)
{p}^{E} = [0, p]^{E} = {t ∈ R^{n}| p^{T} Ct ≤ 1}.  (24)

— After a translation, if necessary, we can assume E_{1} = E(X^{1}^{−1}, 0) to be the maximal ellipsoid of convK. Let y^{11}, …, y^{1r_{1}} and HR_{1}^{1}, …, HR_{r_{1}}^{1} be the corresponding characteristic supporting points and characteristic supporting halfspaces respectively and P_{1} = ⋂_{j=1}^{r_{1}} HR_{j}^{1}. Due to (23),(24) we have {y^{1j}}^{E_{1}} = HR_{j}^{1}, (HR_{j}^{1})^{E_{1}} = [0, y^{1j}], j = 1, …, r_{1}, such that

P_{1}^{E_{1}} = conv{y^{11}, …, y^{1r_{1}}} ⊆ K^{E_{1}} ⊆ E_{1} ⊆ convK ⊆ P_{1}  (25)

(cf. (22)). The corollary (a) states that E_{1} is the minimal ellipsoid of P_{1}^{E_{1}}, thus also of K^{E_{1}} according to (25). Analogously, let E_{0} = E(X^{0}^{−1}, 0) be the minimal ellipsoid (after a suitable translation) of K with the corresponding characteristic supporting points y^{01}, …, y^{0r_{0}} and the characteristic supporting halfspaces HR_{1}^{0}, …, HR_{r_{0}}^{0} and P_{0} := ⋂_{j=1}^{r_{0}} HR_{j}^{0}. Then we obtain

{y^{01}, …, y^{0r_{0}}} ⊆ K ⊆ E_{0} ⊆ K^{E_{0}} ⊆ {y^{01}, …, y^{0r_{0}}}^{E} = P_{0}.

E_{0} is the maximal ellipsoid of P_{0} according to part (b) of our corollary and is contained in the polar set K^{E_{0}}, E_{0} thus turning out to be the maximal ellipsoid of K^{E_{0}} too.

Summarizing these results we obtain

Theorem 3: Let K ⊆ R^{n} be an arbitrarily chosen set with int convK ≠ ∅.

(a) The maximal ellipsoid E_{1} of convK is the minimal ellipsoid of the polar set K^{E_{1}} with respect to the polarization at E_{1}.

(b) The minimal ellipsoid E_{0} of K is the maximal ellipsoid of the polar set K^{E_{0}} with respect to the polarization at E_{0}.

References

[1] Bonan, E.: Comparaison d’un corps convexe avec ses deux ellipsoides optimaux, C.R. Acad. Sci. Paris, t. 315 (1992), Séries I, 557-560.

[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- [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.: Extremal circumscribed ellipsoids and generalized convexity, Approximation & Optimization, ed. Guddat, Jongen, Kummer, Nožička, Verlag Peter Lang, Frankfurt a. M. 1993, 323-340.

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

Received June 22, 1994.