Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 41 (2000), No. 1, 93-105.

Minimal Spherical Shells and Linear Semi-infinite Optimization

Friedrich Juhnke Olaf Sarges

Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg Postfach 4120, D-39016 Magdeburg, Germany e-mail: Juhnke@Mathematik.Uni-Magdeburg.de

Abstract. In this paper we prove some characterizing properties of the minimal shell of a convex body by means of linear semi-infinite optimization. Further we present a representation of the optimal solution of the corresponding optimization problem in dependence of the values of the support function of certain points of contact of the convex body and its minimal shell. MSC 1991: 52A40, 90C34 Keywords: linear semi-infinite optimization, minimal shell, convex bodies.

1. Introduction

Let B(x, r) be the closed n-dimensional ball with center x and radius r. K^{n} denotes the set of all convex bodies (i.e. convex compact sets with a nonempty interior) in ℝ^{n}. Let K ∈ K^{n}. For each x ∈ K there is a ball B(x, R(x)) of minimal volume containing K and a ball B(x, r(x)) of maximal volume, which is contained in K. The set B(x, R(x), r(x)) := B(x, R(x)) \ int B(x, r(x)) is referred to as the (closed) spherical shell of the convex body K with center x ∈ K. We look for a point x^{0} ∈ K for which the function R(x) − r(x) attains its minimum, i.e. the so-called minimal spherical shell (or shortly minimal shell) B(x^{0}, R(x^{0}), r(x^{0})) is a shell of K with minimal thickness. Characterizations of the minimal shell and the uniqueness of the center x^{0} were established by Bonnesen [2], Kritikos [6] and Bárány [1]. Generalizations to Minkowski spaces and to convex shells (shells bounded by two homothetic images of a fixed convex body) are investigated by Peri [7], [8]. Applications of spherical shells to improve a Blaschke’s inequality are given by Peri, Wills, Zucco [9].

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

Using tools and results of convex analysis, Bárány obtained the following characterization: The point x^{0} is the center of the minimal shell of K if and only if there are points p^{1}, ..., p^{k} ∈ ∂K supporting B(x^{0}, R(x^{0})) (i.e. ∥p^{i} − x^{0}∥ = R(x^{0})), and points q^{1}, ..., q^{l} supporting B(x^{0}, r(x^{0})) (k, l ≥ 1) such that the two convex hulls

conv \{\frac{p^{i} − x^{0}}{R(x^{0})} : i = 1, …, k\} and conv \{\frac{q^{j} − x^{0}}{r(x^{0})} : j = 1, …, l\}

have a nonempty intersection. Bárány mentions that the numbers k, l can be restricted to k +l ≤ n+2 (without an explicite proof of this assertion).

In what follows we formulate the minimal shell problem as a linear semi-infinite optimization problem. Using the duality theory of linear semi-infinite optimization, we obtain in a very natural way not only the results of Bárány but also additional properties of the minimal shell.

Let

k(u) := sup_{t∈K} u^{T} t

and

h_{x,ρ}(u) := sup_{t∈B(x,ρ)} u^{T} t = u^{T} x + ρ∥u∥

be the Minkowski support function of the convex body K and the ball B(x, ρ), respectively. The embedding B(x, r) ⊆ K and covering K ⊆ B(x, R) are fulfilled if and only if

h_{x,r}(u) ≤ k(u) ≤ h_{x,R}(u) ∀u ∈ ℝ^{n}.

Thus the minimal shell problem can be formulated as follows:

(SP)  min{R − r | u^{T} x + r∥u∥ ≤ k(u) ≤ u^{T} x + R∥u∥, u ∈ ℝ^{n}, R, r ≥ 0, x ∈ K.}

This is a linear semi-infinite optimization problem, which will be regarded as a primal problem in the following representation:

(SP) min \{z_{P} (x, R, r) = (0_{n}^{T}, 1, −1) ( \begin{matrix}x \\ R \\ r \end{matrix} ) | (x, R, r) ∈ M_{SP} \}

M_{SP} := \{( \begin{matrix}x \\ R \\ r \end{matrix} ) | \begin{matrix}(s^{T} , 1, 0) ( \begin{matrix}x \\ R \\ r \end{matrix} ) & ≥ & k(s), s ∈ ∂B \\ (−t^{T} , 0, −1) ( \begin{matrix}x \\ R \\ r \end{matrix} ) & ≥ & −k(t), t ∈ ∂B \end{matrix} \} .

