Bourbaki

§ 5. Separation of convex sets

1. The Hahn-Banach theorem (geometric form)

Theorem 1 (Hahn-Banach)

— *Let A be an open convex non empty set of the topological vector space E and let M be a non-empty linear variety which does not meet A. Then there exists a closed hyperplane H which contains M and does not meet A.

By translation the problem can be reduced to the case 0∈A0 \in A, so that AA is absorbent. Let pp be the gauge of AA (II, p. 20) so that AA is the set of points x∈Ex \in E such that p(x)<1p(x) < 1. On the other hand, let VV be the vector subspace of EE generated by MM; thus MM is a hyperplane in VV that does not contain 00, and hence there is a unique linear form ff on VV such that MM is the set of points y∈Vy \in V for which f(y)=1f(y) = 1. The hypothesis M∩A=∅M \cap A = \varnothing implies therefore that for all y∈Vy \in V for which f(y)=1f(y) = 1, we have p(y)⩾1p(y) \geqslant 1; as ff and pp are positively homogeneous we have f(y)⩽p(y)f(y) \leqslant p(y) for all y∈Vy \in V such that f(y)>0f(y) > 0; finally as p(y)⩾0p(y) \geqslant 0 for all y∈Vy \in V, we see that f(y)⩽p(y)f(y) \leqslant p(y) for all y∈Vy \in V. By the analytical form of the Hahn-Banach theorem (II, p. 22, th. 1) there exists a linear form hh on EE which extends ff and is such that, for all x∈Ex \in E, h(x)⩽p(x)h(x) \leqslant p(x). Let HH be the hyperplane in EE with the equation h(x)=1h(x) = 1. Clearly H∩V=MH \cap V = M and H∩A=∅H \cap A = \varnothing. On the other hand the complement of HH in EE contains the open non-empty set AA, therefore HH is closed in EE (I, p. 11, corollary).

Q.E.D.

Remark 1

When 0∈M0 \in M, th. 1 can be stated as follows : there exists a continuous linear form in E, such that g(x)=0g(x) = 0 in MM and g(x)>0g(x) > 0 in AA (II, p. 8, prop. 4).

Remark 2

If we apply theorem 1 to the case where EE carries the finest locally convex topology (II, p. 25, Example 2), and if, for the sake of simplicity, we suppose that 0∈A0 \in A, then we get the following result (that superficially does not involve topology) : if AA is an absorbent convex set in the real vector space EE and if MM is a non-empty linear variety that does not meet AA, then there exists a hyperplane HH containing MM and such that AA lies on one side of HH. This result is not valid for every convex set AA (II, p. 65, exerc. 5).

2. Separation of convex sets in a topological vector space

Definition 1

— Two non-empty sets A,BA, B of a real topological vector space EE are said to be separated by a closed hyperplane HH if AA is contained in one of the closed half-spaces determined by HH and BB is contained in the other closed half-space.

Definition 2

— Two non-empty sets A,BA, B of a real topological vector space are said to be strictly separated by the closed hyperplane HH if AA is contained in one of the open half-spaces determined by HH, and BB is contained in the other open half-space.

Proposition 1

— Let AA be an open non-empty convex set and let BB be a non-empty convex set in a real topological vector space EE; if AA does not meet BB then there exists a closed hyperplane that separates AA from BB.

For the set C=A−BC = A - B is open, convex (II, p. 9, prop. 7) and non-empty, also 0∉C0 \notin C. By theorem 1 of II, p. 36, there exists a continuous linear form f≠0f \neq 0 on EE such that f(z)>0f(z) > 0 in CC. Then, for all x∈Ax \in A, and y∈By \in B, we have f(x)>f(y)f(x) > f(y). Write α=inf⁡x∈Af(x)\alpha = \inf_{x \in A} f(x); α\alpha is finite and we have f(x)≥αf(x) \geq \alpha for all x∈Ax \in A and f(y)≤αf(y) \leq \alpha for all y∈By \in B; the closed hyperplane HH with the equation f(z)=αf(z) = \alpha separates AA from BB.

Remark

