42.3. SUBGRADIENTS 1383

x∗0 (y)−φ (y)+δ < x∗0 (x0)−φ∗∗ (x0)

Thus, since this holds for all y,

φ∗ (x∗0)+δ ≤ x∗0 (x0)−φ

∗∗ (x0)

φ∗∗ (x0)+δ ≤ x∗0 (x0)−φ

∗ (x∗0)

Then

φ∗∗ (x0) ≡ sup

{x∗ (x0)−φ

∗ (x∗) ,x∗ ∈ X ′}

≥ x∗0 (x0)−φ∗ (x∗0)≥ φ

∗∗ (x0)+δ

a contradiction.The following corollary is descriptive of the situation just discussed. It says that to find

epi(φ ∗∗) it suffices to take the intersection of all closed convex sets which contain epi(φ).

Corollary 42.3.9 epi(φ ∗∗) is the smallest closed convex set containing epi(φ).

Proof: epi(φ ∗∗)⊇ epi(φ) from Theorem 42.3.8. Also epi(φ ∗∗) is closed by the proofof Theorem 42.3.4. Suppose epi(φ)⊆ K ⊆ epi(φ ∗∗) and K is convex and closed. Let

ψ (x)≡min{a : (x,a) ∈ K}.

({a : (x,a) ∈ K} is a closed subset of (−∞,∞] so the minimum exists.) ψ is also a convexfunction with epi(ψ) = K. To see ψ is convex, let λ ∈ [0,1]. Then, by the convexity of K,

λ (x,ψ (x))+(1−λ )(y,ψ (y))

= (λx+(1−λ )y,λψ (x)+(1−λ )ψ (y)) ∈ K.

It follows from the definition of ψ that

ψ (λx+(1−λ )y)≤ λψ (x)+(1−λ )ψ (y).

Thenφ∗∗ ≤ ψ ≤ φ

and so from the definitions,φ∗∗∗ ≥ ψ

∗ ≥ φ∗

which implies from the definitions and Theorem 42.3.8 that

φ∗∗ = φ

∗∗∗∗ ≤ ψ∗∗ = ψ ≤ φ

∗∗.

Therefore, ψ = φ∗∗ and epi(φ ∗∗) is the smallest closed convex set containing epi(φ) as

claimed.There is an interesting symmetry which relates δφ ,δφ

∗,φ , and φ∗.