Note that each support function is a positively homogeneous one; ∂B denotes the boundary of the unit ball B := B(0, 1). It is not necessary to include the restrictions R, r ≥ 0 and x ∈ K. R > 0 follows with s^{T} x + R ≥ k(s) ∀s ∈ ∂B and int K ≠ ∅. With the existence of the circumsphere B(x^{∗}, R(x^{∗})) of K with x^{∗} ∈ K, cf. [3], [5], follows R_{0} ≥ R(x^{∗}) and r_{0} ≥ r(x^{∗}) ≥ 0 for an optimal solution (x^{0}, R_{0}, r_{0}) of (P) . By r_{0} ≥ 0 one further obtains x^{0} ∈ K.

2. Minimal shells and linear semi-infinite duality

2.1. Duality

The minimal shell problem (SP) is a problem of the type

(P) min{z_{P} (y) := c^{T} y | y ∈ M_{P} }  (1)

M_{P} := \{y ∈ ℝ^{m} | \begin{matrix}a^{1}^{T} (u^{1})x & ≥ & b^{1}(u^{1}), & u^{1} ∈ U^{1} \\ a^{2}^{T} (u^{2})x & ≥ & b^{2}(u^{2}), & u^{2} ∈ U^{2} \end{matrix} \} ,  (2)

with c, y ∈ ℝ^{m}, a^{i}(u^{i}) : U^{i} → ℝ^{m}, b^{i}(u^{i}) : U^{i} → ℝ, i = 1, 2. In accordance with [4] (where only one index set U^{1} occurs) we associate with (1),(2) the data-sets

A := {a^{1}(u^{1}), a^{2}(u^{2}) | u^{1} ∈ U^{1}, u^{2} ∈ U^{2}} ⊆ ℝ^{m}  (3)

\overline{A} := \{( \begin{matrix}b^{1}(u^{1}) \\ a^{1}(u^{1}) \end{matrix} ) , ( \begin{matrix}b^{2}(u^{2}) \\ a^{2}(u^{2}) \end{matrix} ) , | u^{1} ∈ U^{1}, u^{2} ∈ U^{2}\} ⊆ ℝ^{m+1}

and the vertical line g ∈ ℝ^{m+1}, given as

( \begin{matrix}t_{0} \\ t \end{matrix} ) := ( \begin{matrix}0 \\ c \end{matrix} ) + α ( \begin{matrix}1 \\ 0_{m} \end{matrix} ) − ∞ < α < ∞, t ∈ ℝ^{m},

where the t_{0}-axis is referred to as vertical axis. Let

H(y) := \{( \begin{matrix}t_{0} \\ t \end{matrix} )| y^{T} t − t_{0} = 0\} ⊆ ℝ^{m+1}

be a hyperplane not parallel to the t_{0}-axis and going through the origin, with the normal

vector ( \begin{matrix}−1 \\ y \end{matrix} ) , y ∈ ℝ^{m}. The feasibility y ∈ M_{P} is equivalent to the inclusion

\overline{A} ⊆ H_{+}(y) := \{( \begin{matrix}t_{0} \\ t \end{matrix} )| y^{T} t − t_{0} ≤ 0\} .

The vertical line g intersects the hyperplane H in the point

Q := g ∩ H = ( \begin{matrix}c^{T} y \\ c \end{matrix} ) .

From these facts we are led to the following geometric meaning of the primal problem (P):

Among all nonvertical hyperplanes H(y) through the origin in ℝ^{m+1} containing the dataset \overline{A} completely in their nonnegative halfspace H_{+}(y) look for that one which intersects (in the point Q) the vertical line g as low as possible. With this background the duality concept in (semi-infinite) linear optimization can be formulated in the following way: Try to find this lowest intersection point Q as the highest common point of the vertical line g and the convex cone generated by the set \overline{A}, i.e. as the upper piercing point of g in cone \overline{A}. This leads to the dual problem

max \{t_{0} |( \begin{matrix}t_{0} \\ t \end{matrix} ) ∈ g ∩ cone \overline{A}\} .  (4)

In more detail this dual problem has the following representation

(D) max {z_{D}(u; λ) = ∑_{i=1}^{2} ∑_{j=1}^{q_{i}} λ_{j}^{i}b^{i}(u_{j}^{i})| (u; λ) ∈ M_{D}}

with