— 1) The hyperplane HH does not meet AA (II, p. 15, prop. 1; if AA and BB are two convex non-empty open sets that do not meet then there exists a closed hyperplane that separates AA strictly from BB. 2) However, when BB is not open, it is not necessarily the case that there exists a closed hyperplane that separates AA strictly from BB, even if EE is of finite dimension, and even if A‾\overline{A} does not meet B‾\overline{B} (II, p. 78, exerc. 12).

Definition 3

— For a subset AA of a vector space EE, a hyperplane HH is called a support-hyperplane of AA, if HH contains at least one point of AA and all the points of AA lie on the same side of HH.

Let ff be a linear form on EE that is not identically zero; to say that the hyperplane of the equation f(x)=αf(x) = \alpha is a support hyperplane of AA means that α\alpha is either the smallest or the largest member of the set f(A)⊂Rf(A) \subset \mathbf{R}. In other words, there exists a support hyperplane of AA parallel to the hyperplane of equation f(x)=0f(x) = 0, if, and only if, one of the bounds of the set f(A)f(A) is finite and belongs to f(A)f(A).

Proposition 2

— Let AA be a non-empty compact subset of a topological vector space EE. For every closed hyperplane HH in EE, there exists a support hyperplane of AA parallel to HH.

For, if f(x)=γf(x) = \gamma is an equation of HH, where ff is a continuous linear form in EE, the restriction of ff to AA is continuous, therefore bounded and attains its bounds in AA (GT, IV, § 6.1, th. 1).

This demonstrates that there exist one or two support hyperplanes of AA parallel to HH; the first case can only arise when AA is completely contained in a hyperplane parallel to HH.

Proposition 3

— In a topological vector space EE, let AA be a closed convex set with a non-empty interior. Then every support hyperplane of AA is closed and every frontier point of AA belongs to at least one support hyperplane of AA.

Every support hyperplane of AA is closed, since all the points of AA are on the same side of the hyperplane (II, p. 15, prop. 17). Also if x0x_0 is a frontier point of AA, then x0x_0 does not belong to the open non-empty convex set A∘\overset{\circ}{A}; after th. 1 of II, p. 36 there exists a hyperplane HH that contains x0x_0 and does not meet A∘\overset{\circ}{A}. As AA is the closure of A∘\overset{\circ}{A} (II, p. 14, cor. 1 to prop. 16), it follows from prop. 17 of II, p. 15 that HH is a support hyperplane of AA.

3. Separation of convex sets in a locally convex space

Proposition 4

— Let AA be a closed non-empty convex set in a locally convex space EE and let KK be a compact non-empty convex set in EE, that does not meet AA. Then there exists a closed hyperplane HH that strictly separates AA from KK.

For there exists an open convex neighbourhood VV of 0 in EE such that A+VA + V and K+VK + V do not meet (GT, II, § 4.3, prop. 4). As A+VA + V and K+VK + V are convex and open in EE, prop. 1 of II, p. 37 shows that there exists a closed hyperplane HH that strictly separates A+VA + V from K+VK + V, and aa fortiori AA from KK.

Remark

In a Hausdorff locally convex space EE, let AA and BB be two closed non-empty convex sets that are disjoint, if EE is finite dimensional then there exists a closed hyperplane that separates AA from (II, p. 78, exerc. 13); but this conclusion is not necessarily true when EE is of infinite dimension (II, p. 78, exerc. 10 and 11).

Corollary 1

— In a locally convex space, every closed convex set AA is the intersection of the closed half-spaces which contain it.

In fact, for every point x∉Ax \notin A, there exists a closed hyperplane that separates xx strictly from AA (using prop. 4).

Corollary 2

— In a Hausdorff locally convex space, every compact convex set AA is the intersection of the closed half-spaces which contain it and which are determined by support hyperplanes of AA.

For, let x0∉Ax_0 \notin A; {x0}\{ x_0 \} is closed, therefore there exists a closed hyperplane HH which separates x0x_0 strictly from AA (prop. 4); let f(x)=αf(x) = \alpha be an equation of HH (ff a continuous linear form) and suppose that f(x)>αf(x) > \alpha for all x∈Ax \in A. If we put γ=inf⁡x∈Af(x)\gamma = \inf_{x \in A} f(x), the half-space defined by f(x)≥γf(x) \geq \gamma contains AA, is determined by the support hyperplane of equation f(x)=γf(x) = \gamma, and does not contain x0x_0; whence the corollary.

