On a Minimax Theorem

by Jean Saint Raymond

Abstract : The aim of this note is to prove the following statement. It gives an extension of the theorem proved by 0. Y. Borenshtein and V. S. Shul’man in [1].

Theorem 1. Let X be a metrizable compact space, T an interval of ℝ and f a function from X × T to ℝ. Assume that

i) for every x in X the function t ↦ f(x, t) is concave and continuous. ii) for every t in T, the function x ↦ f(x, t) is lower semicontinuous. iii) for every t ∈ T the function x ↦ f(x, t) satisfies the Gm condition. Then the following holds

inf_{x∈X} sup_{t∈T} f(x, t) = sup_{t∈T} inf_{x∈X} f(x, t)

Keywords : Minimax, Global minimum condition. 1991 AMS Classification : 26D07, 26A15, 26A51

This paper provides an answer to questions raised by B. Ricceri. Recall that a function is said to satisfy the Global minimum condition (the Gm condition) if it admits no local minimum value greater than its absolute minimum. It is clear that any convex function satisfies the Gm condition. Theorem 1 is an easy corollary of the following one :

Theorem 2. Let X be a metrizable compact space, T an interval of ℝ and f a function from X × T to ℝ. Assume that

i) for every x in X the function t ↦ f(x, t) is concave and continuous. ii) for every t in T, the function x ↦ f(x, t) is l.s.c. (lower semicontinuous). iii)

δ = sup_{t∈I} inf_{x∈X} f(x, t) < β = inf_{x∈X} sup_{t∈I} f(x, t)

Then, for all ρ ∈]δ, β[, there exist θ ∈ T and x_{1} in X such that f(x_{1}, θ) = ρ and that x_{1} is a local non absolute minimum for the function f(., θ).

Notice that the theorem proved by 0. Y. Borenshtein and V. S. Shul’man in [1] is the particular case of Theorem 1 where the hypothesis ii) is replaced by the continuity of f on X × T.

Lemma 3. Let X be a Hausdorff compact space and (h_{n}) a non-decreasing sequence of l.s.c. functions : X → ℝ. Then

sup_{n} inf_{x∈X} h_{n}(x) = inf_{x∈X} sup_{n} h_{n}(x)

Clearly inf_{x∈X} h_{m}(x) ≤ inf_{x∈X} sup_{n} h_{n}(x) for all m. Denote sup_{n} inf_{x∈X} h_{n}(x) by λ. The set K_{m} = {x ∈ X : h_{m}(x) ≤ λ} is compact and nonempty for all m. Since the sequence (K_{n}) is non-increasing, the intersection ⋂_{n} K_{n} is nonempty ; so, if x_{0} ∈ ⋂_{n} K_{n}, we have h_{n}(x_{0}) ≤ λ for all n, hence

inf_{x∈X} sup_{n} h_{n}(x) ≤ sup_{n} h_{n}(x_{0}) ≤ λ

and this completes the proof. ■

Lemma 4. Let X be a topological space and A some subset of X × ℝ. Assume that, for all x ∈ X, the set A_{x} = {t ∈ ℝ : (x, t) ∈ A} is an open interval, and that, for all t ∈ ℝ, the set A^{t} = {x ∈ X : (x, t) ∈ A} is open in X. Then A is open in X × ℝ.

The set

B = ⋃_{{s,t∈ℝ \atop s<t}}(A^{s} ∩ A^{t})×]s, t[

is open in X × ℝ since so are the sets A^{s} ∩ A^{t} in X. If (x, u) ∈ B, there are s and t in ℝ such that s < u < t and x ∈ A^{s} ∩ A^{t}. Then, s ∈ A_{x} and t ∈ A_{x}, and since A_{x} is an interval in ℝ, u ∈ A_{x}; and that means that (x, u) ∈ A.

Conversely, if (x, u) ∈ A, the point u belongs to the open interval A_{x}; thus there exist s and t in A_{x} such that s < u < t. Hence x belongs to A^{s} and to A^{t}, and (x, u) ∈ (A^{s} ∩ A^{t})×]s, t[ ⊂ B.

We conclude that A = B is open in X × ℝ. ■

Lemma 5. Let X be a topological space, I a compact interval [a, b] of ℝ and f a function from X × I to ℝ. We assume

i) for all x in X the function t ↦ f(x, t) is concave and continuous.

ii) for all t in I, the function x ↦ f(x, t) is l.s.c.. Then f is l.s.c.