M_{D} := \{(u; λ) | \begin{matrix}u = (u_{1}^{1}, ..., u_{q_{1}}^{1}, u_{1}^{2}, ..., u_{q_{2}}^{2}) \\ λ = (λ_{1}^{1}, ..., λ_{q_{1}}^{1}, λ_{1}^{2}, ..., λ_{q_{2}}^{2}) \\ u_{1}^{1}, ..., u_{q_{1}}^{1} ∈ U^{1} \\ u_{1}^{2}, ..., u_{q_{2}}^{2} ∈ U_{2} \\ λ_{1}^{1}, ..., λ_{q_{1}}^{1} ≥ 0 \\ λ_{1}^{2}, ..., λ_{q_{2}}^{2} ≥ 0 \\ ∑_{i=1}^{2} ∑_{j=1}^{q_{i}} λ_{j}^{i}a^{i}(u_{j}^{i}) = c \end{matrix} \} .

It is sufficient to choose q_{1} + q_{2} ≤ m + 1 since each point of cone \overline{A} ⊆ ℝ^{m+1} can generally be written as a nonnegative linear combination of at most m + 1 points of \overline{A} (Caratheodory). Considering the special structure of the vertical line g we obtain the equivalence of the consistency of (D) and of c belonging to cone A:

M_{D} ≠ ∅ ⟺ c ∈ cone A  (5)

Additionally the dual problem (D) will be called superconsistent if c ∈ int cone A. Superconsistency is a regularity condition which allows to prove some duality statements. In this connection we call the primal problem (P) superconsistent if there exists a point ỹ ∈ ℝ^{n} with a^{i}^{T} (u^{i})ỹ > b^{i}(u^{i}) for all u^{i} ∈ U^{i} and i = 1, 2. (Slater-condition, ỹ is referred to as a Slater-point of the feasible set M_{P}.) As usual, we denote v(P) := inf_{x∈M_{P}} z_{P} (x) = inf_{x∈M_{P}} c^{T} x as value of (P) and

v(D) := sup_{(u;λ)∈M_{D}} z_{D}(u; λ) = sup_{(u;λ)∈M_{D}} ∑_{i=1}^{2} ∑_{j=1}^{q_{i}} λ_{j}^{i}b^{i}(u_{j}^{i}) as value of (D).

With these notations the following duality properties can be verified in the same way as in [4]: Weak duality: Let x ∈ M_{P} , (u; λ) = (u_{1}^{1}, ..., u_{q_{1}}^{1}, u_{1}^{2}, ..., u_{q_{2}}^{2}; λ_{1}^{1}, ..., λ_{q_{1}}^{1}, λ_{1}^{2}, ..., λ_{q_{2}}^{m}) ∈ M_{D}. Then

z_{D}(u; λ) ≤ v(D) ≤ v(P) ≤ z_{P} (x)  (6)

holds.

Complementarity:

[ \begin{matrix}y ∈ M_{P} & λ_{j}^{i}[a^{i}(u_{j}^{i})y − b^{i}(u_{j}^{i})] = 0 \\ (u; λ) ∈ M_{D} & j = 1, ..., q_{i}, i = 1, 2 \end{matrix} ] ⇔ [ \begin{matrix}y solves (P) \\ and \\ (u; λ) solves (D) \\ and v(P) = v(D) \end{matrix} ]  (7)

Existence:

If M_{D} ≠ ∅, v(D) < ∞ and cone \overline{A} is closed, then there exists an optimal solution of (D), further M_{P} ≠ ∅ holds and no duality gap occurs, i.e. v(P) = v(D).

(8)

The closure of cone \overline{A} is guaranteed under the following sufficient conditions:

·) U^{1}, U^{2} are compact sets of finite dimensional linear spaces ·) a^{i}(·), b^{i}(·) are continuous functions on U^{i}, i = 1, 2 ·) (P) is superconsistent

(9)

If M_{P} ≠ ∅ and the dual problem (D) is superconsistent, then there exists an optimal solution of (P) and v(P) = v(D) holds.

(10)

Strong duality:

If both (P) and (D) are superconsistent, then both (P) and (D) have an optimal solution and v(P) = v(D) holds.

(11)

It should be mentioned that all these results can be generalized to an arbitrary number N of index sets U^{1}, ..., U^{N}.

2.2. Optimality conditions of the minimal shell

Let K ∈ K^{n} be a fixed convex body. To the minimal shell problem (SP) there corresponds according to 2.1 the following dual problem

(SD) max {z(w) = ∑_{i=1}^{q} λ_{i}k(s^{i}) + ∑_{j=1}^{p} μ_{j}(−k(t^{j})) | w ∈ M_{SD}}

with