It is possible that a closed convex set that is not compact and has no interior point, in a locally convex space, does not have any closed support hyperplane (II, p. 86, exerc. 18 : cf. also V, p. 71, exerc. 11).

Corollary 3

— In a locally convex space, the closure of each linear variety MM is the intersection of the closed hyperplanes that contain MM.

For all x∉M‾x \notin \overline{M}, let HH be a closed hyperplane that separates xx strictly from M‾\overline{M};

thus M‾\overline{M} is parallel to HH; the closed hyperplane H1H_1, containing M‾\overline{M} and parallel to HH does not contain xx. The corollary follows.

Corollary 4

Let CC be a closed convex set in a locally convex space EE. A subset AA of EE is contained in CC, if, and only if, for every real valued continuous affine function uu in EE such that u(x)⩾0u(x) \geqslant 0 for all xx in CC, we have u(y)⩾0u(y) \geqslant 0 for all yy in AA.

The condition is obviously necessary. Conversely we show that it is sufficient; if a point x∈Ax \in A is not contained in CC, there exists a closed hyperplane of equation f(z)=αf(z) = \alpha separating xx strictly from CC; if we suppose for example that f(x)<αf(x) < \alpha, then the continuous affine function u=f−αu = f - \alpha contradicts the hypotheses.

Corollary 5

In a locally convex space EE, the closure of each convex cone CC of vertex 00 is the intersection of closed half-spaces containing CC determined by closed hyperplanes that pass through 00.

For C‾\overline{C} is a convex cone of vertex 00 (II, p. 13, prop. 14). For x∉C‾x \notin \overline{C}, there exists a closed hyperplane HH that separates xx strictly from C‾\overline{C}(prop. 4). It is now just necessary to apply the following lemma :

Lemma 1

— *If a cone AA, with vertex 00, is contained in an open half-space determined by a hyperplane HH, then it is contained in a closed half-space determined by a hyperplane H0H_0, that is parallel to HH and passes through 00.

Let f(z)=αf(z) = \alpha with α<0\alpha < 0 be an equation of HH, so that f(z)=0f(z) = 0 is the equation of H0H_0. If there exists z∈Az \in A such that f(z)<0f(z) < 0, then there would exist λ>0\lambda > 0, such that f(λz)=αf(\lambda z) = \alpha, and as λz∈A\lambda z \in A, this would contradict the hypothesis.

4. Approximation to convex functions

Proposition 5

Let XX be a closed convex set in a locally convex space EE. Then every lower semi-continuous convex function ff defined in XX is the upper envelope of a family of functions that are the restrictions to XX of continuous affine linear functions in EE.

For, the set A⊂E×RA \subset E \times \mathbf{R} of points (x,t)(x, t) such that x∈Xx \in X and t⩾f(x)t \geqslant f(x) is convex (II, p. 17, prop. 19) and closed, since the function (x,t)↦f(x)−t(x, t) \mapsto f(x) - t is lower semi-continuous. Then let xx be any point of XX and let a∈Ra \in \mathbf{R} be such that a<f(x)a < f(x). By cor. 1 of II, p. 38, there exists a closed hyperplane HH in E×RE \times \mathbf{R}, that contains (x,a)(x, a) and does not meet AA. Every linear continuous form on E×RE \times \mathbf{R} being of the form

(z,t)→u(z)+λt, (z, t) \to u(z) + \lambda t ,

where λ∈R\lambda \in \mathbf{R} and uu is a continuous linear form on EE, it follows that HH has an equation of the form u(z)+λt=αu(z) + \lambda t = \alpha, and as HH contains (x,a)(x, a) we have α=u(x)+λa\alpha = u(x) + \lambda a. Now the point (x,f(x))∈A(x, f(x)) \in A does not belong to HH and therefore λ≠0\lambda \neq 0. Dividing by −λ-\lambda, if necessary, we can write the equation of HH as t−a=u(z−x)t - a = u(z - x). As f(x)−a>0f(x) - a > 0, we have, therefore, f(z)>u(z−x)+af(z) > u(z - x) + a for all z∈Xz \in X and this proves the proposition.

Remark 1