For convenience we extend f to a function : f̃: X × ℝ → ℝ by letting

f̃(x, t) = \{ \begin{matrix}f(x, a) & if t ≤ a \\ f(x, t) & if a ≤ t ≤ b \\ f(x, b) & if b ≤ t \end{matrix}

It is enough to show that, for every λ ∈ ℝ, the set A_{λ} = {(x, t) ∈ X × ℝ : f̃(x, t) > λ} is open in X × ℝ. But this follows immediately from the previous lemma, if we notice that for all x ∈ X the set {t ∈ ℝ : f̃(x, t) > λ} is an open interval since f(x, .) is concave and continuous on I. ■

Theorem 6. Let X be a metrizable compact space, I a compact interval [a, b] of ℝ and f a function from X × I to ℝ. Assume that

i) for every x in X the function t ↦ f(x, t) is concave and continuous. ii) for every t in I, the function x ↦ f(x, t) is lower semicontinuous. iii)

δ = sup_{t∈I} inf_{x∈X} f(x, t) < β = inf_{x∈X} sup_{t∈I} f(x, t)

Then, for all ρ ∈]δ, β[, there exist θ ∈ I and x_{1} in X such that f(x_{1}, θ) = ρ and that x_{1} is a local non absolute minimum for the function f(., θ).

For every x in X, the set

J_{x} = {t ∈ I : f(x, t) ≥ β}

is a non-empty compact subset of I. Choose β′ such that δ < β′ < β. By definition of δ, we have inf_{x∈X} f(x, a) ≤ δ. Since f(., a) is l.s.c.. and X is compact, there exists some ξ in X such that f(ξ, a) ≤ δ. Thus t_{1} = a ∉ J_{ξ} and there exists a t_{2} ∈ J_{ξ}. Then we have t_{2} ≥ t_{1} and :

f(ξ, t_{1}) ≤ δ < β′ < β ≤ f(ξ, t_{2})

Using lemma 5, we see that f is l.s.c. ; thus, since X is metrizable, there is a nondecreasing sequence (f_{n}) of continuous functions on X × I which converges to f.

Lemma 7. There exists an integer m such that f_{m}(ξ, t_{2}) ≥ β′ and that, for every x in X, sup_{t∈I} f_{m}(x, t) > β′ holds.

The set

U_{n} = {(x, t) ∈ X × I : f_{n}(x, t) > β′}

is open in X × I. If we denote by π the projection of X × I on X, the following holds for every x in X :

∃t ∈ I lim_{n→∞} f_{n}(x, t) = f(x, t) ≥ β > β′ .

Thus x ∈ ⋃_{n} π(U_{n}). And since the compact space X is the union of the non-decreasing sequence (π(U_{n})) of open sets, there is some integer n such that X = π(U_{n}), and that means that for every x in X there exists some t such that f_{n}(x, t) > β′. Then there exists some integer m ≥ n such that f_{m}(ξ, t_{2}) > β′, and this integer satisfies the conclusion of the Lemma. ■

For δ < ρ < β′, denote by K_{ρ} the compact subspace of X × I × I defined by

K_{ρ} = {(x, t, t′) : t ≤ t′ and f(x, t) ≤ ρ and f_{m}(x, t′) ≥ β′}

It is easily seen that (ξ, t_{1}, t_{2}) ∈ K_{ρ}, thus that K_{ρ} ≠ ∅. Then put

θ_{ρ} = sup{t ∈ I : ∃x ∈ X ∃t′ ∈ I (x, t, t′) ∈ K_{ρ}}

which is well-defined since K_{ρ} is non-empty. Moreover define

\begin{aligned}X_{0}(ρ) & = \{x ∈ X : ∃t ≤ θ_{ρ} f_{m}(x, t) ≥ β′\} \\ X_{1}(ρ) & = \{x ∈ X : ∃t ≥ θ_{ρ} f_{m}(x, t) ≥ β′\} \end{aligned}

Lemma 8. The sets X_{0}(ρ) and X_{1}(ρ) are both compact and cover X.

The set {(x, t) : t ≤ θ_{ρ} and f_{m}(x, t) ≥ β′} is clearly compact since f_{m} is continuous. Its projection X_{0}(ρ) is also compact. Similarly X_{1}(ρ) is compact.

Let x ∈ X. From lemma 7, there exists a t such that f_{m}(x, t) > β′. Then x ∈ X_{0}(ρ) if t ≤ θ_{ρ}, and x ∈ X_{1}(ρ) if not, whence x ∈ X_{0}(ρ) ∪ X_{1}(ρ). ■

Lemma 9. If x ∈ X_{1}(ρ) then we have f(x, θ_{ρ}) ≥ ρ.

If we had f(x, θ_{ρ}) < ρ and x ∈ X_{1}(ρ), there would be some t′ ≥ θ_{ρ} such that f_{m}(x, t′) ≥ β′, and since f_{m}(x, t′) ≥ β′ > ρ > f(x, θ_{ρ}) ≥ f_{m}(x, θ_{ρ}), we would have t′ ≠ θ_{ρ}. Since f(x, .) is continuous, there would then exist θ′ such that θ_{ρ} < θ′ < t′ and f(x, θ′) < ρ. Then (x, θ′, t′) would belong to K_{ρ}, and this would contradict the definition of θ_{ρ}. ■

Since the function g_{ρ} : x ↦ f(x, θ_{ρ}) is l.s.c., it attains its minimum over the compact subset X_{1}(ρ) at a point x_{1}.

Lemma 10. The function g_{ρ} has at x_{1} a local non absolute minimum, and g_{ρ}(x_{1}) = ρ.

Since K_{ρ} is compact, there are some x′ ∈ X and t′ ∈ I such that (x′, θ_{ρ}, t′) ∈ K_{ρ}. This shows that f_{m}(x′, t′) ≥ β′ with t′ ≥ θ_{ρ}, whence x′ ∈ X_{1}(ρ), and that g_{ρ}(x′) = f(x′, θ_{ρ}) ≤ ρ, whence

g_{ρ}(x_{1}) = inf_{y∈X_{1}(ρ)} g_{ρ}(y) ≤ g_{ρ}(x′) ≤ ρ  (∗)

By hypothesis, there is some x ∈ X such that f(x, θ_{ρ}) = min_{y∈X} g_{ρ}(y) ≤ δ < ρ. Hence the absolute minimum of g_{ρ} is less than ρ. Moreover, the point x_{1} does not belong to X_{0}(ρ) : indeed if not, we would have x_{1} ∈ X_{0}(ρ) ∩ X_{1}(ρ), and there would exist t′ ≤ θ_{ρ} and t′′ ≥ θ_{ρ} such that f_{m}(x_{1}, t′) ≥ β′ and f_{m}(x_{1}, t′′) ≥ β′. But since f(x_{1}, .) is concave and t′ ≤ θ_{ρ} ≤ t′′, we would have f(x_{1}, t′) ≥ f_{m}(x_{1}, t′) ≥ β′ and f(x_{1}, t′′) ≥ f_{m}(x_{1}, t′′) ≥ β′, thus g_{ρ}(x_{1}) = f(x_{1}, θ_{ρ}) ≥ β′ > ρ; and that contradicts the inequality (∗). We deduce that V = X \ X_{0}(ρ) is an open neighborhood of x_{1}, contained in X_{1}(ρ). And we have

g_{ρ}(x_{1}) ≥ inf_{y∈V} g_{ρ}(y) ≥ inf_{y∈X_{1}(ρ)} g_{ρ}(y) = g_{ρ}(x_{1})

and since g_{ρ}(x_{1}) = ρ according to lemma 9 and inequality (∗), we conclude that

ρ = g_{ρ}(x_{1}) = inf_{y∈V} g_{ρ}(y) > δ ≥ inf_{y∈X} g_{ρ}(y)

And this shows that x_{1} is a local non absolute minimum of g_{ρ}.

Thus we showed that for every ρ ∈]δ, β′[ there exists some θ = θ_{ρ} such that the function f(., θ) admits a local non absolute minimum with value ρ. And since β′ is arbitrary in ]δ, β[, this completes the proof of Theorem 6. ■

Proof of Theorem 2.

The interval T is the union of a non-decreasing sequence of compact subintervals I_{n}. If we put δ_{n} = sup_{t∈I_{n}} inf_{x∈X} f(x, t) and β_{n} = inf_{x∈X} sup_{t∈I_{n}} f(x, t), we have clearly δ = sup_{n} δ_{n}. And Lemma 3 applied to the l.s.c. functions h_{n}(x) = sup_{t∈I_{n}} f(x, t), shows that β = sup_{n} β_{n}. Thus if ρ ∈]δ, β[, there is some n such that ρ < β_{n}. Then Theorem 6 applied to X, I_{n} and f provides θ ∈ I_{n} ⊂ T and x_{1} ∈ X as required in the statement of Theorem 2. ■

Theorem 11. Under the hypotheses of Theorem 2, there exists a non-empty open interval J ⊂ T such that, for every θ ∈ J, the function f(., θ) does not satisfy the Gm condition.

Suppose first that T = [a, b] is compact. Fix m and β′ as above. We show that the function ψ : ρ ↦ θ_{ρ} defined in the proof of theorem 6 is continuous on the interval ]δ, β′[. It is clear that K_{ρ} ⊂ K_{ρ′} for ρ < ρ′, thus that ψ is non-decreasing.

Let ρ ∈]δ, β′[ and ε > 0. Since the K_{ρ′}’s are compact and K_{ρ} = ⋂_{ρ′∈]ρ,β′[} K_{ρ′} is included in the open set W = {(x, t, t′) ∈ X × I × I : t < θ_{ρ} + ε} there exists a ρ′ ∈]ρ, β′[ such that K_{ρ′} ⊂ W, and this shows that, for ρ < ρ^{∗} < ρ′ we have θ_{ρ^{∗}} ≤ θ_{ρ′} < θ_{ρ} + ε.

Conversely, if θ_{ρ} > a, there exists some x ∈ X and some t′ such that (x, θ_{ρ}, t′) ∈ K_{ρ}. Then f_{m}(x, t′) ≥ β′, θ_{ρ} ≤ t′ and f(x, θ_{ρ}) ≤ ρ. Since the function t ↦ f(x, t) is concave with f(x, θ_{ρ}) < f(x, t′), it is increasing on [0, θ_{ρ}] and we have, for 0 < ε ≤ θ_{ρ} − a,

ρ′ = f(x, θ_{ρ} − ε) < f(x, θ_{ρ}) ≤ ρ

thus, for ρ′ < ρ^{∗} < ρ, (x, θ_{ρ} − ε, t′) ∈ K_{ρ^{∗}}, and θ_{ρ^{∗}} ≥ θ_{ρ} − ε. This completes the proof of the continuity of ψ.

Then J_{0} = ψ(]δ, β′[) is an interval of I. Moreover, for a function g : X → ℝ, there exists at most countably values which are local minimums for g since X is second-countable. And since, by lemma 10, any element of ]ρ_{0}, β′[ is a locally minimal value of some function f(., θ) for θ ∈ J_{0}, J_{0} cannot be a singleton. Thus the interior J of J_{0} is a non-empty open interval satisfying the conclusion of the Theorem.

In the general case, the interval T is the union of a nondecreasing sequence (I_{n}) of compact intervals. And we saw in the proof of Theorem 2 that the sequence (β_{n}) converges to β. Then there is some n such that β_{n} > δ ≥ δ_{n}, and the previous proof shows that there exists some nonempty open interval J ⊂ I_{n} ⊂ T such that, for every θ ∈ J, the function f(., θ) does not satisfy the Gm condition. ■

Remark 12. The unit interval I cannot be replaced in Theorem 1 by an arbitrary compact convex set T, even if f is assumed to be continuous in (x, t) and T of finite dimension.

Take for example X = T the closed unit disk of the euclidean space ℝ^{2}, and put :

f(x, t) = − ∥x − t∥^{2}

Then it is clear that t ↦ f(x, t) is concave for all x, that for every x ∈ X sup_{t∈T} f(x, t) = 0 (attained for t = x), hence that

β = inf_{x∈X} sup_{t∈T} f(x, t) = 0,

and that for every t ∈ T, inf_{x∈X} f(x, t) = −(1 + ∥t∥)^{2} (attained for ∥x∥ = 1 and ⟨x, t⟩ = − ∥x∥ . ∥t∥). Hence

δ = sup_{t∈T} inf_{x∈X} f(x, t) = −1 < β

Nevertheless, for any t, the concave function f(., t) cannot have a local minimum in the open disk ; and on the unit circle the function f(., t) agrees with the affine function x ↦ −1 − ∥t∥^{2} + 2⟨x, t⟩ which does not admit any local non global minimum. So each function f(., t) satisfies the Gm condition on X. ■

REFERENCE

[ 1 ] 0. Y. Borenshtein and V. S. Shul’man, A Minimax Theorem, Mathematical Notes Acad. Sc. USSR 50 (1991), 752-754

Jean SAINT RAYMOND Equipe d’Analyse – ESA 7084 Boîte 186 Université Paris 6 4, place Jussieu F 75252 Paris CEDEX 05