M_{SD} := \{ \begin{matrix}w & = & (s^{1}, ..., s^{q}, t^{1}, ..., t^{p}; λ_{1}, ..., λ_{q}, μ_{1}, ..., μ_{p}) : \\ & s.t. & s^{1}, ..., s^{q}, t^{1}, ..., t^{p} ∈ ∂B \\ & & λ_{1}, ..., λ_{q}, μ_{1}, ..., μ_{p} ≥ 0 \\ & & ∑_{i=1}^{q} λ_{i} ( \begin{matrix}s^{i} \\ 1 \\ 0 \end{matrix} ) + ∑_{j=1}^{p} μ_{j} ( \begin{matrix}−t^{j} \\ 0 \\ −1 \end{matrix} ) = ( \begin{matrix}0_{n} \\ 1 \\ −1 \end{matrix} ) \end{matrix} \}

or

M_{SD} := \{ \begin{matrix}w & = & (s^{1}, ..., s^{q}, t^{1}, ..., t^{p}; λ_{1}, ..., λ_{q}, μ_{1}, ..., μ_{p}) : \\ & s.t. & s^{1}, ..., s^{q}, t^{1}, ..., t^{p} ∈ ∂B \\ & & λ_{1}, ..., λ_{q}, μ_{1}, ..., μ_{p} ≥ 0 \\ & & ∑_{i=1}^{q} λ_{i}s^{i} = ∑_{j=1}^{p} μ_{j}t^{j} \\ & & ∑_{i=1}^{q} λ_{i} = 1 \\ & & ∑_{j=1}^{p} μ_{j} = 1 \end{matrix} \} .

We further have, in view of (3), the data-set

A = \{( \begin{matrix}s \\ 1 \\ 0 \end{matrix} ) , ( \begin{matrix}−t \\ 0 \\ −1 \end{matrix} ) | s, t ∈ ∂B\} .

Both problems (SP) and (SD) turn out to fulfill the described regularity conditions:

Lemma 1. The minimal shell problem (SP) is superconsistent.

Proof. The continuous function k attains its maximum and its minimum on the compact set ∂B.

Let m := min_{u∈∂B} k(u) and M := max_{u∈∂B} k(u). Then ỹ := ( \begin{matrix}0_{n} \\ M + 1 \\ m − 1 \end{matrix} ) is a slater-point of (SP)

since

\begin{aligned}(s^{T} , 1, 0)ỹ & = & M + 1 & > & k(s), ∀s ∈ ∂B, \\ (−t^{T} , 0, −1)ỹ & = & −(m − 1) & > & −k(t), ∀t ∈ ∂B, \end{aligned}

holds. □

Lemma 2. The dual problem (SD) is superconsistent.

Proof. We have to prove

c = ( \begin{matrix}0_{n} \\ 1 \\ −1 \end{matrix} ) ∈ int cone A.

In the first place the point c belongs to cone A: Choosing an arbitrary (fixed) point e ∈ ∂B and setting s^{1} = t^{1} := e, λ_{1} := μ_{1} := 1, we have w := (e, e; 1, 1) ∈ M_{SD}, i.e. M_{SD} ≠ ∅ and therefore c ∈ cone A according to (5).

Suppose c ∉ int cone A: Then c is a boundary point of cone A and there exists a supporting hyperplane H of cone A with normal vector

( \begin{matrix}a \\ a_{n+1} \\ a_{n+2} \end{matrix} ) ≠ 0_{n+2},  (12)

which goes through both the origin and c. H has the representation

H = \{( \begin{matrix}t \\ t_{n+1} \\ t_{n+2} \end{matrix} ) ∈ ℝ^{⋉+⊭} | a^{T} t + a_{n+1}t_{n+1} + a_{n+2}t_{n+2} = 0\} ,

where a, t ∈ ℝ^{⋉}, ⅁_{⋉+⊮}, ⅁_{⋉+⊭}, ≈_{⋉+⊮}, ≈_{⋉+⊭} ∈ ℝ. a_{n+1} = a_{n+2} =: a_{0} follows by c ∈ H. All points of cone A are contained in a halfspace of H, say

a^{T} t + a_{0}(t_{n+1} + t_{n+2}) ≤ 0, ∀ ( \begin{matrix}t \\ t_{n+1} \\ t_{n+2} \end{matrix} ) ∈ cone A.  (13)

We have

( \begin{matrix}d \\ 1 \\ 0 \end{matrix} ) , ( \begin{matrix}−d \\ 1 \\ 0 \end{matrix} ) ∈ A