It follows from prop. 5 that ff is the upper envelope of a directed increasing family of functions that are the restrictions to XX of functions which are continuous and convex in EE.

Remark 2

Suppose further that XX is a closed convex cone with vertex 0 and that ff is positively homogeneous. Then ff is the upper envelope of a family of functions which are the restrictions to XX of continuous linear forms in EE. For, let (uα)(u_\alpha) be a family of continuous affine linear functions in EE of which the restrictions to XX have ff as their upper envelope. Put uα=vα+λαu_\alpha = v_\alpha + \lambda_\alpha, where λα∈R\lambda_\alpha \in \mathbf{R}, and where vαv_\alpha is a continuous linear form in EE. We have λα=uα(0)≤f(0)=0\lambda_\alpha = u_\alpha(0) \leq f(0) = 0. On the other hand, if x∈Xx \in X, we have for every μ>0\mu > 0,

μ−1λα+vα(x)=μ−1(λα+vα(μx))=μ−1uα(μx)≤μ−1f(μx)=f(x) \mu^{-1} \lambda_\alpha + v_\alpha(x) = \mu^{-1} (\lambda_\alpha + v_\alpha(\mu x)) = \mu^{-1} u_\alpha(\mu x) \leq \mu^{-1} f(\mu x) = f(x)
therefore uα≤vα≤fu_\alpha \leq v_\alpha \leq f in XX so that ff is the upper envelope of the vαv_\alpha.

Remark 3

The restriction to XX of a continuous affine function in EE is a function that is affine in XX (i.e. both concave and convex II, p. 17); but it may be the case that there exist continuous affine functions in a compact convex set X⊂EX \subset E, that are not the restrictions to XX of continuous affine functions in EE (II, p. 78, exerc. II, c)). However :

Proposition 6

Let ff be an upper semi-continuous affine function in a compact convex set XX, of the Hausdorff locally convex space EE. Let LL be the set of restrictions to XX of continuous affine functions in EE; the set L′L' of the h∈Lh \in L such that h(x)>f(x)h(x) > f(x) for all x∈Xx \in X, is then decreasing directed and its lower envelope is equal to ff.

We may suppose that XX is non-empty. Let u,vu, v be two elements of LL, such that u(x)>f(x)u(x) > f(x) and v(x)>f(x)v(x) > f(x) for all x∈Xx \in X, and let bb be a constant that is an upper bound of uu and vv. Let UU (resp. VV) be the compact convex set of points (x,t)(x, t) of X×RX \times \mathbf{R} such that u(x)≤t≤bu(x) \leq t \leq b (resp. v(x)≤t≤bv(x) \leq t \leq b), and let FF be the set of (x,t)∈X×R(x, t) \in X \times \mathbf{R} such that t≤f(x)t \leq f(x); FF is convex and closed in X×RX \times \mathbf{R}. The convex envelope KK of U∪VU \cup V does not meet FF, since U∪VU \cup V is contained in the set of (x,t)∈X×R(x, t) \in X \times \mathbf{R} such that f(x)<tf(x) < t, a set which is convex and does not meet FF. As KK is compact (II, p. 14, prop. 15), we can separate FF strictly from KK by a closed hyperplane HH in E×RE \times \mathbf{R}. For every x∈Xx \in X, the hyperplane HH separates (x,f(x))(x, f(x)) strictly from (x,b)(x, b), and therefore meets the line {x}×R\{ x \} \times \mathbf{R} in a single point w(x)w(x); thus HH is the graph of a continuous affine function whose restriction ww to XX is a member of LL, that is a lower bound for uu and vv and that satisfies the inequality w(x)>f(x)w(x) > f(x) for all x∈Xx \in X. This proves that the set L′L' is decreasing directed. Prop. 5 of II, p. 39, applied to −f-f shows that ff is the lower envelope of L′L'.

Corollary

Let ff be a continuous affine function in XX; then there exists a sequence (hn)(h_n) of elements of LL which converges uniformly to ff in XX.

For, prop. 6 and Dini’s theorem (GT, X, § 4.1, th. 1) show that for all nn there exists hn∈Lh_n \in L such that f≤hn≤f+1/nf \leq h_n \leq f + 1/n.

Exercises

See the exercises for § 5.

Transcribed from the printed volume. Not translated.