for arbitrarily chosen d ∈ ∂B and thus a_{0} ≤ 0 follows by

a^{T} d + a_{0} ≤ 0 and − a^{T} d + a_{0} ≤ 0.

With the same argument a_{0} ≥ 0 holds due to

( \begin{matrix}d \\ 0 \\ −1 \end{matrix} ) , ( \begin{matrix}−d \\ 0 \\ −1 \end{matrix} ) ∈ A

such that a_{0} = 0 and therefore a ≠ 0_{n}, cf. (12). From

( \frac{a}{∥a∥} ; 1 ; 0 ) ∈ A

we get due to (13) the inequality

a^{T} (\frac{a}{∥a∥}) + 0(1 + 0) ≤ 0,

a contradiction to a ≠ 0. This shows c ∈ int cone A and (SD) is superconsistent. □

The support function k of the convex body K is as a convex function on ℝ^{⋉} automatically continuous on ℝ^{⋉}. Consequently all the coefficient functions of the primal problem (SP) are continuous ones on the finite-dimensional index set B = B(0, 1). Further both (SP) and (SD) are superconsistent. According to the strong duality property we obtain the following lemma

Lemma 3. Both the minimal shell problem (SP) and its dual problem possess optimal solutions and v(SP) = v(SD) holds.

It is a general result in linear semi-infinite duality that – if there exist optimal solutions of the dual problem – then there exists also an optimal solution (basic solution) of the dual problem in which the number of positive components (λ_{i}, μ_{j}) is not greater than the number of primal variables (cf. [4]). In view of (4) the geometric interpretation is as follows: The upper piercing point of a vertical line in the cone \overline{A} automatically is a boundary point of cone \overline{A}. Hence (SD) possesses an optimal solution with p + q ≤ n + 2.

The duality properties given in 2.1 allow to establish necessary and sufficient optimality conditions of the minimal shell which are summarized in the following theorem:

Theorem 1. Let K be a convex body in ℝ^{n} and B(x^{0}, r_{0}) ⊆ K ⊆ B(x^{0}, R_{0}). Then the following equivalence holds: B(x^{0}, R_{0}, r_{0}) is a minimal shell of K if and only if there exist directions s^{1}, …, s^{q}, t^{1}, …, t^{p} ∈ ∂B, p + q ≤ n + 2, with

(i) conv {s^{1}, …, s^{q}} ∩ conv {t^{1}, …, t^{p}} ≠ ∅. (ii)

x^{0} + R_{0}s^{i} ∈ ∂B(x^{0}, R_{0}) ∩ ∂K, i = 1, …, q  (14)
x^{0} + r_{0}t^{j} ∈ ∂B(x^{0}, r_{0}) ∩ ∂K, j = 1, …, p  (15)

Proof. (a) Let B(x^{0}, R_{0}, r_{0}) be a minimal shell of K. Then ( \begin{matrix}x^{0} \\ R_{0} \\ r_{0} \end{matrix} ) is an optimal solution of

(SP). Let w_{0} = (s^{1}, ..., s^{q}, t^{1}, ..., t^{p}; λ_{1}, ..., λ_{q}, μ_{1}, ..., μ_{p}) be an optimal solution of (SD), where p+q is assumed to be minimal. The minimality of p+q implies λ_{i}, μ_{j} > 0 and p+q ≤ n+2. In what follows we show that the components s^{1}, ..., s^{q}, t^{1}, ..., t^{p} from the dual optimal solution w_{0} turn out in a very natural way to satisfy the assertions (i) and (ii). The dual feasibility

of w_{0} implies ∑_{i=1}^{q} λ_{i} = ∑_{j=1}^{p} μ_{j} = 1 and ∑_{i=1}^{q} λ_{i}s^{i} = ∑_{j=1}^{p} μ_{j}t^{j} such that (i) is fulfilled.

Due to v(SP) = v(SD) and the feasibility of ( \begin{matrix}x^{0} \\ R_{0} \\ r_{0} \end{matrix} ) and w_{0} we have

R_{0} − r_{0} = ∑_{i=1}^{q} λ_{i}k(s^{i}) − ∑_{j=1}^{p} μ_{j}k(t^{j})
≤ ∑_{i=1}^{q} λ_{i} (s^{i}^{T} x^{0} + R_{0}) − ∑_{j=1}^{p} μ_{j} (t^{j}^{T} x^{0} + r_{0})

= (∑_{i=1}^{q} λ_{i}s^{i} − ∑_{j=1}^{p} μ_{j}t^{j})^{T} x^{0} + ∑_{i=1}^{q} λ_{i}R_{0} − ∑_{j=1}^{p} μ_{j}r_{0}
= R_{0} − r_{0}.

In view of λ_{i}, μ_{j} > 0 this yields

s^{i}^{T} x^{0} + R_{0} = k(s^{i})  (16)

and

t^{j}^{T} x^{0} + r_{0} = k(t^{j})  (17)

for i = 1, …, q and j = 1, …, p ((16), (17) correspond to the complementarity property (7)). Therefore the values of the support functions of K and B(x^{0}, R_{0}) in direction s^{i} and of K and B(x^{0}, r_{0}) in direction t^{j} have to coincide and the hyperplanes

H_{i} := {x ∈ ℝ^{n} | s^{i}^{T} x = k(s^{i})}, i = 1, …, q,
h_{j} := {x ∈ ℝ^{n} | t^{j}^{T} x = k(t^{i})}, j = 1, …, p,

are supporting hyperplanes of both the convex body K and the outer ball B(x^{0}, R_{0}) and the inner ball B(x^{0}, r_{0}), respectively. The point

Z^{i} := x^{0} + R_{0}s^{i}

is the uniquely determined supporting point of H_{i} and B(x^{0}, R_{0}). Let Z ∈ H_{i} ∩ K be any supporting point of K and H_{i}. Due to K ⊆ B(x^{0}, R_{0}) we have Z ∈ H_{i} ∩ B(x^{0}, R_{0}) too and therefore H_{i} ∩ ∂B(x^{0}, R_{0}) = {Z^{i}} = H_{i} ∩ ∂K, i = 1, …, q, thus (14) is fulfilled. In the same way the point

z^{j} := x^{0} + r_{0}t^{j}

turns out to be a supporting point of the inner ball B(x^{0}, r_{0}) and both the hyperplane h_{j} and the boundary of K,

h_{j} ∩ B(x^{0}, r_{0}) = {z^{j}} ⊆ h_{j} ∩ ∂K, j = 1, …, p,

such that (15) is fulfilled too.

(b) Conversely, assume there are directions s^{1}, …, s^{q}, t^{1}, …, t^{p} ∈ ∂B with (i) and (ii). A point z ∈ conv {s^{1}, …, s^{q}} ∩ conv {t^{1}, …, t^{p}}, i.e.

z = ∑_{i=1}^{q} α_{i}s^{i} = ∑_{j=1}^{p} β_{j}t^{j}

∑_{i=1}^{q} α_{i} = ∑_{j=1}^{p} β_{j} = 1, α_{1}, …, α_{q}, β_{1}, …, β_{p} ≥ 0

produces a dual feasible solution γ := (s^{1}, …, s^{q}, t^{1}, …, t^{p}; α_{1}, …, α_{q}, β_{1}, …, β_{p}) ∈ M_{SD}. Using B(x^{0}, R_{0}) ⊇ K and x^{0} + R_{0}s^{i} ∈ K one obtains

h_{x^{0},R_{0}}(s^{i}) ≥ k(s^{i}) ≥ s^{i}^{T} (x^{0} + R_{0}s^{i}) = s^{i}^{T} x^{0} + R_{0} = h_{x^{0},R_{0}}(s^{i})

and thus

s^{i}^{T} x^{0} + R_{0} = k(s^{i}) for i = 1, …, q.  (18)

Let H be a supporting hyperplane of K with normal unit vector t which contains the point x^{0} + r_{0}t^{j}. H also supports B(x^{0}, r_{0}) because B(x^{0}, r_{0}) ⊆ K and x^{0} + r_{0}t^{j} ∈ B(x^{0}, r_{0}). This leads to t = t^{j} and thus

t^{j}^{T} x^{0} + r_{0} = k(t^{j}) for j = 1, …, p.  (19)

(18), (19) verify that the primal feasible solution ( \begin{matrix}x^{0} \\ R_{0} \\ r_{0} \end{matrix} ) and the dual feasible solution

γ fulfill the complementarity condition (7). Therefore these solutions are optimal solutions of (SP) and (SD) respectively, what also can be seen directly from their objective function values:

\begin{aligned}z_{D}(γ) & = & ∑_{i=1}^{q} α_{i}k(s^{i}) + ∑_{j=1}^{p} β_{j}(−k(t^{j})) \\ & = & ∑_{i=1}^{q} α_{i} (s^{i}^{T} x^{0} + R_{0}) + ∑_{j=1}^{p} β_{j} (−t^{j}^{T} x^{0} − r_{0}) \\ & = & (∑_{i=1}^{q} α_{i}s^{i} − ∑_{j=1}^{p} β_{j}t^{j})^{T} x^{0} + R_{0} − r_{0} \\ & = & R_{0} − r_{0} = z_{P} (x^{0}, R_{0}, r_{0}). \end{aligned}  (20)

From weak duality (6) we obtain immediately the optimality of ( \begin{matrix}x^{0} \\ R_{0} \\ r_{0} \end{matrix} ), i.e. B(x^{0}, R_{0}, r_{0}) is the minimal shell. □

Corollary. Let B(x^{0}, R_{0}, r_{0}) be a minimal shell of the convex body K and suppose s^{1}, …, s^{q}, t^{1}, …, t^{p} to be the characteristic directions according to Theorem 1. Then each point

z ∈ conv{s^{1}, …, s^{q}} ∩ conv{t^{1}, …, t^{p}}

produces with each representation

z = ∑_{i=1}^{q} λ_{i}s^{i} = ∑_{j=1}^{p} μ_{j}t^{j}

∑_{i=1}^{q} λ_{i} = ∑_{j=1}^{p} μ_{j} = 1, λ_{i}, μ_{j} ≥ 0, i = 1, …, q, j = 1, …, p

the thickness R_{0} − r_{0} of the minimal shell to

R_{0} − r_{0} = ∑_{i=1}^{q} λ_{i}k(s^{i}) − ∑_{j=1}^{p} μ_{j}k(t^{j}).  (21)

To confirm this corollary we only have to note that in part (b) of the proof of theorem 1 the point z ∈ conv {s^{1}, ..., s^{q}} ∩ {t^{1}, ..., t^{p}} can be chosen arbitrarily. Each such point z leads to the representation (21) of the thickness R_{0} − r_{0} according to (20).

Theorem 2.

(i) The center of the minimal shell of K is an inner point of K (ii) The minimal shell of a convex body K is uniquely determined Proof. (i) Assume r_{0} = 0. The supporting points x_{0} + Rs^{i} belong to K, i = 1, ..., q; together with (19) this leads to

t^{j}^{T} x_{0} = k(t^{j}) = max_{x∈K} t^{j}^{T} x ≥ t^{j}^{T} (x_{0} + Rs^{i}) = t^{j}^{T} x_{0} + R_{0}t^{j}^{T} s^{i}

such that

t^{j}^{T} s^{i} ≤ 0 i = 1, ..., q, j = 1, ..., p.

For u := ∑_{i=1}^{q} λ_{i}s^{i} = ∑_{j=1}^{p} μ_{j}t^{j} it follows

∥u∥^{2} = (∑_{i=1}^{q} λ_{i}s^{i})^{T} (∑_{j=1}^{p} μ_{j}t^{j}) = ∑_{i=1}^{q} ∑_{j=1}^{p} λ_{i}μ_{j}s^{i}^{T} t^{j} ≤ 0

thus u = 0. Let a ∈ int K, then

t^{j}^{T} a < k(t^{j}) = t^{j}^{T} x_{0}

holds, j = 1, …, p, hence

u^{T} a = (∑_{j=1}^{p} μ_{j}t^{j})^{T} a < (∑_{j=1}^{p} μ_{j}t^{j})^{T} x^{0} = u^{T} x_{0}

in contradiction to u = 0. Therefore r_{0} > 0 holds which implies x_{0} ∈ int K. (ii) The thickness R_{0} − r_{0} of a minimal shell B(x^{0}, R_{0}, r_{0}) of K vanishes if and only if K = B(x^{0}, R_{0}) is a ball itself; in this case the uniqueness of B(x^{0}, R_{0}, r_{0}) = ∂K is obvious.

Let B(x^{0}, R_{0}, r_{0}) and B(x^{1}, R_{1}, r_{1}) be two minimal shells with ( \begin{matrix}x^{0} \\ R_{0} \\ r_{0} \end{matrix} ) ≠ ( \begin{matrix}x^{1} \\ R_{1} \\ r_{1} \end{matrix} ),

suppose r_{1} ≥ r_{0} and R_{0} > r_{0}. This implies R_{0} − r_{0} = R_{1} − r_{1} and R_{1} ≥ R_{0}. Let w_{0} = (s^{1}, …, s^{q}, t^{1}, …, t^{p}; λ_{1}, …, λ_{q}, μ_{1}, …, μ_{p}) be an optimal solution of (SD). Then

\begin{matrix}x^{m} + R_{m}s^{i} ∈ ∂B(x^{m}, R_{m}) ∩ ∂K, i = 1, …, q \\ x^{m} + r_{m}t^{j} ∈ ∂B(x^{m}, r_{m}) ∩ ∂K, j = 1, …, p \end{matrix} , m = 0, 1.  (22)

We have

\begin{matrix}k(s^{i}) = s^{i}^{T} x^{0} + R_{0} = s^{i}^{T} x^{1} + R_{1} \\ k(t^{j}) = t^{j}^{T} x^{0} + r_{0} = t^{j}^{T} x^{1} + r_{1}, \end{matrix}  (23)

such that

s^{i}^{T} (x^{0} − x^{1}) = R_{1} − R_{0} = r_{1} − r_{0} = t^{j}^{T} (x^{0} − x^{1})  (24)

i = 1, …, q, j = 1, …, p.

From x^{0} + R_{0}s^{i} ∈ K ⊆ B(x^{1}, R_{1}) and (24) we obtain

R_{1}^{2} ≥ ∥x^{0} + R_{0}s^{i} − x^{1}∥^{2} = ∥x^{0} − x^{1}∥^{2} + 2R_{0}s^{i}^{T} (x^{0} − x^{1}) + R_{0}^{2} = ∥x^{0} − x^{1}∥^{2} + 2R_{0}R_{1} − R_{0}^{2}, hence ∥x^{0} − x^{1}∥ ≤ R_{1} − R_{0}.

On the other hand (24) shows

R_{1} − R_{0} = s^{i}^{T} (x^{0} − x^{1}) ≤ ∥x^{0} − x^{1}∥,  (25)

and all in all

∥x^{0} − x^{1}∥ = R_{1} − R_{0} = r_{1} − r_{0}  (26)

holds; so from (x^{0}, R_{0}, r_{0}) ≠ (x^{1}, R_{1}, r_{1}) we obtain x^{0} ≠ x^{1} and r_{0} ≠ r_{1} and R_{0} ≠ R_{1} as well. The (Schwarz-)inequality (25) is fulfilled as equality what only may hold if

s^{i} = \frac{x^{0} − x^{1}}{∥x^{0} − x^{1}∥}

for all i=1,…,q, thus q = 1.

In the same way we get from (24), (26)

r_{1} − r_{0} = t^{j}^{T} (x^{0} − x^{1}) ≤ ∥x^{0} − x^{1}∥ = r_{1} − r_{0}

and therefore

t^{j} = \frac{x^{0} − x^{1}}{∥x^{0} − x^{1}∥}

for all j = 1, …, p, i.e. p = 1. The dual optimal solution turns out to be

w = (d, d, 1, 1) with d = \frac{x^{0} − x^{1}}{∥x^{0} − x^{1}∥}.

The center x^{0} is always an inner point of K according to (i) and the supporting point x^{0}+R_{0}d belongs to the boundary of K. This leads to

x^{0} + λd ∈ int K for 0 ≤ λ < R_{0}

such that

x^{0} + r_{0}d ∉ ∂K

according to r_{0} < R_{0}, so x^{0} + r_{0}d cannot be a supporting point of K and B(x^{0}, r_{0}), a contradiction to (22). □

References

[1] Bárány, I.: On the minimal shell containing the boundary of a convex body. Acta Sci. Math. 52 (1988), 93–100.

[2] Bonnesen, T.: Über das isoperimetrische Defizit ebener Figuren. Math. Ann. 91 (1924), 252–268.

[3] Bonnesen, T.; Fenchel, W.: Theorie der konvexen Körper. Springer, Berlin 1934.

[4] Glashoff, K.; Gustafson, S.: Linear Optimization and Approximation. Springer, New York Heidelberg Berlin 1983.

[5] Juhnke, F.: Das Umkugelproblem und lineare semi-infinite Optimierung. Beitr. Algebra Geom. 28 (1988), 147–156.

[6] Kritikos, N.: Über konvexe Flächen und einschließende Kugeln. Math. Ann. 96 (1927), 583–586.

[7] Peri, C.: On the minimal convex shell of a convex body. Canad. Math. Bull. 36 (1993), 466–472.

[8] Peri, C.: Minimal shells containing a convex surface in Minkowski space. Manuscripta math. 90 (1996), 333–342.

[9] Peri, C.; Wills, J. M.; Zucco, A.: On Blaschke’s extension of Bonnesen’s inequality. Geom. Dedicata 48 (1993), 349–357.

Received December 16, 1998