Core idea

A Review of Vector Spaces, Metric Spaces, and Normed Vector Spaces 1.1 Vector Spaces 1.1.1 Vector Spaces: Definition and Examples 1.1.2 Basis and Dimension 1.1.3 Operations on Subsets of a Vector Space 1.1.4 Linear Subspaces of a Vector Space 1.1.5 Linear Subspace Generated by a Set 1.1.6 Sums and Direct Sums of Linear Subspaces 1.1.7 Cartesian Products and Quotient Spaces 1.1.8 Linear Operators between Vector Spaces 1.2 Metric Spaces 1.2.1 Definitions, Basic Concepts, and Properties 1.2.2 Convergence and Completeness 1.3 Normed Vector Spaces 1.3.1 Definitions, Examples, and Basic Properties 1.3.2 Convergence in Normed Spaces

Convex Sets and Convex Functions 2.1 Convex Sets 2.1.1 Basic Definitions and Elementary Properties 2.1.2 Operations on Convex Sets and Convex Hulls 2.2 Convexity of Functions 2.2.1 Descriptions and Properties of Convex Functions 2.2.2 Convexity under Differentiability 2.2.3 Operations Preserving Convexity of Functions

Convex Separation 3.1 Minkowski Functions, Sublinear Functions, and Seminorms 3.1.1 Algebraic Interior and Linear Closure 3.1.2 Minkowski Gauges 3.2 Hahn–Banach Theorems 3.2.1 Hahn–Banach theorem in real vector spaces 3.2.2 Hahn–Banach theorem in general vector spaces 3.2.3 Hahn–Banach theorem in normed vector spaces 3.3 Quotient Spaces, Codimensions, Affine Sets, and Hyperplanes 3.3.1 Quotient spaces and codimensions 3.3.2 Affine Sets and Hyperplanes 3.4 Convex Separation: Geometric Forms of Hahn–Banach Theorems 3.4.1 Convex separation in vector spaces 3.4.2 Convex separation in normed spaces

References

---

1. A Review of Vector Spaces, Metric Spaces, and Normed Vector Spaces

This chapter presents definitions, examples, and basic properties of vector spaces, normed vector spaces, and linear functions between normed vector spaces.

1.1 Vector Spaces

1.1.1 Vector Spaces: Definition and Examples

Definition 1.1. Let $X$ be a nonempty set and let $K$ be a field. We consider

the addition $+:X\times X\to X$ which maps each element $(x,y)\in X\times X$ to $x+y$ , and
the scalar multiplication $\cdot:K\times X\to X$ which maps each element $(\lambda,x)\in K\times X$ to $\lambda\cdot x$ (or simply $\lambda x$ ).

We say that $(X,+,\cdot)$ is a vector space / linear space over the field $K$ if the following properties are satisfied:

(i) $x+y=y+x$ for all $x,y\in X$ . (ii) $(x+y)+z=x+(y+z)$ for all $x,y,z\in X$ . (iii) There exists a zero element $0\in X$ such that $x+0=x$ for all $x\in X$ . (iv) For any $x\in X$ , there exists an element called the inverse of $x$ denoted by $-x$ such that $x+(-x)=0$ . (v) $\alpha(x+y)=\alpha x+\alpha y$ for all $\alpha\in K$ , $x,y\in X$ . (vi) $(\alpha+\beta)x=\alpha x+\beta x$ for all $\alpha,\beta\in K$ and $x\in X$ . (vii) $\alpha(\beta x)=(\beta\alpha)x=\alpha\beta x$ for all $\alpha,\beta\in K$ and $x\in X$ . (viii) $1x=x$ for all $x\in X$ .

An element in $X$ is called a vector, and a number $\alpha\in K$ is called a scalar. We say that $X$ is a vector space over $K$ if no confusion occurs.

In this course, we will work with the field $K=\mathbb{R}$ (the real numbers) or $K=\mathbb{C}$ (the complex numbers). Therefore, from now on we assume that $K$ is either $\mathbb{R}$ or $\mathbb{C}$ .

Example 1.2. Consider the set $K^n$ of all $n$ -tuples of elements of a field $K$ together with the addition and scalar multiplication:

x+y=(x_1+y_1,\dots,x_n+y_n),\qquad \alpha\cdot x=(\alpha x_1,\dots,\alpha x_n),

where $\alpha\in K$ , $x=(x_1,\dots,x_n)$ , and $y=(y_1,\dots,y_n)\in K^n$ . Then $(K^n,+,\cdot)$ is a vector space over $K$ . In particular, if $n=1$ , then $K$ is a vector space over itself.

Example 1.3. The set $P$ of all polynomials with real coefficients on $\mathbb{R}$ with the addition of two polynomials and the multiplication of a real number with a polynomial as usual is a vector space over $\mathbb{R}$ .

Example 1.4. Let $\Omega$ be a nonempty set. Denote by $\mathcal{F}(\Omega)$ the collection of all real-valued (resp. complex-valued) functions on $\Omega$ . Given $f,g\in\mathcal{F}(\Omega)$ and $\lambda\in\mathbb{R}$ (resp. $\lambda\in\mathbb{C}$ ), define $f+g\in\mathcal{F}(\Omega)$ and $\lambda f\in\mathcal{F}(\Omega)$ by

(f+g)(x)=f(x)+g(x),\qquad (\lambda f)(x)=\lambda f(x),\quad x\in\Omega.

Then $\mathcal{F}(\Omega)$ is a vector space over $\mathbb{R}$ (resp. $\mathbb{C}$ ).

Example 1.5. Let $s$ be the set of all sequences of real (resp. complex) numbers. Given $x=(x_n)\in s$ , $y=(y_n)\in s$ , and $\lambda\in\mathbb{R}$ (resp. $\lambda\in\mathbb{C}$ ), define

x+y=(x_n+y_n),\qquad \lambda x=(\lambda x_n).

Then $s$ is a vector space over $\mathbb{R}$ (resp. $\mathbb{C}$ ).

1.1.2 Basis and Dimension

Let $X$ be a vector space over $K$ and let $x_1,x_2,\dots,x_m$ be vectors in $X$ . A linear combination of $x_1,x_2,\dots,x_m$ is a vector in $X$ of the form

\alpha_1x_1+\cdots+\alpha_mx_m=\sum_{i=1}^m \alpha_i x_i,

where $\alpha_i\in K$ for all $i=1,\dots,m$ .

Definition 1.6. Let $M$ be a subset of a vector space $X$ . We say that $M$ is linearly independent if for any finite set $\{x_1,\dots,x_m\}\subset M$ and scalars $\alpha_1,\dots,\alpha_m\in K$ we have the implication

\sum_{i=1}^m \alpha_i x_i=0 \quad\Longrightarrow\quad \alpha_i=0\ \text{for all } i=1,\dots,m.

If a set $M$ is not linearly independent, it is said to be linearly dependent.

Definition 1.7. Let $B$ be a subset of a vector space $X$ . The set $B$ is called a basis (or Hamel basis) of $X$ if the following conditions are satisfied:

(i) $B$ is linearly independent. (ii) For any $x\in X$ , there exist $\alpha_1,\dots,\alpha_m\in K$ and $x_1,\dots,x_m\in B$ such that

x=\sum_{i=1}^m \alpha_i x_i. \qquad (1.1)

Assume that a vector space $X$ has a basis $B$ of finitely many elements; then we say that $X$ is a finite-dimensional space and the number of elements in $B$ is called the dimension of $X$ denoted by $\dim X$ (or $\dim(X)$ ). If $X$ is not finite-dimensional, then it is said to be an infinite-dimensional space and we write $\dim X=\infty$ .

Proposition 1.8. (Basis characterized by maximal linear independence) Let $B$ be a nonempty subset of a vector space $X$ . Then $B$ is a basis of $X$ if and only if both of the following conditions are satisfied:

(i) $B$ is a linearly independent set. (ii) If $M\supsetneq B$ , then $M$ is linearly dependent.

Proof. $\Rightarrow$ : Suppose that $B$ is a basis of $X$ . Obviously, (i) is satisfied. Let $M\supsetneq B$ . Fix an element $x\in M$ such that $x\notin B$ . Then by the definition of a basis, there must be $x_1,\dots,x_n\in B$ , $\alpha_1,\dots,\alpha_n\in K$ such that

x=\sum_{i=1}^n \alpha_i x_i \quad\text{or}\quad \sum_{i=1}^n \alpha_i x_i - 1\cdot x = 0.

Thus, $\{x_1,\dots,x_n,x\}$ is linearly dependent, so $M$ is linearly dependent. Therefore, (ii) is satisfied.

$\Leftarrow$ : Suppose that (i) and (ii) are satisfied. Fix any $x\in X$ . If $x\in B$ , then $x=1\cdot x$ . Consider the case where $x\notin B$ . By (ii), the set $B\cup\{x\}$ is linearly dependent, so there exists a linear combination

\alpha_0 x+\alpha_1 x_1+\cdots+\alpha_m x_m=0

such that not all $\alpha_0,\alpha_1,\dots,\alpha_m$ are zero. Since $B$ is linearly independent, we see that $\alpha_0\neq 0$ (why?). Thus,

x=-\big(\alpha_0^{-1}\alpha_1 x_1+\cdots+\alpha_0^{-1}\alpha_m x_m\big).

By definition, $B$ is a basis of $X$ . $\square$

The theorem below asserts that we can add more vectors to a linearly independent set of a vector space $X$ to obtain a basis of $X$ .

Theorem 1.9. (Extension of a linearly independent set to a basis) Let $X$ be a vector space and let $\varnothing\neq M$ be a linearly independent set in $X$ . Then there exists a basis $B$ of $X$ such that $B\supset M$ .

Proof. Denote by $\mathcal{F}$ the collection of all subsets $N$ of $X$ that are linearly independent and contain $M$ . Then $\mathcal{F}\neq\varnothing$ because $M\in\mathcal{F}$ . Given any two sets $N_1,N_2\in\mathcal{F}$ , define $N_1\le N_2$ if and only if $N_1\subset N_2$ . Then " $\le$ " defines a partial order on $\mathcal{F}$ . Assume $A\subset \mathcal{F}$ is a totally ordered subset of $\mathcal{F}$ . Let $N_0$ be the union of all sets $N$ in $A$ . Then $N_0$ is an upper bound of $A$ . Since $\mathcal{F}$ satisfies the conditions of Zorn's Lemma, in $\mathcal{F}$ there exists a maximal element $B$ . It follows from Proposition 1.8 that $B$ is a basis of $X$ that contains $M$ . $\square$

Corollary 1.10. (Existence of a basis) Every vector space $X\neq\{0\}$ has a basis.

Proof. Take $x\in X\setminus\{0\}$ and let $M=\{x\}$ . Then $M$ is linearly independent. Therefore, the conclusion follows directly from Theorem 1.9. $\square$

Remark 1.11. Suppose that $X$ is a trivial vector space, i.e., $X=\{0\}$ . By convention, the empty set is a basis of $X$ . With this convention, we can say that any vector space has a basis.

1.1.3 Operations on Subsets of a Vector Space

Definition 1.12. Let $X$ be a vector space. Consider two sets $M,N$ in $X$ and $\alpha\in K$ . We define:

(i) $M+N=\{m+n\mid m\in M,\ n\in N\}$ . (ii) $\alpha M=\{\alpha x\mid x\in M\}$ . (iii) $(-1)M=-M$ , and $M-N=M+(-N)$ .

It follows from definition that $M\pm N$ and $\alpha M$ are subsets of $X$ and that $M+N=N+M$ .

Remark 1.13. For every set $M\subset X$ , we have $2M\subset M+M$ but the reverse inclusion is generally not true. Hence, for the operations just defined, the set $\mathcal{P}^\ast (X)=\mathcal{P}(X)\setminus\{\varnothing\}$ does not have the structure of a vector space, but it is still convenient for presenting other problems.

The operations on sets introduced in this section provide convenient tools to define many important notions in what follows.

Definition 1.14. Let $M$ be a subset of a vector space $X$ over a field $K$ (either $\mathbb{R}$ or $\mathbb{C}$ ).

(i) The set $M$ is said to be balanced if $\lambda M\subset M$ whenever $\lambda\in K$ and $|\lambda|\le 1$ . (ii) The set $M\subset X$ is said to be absorbing if for every $x\in X$ , there exists $t>0$ such that $x\in sM$ for every real $s\ge t$ .

1.1.4 Linear Subspaces of a Vector Space

Definition 1.15. Let $(X,+,\cdot)$ be a vector space over a field $K$ and let $Y$ be a subset of $X$ . The set $Y$ is said to be a linear subspace of $X$ if:

(i) $0\in Y$ . (ii) $a+b\in Y$ for all $a,b\in Y$ . (iii) $\lambda a\in Y$ for all $\lambda\in K$ and $a\in Y$ .

Suppose that $(X,+,\cdot)$ is a vector space and $Y$ is a linear subspace of $X$ . Consider the addition as a function from $Y\times Y$ to $Y$ , and the scalar multiplication as a function from $K\times Y$ to $Y$ . Then $(Y,+,\cdot)$ is also a vector space over $K$ .

The proposition below follows directly from definitions.

Proposition 1.16. (Subspace test) Let $Y$ be a nonempty subset of a vector space $X$ over a field $K$ . Then $Y$ is a linear subspace of $X$ if and only if:

(i) $Y+Y\subset Y$ (i.e., $Y$ is closed under addition). (ii) $\alpha Y\subset Y$ for all $\alpha\in K$ (i.e., $Y$ is closed under scalar multiplication).

In practice, to check if a nonempty set $Y$ is a vector space, people usually embed it into a known vector space and then check conditions (i) and (ii) in Proposition 1.16.

Example 1.17. The set $\ell^1$ consisting of all real or complex sequences $x=(x_n)$ such that $\sum_{n=1}^\infty |x_n|<\infty$ is a subspace of the vector space $s$ considered in Example 1.5.

Example 1.18. Denote by $C[a,b]$ ( $a<b$ ) the set of all continuous functions on $[a,b]$ with real (resp. complex) values. Then $C[a,b]$ is a subset of $\mathcal{F}(\Omega)$ , where $\Omega=[a,b]$ , considered in Example 1.4. We can easily show that $C[a,b]$ is a linear subspace of $\mathcal{F}[a,b]$ . Therefore, $C[a,b]$ is a vector space with the addition and scalar multiplication given in Example 1.4 for $\Omega=[a,b]$ .

Remark 1.19. Let us identify each element $x=(x_1,\dots,x_n)\in K^n$ with a function $f_x:\{1,\dots,n\}\to K$ , where $f_x(i)=x_i$ for $i=1,\dots,n$ . Then we can identify $K^n$ with $\mathcal{F}(\Omega)$ , where $\Omega=\{1,2,\dots,n\}$ . Similarly, we can identify $s$ with $\mathcal{F}(\mathbb{N})$ . In the rest of the book, we will consider different vector spaces as particular cases of $\mathcal{F}(\Omega)$ or linear subspaces of $\mathcal{F}(\Omega)$ .

1.1.5 Linear Subspace Generated by a Set

Proposition 1.20. (Intersection of subspaces is a subspace) The intersection of a family of linear subspaces of a vector space $X$ is also a linear subspace of $X$ .

Proof. Let $\{Y_\alpha\}_{\alpha\in I}$ be a family of linear subspaces of $X$ . Set

Y=\bigcap_{\alpha\in I} Y_\alpha.

The set $Y$ is nonempty because it contains the zero vector. Take any $x,y\in Y$ . Then $x,y\in Y_\alpha$ , thus $x+y\in Y_\alpha$ for all $\alpha\in I$ . Since every $Y_\alpha$ is a linear subspace, we have

x+y\in \bigcap_{\alpha\in I} Y_\alpha=Y.

It is similar to show that $Y$ is closed under scalar multiplication. Therefore, $Y$ is a linear subspace of $X$ . $\square$

Definition 1.21. Let $A$ be a subset of a vector space $X$ . The intersection of all linear subspaces of $X$ containing $A$ is said to be the linear subspace generated by $A$ or the span of $A$ . It is denoted by $\langle A\rangle$ , $\operatorname{span}A$ , or $\operatorname{lin}A$ .

According to the definition, $\operatorname{span}A$ is the smallest linear subspace of $X$ containing the set $A$ .

Theorem 1.22. (Span equals the set of all finite linear combinations) Let $X$ be a vector space. The subspace generated by a subset $A$ of $X$ is the set of all linear combinations of elements of $A$ .

Proof. Let $Y$ be the set of all linear combinations of elements of $A$ , i.e.,

Y=\left\{\sum_{i=1}^m \alpha_i x_i \ \middle|\ \alpha_i\in K,\ x_i\in A,\ m\in\mathbb{N}\right\}.

We can easily show that $Y$ is a linear subspace of $X$ . Since $A\subset Y$ , we see $\operatorname{span}A\subset Y$ . To prove the reverse inclusion, observe that if $x_i\in A$ and $\alpha_i\in K$ for all $i=1,\dots,m$ , then $\sum_{i=1}^m \alpha_i x_i\in \operatorname{span}A$ because $\operatorname{span}A$ is a linear subspace of $X$ . Therefore, $Y\subset \operatorname{span}A$ and hence $Y=\operatorname{span}A$ . $\square$

1.1.6 Sums and Direct Sums of Linear Subspaces

Proposition 1.23. (Sum of subspaces equals span of the union) Let $M$ and $N$ be two linear subspaces of a vector space $X$ . Then $M+N$ is also a subspace of $X$ . Furthermore, we have the representation

M+N=\langle M\cup N\rangle.

Proof. It is straightforward to show that $M+N$ is a linear subspace of $X$ . By definition we have $M\subset \langle M\cup N\rangle$ and $N\subset \langle M\cup N\rangle$ . Thus $M+N\subset \langle M\cup N\rangle$ because $\langle M\cup N\rangle$ is a linear subspace.

Since $0\in M$ and $0\in N$ , we see that $M\subset M+N$ and $N\subset M+N$ . Then $M\cup N\subset M+N$ . This implies $\langle M\cup N\rangle\subset M+N$ by the definition of $\langle M\cup N\rangle$ and the fact that $M+N$ is a linear subspace of $X$ containing $M\cup N$ . $\square$

Definition 1.24. Let $X$ be a vector space and let $M,N$ be two linear subspaces of $X$ . If $Y=M+N$ and $M\cap N=\{0\}$ , then $Y$ is called the direct sum of $M$ and $N$ denoted $Y=M\oplus N$ .

Theorem 1.25. (Characterization of direct sums) Let $M$ and $N$ be two linear subspaces of a vector space $X$ and let $Y$ be a subset of $X$ . Then $Y=M\oplus N$ if and only if any element $y\in Y$ has a unique representation $y=a+b$ for $a\in M$ and $b\in N$ .

Proof. $\Rightarrow$ : Assume $Y=M\oplus N$ and $y=a+b=a'+b'$ , where $a,a'\in M$ and $b,b'\in N$ . Then $a-a'=b'-b$ . Since $a-a'\in M$ and $b'-b\in N$ , we see that

a-a'=b'-b\in M\cap N=\{0\}.

Thus, $a=a'$ and $b=b'$ .

$\Leftarrow$ : Suppose that each element $y\in Y$ has a unique representation $y=a+b$ with $a\in M$ and $b\in N$ . We obviously have $Y=M+N$ . Assume $x\in M\cap N$ . Then we can write $x=x+0=0+x$ . Due to the uniqueness of the representation, we have $x=0$ , implying $M\cap N=\{0\}$ . Therefore, $Y=M\oplus N$ . $\square$

1.1.7 Cartesian Products and Quotient Spaces

Definition 1.26. Let $X_1,\dots,X_m$ be $m$ vector spaces over the same field $K$ . Denote by $X$ the Cartesian product of these vector spaces, i.e.,

X=X_1\times\cdots\times X_m.

For any two elements $x=(x_1,\dots,x_m)$ , $y=(y_1,\dots,y_m)$ in $X$ and $\alpha\in K$ , define

x+y=(x_1+y_1,\dots,x_m+y_m),\qquad \alpha x=(\alpha x_1,\dots,\alpha x_m).

It can be shown that with these two operations, $X$ becomes a vector space over $K$ which is called the product space (or direct product) of the $m$ vector spaces $X_1,\dots,X_m$ .

Let $X$ be a vector space over a field $K$ and let $Y$ be a linear subspace of $X$ . Define the binary relation $R$ on $X$ by

x\,R\,u \quad\text{if and only if}\quad x-u\in Y.

We can check that $R$ is an equivalence relation on $X$ . For any $x\in X$ , denote by $[x]$ the equivalence class of $x$ . Then

[x]=\{u\in X\mid u-x\in Y\}=\{u\in X\mid u\in x+Y\}=x+Y.

Denote by $X/Y$ the set of all equivalence classes:

X/Y=\{x+Y\mid x\in X\}.

For $x,u\in X$ and $\lambda\in K$ , define the addition and the scalar multiplication:

(x+Y)+(u+Y)=(x+u)+Y,\qquad \lambda(x+Y)=\lambda x+Y. \qquad (1.2)

We can check that these operations are well-defined.

Definition 1.27. Let $Y$ be a linear subspace of a vector space $X$ . Then $X/Y$ with the addition and scalar multiplication defined in (1.2) is a vector space, which is called a quotient vector space. The dimension of $X/Y$ is called the codimension of $Y$ denoted by $\operatorname{codim}Y$ (or $\operatorname{codim}(Y)$ ), i.e.,

\operatorname{codim}Y=\dim(X/Y).

1.1.8 Linear Operators between Vector Spaces

Definition 1.28. Let $X$ and $Y$ be two vector spaces over a field $K$ . A function $T:X\to Y$ is called a linear operator (or a linear transformation) if:

(i) $T(x+u)=T(x)+T(u)$ for all $x,u\in X$ . (ii) $T(\alpha x)=\alpha T(x)$ for all $\alpha\in K$ and $x\in X$ .

For simplicity, for $x\in X$ we also use $Tx$ to denote $T(x)$ .

It follows from definition that a function $T:X\to Y$ between vector spaces $X$ and $Y$ is a linear operator if and only if

T(\alpha x+\beta u)=\alpha T(x)+\beta T(u)\quad\text{for all }\alpha,\beta\in K,\ x,u\in X.

Let $X$ and $Y$ be vector spaces over a field $K$ and let $T:X\to Y$ be a linear operator. The set $\operatorname{im}T=T(X)$ is called the image of $T$ , and the set $\ker T=T^{-1}(0)$ is called the kernel of $T$ . If $T$ is a bijection, we say that it is a linear isomorphism and the spaces $X$ and $Y$ are said to be isomorphic, and we write $X\cong Y$ .

Proposition 1.29. (Images and preimages of subspaces) Let $T:X\to Y$ be a linear operator between vector spaces $X$ and $Y$ .

(i) If $M$ is a linear subspace of $X$ , then $T(M)$ is a linear subspace of $Y$ . (ii) If $N$ is a linear subspace of $Y$ , then $T^{-1}(N)$ is a linear subspace of $X$ .

In particular, $\ker T$ is a linear subspace of $X$ , and $\operatorname{im}T$ is a linear subspace of $Y$ .

Theorem 1.30. (Isomorphism theorem) Let $T:X\to Y$ be a linear operator between vector spaces $X$ and $Y$ . Then

\operatorname{im}T \cong X/\ker T.

In particular,

\dim(\operatorname{im}T)=\operatorname{codim}(\ker T).

Now, assume that $S,T:X\to Y$ are two linear operators and $\alpha\in K$ . We define $S+T:X\to Y$ and $\alpha S:X\to Y$ by

(S+T)(x)=S(x)+T(x),\qquad (\alpha S)(x)=\alpha S(x),

where $x\in X$ . It can be shown that $S+T$ and $\alpha T$ are linear operators from $X$ to $Y$ . Denote by $L(X,Y)$ the set of all linear operators from $X$ to $Y$ . Then with the above-defined operations, $L(X,Y)$ forms a vector space.

---

1.2 Metric Spaces

1.2.1 Definitions, Basic Concepts, and Properties

Definition 1.31. Let $X$ be a nonempty set. A function $d:X\times X\to\mathbb{R}$ is called a metric on $X$ if the following hold for all $x,y,z\in X$ :

(1) $d(x,y)\ge 0$ , and $d(x,y)=0$ if and only if $x=y$ . (2) $d(x,y)=d(y,x)$ . (3) $d(x,z)\le d(x,y)+d(y,z)$ (the triangle inequality).

The set $X$ together with the metric $d$ is called a metric space and is denoted by $(X,d)$ . If the metric $d$ has been specified on $X$ so that no confusion will occur, we can say simply that $X$ is a metric space.

The concepts of open and closed balls have been known in the plane and in space. These concepts can also be defined in metric spaces.

Definition 1.32 (open and closed balls in a metric space). Let $(X,d)$ be a metric space.

(i) The open ball in $X$ of center $x_0$ and radius $r$ is the set

B(x_0;r):=\{x\in X\mid d(x,x_0)<r\}.

(ii) The closed ball in $X$ of center $x_0$ and radius $r$ is the set

B'(x_0;r):=\{x\in X\mid d(x,x_0)\le r\}.

Definition 1.33. A subset $A$ of a metric space $X$ is open if for each $a\in A$ , there exists an open ball $B(a;\delta)$ such that $B(a;\delta)\subset A$ .

Proposition 1.34. (Open balls are open sets) In any metric space, an open ball is an open set.

Theorem 1.35. (Basic properties of open sets) Let $X$ be a metric space. The following hold:

(i) $\varnothing$ is open. (ii) $X$ is open. (iii) The union of any collection of open subsets of $X$ is open. (iv) The intersection of a finite number of open subsets of $X$ is open.

Definition 1.36. A subset $F$ of a metric space $X$ is called closed if its complement $F^c=X\setminus F$ is open.

Proposition 1.37. (Closed balls are closed sets) In any metric space, a closed ball is a closed set.

Proposition 1.38. (Basic properties of closed sets) Let $X$ be a metric space. The following hold:

(i) $\varnothing$ is closed. (ii) $X$ is closed. (iii) The intersection of any collection of closed subsets of $X$ is closed. (iv) The union of a finite number of closed subsets of $X$ is closed.

Definition 1.39. Let $E$ be a subset of a metric space $X$ . The interior of $E$ , denoted by $\operatorname{int}(E)$ or $E^\circ$ , is defined as the union of all open sets contained in $E$ :

\operatorname{int}(E)=\bigcup_{\substack{G\subset E\\ G\ \text{open}}} G.

Remark 1.40. Let $X$ be a metric space and let $E$ be a subset of $X$ . It follows from definition that:

(i) $\operatorname{int}(E)$ is open. (ii) If $G$ is open and $G\subset E$ , then $G\subset \operatorname{int}(E)$ . (iii) $\operatorname{int}(E)\subset E$ .

Therefore, $\operatorname{int}(E)$ is the largest open set contained in $E$ .

Proposition 1.41. (Basic properties of the interior operator) Let $A,B\subset X$ , where $X$ is a metric space. Then:

(i) $A\subset B$ implies $A^\circ\subset B^\circ$ . (ii) $A^\circ=A$ if and only if $A$ is open. (iii) $(A^\circ)^\circ=A^\circ$ . (iv) $(A\cap B)^\circ=A^\circ\cap B^\circ$ .

Proposition 1.42. (Interior characterized by existence of a ball) Let $X$ be a metric space, let $a\in X$ , and let $E\subset X$ . Then

a\in \operatorname{int}(E)\ \Longleftrightarrow\ \exists\,\delta>0\ \text{such that } B(a;\delta)\subset E.

Proof. Suppose that $a\in \operatorname{int}(E)$ . By definition, $a\in G$ for some open set $G\subset E$ . Since $G$ is open and $a\in G$ , there exists $\delta>0$ such that $B(a;\delta)\subset G$ . Then $B(a;\delta)\subset E$ .

Now, suppose that there exists $\delta>0$ such that $B(a;\delta)\subset E$ . Since $B(a;\delta)$ is an open set, we see that $B(a;\delta)\subset \operatorname{int}(E)$ . Then $a\in \operatorname{int}(E)$ because we always have $a\in B(a;\delta)$ . $\square$

Definition 1.43. Let $E$ be a subset of a metric space $(X,d)$ . The closure of $E$ , denoted by $\overline{E}$ , is the intersection of all closed sets that contain $E$ .

Remark 1.44. Let $X$ be a metric space and let $E$ be a subset of $X$ . It follows from definition that:

(i) $\overline{E}$ is closed. (ii) If $F$ is closed and $E\subset F$ , then $\overline{E}\subset F$ . (iii) $E\subset \overline{E}$ .

Therefore, $\overline{E}$ is the smallest closed set containing $E$ .

Proposition 1.45. (Basic properties of the closure operator) Let $A,B\subset X$ . Then:

(i) $A\subset B$ implies $\overline{A}\subset \overline{B}$ . (ii) $\overline{A}=A$ if and only if $A$ is closed. (iii) $\overline{\overline{A}}=\overline{A}$ . (iv) $\overline{A\cup B}=\overline{A}\cup \overline{B}$ .

Proof. (i), (ii), and (iii) are trivial. (iv) Obviously, $A\cup B\subset \overline{A}\cup \overline{B}$ . Since $\overline{A}\cup \overline{B}$ is closed, by (i) we get $\overline{A\cup B}\subset \overline{A}\cup \overline{B}$ . Since $A\subset A\cup B$ , one has $\overline{A}\subset \overline{A\cup B}$ . Similarly, $\overline{B}\subset \overline{A\cup B}$ . Thus, $\overline{A}\cup \overline{B}\subset \overline{A\cup B}$ , which completes the proof. $\square$

Proposition 1.46. (Closure characterized by ball intersections) Let $(X,d)$ be a metric space and let $E$ be a subset of $X$ . For any element $a\in X$ , the following are equivalent:

(i) $a\in \overline{E}$ . (ii) For any $r>0$ , one has $B(a;r)\cap E\neq\varnothing$ .

Proof. Suppose that $a\in \overline{E}$ . By contradiction, suppose that there exists $r_0>0$ such that $B(a;r_0)\cap E=\varnothing$ . Then

E\subset [B(a;r_0)]^c,

which is a closed set. Thus, $\overline{E}\subset [B(a;r_0)]^c$ because $\overline{E}$ is the smallest closed set that contains $E$ . This is a contradiction because $a\in \overline{E}$ and $a\in B(a;r_0)$ .

Conversely, suppose that (ii) is satisfied, which means that for any $r>0$ , one has $B(a;r)\cap E\neq\varnothing$ . We will show that $a\in \overline{E}$ . Suppose by contradiction that $a\notin \overline{E}$ . Since $\overline{E}$ is closed, there exists $r_0>0$ such that

B(a;r_0)\subset (\overline{E})^c \subset E^c.

Then $B(a;r_0)\cap E=\varnothing$ , which is a contradiction. $\square$

1.2.2 Convergence and Completeness

Definition 1.47. Let $(X,d)$ be a metric space. A sequence $(x_n)$ of points in $X$ is said to converge to a point $a\in X$ if for each $\varepsilon>0$ , there exists $N\in\mathbb{N}$ such that

d(x_n,a)<\varepsilon\quad\text{for all } n\ge N.

From the definition we see that a sequence $(x_n)$ of points in $X$ converges to $a\in X$ if and only if the sequence of real numbers $(d(x_n,a))$ converges to $0$ in $\mathbb{R}$ . When the sequence $(x_n)$ converges to $a$ we write

\lim_{n\to\infty} x_n = a.

Lemma 1.48. Let $\ell\ge 0$ . If $\ell<\varepsilon$ whenever $\varepsilon>0$ , then $\ell=0$ .

Proof. Assume by contradiction that $\ell>0$ . Then for $\varepsilon=\ell/2$ , one has $\varepsilon<\ell$ . This is a contradiction. $\square$

Proposition 1.49. (Uniqueness of limits) A sequence $(x_n)$ in a metric space $X$ has at most one limit.

Proof. Assume by contradiction that $(x_n)$ converges to $a$ and $b$ . Then for any $\varepsilon>0$ , there exist $N_1$ and $N_2$ such that

d(x_n,a)<\varepsilon/2\ \text{for all } n\ge N_1,\qquad d(x_n,b)<\varepsilon/2\ \text{for all } n\ge N_2.

Choose $N:=\max\{N_1,N_2\}$ . Then

d(a,b)\le d(a,x_N)+d(x_N,b)<\varepsilon/2+\varepsilon/2=\varepsilon.

Since $\varepsilon>0$ is arbitrary, $d(a,b)=0$ and $a=b$ . $\square$

Definition 1.50. A subset $A$ of a metric space $X$ is bounded if there exists a ball $B(a;r)$ such that $A\subset B(a;r)$ . Therefore, a sequence $(x_n)$ is bounded if the set $\{x_n\mid n\in\mathbb{N}\}$ is bounded.

Proposition 1.51. (Convergent sequences are bounded) Any convergent sequence in a metric space is bounded.

Proof. Suppose $(x_n)$ converges to $a$ . Then for $\varepsilon=1$ , there exists $N$ such that $d(x_n,a)<1$ for all $n\ge N$ . This means $x_n\in B(a;1)$ for all $n\ge N$ . Define

r:=\max\{d(x_1,a),\dots,d(x_{N-1},a),1\}.

Then

\{x_n\mid n\in\mathbb{N}\}\subset B'(a;r),

and hence the sequence is bounded. $\square$

Proposition 1.52. (Closure characterized by convergent sequences) Let $X$ be a metric space and let $A$ be a subset of $X$ . Then

a\in \overline{A}\ \Longleftrightarrow\ \exists\ \text{a sequence }(a_n)\subset A\text{ with }a_n\to a.

Proof. Suppose $a\in \overline{A}$ . By Proposition 1.46, for any $r>0$ one has $B(a;r)\cap A\neq\varnothing$ . In particular, for every $n\in\mathbb{N}$ one has $B(a;1/n)\cap A\neq\varnothing$ . For each $n\in\mathbb{N}$ choose $a_n\in B(a;1/n)\cap A$ . Then $a_n\in A$ and $0\le d(a_n,a)<1/n\to 0$ . Hence $a_n\to a$ .

Conversely, suppose there exists a sequence $(a_n)\subset A$ with $a_n\to a$ . We will show $a\in \overline{A}$ using Proposition 1.46. Fix any $r>0$ . By convergence, there exists $N\in\mathbb{N}$ such that $d(a_n,a)<r$ for all $n\ge N$ . Then $a_n\in B(a;r)$ for all $n\ge N$ , so $A\cap B(a;r)\neq\varnothing$ . Thus $a\in\overline{A}$ . $\square$

Proposition 1.53. (Closed sets characterized by sequences) Let $A$ be a subset of a metric space $X$ . Then $A$ is closed if and only if whenever $(a_n)$ is a sequence in $A$ that converges to $a$ , we have $a\in A$ .

Proof 1. Suppose that $A$ is closed. Take any sequence $(a_n)$ in $A$ that converges to $a$ . By Proposition 1.52, $a\in \overline{A}$ . Since $A$ is closed, $\overline{A}=A$ , so $a\in A$ .

Conversely, suppose that whenever $(a_n)$ is a sequence in $A$ that converges to $a$ , we have $a\in A$ . We will show that $A$ is closed, or equivalently $\overline{A}=A$ . It is obvious that $A\subset \overline{A}$ , so we only need to show $\overline{A}\subset A$ . Take any $x\in\overline{A}$ . By Proposition 1.52, there exists a sequence $(a_n)\subset A$ that converges to $x$ . By the hypothesis, $x\in A$ . So $\overline{A}\subset A$ , and hence $\overline{A}=A$ and $A$ is closed. $\square$

Proposition 1.54. Let $A$ be a subset of a metric space $X$ . Then $A$ is closed if and only if whenever $(a_n)$ is a sequence in $A$ converging to $a$ , we have $a\in A$ .

Proof 2. Suppose $A$ is closed and $(a_n)$ is a sequence in $A$ that converges to $a$ . Assume by contradiction that $a\notin A$ . Then $a\in A^c$ . Because $A^c$ is open, there exists $\varepsilon>0$ such that $B(a;\varepsilon)\subset A^c$ . Since $a_n\to a$ , there exists $N$ such that $d(a_n,a)<\varepsilon$ for all $n\ge N$ . Then $a_n\in B(a;\varepsilon)\subset A^c$ for all $n\ge N$ , contradicting $a_n\in A$ .

Conversely, suppose that whenever $(a_n)$ is a sequence in $A$ converging to $a$ , we have $a\in A$ . Let us show that $A$ is closed, or equivalently, $A^c$ is open. Assume by contradiction that $A^c$ is not open. Then there exists $a\in A^c$ such that $B(a;\varepsilon)\cap A\neq\varnothing$ for every $\varepsilon>0$ . For each $n\in\mathbb{N}$ , let $\varepsilon=1/n>0$ , so there exists $a_n\in B(a;1/n)\cap A$ . It follows that $d(a_n,a)<1/n$ and $a_n\in A$ for all $n$ . However, $(a_n)$ converges to $a\notin A$ , a contradiction. $\square$

Definition 1.55 (Cauchy sequence). Let $(X,d)$ be a metric space. A sequence $(x_n)$ in $X$ is called a Cauchy sequence if for each $\varepsilon>0$ , there exists $N\in\mathbb{N}$ such that $d(x_m,x_n)<\varepsilon$ for all $m,n\ge N$ .

Proposition 1.56. (Convergent sequences are Cauchy) If $(x_n)$ is a convergent sequence in a metric space, then it is a Cauchy sequence.

Proof. Let $(x_n)$ be a convergent sequence with $\lim_{n\to\infty} x_n=a$ . Then for any $\varepsilon>0$ , there exists $N$ such that

d(x_n,a)<\varepsilon/2\quad\text{for all } n\ge N.

Then for any $m,n\ge N$ ,

d(x_m,x_n)\le d(x_m,a)+d(a,x_n)<\varepsilon/2+\varepsilon/2=\varepsilon.

Thus, $(x_n)$ is a Cauchy sequence. $\square$

Proposition 1.57. (Cauchy sequences are bounded) A Cauchy sequence in a metric space is bounded.

Proof. Let $(x_n)$ be a Cauchy sequence. Then for $\varepsilon=1$ , there exists $N$ such that $d(x_m,x_n)<1$ for all $m,n\ge N$ . In particular, $d(x_n,x_N)<1$ for all $n\ge N$ , i.e., $x_n\in B(x_N;1)$ for all $n\ge N$ . Let

r=\max\{d(x_1,x_N),\dots,d(x_{N-1},x_N),1\}.

Then $x_n\in B'(x_N;r)$ for all $n\in\mathbb{N}$ , and hence the sequence is bounded. $\square$

Definition 1.58 (subsequences). Let $(x_n)$ be a sequence in a metric space $X$ . Consider a sequence of increasing positive integers

n_1<n_2<n_3<\cdots.

Then $(x_{n_k})_{k}$ is a sequence in $X$ and it is called a subsequence of $(x_n)$ .

Example 1.59. Consider the sequence $x_n=(-1)^n$ . Then $(x_{2k})$ is a subsequence of $(x_n)$ and $x_{2k}=1$ for all $k$ . Similarly, $(x_{2k+1})$ is also a subsequence of $(x_n)$ and $x_{2k+1}=-1$ for all $k$ .

Lemma 1.60. (Subsequence index bound) Let $(n_k)_k$ be a sequence of positive integers with $n_1<n_2<\cdots$ . Then $n_k\ge k$ for all $k=1,2,\dots$ .

Proof. By induction. When $k=1$ , $n_1\ge 1$ since $n_1$ is a positive integer. Assume $n_k\ge k$ . Then $n_{k+1}>n_k\ge k$ , hence $n_{k+1}\ge k+1$ . $\square$

Proposition 1.61. (Subsequences of convergent sequences converge to the same limit) If a sequence $(x_n)$ converges to $a$ , then any subsequence $(x_{n_k})$ of $(x_n)$ also converges to $a$ .

Proof. Since $x_n\to a$ , for any $\varepsilon>0$ there exists $N$ such that $d(x_n,a)<\varepsilon$ for all $n\ge N$ . Let $K:=N$ . Then for any $k\ge K$ , we have $n_k\ge n_K\ge K=N$ , hence $d(x_{n_k},a)<\varepsilon$ . Thus $x_{n_k}\to a$ . $\square$

Proposition 1.62. (Cauchy sequence with a convergent subsequence converges) A Cauchy sequence in a metric space that has a convergent subsequence is convergent.

Proof. Let $(x_n)$ be a Cauchy sequence. Then for any $\varepsilon>0$ , there exists $N$ such that

d(x_n,x_m)\le \varepsilon/2\quad\text{for all }m,n\ge N.

Let $(x_{n_k})$ be a subsequence of $(x_n)$ that converges to $a$ . Then there exists $K$ such that

d(x_{n_k},a)<\varepsilon/2\quad\text{for all }k\ge K.

Choose an index $n_\ell>N$ such that $d(x_{n_\ell},a)<\varepsilon/2$ . Then for any $n\ge N$ ,

d(x_n,a)\le d(x_n,x_{n_\ell})+d(x_{n_\ell},a)<\varepsilon.

Therefore, $x_n\to a$ . $\square$

Definition 1.63 (complete metric spaces). A metric space $(X,d)$ is said to be complete if every Cauchy sequence in $X$ is convergent. That means: if $(x_n)$ is a Cauchy sequence in $X$ , then there exists $x\in X$ such that $\lim_{n\to\infty} x_n=x$ .

A subset $E\subset X$ is called complete if $(E,d)$ is a complete metric space.

Proposition 1.64. (Completeness and closedness) Let $X$ be a metric space and let $E\subset X$ . Then:

(i) If $E$ is complete, then it is closed. (ii) If $X$ is complete and $E$ is closed, then $E$ is complete.

Theorem 1.65. (Completeness of R^k) $\mathbb{R}^k$ is complete for any positive integer $k$ .

---

1.3 Normed Vector Spaces

1.3.1 Definitions, Examples, and Basic Properties

Definition 1.66. Let $X$ be a vector space over a field $K$ (either $\mathbb{R}$ or $\mathbb{C}$ ). A function $\|\cdot\|:X\to\mathbb{R}$ is called a norm on $X$ if the following conditions hold for all $x,y\in X$ and $\lambda\in K$ :

(i) $\|x\|\ge 0$ , and $\|x\|=0$ if and only if $x=0$ . (ii) $\|\lambda x\|=|\lambda|\,\|x\|$ . (iii) $\|x+y\|\le \|x\|+\|y\|$ (the triangle inequality).

If $\|\cdot\|$ is a norm on $X$ , then $(X,\|\cdot\|)$ is called a normed vector space (or a normed linear space) over $K$ . We can also say simply that $X$ is a normed space over $K$ if no confusion occurs. If the field $K$ is $\mathbb{R}$ (resp. $\mathbb{C}$ ), then we say that $X$ is a real (resp. complex) normed space. The real number $\|x\|$ is called the norm of the vector $x\in X$ .

Proposition 1.67. (Norm induces a metric and conversely) Let $X$ be a normed space over $K$ . Define $d:X\times X\to\mathbb{R}$ by

d(x,y)=\|x-y\|\quad\text{for }(x,y)\in X\times X. \qquad (1.3)

Then $(X,d)$ is a metric space. In addition:

(i) $d(x+z,y+z)=d(x,y)$ for all $x,y,z\in X$ . (ii) $d(\lambda x,\lambda y)=|\lambda|\,d(x,y)$ for all $x,y\in X$ and $\lambda\in K$ .

Conversely, let $X$ be a vector space and let $d$ be a metric on $X$ such that both (i) and (ii) are satisfied. Define

\|x\|=d(x,0)\quad\text{for }x\in X.

Then $(X,\|\cdot\|)$ is a normed space.

Proof. Fix any $x,y,z\in X$ and $\lambda\in K$ . By Definition 1.66(i), we have $d(x,y)=\|x-y\|\ge 0$ , and $d(x,y)=0$ if and only if $x-y=0$ , i.e., $x=y$ . Using Definition 1.66(ii) with $\lambda=-1$ gives

d(x,y)=\|x-y\|=\|(-1)(y-x)\|=|-1|\,\|y-x\|=\|y-x\|=d(y,x).

The triangle inequality for $d$ is also satisfied because

d(x,z)=\|x-z\|=\|x-y+y-z\|\le \|x-y\|+\|y-z\|=d(x,y)+d(y,z)

by Definition 1.66(iii). We also have:

d(x+z,y+z)=\|(x+z)-(y+z)\|=\|x-y\|=d(x,y),

d(\lambda x,\lambda y)=\|\lambda x-\lambda y\|=\|\lambda(x-y)\|=|\lambda|\,\|x-y\|.

The converse implication is left for the reader as an exercise. $\square$

Proposition 1.68. (Reverse triangle inequality) Let $(X,\|\cdot\|)$ be a normed space. Then

\big|\|x\|-\|y\|\big|\le \|x-y\|\quad\text{for all }x,y\in X. \qquad (1.4)

Proof. Fix any $x,y\in X$ and observe by the triangle inequality that

\|x\|=\|(x-y)+y\|\le \|x-y\|+\|y\|,

which implies $\|x\|-\|y\|\le \|x-y\|$ . By changing the role of $x$ and $y$ , we have

\|y\|-\|x\|\le \|y-x\|=\|x-y\|.

This implies (1.4). $\square$

Example 1.69. Consider the vector space $K^n$ of all $n$ -tuples of real (or complex) numbers from Example 1.2. Given any $x\in K^n$ , define

\|x\|_2=\left(\sum_{k=1}^n |x_k|^2\right)^{1/2},\qquad \|x\|_1=\sum_{k=1}^n |x_k|,\qquad \|x\|_\infty=\max_{k=1,\dots,n} |x_k|.

These are three norms on $K^n$ . The norm $\|\cdot\|_2$ is called the Euclidean norm in $K^n$ , and $(K^n,\|\cdot\|_2)$ is called an $n$ -dimensional Euclidean space. If $n=1$ , then $K=\mathbb{R}$ (or $K=\mathbb{C}$ ) and $\|x\|_2=\|x\|_1=\|x\|_\infty$ , which is the absolute value (or complex modulus) of the number $x$ .

Example 1.70. Consider the set $\ell^\infty$ of all bounded sequences of real (or complex) numbers. Then $\ell^\infty$ is a linear subspace of the vector space $s$ from Example 1.5. Given any $x=(x_n)\in \ell^\infty$ , define

\|x\|=\sup_{n\in\mathbb{N}} |x_n|.

Then $\|\cdot\|$ is a norm on $\ell^\infty$ and thus $(\ell^\infty,\|\cdot\|)$ is a normed space. To verify the triangle inequality, take any $x=(x_n)$ and $y=(y_n)$ in $\ell^\infty$ . By the triangle inequality for absolute value,

|x_n+y_n|\le |x_n|+|y_n|\le \sup_{n\in\mathbb{N}}|x_n|+\sup_{n\in\mathbb{N}}|y_n|=\|x\|+\|y\|

for all $n\in\mathbb{N}$ . This implies

\|x+y\|=\sup_{n\in\mathbb{N}}|x_n+y_n|\le \|x\|+\|y\|.

Example 1.71. Denote by $\ell^2$ the set of all sequences of real (or complex) numbers $x=(x_n)$ such that the series $\sum_{n=1}^\infty |x_n|^2$ converges. Given any $x=(x_n)\in\ell^2$ , define

\|x\|=\left(\sum_{n=1}^\infty |x_n|^2\right)^{1/2}.

Observe that $\ell^2$ is a linear subspace of the vector space $s$ from Example 1.5. Indeed, take any $x=(x_n)$ and $y=(y_n)$ in $\ell^2$ and any scalar $\lambda$ . We have

|x_n+y_n|^2\le (|x_n|+|y_n|)^2\le 2(|x_n|^2+|y_n|^2).

Since $\sum_{n=1}^\infty |x_n|^2<\infty$ and $\sum_{n=1}^\infty |y_n|^2<\infty$ , we see that

\sum_{n=1}^\infty |x_n+y_n|^2<\infty.

Furthermore,

\sum_{n=1}^\infty |\lambda x_n|^2=|\lambda|^2\sum_{n=1}^\infty |x_n|^2<\infty.

Therefore, $x+y$ and $\lambda x$ belong to $\ell^2$ , so $\ell^2$ is a linear subspace of $s$ .

Next, we show the triangle inequality $\|x+y\|\le \|x\|+\|y\|$ . For all $n\in\mathbb{N}$ , applying the Cauchy–Schwarz inequality gives

\sum_{k=1}^n |x_k+y_k|^2 =\sum_{k=1}^n\big(|x_k|^2+2|x_k y_k|+|y_k|^2\big)

\le \sum_{k=1}^n |x_k|^2 +2\left(\sum_{k=1}^n |x_k|^2\right)^{1/2}\left(\sum_{k=1}^n |y_k|^2\right)^{1/2} +\sum_{k=1}^n |y_k|^2

\le \left(\left(\sum_{k=1}^n |x_k|^2\right)^{1/2}+\left(\sum_{k=1}^n |y_k|^2\right)^{1/2}\right)^2.

Letting $n\to\infty$ , we have

\|x+y\|^2\le (\|x\|+\|y\|)^2,

which implies the triangle inequality. Therefore, $\ell^2$ is a normed space.

Example 1.72. Consider the vector space $C[a,b]$ from Example 1.18. Given $x\in C[a,b]$ , define

\|x\|=\max_{t\in[a,b]} |x(t)|,\qquad \|x\|_1=\int_a^b |x(t)|\,dt.

Take any $x,y\in C[a,b]$ and any scalar $\lambda$ . First, observe that $\|x\|=\max_{t\in[a,b]}|x(t)|\ge 0$ , and $\|x\|=0$ iff $x(t)=0$ for all $t\in[a,b]$ , i.e., $x$ is the zero element in $C[a,b]$ . Also,

\|\lambda x\|=\max_{t\in[a,b]}|(\lambda x)(t)| =\max_{t\in[a,b]}|\lambda x(t)| =|\lambda|\,\max_{t\in[a,b]}|x(t)| =|\lambda|\,\|x\|.

For any $t\in[a,b]$ ,

|(x+y)(t)|=|x(t)+y(t)|\le |x(t)|+|y(t)|\le \max_{t\in[a,b]}|x(t)|+\max_{t\in[a,b]}|y(t)|.

This implies

\|x+y\|=\max_{t\in[a,b]}|(x+y)(t)|\le \|x\|+\|y\|.

1.3.2 Convergence in Normed Spaces

In this section, we introduce the notion of convergence of sequences in a normed space and explore its basic properties. Since any normed space is a metric space, this notion in a normed space is inherited from that in a metric space.

Definition 1.73. Let $X$ be a normed space and let $(x_n)$ be a sequence in $X$ . The sequence $(x_n)$ is said to converge in $X$ if there exists $x\in X$ such that $\|x_n-x\|\to 0$ as $n\to\infty$ .

If $x_n\to x$ , we write $\lim_{n\to\infty} x_n=x$ or $x_n\to x$ as usual. The element $x$ is called a limit of $(x_n)$ .

It follows from definition that:

\lim_{n\to\infty} x_n=x \quad\Longleftrightarrow\quad (\forall\varepsilon>0)(\exists n_0\in\mathbb{N})(\forall n\ge n_0):\ \|x_n-x\|<\varepsilon.

Example 1.74. Consider the sequence $(x_n)$ in $\mathbb{R}^2$ given by

x_n=\left(\frac{1}{n},\frac{n+1}{n}\right),\quad n\in\mathbb{N}.

Let $x=(0,1)\in\mathbb{R}^2$ . Then for any $n\in\mathbb{N}$ we have

\|x_n-x\|_2=\frac{\sqrt{2}}{n},\qquad \|x_n-x\|_1=\frac{2}{n},\qquad \|x_n-x\|_\infty=\frac{1}{n}.

Since these sequences converge to $0$ in $\mathbb{R}$ , we see that $(x_n)$ converges to $x$ in $\mathbb{R}^2$ with each norm $\|\cdot\|_2$ , $\|\cdot\|_1$ , and $\|\cdot\|_\infty$ .

Example 1.75. In $\ell^\infty$ (see Example 1.70), consider the sequence $(z_n)$ given by

z_n=\left(1,\frac{1}{2},\dots,\frac{1}{n},0,0,\dots\right),\quad n\in\mathbb{N}.

Letting $z=\left(1,\frac{1}{2},\dots,\frac{1}{n},\dots\right)$ , we can easily check that $z\in\ell^\infty$ and

\|z_n-z\|_\infty=\frac{1}{n+1}\quad\text{for all }n\in\mathbb{N}.

Since $\left(\frac{1}{n+1}\right)\to 0$ , we see that $z_n\to z$ in $\ell^\infty$ . The reader can check that $z_n\to z$ also in $\ell^2$ .

Example 1.76. In $C[0,1]$ (see Example 1.72) consider the sequence $(x_n)$ given by

x_n(t)=t^n,\quad t\in[0,1],\ n\in\mathbb{N}.

Let $x=0$ be the zero function in $C[0,1]$ , i.e., $x(t)=0$ for all $t\in[0,1]$ . Then

\|x_n-x\|=1,\qquad \|x_n-x\|_1=\frac{1}{n+1}\quad\text{for all }n\in\mathbb{N}.

Thus, $x_n\to x$ in $(C[0,1],\|\cdot\|_1)$ , but $(x_n)$ does not converge to $x$ in $(C[0,1],\|\cdot\|)$ .

Proposition 1.77. (Convergence implies convergence of norms) Consider a normed space $X$ over a field $K$ . Let $(x_n)$ be a sequence in $X$ . If $x_n\to x_0$ in $X$ , then $\|x_n\|\to \|x_0\|$ in $\mathbb{R}$ .

Proof. Suppose $x_n\to x_0$ . Applying Proposition 1.68, we have

\big|\|x_n\|-\|x_0\|\big|\le \|x_n-x_0\|\to 0,

which implies $\|x_n\|\to \|x_0\|$ . $\square$

Proposition 1.78. (Uniqueness of limits and boundedness) Consider a normed space $X$ over a field $K$ . Let $(x_n)$ be a sequence in $X$ . Then:

(i) If $(x_n)$ is convergent, then it has a unique limit. (ii) If $(x_n)$ is convergent, then it is bounded, i.e., there exists $M\ge 0$ such that $\|x_n\|\le M$ for all $n\in\mathbb{N}$ .

Proof. (i) Suppose that $(x_n)$ converges to $x$ and $y$ in $X$ . Fix any $\varepsilon>0$ . Then there exists $n_0$ such that

\|x_n-x\|<\varepsilon/2\quad\text{and}\quad \|x_n-y\|<\varepsilon/2

for all $n\ge n_0$ . Using the triangle inequality gives

\|x-y\|\le \|x-x_{n_0}\|+\|x_{n_0}-y\|<\varepsilon.

Since $\varepsilon>0$ is arbitrary, $\|x-y\|=0$ , hence $x=y$ .

(ii) Suppose $x_n\to x_0$ . By Proposition 1.77, $\|x_n\|\to \|x_0\|$ in $\mathbb{R}$ . Since every real sequence is bounded, $(\|x_n\|)$ is bounded, hence $(x_n)$ is bounded in $X$ . $\square$

Proposition 1.79. (Algebra of limits in normed spaces) Consider a normed space $X$ over a field $K$ . Let $(x_n)$ , $(y_n)$ be sequences in $X$ and let $(\alpha_n)$ be a sequence in $K$ . Then:

(i) If $x_n\to x_0$ and $y_n\to y_0$ in $X$ , then $x_n+y_n\to x_0+y_0$ in $X$ . (ii) If $x_n\to x_0$ in $X$ and $\alpha_n\to \alpha_0$ in $K$ , then $\alpha_n x_n\to \alpha_0 x_0$ in $X$ .

Proof. (i) For any $n\in\mathbb{N}$ ,

\|(x_n+y_n)-(x_0+y_0)\|\le \|x_n-x_0\|+\|y_n-y_0\|\to 0.

Thus $x_n+y_n\to x_0+y_0$ .

(ii) Suppose $x_n\to x_0$ and $\alpha_n\to\alpha_0$ . Then $(\alpha_n)$ is bounded, so there exists $M\ge 0$ such that $|\alpha_n|\le M$ for all $n$ . We estimate:

\|\alpha_n x_n-\alpha_0 x_0\| =\|(\alpha_n x_n-\alpha_n x_0)+(\alpha_n x_0-\alpha_0 x_0)\|

\le |\alpha_n|\,\|x_n-x_0\|+|\alpha_n-\alpha_0|\,\|x_0\| \le M\|x_n-x_0\|+|\alpha_n-\alpha_0|\,\|x_0\|\to 0.

Thus $\alpha_n x_n\to \alpha_0 x_0$ . $\square$

---

2 Convex Sets and Convex Functions

2.1 Convex Sets

2.1.1 Basic Definitions and Elementary Properties

Here is the underlying definition of set convexity in vector spaces.

Definition 2.1. A subset $\Omega$ of a vector space $X$ is called convex if we have

\lambda x + (1-\lambda)y \in \Omega \quad \text{for all } x,y\in \Omega \text{ and } \lambda\in(0,1).

Given $a,b\in X$ , the line segment $[a,b]\subset X$ connecting these points is

[a,b] := \{\lambda a + (1-\lambda)b \mid \lambda\in[0,1]\}. \qquad (2.1)

The line segments $(a,b)$ , $(a,b]$ , and $[a,b)$ are defined similarly by

(a,b) := \{\lambda a + (1-\lambda)b \mid \lambda\in(0,1)\},

(a,b] := \{\lambda a + (1-\lambda)b \mid \lambda\in[0,1)\},

[a,b) := \{\lambda a + (1-\lambda)b \mid \lambda\in(0,1]\}.

Note that if $a=b$ , then all these segments reduce to the singleton $\{a\}$ .

It is obvious that a set $\Omega$ is convex if and only if $[a,b]\subset \Omega$ for all $a,b\in \Omega$ . Simple geometric illustrations of convex and nonconvex sets in the plane are presented in Figure 2.1.

Fig. 2.1. Convex and nonconvex sets (figure omitted).

Let $X$ and $Y$ be vector spaces. A mapping $B:X\to Y$ is called affine if there exist a linear mapping $A:X\to Y$ and a vector $b\in Y$ such that

B(x)=A(x)+b \quad \text{for all } x\in X. \qquad (2.2)

The following proposition provides a characterization of affine mappings.

Proposition 2.2. (Characterization of affine mappings) Let $X$ and $Y$ be vector spaces. Then $B:X\to Y$ is an affine mapping if and only if we have

B\big(\lambda x_1 + (1-\lambda)x_2\big)=\lambda B(x_1)+(1-\lambda)B(x_2) \qquad (2.3)

for all $\lambda\in K$ and $x_1,x_2\in X$ .

Proof. To prove the "only if" part, suppose that $B$ is an affine mapping. Then there exist a linear mapping $A:X\to Y$ and a vector $b\in Y$ such that (2.2) is satisfied. Given any $x_1,x_2\in X$ and $\lambda\in K$ , it follows that

\begin{aligned} B\big(\lambda x_1+(1-\lambda)x_2\big) &=A\big(\lambda x_1+(1-\lambda)x_2\big)+b \\\\ &=\lambda A(x_1)+(1-\lambda)A(x_2)+\lambda b+(1-\lambda)b \\\\ &=\lambda(A(x_1)+b)+(1-\lambda)(A(x_2)+b) \\\\ &=\lambda B(x_1)+(1-\lambda)B(x_2), \end{aligned}

which therefore verifies the validity of (2.3).

To prove the reverse implication, suppose that $B:X\to Y$ satisfies (2.3) for all $\lambda\in K$ and $x_1,x_2\in X$ . Let $b:=B(0)$ , define the mapping

A(x):=B(x)-b \quad \text{for } x\in X, \qquad (2.4)

and show that it is linear. Indeed, for any $x_1,x_2\in X$ and $\lambda\in K$ we employ (2.3) and (2.4) to verify that

A\big(\lambda x_1+(1-\lambda)x_2\big)=\lambda A(x_1)+(1-\lambda)A(x_2) \quad\text{and}\quad A(0)=0.

Given any $x\in X$ , observe that

A(\lambda x)=A(\lambda x+(1-\lambda)0)=\lambda A(x)+(1-\lambda)A(0)=\lambda A(x).

We have furthermore that

\begin{aligned} A(x_1+x_2) &=A\!\left(2\cdot\frac{x_1+x_2}{2}\right) =2A\!\left(\frac{x_1+x_2}{2}\right) =2\left(\frac{A(x_1)+A(x_2)}{2}\right) =A(x_1)+A(x_2), \end{aligned}

which justifies the linearity of $A$ . It follows from (2.4) that $B(x)=A(x)+b$ whenever $x\in X$ , and thus the mapping $B$ is affine. $\square$

It is easy to verify that the convexity of sets is preserved while taking their direct and inverse images/preimages by affine mappings.

Proposition 2.3. (Affine images and preimages of convex sets are convex) Let $X$ and $Y$ be vector spaces, and let $B:X\to Y$ be an affine mapping. The following assertions hold:

(i) If $\Omega$ is a convex subset of $X$ , then $B(\Omega)$ is a convex subset of $Y$ . (ii) If $\Theta$ is a convex subset of $Y$ , then $B^{-1}(\Theta)$ is a convex subset of $X$ .

Proof. We only prove the first assertion and leave the proof of the second one as an exercise for the reader. Fix any $a,b\in B(\Omega)$ and $\lambda\in(0,1)$ . Then $a=B(x)$ and $b=B(y)$ for some $x,y\in \Omega$ . Proposition 2.2 tells us that

\lambda a+(1-\lambda)b =\lambda B(x)+(1-\lambda)B(y) =B\big(\lambda x+(1-\lambda)y\big).

Since $\Omega$ is convex, we get $\lambda x+(1-\lambda)y\in\Omega$ , and hence $\lambda a+(1-\lambda)b\in B(\Omega)$ . This verifies the convexity of the image $B(\Omega)$ . $\square$

Next we proceed with Cartesian products. Given two vector spaces $X$ and $Y$ , their product $X\times Y$ is a vector space with the operations

(x_1,y_1)+(x_2,y_2):=(x_1+x_2,\,y_1+y_2), \qquad \lambda(x_1,y_1):=(\lambda x_1,\,\lambda y_1)

for $(x_1,y_1),(x_2,y_2)\in X\times Y$ and $\lambda\in\mathbb{R}$ .

Proposition 2.4. (Cartesian product of convex sets is convex) Let $X$ and $Y$ be vector spaces. If $\Omega_1$ is a convex subset of $X$ and $\Omega_2$ is a convex subset of $Y$ , then the Cartesian product $\Omega_1\times \Omega_2$ is a convex subset of the product space $X\times Y$ .

Proof. Fix any $(a_1,a_2),(b_1,b_2)\in \Omega_1\times \Omega_2$ and $\lambda\in(0,1)$ . Then $a_1,b_1\in\Omega_1$ and $a_2,b_2\in\Omega_2$ . It follows from the convexity of $\Omega_i$ , $i=1,2$ , that

\lambda(a_1,a_2)+(1-\lambda)(b_1,b_2) =\big(\lambda a_1+(1-\lambda)b_1,\ \lambda a_2+(1-\lambda)b_2\big) \in \Omega_1\times\Omega_2,

and thus $\Omega_1\times \Omega_2$ is a convex subset of $X\times Y$ . $\square$

Finally in this subsection, we observe that the notion of convexity for sets can be directly extended to set-valued mappings via passing to their graphs.

By a set-valued mapping / multifunction between vector spaces $X$ and $Y$ we understand a mapping $F$ defined on $X$ with values in the collection of all the subsets of $Y$ , i.e., with $F(x)\subset Y$ ; see Figure 2.2. The notation $F:X\rightrightarrows Y$ is used for set-valued mappings instead of the usual notation $F:X\to Y$ for single-valued ones. As we see below in the text and commentaries, set-valued mappings play a highly important role in many aspects of convex and variational analysis as well as in their numerous applications.

Having a set-valued mapping $F:X\rightrightarrows Y$ , we associate with it the following two sets: the domain and graph of $F$ defined by

\operatorname{dom}(F):=\{x\in X \mid F(x)\neq \emptyset\}, \qquad \operatorname{gph}(F):=\{(x,y)\in X\times Y \mid y\in F(x)\},

respectively. The mapping $F$ in question is called convex if its graph is a convex set. In contrast to the case of single-valued mappings, where convexity reduces in fact to linearity, for set-valued mappings this assumption is fairly reasonable, and it is broadly used in the book.

Fig. 2.2. An example of a set-valued mapping (figure omitted).

2.1.2 Operations on Convex Sets and Convex Hulls

First we consider the following standard operations on arbitrary (not necessarily convex) sets in vector spaces. Given $\Omega,\Omega_1,\Omega_2\subset X$ and $\lambda\in\mathbb{R}$ , define the set addition and multiplication by a real scalar as

\Omega_1+\Omega_2 := \{x_1+x_2 \mid x_1\in\Omega_1,\ x_2\in\Omega_2\}, \qquad \lambda\Omega := \{\lambda x \mid x\in\Omega\}.

Proposition 2.5. (Sums and scalar multiples of convex sets are convex) Let $\Omega_1$ and $\Omega_2$ be convex subsets of $X$ , and let $\lambda\in\mathbb{R}$ be a scalar. Then $\lambda\Omega_1$ and $\Omega_1+\Omega_2$ are convex subsets of $X$ .

Proof. To verify the first statement, consider the mapping $B:X\to X$ given by $B(x):=\lambda x$ , $x\in X$ . Then $B$ is affine and $B(\Omega_1)=\lambda\Omega_1$ . Proposition 2.3 ensures that the set $B(\Omega_1)$ is convex. The convexity of the sum $\Omega_1+\Omega_2$ can be verified similarly by using Proposition 2.4. $\square$

A vector $x\in X$ is called a convex combination of $x_1,\dots,x_m\in X$ if there are numbers $\lambda_1,\dots,\lambda_m\ge 0$ such that

\sum_{i=1}^m \lambda_i = 1 \quad\text{and}\quad x = \sum_{i=1}^m \lambda_i x_i.

It follows from the definition that any vector of the form $x=\lambda a+(1-\lambda)b$ , where $a,b\in X$ and $0\le \lambda\le 1$ , is a convex combination of $a$ and $b$ .

Fig. 2.3. Illustration of Proposition 2.6 (figure omitted).

Here is a useful characterization of convexity for arbitrary nonempty sets in general (real) vector spaces via convex combinations of their elements; see the illustration of this result in Figure 2.3.

Proposition 2.6. (Convex sets characterized by closure under convex combinations) A subset $\Omega$ of a vector space $X$ is convex if and only if it contains all the convex combinations of its elements.

Proof. The sufficiency part is trivial. To justify the necessity, we show by induction that any convex combination $x=\sum_{i=1}^m \lambda_i \omega_i$ of elements in $\Omega$ is also an element of $\Omega$ . This conclusion follows directly from the definition for $m=1,2$ . Fix now a positive integer $m\ge 2$ and suppose that every convex combination of $m$ elements from $\Omega$ belongs to $\Omega$ . Form the convex combination

y=\sum_{i=1}^{m+1}\lambda_i\omega_i, \qquad \sum_{i=1}^{m+1}\lambda_i=1, \qquad \lambda_i\ge 0.

Observe that if $\lambda_{m+1}=1$ , then $\lambda_1=\cdots=\lambda_m=0$ , and so $y=\omega_{m+1}\in\Omega$ . In the case where $\lambda_{m+1}<1$ we get the representations

\sum_{i=1}^m \lambda_i = 1-\lambda_{m+1}, \qquad \sum_{i=1}^m \frac{\lambda_i}{1-\lambda_{m+1}}=1,

which imply in turn the inclusion

z:=\sum_{i=1}^m \frac{\lambda_i}{1-\lambda_{m+1}}\omega_i \in \Omega.

It yields therefore the relationships

\begin{aligned} y &=(1-\lambda_{m+1})\sum_{i=1}^m \frac{\lambda_i}{1-\lambda_{m+1}}\omega_i+\lambda_{m+1}\omega_{m+1} \\\\ &=(1-\lambda_{m+1})z+\lambda_{m+1}\omega_{m+1}\in\Omega, \end{aligned}

and thus completes the proof of the proposition. $\square$

Next we proceed with intersections of convex sets.

Proposition 2.7. (Intersections of convex sets are convex) Let $\{\Omega_\alpha\}_{\alpha\in I}$ be a collection of convex subsets of $X$ . Then $\bigcap_{\alpha\in I}\Omega_\alpha$ is also a convex subset of $X$ .

Proof. Taking any $a,b\in\bigcap_{\alpha\in I}\Omega_\alpha$ and $\lambda\in(0,1)$ , we get that $a,b\in\Omega_\alpha$ for all $\alpha\in I$ . The convexity of each $\Omega_\alpha$ ensures that $\lambda a+(1-\lambda)b\in\Omega_\alpha$ . Thus $\lambda a+(1-\lambda)b\in\bigcap_{\alpha\in I}\Omega_\alpha$ , and the intersection is convex. $\square$

When a set is not convex, it is useful in many situations to consider its convexification. Let us define this notion and study some of its properties.

Definition 2.8. Let $\Omega$ be a subset of a vector space $X$ . The convex hull of $\Omega$ is the intersection of all convex sets in $X$ that contain $\Omega$ , i.e.,

\operatorname{co}(\Omega) := \bigcap\{C \mid C \text{ is convex and } \Omega\subset C\}.

The next result follows from the definition and Proposition 2.7.

Proposition 2.9. (Convex hull is the smallest convex set containing) Let $X$ be a vector space, and let $\Omega$ be a subset of $X$ . Then the convex hull $\operatorname{co}(\Omega)$ is the smallest convex set containing $\Omega$ .

Proof. The convexity of $\operatorname{co}(\Omega)\supset \Omega$ is a consequence of Proposition 2.7. On the other hand, for any convex set $C$ in $X$ with $\Omega\subset C$ we clearly get from the definition that $\operatorname{co}(\Omega)\subset C$ . $\square$

Now we are ready to provide an important representation of convex hulls of arbitrary sets in vector spaces.

Theorem 2.10. (Convex hull via convex combinations) For any subset $\Omega$ of a vector space $X$ , its convex hull $\operatorname{co}(\Omega)$ admits the representation

\operatorname{co}(\Omega) =\left\lbrace\sum_{i=1}^m \lambda_i a_i \ \middle|\ \sum_{i=1}^m \lambda_i=1,\ \lambda_i\ge 0,\ a_i\in\Omega,\ m\in\mathbb{N}\right\rbrace.

Proof. Denoting by $C$ the right-hand side of the claimed representation, we have $\Omega\subset C$ . Let us check that $C$ is convex. Take any $a,b\in C$ with

a=\sum_{i=1}^p \alpha_i a_i, \qquad b=\sum_{j=1}^q \beta_j b_j,

where $a_i,b_j\in\Omega$ , $\alpha_i,\beta_j\ge 0$ with $\sum_{i=1}^p \alpha_i=\sum_{j=1}^q \beta_j=1$ , and $p,q\in\mathbb{N}$ . It is easy to see that for every number $\lambda\in(0,1)$ we have

\lambda a+(1-\lambda)b =\sum_{i=1}^p \lambda\alpha_i a_i + \sum_{j=1}^q (1-\lambda)\beta_j b_j.

Then the resulting equality

\sum_{i=1}^p \lambda\alpha_i + \sum_{j=1}^q (1-\lambda)\beta_j =\lambda\sum_{i=1}^p \alpha_i + (1-\lambda)\sum_{j=1}^q \beta_j =1

ensures that $\lambda a+(1-\lambda)b\in C$ , which yields $\operatorname{co}(\Omega)\subset C$ by the definition of $\operatorname{co}(\Omega)$ . Fix now any

a=\sum_{i=1}^m \lambda_i a_i \in C \quad\text{with}\quad \sum_{i=1}^m \lambda_i=1 \quad\text{and}\quad a_i\in \Omega \subset \operatorname{co}(\Omega) \ \text{ for } i=1,\dots,m.

Since $\operatorname{co}(\Omega)$ is convex, it follows from Proposition 2.6 that $a\in \operatorname{co}(\Omega)$ . Thus we arrive at the equality $\operatorname{co}(\Omega)=C$ . $\square$

The next proposition concerns the operations of taking the topological interior and closure of a convex set.

Proposition 2.11. (Interior and closure of a convex set are convex) Let $X$ be a normed vector space. Then the interior $\operatorname{int}(\Omega)$ and closure $\overline{\Omega}$ of a convex set $\Omega\subset X$ are also convex.

Proof. Picking any $a,b\in \operatorname{int}(\Omega)$ and $\lambda\in(0,1)$ , find an open set $V$ such that

a\in V \subset \Omega, \quad\text{and so}\quad \lambda a+(1-\lambda)b \in \lambda V + (1-\lambda)b \subset \Omega.

Since $\lambda V+(1-\lambda)b$ is open, we get $\lambda a+(1-\lambda)b\in \operatorname{int}(\Omega)$ and thus verify the convexity of the set $\operatorname{int}(\Omega)$ .

To proceed further with $\overline{\Omega}$ , fix $a,b\in\overline{\Omega}$ and $\lambda\in(0,1)$ . Then we have the relationships

\lambda a+(1-\lambda)b \in \lambda\overline{\Omega}+(1-\lambda)\overline{\Omega} =\overline{\lambda\Omega}+\overline{(1-\lambda)\Omega} \subset \overline{\lambda\Omega+(1-\lambda)\Omega} \subset \overline{\Omega},

which show that the closure $\overline{\Omega}$ is also convex. $\square$

Fig. 2.4. An illustration of Lemma 2.12 (figure omitted).

The following lemma is fairly important for subsequent considerations. It is illustrated by Figure 2.4.

Lemma 2.12. (Segments from interior points stay in the interior) Let $X$ be a normed vector space, and let $\Omega\subset X$ be a convex set with nonempty interior. Then for any $a\in\operatorname{int}(\Omega)$ and $b\in\overline{\Omega}$ we have the inclusion

[a,b)\subset \operatorname{int}(\Omega).

Proof. Since $b\in\overline{\Omega}$ , it follows that $b\in \Omega+\varepsilon\mathbb{B}$ for any $\varepsilon>0$ . Pick now a real number $\lambda$ such that $0<\lambda\le 1$ , and let $x_\lambda=\lambda a+(1-\lambda)b$ . Choosing $\varepsilon>0$ such that

a+\varepsilon\frac{2-\lambda}{\lambda}\mathbb{B}\subset \Omega,

we then have the relationships

\begin{aligned} x_\lambda+\varepsilon\mathbb{B} &=\lambda a+(1-\lambda)b+\varepsilon\mathbb{B} \\\\ &\subset \lambda a+(1-\lambda)(\Omega+\varepsilon\mathbb{B})+\varepsilon\mathbb{B} \\\\ &=\lambda a+(1-\lambda)\Omega+(1-\lambda)\varepsilon\mathbb{B}+\varepsilon\mathbb{B} \\\\ &=\lambda\left(a+\varepsilon\frac{2-\lambda}{\lambda}\mathbb{B}\right)+(1-\lambda)\Omega \\\\ &\subset \lambda\Omega+(1-\lambda)\Omega=\Omega. \end{aligned}

This shows that $x_\lambda\in \operatorname{int}(\Omega)$ and thus verifies the inclusion $[a,b)\subset \operatorname{int}(\Omega)$ . $\square$

Next we discuss some relationships between the closure and interior operations applied to the convex set in question and its closure.

Theorem 2.13. (Interior and closure relations for convex sets) Let $X$ be a normed vector space, and let $\Omega\subset X$ be a convex set with nonempty interior. Then the following assertions hold:

(i) $\overline{\operatorname{int}(\Omega)}=\overline{\Omega}$ . (ii) $\operatorname{int}(\Omega)=\operatorname{int}(\overline{\Omega})$ .

Proof. The first assertion requires us to show that $\overline{\Omega}\subset \overline{\operatorname{int}(\Omega)}$ , since the opposite inclusion is obvious. Picking $b\in\overline{\Omega}$ , $a\in\operatorname{int}(\Omega)$ , and $k\in\mathbb{N}$ , we set

x_k := \frac{1}{k}a+\left(1-\frac{1}{k}\right)b.

Then $x_k\in \operatorname{int}(\Omega)$ for every $k\in\mathbb{N}$ and $x_k\to b$ . This yields $b\in \overline{\operatorname{int}(\Omega)}$ , and we are done.

To prove the second assertion, we need to verify that $\operatorname{int}(\overline{\Omega})\subset \operatorname{int}(\Omega)$ ; the opposite inclusion is obvious. Fix any vectors $b\in\operatorname{int}(\overline{\Omega})$ and $a\in\operatorname{int}(\Omega)$ and then take $\varepsilon>0$ sufficiently small such that

c:=b+\varepsilon(b-a)\in \overline{\Omega}.

Using Lemma 2.12 brings us to the inclusion

b=\frac{\varepsilon}{1+\varepsilon}a+\frac{1}{1+\varepsilon}c \in (a,c)\subset \operatorname{int}(\Omega),

which justifies that $\operatorname{int}(\overline{\Omega})\subset \operatorname{int}(\Omega)$ and thus completes the proof. $\square$

The next result also employs Lemma 2.12 to calculate the closure of convex set intersections under the interiority qualification condition.

Theorem 2.14. (Closure of intersections under interior point condition) Let $X$ be a normed vector space, and let $\Omega_1$ and $\Omega_2$ be convex subsets of $X$ satisfying the qualification condition

\operatorname{int}(\Omega_1)\cap \operatorname{int}(\Omega_2)\neq \emptyset.

Then we have the representation

\overline{\Omega_1\cap \Omega_2}=\overline{\Omega_1}\cap \overline{\Omega_2}.

Remark 2.15. The conclusion of the theorem remains valid if we only assume that $\operatorname{int}(\Omega_1)\cap \Omega_2\neq \emptyset$ .

2.2 Convexity of Functions

In this section we start a systematic study of convex functions. The convexity of functions is closely related to (in fact, is generated by) the convexity of sets, while the functional framework exhibits important features which are not present in the geometric setting of sets. Here we consider some basic properties of convex functions (not concerning duality and generalized differentiation, which will be studied in the subsequent sections) and discuss particular classes of functional convexity together with related notions and applications.

We consider the extended real number system which consists of $\mathbb{R}$ and two symbols $-\infty$ and $\infty$ . Along with the usual properties of $\mathbb{R}$ , the conventions of extended arithmetic and orders are as follows:

\begin{aligned} & a+\infty=\infty,\quad a+(-\infty)=a-\infty=-\infty \quad \text{for } a\in\mathbb{R},\\\\ & \infty+\infty=\infty,\quad (-\infty)+(-\infty)=-\infty,\\\\ & t\cdot\infty=\infty,\quad t\cdot(-\infty)=-\infty \quad \text{for } t\in(0,\infty),\\\\ & t\cdot\infty=-\infty,\quad t\cdot(-\infty)=\infty \quad \text{for } t\in(-\infty,0),\\\\ & 0\cdot\infty = 0\cdot(-\infty)=0,\\\\ & -\infty < a < \infty \quad \text{for } a\in\mathbb{R}. \end{aligned}

In the extended real number system, $-\infty$ is a lower bound of every subset, and every nonempty subset has a greatest lower bound. If $D$ is nonempty and not bounded below, then $\inf D=-\infty$ . We also use the convention that $\inf\emptyset=\infty$ . Similarly, $\infty$ is an upper bound of every subset of the extended real number system, and every nonempty subset has a least upper bound. If $D$ is nonempty and not bounded above, then $\sup D=\infty$ . We also use the convention that $\sup\emptyset=-\infty$ .

Throughout the entire book, we mostly consider for convenience extended-real-valued functions $f:X\to \overline{\mathbb{R}}$ , which take values in $\overline{\mathbb{R}}:=(-\infty,\infty]=\mathbb{R}\cup\{\infty\}$ . This allows us to avoid undefined operations on the extended real number system such as $-\infty+\infty$ .

2.2.1 Descriptions and Properties of Convex Functions

This subsection presents the basic definitions, descriptions, and properties of convex functions in general infinite-dimensional spaces. Unless otherwise stated, the spaces under consideration are (real) vector spaces on which we define extended-real-valued functions $f:X\to \overline{\mathbb{R}}:=(-\infty,\infty]$ .

Given such a function $f:X\to \overline{\mathbb{R}}$ , let us associate with it the domain and epigraph, which are the sets defined by

\operatorname{dom}(f):=\{x\in X \mid f(x)<\infty\}, \qquad \operatorname{epi}(f):=\{(x,\alpha)\in X\times \mathbb{R} \mid f(x)\le \alpha\},

respectively. We say that $f$ is proper if $\operatorname{dom}(f)\neq \emptyset$ .

Developing a geometric approach to convex analysis, we define the convexity of a function via the convexity of its epigraphical set; see Figures 2.5 and 2.6. This makes it possible to widely employ geometric results on set convexity in the study and applications of convex functions.

Definition 2.16. (Convex function via epigraph) Let $f:X\to \overline{\mathbb{R}}$ be an extended-real-valued function on a vector space $X$ . We say that $f$ is convex if $\operatorname{epi}(f)$ is a convex set in the real vector space $X\times \mathbb{R}$ .

Fig. 2.5. Convex and nonconvex functions (figure omitted). Fig. 2.6. Epigraphs of convex and nonconvex functions (figure omitted).

Next we present equivalent analytic descriptions of convex functions.

Theorem 2.17. (Equivalent characterizations of convex functions) The convexity of a function $f:X\to \overline{\mathbb{R}}$ on a vector space $X$ is equivalent to each of the following statements:

(i) (Jensen inequality) For all $x,y\in X$ and $\lambda\in(0,1)$ we have

f\big(\lambda x+(1-\lambda)y\big)\le \lambda f(x)+(1-\lambda)f(y). \qquad (2.5)

(ii) (Extended Jensen inequality) For any points $x_i\in X$ and $\lambda_i>0$ for $i=1,\dots,m$ with $m\in\mathbb{N}$ satisfying $\sum_{i=1}^m \lambda_i=1$ we have

f\!\left(\sum_{i=1}^m \lambda_i x_i\right)\le \sum_{i=1}^m \lambda_i f(x_i). \qquad (2.6)

Proof. Assuming that (2.5) holds, fix any pairs $(x,s),(y,t)\in \operatorname{epi}(f)$ and a number $\lambda\in(0,1)$ . Then we have

f\big(\lambda x+(1-\lambda)y\big)\le \lambda f(x)+(1-\lambda)f(y)\le \lambda s+(1-\lambda)t,

which immediately implies that

\lambda(x,s)+(1-\lambda)(y,t)=\big(\lambda x+(1-\lambda)y,\ \lambda s+(1-\lambda)t\big)\in \operatorname{epi}(f)

and shows that the epigraph $\operatorname{epi}(f)$ is a convex subset of the real vector space $X\times\mathbb{R}$ .

Conversely, suppose that $f$ is convex and pick $x,y\in \operatorname{dom}(f)$ and $\lambda\in(0,1)$ . Then $(x,f(x)),(y,f(y))\in \operatorname{epi}(f)$ . Definition 2.16 tells us that

\big(\lambda x+(1-\lambda)y,\ \lambda f(x)+(1-\lambda)f(y)\big) =\lambda(x,f(x))+(1-\lambda)(y,f(y))\in \operatorname{epi}(f)

and therefore ensures the inequality

f\big(\lambda x+(1-\lambda)y\big)\le \lambda f(x)+(1-\lambda)f(y).

The latter also holds if $x\notin \operatorname{dom}(f)$ or $y\notin \operatorname{dom}(f)$ , and so (2.5) is satisfied.

To verify now the equivalence with the extended Jensen inequality, observe first that (ii) implies (i). Thus the only thing we need to show is that the convexity of $f$ implies (ii). To proceed, fix $x_i\in X$ and $\lambda_i>0$ for $i=1,\dots,m$ with $\sum_{i=1}^m \lambda_i=1$ . It suffices to consider the case where $x_i\in \operatorname{dom}(f)$ for $i=1,\dots,m$ . Then $(x_i,f(x_i))\in \operatorname{epi}(f)$ for every $i=1,\dots,m$ . Using Proposition 2.6, we conclude that

\left(\sum_{i=1}^m \lambda_i x_i,\ \sum_{i=1}^m \lambda_i f(x_i)\right) =\sum_{i=1}^m \lambda_i (x_i,f(x_i)) \in \operatorname{epi}(f),

which verifies (2.6) and hence completes the proof of the theorem. $\square$

It follows from the proof of Theorem 2.17 that a function $f:X\to \overline{\mathbb{R}}$ is convex if and only if for all $x,y\in \operatorname{dom}(f)$ and $\lambda\in(0,1)$ we have

f\big(\lambda x+(1-\lambda)y\big)\le \lambda f(x)+(1-\lambda)f(y).

Considering further the case where a function $f:\Omega\to \overline{\mathbb{R}}$ is given on a nonempty convex subset $\Omega\subset X$ , the function $f$ can be extended to the whole space $X$ by the formula

\tilde f(x):= \begin{cases} f(x) & \text{if } x\in\Omega,\\\\ \infty & \text{otherwise}. \end{cases}

We say that $f$ is convex on $\Omega$ if its extension $\tilde f:X\to \overline{\mathbb{R}}$ is a convex function on $X$ . It is easy to see that $f$ is convex on $\Omega$ if and only if for all $x,y\in\Omega$ and $\lambda\in(0,1)$ we have

f\big(\lambda x+(1-\lambda)y\big)\le \lambda f(x)+(1-\lambda)f(y).

Since any convex function on $X$ is obviously convex on every nonempty convex subset of $X$ , it allows us to deal with extended-real-valued convex functions defined on the entire space $X$ .

The next result is a direct consequence of Theorem 2.17(i).

Corollary 2.18. (Domain of a convex function is convex) Any convex function $f:X\to \overline{\mathbb{R}}$ defined on a vector space $X$ has a convex domain $\operatorname{dom}(f)$ .

Proof. If $f$ is convex, then for every $x,y\in \operatorname{dom}(f)$ and $\lambda\in(0,1)$ we get by Theorem 2.17(i) that

f\big(\lambda x+(1-\lambda)y\big)\le \lambda f(x)+(1-\lambda)f(y) < \infty.

Thus $\lambda x+(1-\lambda)y\in \operatorname{dom}(f)$ , which verifies the convexity of $\operatorname{dom}(f)$ . $\square$

Let us illustrate the convexity of functions with some simple examples.

Example 2.19. Consider the following real-valued functions $f:X\to\mathbb{R}$ on a normed space $X$ :

(i) $f(x):=\|x\|,\quad x\in X$ . (ii) $f(x):=\|x\|^2,\quad x\in X$ .

Check the convexity of both functions by using the characterizing inequality (2.5). Fix $x,y\in X$ and $\lambda\in(0,1)$ . Then we have for $f(x)=\|x\|$ that

f(\lambda x+(1-\lambda)y)=\|\lambda x+(1-\lambda)y\| \le \lambda\|x\|+(1-\lambda)\|y\| =\lambda f(x)+(1-\lambda)f(y)

due to the triangle inequality and $\|\alpha u\|=|\alpha|\,\|u\|$ if $\alpha\in\mathbb{R}$ and $u\in X$ .

To proceed with $f(x)=\|x\|^2$ , we clearly get

\begin{aligned} f(\lambda x+(1-\lambda)y) &=\|\lambda x+(1-\lambda)y\|^2 \\\\ &\le \big(\lambda\|x\|+(1-\lambda)\|y\|\big)^2 \\\\ &=\lambda^2\|x\|^2+2\lambda(1-\lambda)\|x\|\,\|y\|+(1-\lambda)^2\|y\|^2 \\\\ &\le \lambda^2\|x\|^2+\lambda(1-\lambda)\big(\|x\|^2+\|y\|^2\big)+(1-\lambda)^2\|y\|^2 \\\\ &=\lambda\|x\|^2+(1-\lambda)\|y\|^2 =\lambda f(x)+(1-\lambda)f(y), \end{aligned}

which verifies the convexity of this function.

Example 2.20. Let $H$ be an inner product (in particular, a Hilbert) space. Recall that a linear operator $A:H\to H$ is called self-adjoint if

\langle Ax,y\rangle = \langle x,Ay\rangle \quad \text{for all } x,y\in H.

We say that $A$ is nonnegative (or positive-semidefinite) if it is self-adjoint and $\langle Ax,x\rangle \ge 0$ for all $x\in H$ .

Let us check that a self-adjoint mapping $A:H\to H$ is nonnegative if and only if the scalar function $f:H\to\mathbb{R}$ defined by

f(x):=\frac{1}{2}\langle Ax,x\rangle,\quad x\in H,

is convex. Indeed, a direct calculation shows that

\lambda f(x)+(1-\lambda)f(y)-f(\lambda x+(1-\lambda)y) =\frac{1}{2}\lambda(1-\lambda)\langle A(x-y),x-y\rangle \qquad (2.7)

for any $x,y\in H$ and $\lambda\in(0,1)$ . If $A$ is nonnegative, then $\langle A(x-y),x-y\rangle\ge 0$ , so the function $f$ is convex by (2.7). Conversely, assuming the convexity of $f$ and using equality (2.7) for $y=0$ verify that $A$ is nonnegative.

The next two examples describe classes of functions associated with given sets that are highly important in convex analysis and its extensions.

Example 2.21. Let $\Omega$ be a nonempty subset of a vector space $X$ . Associate with it the indicator function $\delta_\Omega:X\to\overline{\mathbb{R}}$ by

\delta(x;\Omega)=\delta_\Omega(x):= \begin{cases} 0 & \text{if } x\in\Omega,\\\\ \infty & \text{if } x\notin\Omega, \end{cases}

which is a proper extended-real-valued function with $\operatorname{dom}(\delta_\Omega)=\Omega$ and $\operatorname{epi}(\delta_\Omega)=\Omega\times[0,\infty)$ . The latter implies that the indicator function $\delta_\Omega$ is convex if and only if the set $\Omega$ is convex.

Fig. 2.7. The distance function (figure omitted).

The following example associates with a nonempty subset $\Omega\subset X$ of a normed space a real-valued function, which is actually Lipschitz continuous while being usually nondifferentiable. Figure 2.7 illustrates the distance function to a convex set in the plane endowed with the Euclidean norm.

Example 2.22. Let $\Omega$ be a nonempty subset of a normed space $X$ . Define the distance function $d_\Omega:X\to\mathbb{R}$ associated with $\Omega$ by

d(x;\Omega)=d_\Omega(x):=\inf\\{\|x-w\|\mid w\in\Omega\\},\quad x\in X. \qquad (2.8)

It is not hard to verify that the convexity of $\Omega$ implies the convexity of (2.8), and the converse also holds provided that $\Omega$ is closed.

Next we define a useful specification of function convexity and illustrate it by a typical example in infinite dimensions.

Definition 2.23. (Strictly convex function) Let $f:X\to\overline{\mathbb{R}}$ be a function defined on a vector space $X$ . It is said to be strictly convex if

f(\lambda x+(1-\lambda)y) < \lambda f(x)+(1-\lambda)f(y)

for all $x,y\in \operatorname{dom}(f)$ with $x\neq y$ and $\lambda\in(0,1)$ .

Example 2.24. Let $H$ be an inner product (in particular, a Hilbert) space. Then the function $f:H\to\mathbb{R}$ given by $f(x):=\|x\|^2$ as $x\in H$ is strictly convex. Indeed, for any $x,y\in H$ and $\lambda\in(0,1)$ we have

\begin{aligned} f(\lambda x+(1-\lambda)y) &=\|\lambda x+(1-\lambda)y\|^2 \\\\ &=\lambda^2\|x\|^2+2\lambda(1-\lambda)\langle x,y\rangle+(1-\lambda)^2\|y\|^2 \\\\ &\le \lambda^2\|x\|^2+2\lambda(1-\lambda)\|x\|\,\|y\|+(1-\lambda)^2\|y\|^2 \\\\ &\le \lambda^2\|x\|^2+\lambda(1-\lambda)\big(\|x\|^2+\|y\|^2\big)+(1-\lambda)^2\|y\|^2 \\\\ &=\lambda\|x\|^2+(1-\lambda)\|y\|^2 =\lambda f(x)+(1-\lambda)f(y). \end{aligned}

Here we apply the Cauchy–Schwarz inequality and the fact that $2\|x\|\,\|y\|\le \|x\|^2+\|y\|^2$ . Note further that $f(\lambda x+(1-\lambda)y)=\lambda f(x)+(1-\lambda)f(y)$ if and only if $\langle x,y\rangle=\|x\|\,\|y\|$ and $\|x\|^2=\|y\|^2$ . In this case we get

\|x-y\|^2=\|x\|^2-2\langle x,y\rangle+\|y\|^2=0,

and so $x=y$ . Having $x\neq y$ , it shows that

f(\lambda x+(1-\lambda)y) < \lambda f(x)+(1-\lambda)f(y),

which verifies the strict convexity of $f$ .

Next we consider an extension of function convexity important for various applications; in particular, to those in economic modeling.

Definition 2.25. (Quasiconvex function) A function $f:X\to\overline{\mathbb{R}}$ defined on a vector space $X$ is called quasiconvex if we have

f(\lambda x+(1-\lambda)y)\le \max\\{f(x),f(y)\\} \qquad (2.9)

for all $x,y\in X$ and $\lambda\in(0,1)$ .

It follows from the definitions that every convex function is quasiconvex. The opposite implication fails as for the simple function $f(x):=\sqrt{|x|}$ on $\mathbb{R}$ , which is illustrated by Figure 2.8.

Fig. 2.8. A quasiconvex function (figure omitted).

The final proposition here shows that quasiconvexity of functions has a characterization via convexity of a family of sets.

Proposition 2.26. (Quasiconvexity characterized by convex sublevel sets) Let $X$ be a vector space. A function $f:X\to\overline{\mathbb{R}}$ is quasiconvex if and only if the sublevel set

L_\alpha := \\{x\in X \mid f(x)\le \alpha\\} \qquad (2.10)

is convex for every number $\alpha\in\mathbb{R}$ .

Proof. $\Rightarrow$ : Assuming that $f$ is quasiconvex, fix any $\alpha\in\mathbb{R}$ , $x,y\in L_\alpha$ , and $\lambda\in(0,1)$ . Then $f(x)\le \alpha$ and $f(y)\le \alpha$ . It tells us therefore that

f(\lambda x+(1-\lambda)y)\le \max\\{f(x),f(y)\\}\le \alpha.

This shows that $\lambda x+(1-\lambda)y\in L_\alpha$ , and so the sublevel set (2.10) is convex.

$\Leftarrow$ : Suppose now that the sublevel set $L_\alpha$ is convex for all $\alpha\in\mathbb{R}$ and fix any $x,y\in X$ and $\lambda\in(0,1)$ . If either $f(x)=\infty$ or $f(y)=\infty$ , then (2.9) clearly is satisfied. Otherwise, let $\alpha:=\max\\{f(x),f(y)\\}\in\mathbb{R}$ and then get $x\in L_\alpha$ and $y\in L_\alpha$ . It yields $\lambda x+(1-\lambda)y\in L_\alpha$ , and thus

f(\lambda x+(1-\lambda)y)\le \alpha=\max\\{f(x),f(y)\\},

which verifies the quasiconvexity of $f$ . $\square$

2.2.2 Convexity under Differentiability

In this subsection we present characterizations of convexity under first-order and second-order differentiability assumptions on the function in question. Then the obtained characterizations are applied to verify the convexity of remarkable functions and to derive some classical inequalities in real analysis.

We begin with the following simple albeit useful lemma for real-valued convex functions of one variable; see the illustration in Figure 2.9.

Lemma 2.27. (Slope inequalities for convex functions) Let $f:I\to\mathbb{R}$ be a convex function, where $I\subset\mathbb{R}$ is a nonempty interval. Then for any different numbers $a,b\in I$ with $a<b$ and any $x\in(a,b)$ we have the inequalities

\frac{f(x)-f(a)}{x-a}\le \frac{f(b)-f(a)}{b-a}\le \frac{f(b)-f(x)}{b-x}.

Proof. Fix $a,b,x$ as above and form the number $t:=\dfrac{x-a}{b-a}\in(0,1)$ . Then

\begin{aligned} f(x) &=f\big(a+(x-a)\big) =f\!\left(a+\frac{x-a}{b-a}(b-a)\right) =f\big(a+t(b-a)\big) =f(tb+(1-t)a). \end{aligned}

This gives us the inequality $f(x)\le t f(b)+(1-t)f(a)$ and

\begin{aligned} f(x)-f(a) &\le t f(b)+(1-t)f(a)-f(a) =t\big(f(b)-f(a)\big) =\frac{x-a}{b-a}\big(f(b)-f(a)\big), \end{aligned}

where the latter one can be equivalently rewritten as

\frac{f(x)-f(a)}{x-a}\le \frac{f(b)-f(a)}{b-a}.

Similarly we have the estimate

\begin{aligned} f(x)-f(b) &\le t f(b)+(1-t)f(a)-f(b) =(t-1)\big(f(b)-f(a)\big) =\frac{x-b}{b-a}\big(f(b)-f(a)\big), \end{aligned}

which finally implies that

\frac{f(b)-f(a)}{b-a}\le \frac{f(b)-f(x)}{b-x}

and thus completes the proof of the lemma. $\square$

Fig. 2.9. Lemma 2.27 (figure omitted).

Now we arrive at a classical characterization of convexity for differentiable real functions of one variable.

Theorem 2.28. (Convexity characterized by monotonicity of derivative) Let $f:I\to\mathbb{R}$ be a differentiable function, where $I\subset\mathbb{R}$ is a nonempty open interval. Then the function $f$ is convex if and only if its derivative $f'$ is nondecreasing on the entire interval $I$ .

Proof. Fix $a<b$ with $a,b\in I$ and assume that the function $f$ is convex. Then we get from Lemma 2.27 that

\frac{f(x)-f(a)}{x-a}\le \frac{f(b)-f(a)}{b-a} \quad \text{for every } x\in(a,b).

This implies by the derivative definition that

f'(a)\le \frac{f(b)-f(a)}{b-a}.

Similarly we arrive at the estimate

\frac{f(b)-f(a)}{b-a}\le f'(b)

and conclude that $f'(a)\le f'(b)$ , i.e., $f'$ is a nondecreasing function.

To prove the converse implication, suppose that $f'$ is nondecreasing on $I$ and fix $x_1<x_2$ with $x_1,x_2\in I$ and $t\in(0,1)$ . Then

x_1<x_t<x_2 \quad\text{for}\quad x_t:=t x_1+(1-t)x_2.

Using the classical mean value theorem gives us numbers $c_1,c_2$ with $x_1<c_1<x_t<c_2<x_2$ such that we have the equalities

f(x_t)-f(x_2)=f'(c_2)(x_t-x_2)=f'(c_2)t(x_1-x_2)

and

f(x_t)-f(x_1)=f'(c_1)(x_t-x_1)=f'(c_1)(1-t)(x_2-x_1),

which can be equivalently rewritten as

t f(x_t)-t f(x_1)=f'(c_1)t(1-t)(x_2-x_1)

and

(1-t)f(x_t)-(1-t)f(x_2)=f'(c_2)t(1-t)(x_1-x_2).

Summing up these equalities and using $f'(c_1)\le f'(c_2)$ give us the estimate

f(x_t)\le t f(x_1)+(1-t)f(x_2),

and thus justifies the convexity of the function $f$ . $\square$

As a direct consequence of Theorem 2.28, we get the following characterization of convexity for twice differentiable real functions of one variable.

Corollary 2.29. (Convexity via nonnegative second derivative) Let $f:I\to\mathbb{R}$ be twice differentiable, where $I\subset\mathbb{R}$ is a nonempty open interval. Then $f$ is convex if and only if its second derivative is nonnegative on $I$ , i.e., $f''(x)\ge 0$ for all $x\in I$ .

Proof. Recall that $f''(x)\ge 0$ for all $x\in I$ if and only if the first derivative $f'$ is nondecreasing on this interval. Then the conclusion of the corollary follows directly from Theorem 2.28. $\square$

The next result provides a characterization of convexity for twice continuously differentiable functions on open subsets of $\mathbb{R}^n$ in terms of their Hessians.

Theorem 2.30. (Convexity characterized by positive-semidefinite Hessian) Let $f:\Omega\to\mathbb{R}$ be twice continuously differentiable on a nonempty open convex set $\Omega\subset\mathbb{R}^n$ . Then the function $f$ is convex on $\Omega$ if and only if for all $x\in\Omega$ its Hessian matrix $\nabla^2 f(x)$ is positive-semidefinite, i.e., we have

\langle v,\nabla^2 f(x)v\rangle \ge 0 \quad \text{whenever } v\in\mathbb{R}^n.

Proof. It is easy to observe that the convexity of $f:\Omega\to\mathbb{R}$ can be equivalently described via the convexity of functions of one variable on open intervals. In fact, $f$ is convex if and only if for any $x\in\Omega$ and $d\in\mathbb{R}^n$ the real-valued function of one variable

\varphi_{x,d}(t):=f(x+td)\quad\text{whenever } t\in I,

is convex, where $I$ is the open interval $I:=\\{t\in\mathbb{R}\mid x+td\in\Omega\\}$ . This observation leads us to the claimed statement by applying Corollary 2.29 to the function $\varphi_{x,d}(t)$ . $\square$

Using the obtained characterizations allows us to verify function convexity in the following examples and also to prove some classical inequalities formulated in the subsequent propositions.

Example 2.31. Each of the functions below is convex on the given domain:

(i) $f(x):=e^{ax}$ on $\mathbb{R}$ , where $a\in\mathbb{R}$ . (ii) $f(x):=x^q$ on $[0,\infty)$ , where $q\ge 1$ is a constant. (iii) $f(x):=-\ln(x)$ on $(0,\infty)$ . (iv) $f(x):=x\ln(x)$ on $(0,\infty)$ . (v) $f(x):=1/x$ on $(0,\infty)$ . (vi) $f(x_1,x_2):=x_1^{2n}+x_2^{2n}$ on $\mathbb{R}^2$ , where $n\in\mathbb{N}$ . (vii) $f(x)=\langle Ax,x\rangle+\langle b,x\rangle + c$ on $\mathbb{R}^n$ , where $A$ is a positive-semidefinite matrix, $b\in\mathbb{R}^n$ , and $c\in\mathbb{R}$ .

Proposition 2.32. (Weighted arithmetic-geometric mean inequality) For every $a,b\ge 0$ and $0<\theta<1$ we have the inequality

a^\theta b^{1-\theta}\le \theta a+(1-\theta)b. \qquad (2.11)

Proof. It suffices to consider the case where $a>0$ and $b>0$ . It follows from the convexity of the function $f(x):=-\ln(x)$ on $(0,\infty)$ that

-\ln(\theta a+(1-\theta)b)\le -\theta\ln(a)-(1-\theta)\ln(b),

which implies in turn that

\ln\big(a^\theta b^{1-\theta}\big)\le \ln(\theta a+(1-\theta)b).

Then (2.11) is satisfied since $\ln$ is monotone increasing. $\square$

Proposition 2.33. (Hölder inequality for finite sums) Let $x_i,y_i\in\mathbb{R}$ for $i=1,\dots,m$ . Then for $p>1$ and $q>1$ such that $1/p+1/q=1$ we have the inequality

\sum_{i=1}^m |x_i y_i| \le \left(\sum_{i=1}^m |x_i|^p\right)^{1/p} \left(\sum_{i=1}^m |y_i|^q\right)^{1/q}. \qquad (2.12)

Proof. It suffices to consider the case where $\sum_{i=1}^m |x_i|^p\neq 0$ and $\sum_{i=1}^m |y_i|^q\neq 0$ . Let

a:=\frac{|x_i|^p}{\sum_{i=1}^m |x_i|^p}, \qquad b:=\frac{|y_i|^q}{\sum_{i=1}^m |y_i|^q}, \qquad \theta:=\frac{1}{p}.

It follows from the estimate in (2.11) that

\frac{|x_i y_i|}{\left(\sum_{i=1}^m |x_i|^p\right)^{1/p}\left(\sum_{i=1}^m |y_i|^q\right)^{1/q}} \le \frac{|x_i|^p}{p\sum_{i=1}^m |x_i|^p} + \frac{|y_i|^q}{q\sum_{i=1}^m |y_i|^q}

for all $i=1,\dots,m$ . Summing up these inequalities gives us (2.12). $\square$

Proposition 2.34. (Hölder inequality for integrals) Let $f,g:\mathbb{R}\to\mathbb{R}$ be summable functions of the corresponding degree on $[a,b]$ , and let $\gamma(\cdot)$ stand for the Lebesgue measure on this interval. Given $p>1$ and $q>1$ with $1/p+1/q=1$ , we have the inequality

\int_a^b |fg|\,d\gamma \le \left(\int_a^b |f|^p\,d\gamma\right)^{1/p} \left(\int_a^b |g|^q\,d\gamma\right)^{1/q} \qquad (2.13)

whenever $f\in L^p[a,b]$ and $g\in L^q[a,b]$ .

Proof. If either $\left(\int_a^b |f|^p\,d\gamma\right)^{1/p}=0$ or $\left(\int_a^b |g|^q\,d\gamma\right)^{1/q}=0$ , then $f=0$ a.e. and $g=0$ a.e., respectively. Thus inequality (2.13) is satisfied in this case because its left-hand side is zero.

Consider now the case where

0<\left(\int_a^b |f|^p\,d\gamma\right)^{1/p}<\infty \quad\text{and}\quad 0<\left(\int_a^b |g|^q\,d\gamma\right)^{1/q}<\infty.

For each $x\in[a,b]$ we define the numbers

a:=\frac{|f(x)|^p}{\int_a^b |f|^p\,d\gamma}, \qquad b:=\frac{|g(x)|^q}{\int_a^b |g|^q\,d\gamma},

and then let $\theta:=1/p$ . It follows from (2.11) that

\frac{|f(x)g(x)|}{\left(\int_a^b |f|^p\,d\gamma\right)^{1/p}\left(\int_a^b |g|^q\,d\gamma\right)^{1/q}} \le \frac{|f(x)|^p}{p\int_a^b |f|^p\,d\gamma} + \frac{|g(x)|^q}{q\int_a^b |g|^q\,d\gamma}.

Integrating both sides of this inequality, we arrive at (2.13). $\square$

The next classical result is known as Young's inequality.

Proposition 2.35. (Young's inequality) Let $p,q>0$ be such numbers that $1/p+1/q=1$ . Then we have the estimate

|xy|\le \frac{|x|^p}{p}+\frac{|y|^q}{q} \quad\text{whenever } x,y\in\mathbb{R}.

Proof. It suffices to apply (2.11) with $a:=|x|^p$ , $b:=|y|^q$ , and $\theta=1/p$ . $\square$

2.2.3 Operations Preserving Convexity of Functions

Now we come back to the general setting of vector spaces and note first that the convexity of functions is obviously a unilateral notion meaning that $-f$ may not be convex for a convex function $f$ as, e.g., for $f(x)=|x|$ on $\mathbb{R}$ . Furthermore, convexity is not preserved under some simple operations even over linear functions such as taking the minimum; see, e.g., $\min\\{x,-x\\}=-|x|$ . However, many operations particularly important in convex analysis and applications preserve convexity. We discuss them in this subsection.

Proposition 2.36. (Basic operations preserving convexity) Let $X$ be a vector space, and let $f,f_i:X\to\overline{\mathbb{R}}$ be convex functions for all $i=1,\dots,m$ . Then the following functions are convex as well:

(i) The multiplication by scalars $\lambda f$ for any $\lambda\ge 0$ . (ii) The sum function $\sum_{i=1}^m f_i$ . (iii) The maximum function $\max_{1\le i\le m} f_i$ .

Proof. The convexity of scalar multiplication $\lambda f$ as $\lambda\ge 0$ follows directly from the definition.

Let us check that the sum of two convex functions $f_1+f_2$ is convex. The case of finitely many functions under summation easily follows by induction. To proceed, pick any $x,y\in X$ and $\lambda\in(0,1)$ . Then we get

\begin{aligned} (f_1+f_2)\big(\lambda x+(1-\lambda)y\big) &=f_1\big(\lambda x+(1-\lambda)y\big)+f_2\big(\lambda x+(1-\lambda)y\big) \\\\ &\le \lambda f_1(x)+(1-\lambda)f_1(y)+\lambda f_2(x)+(1-\lambda)f_2(y) \\\\ &=\lambda(f_1+f_2)(x)+(1-\lambda)(f_1+f_2)(y), \end{aligned}

and thus the sum function $f_1+f_2$ is convex.

Likewise, it is sufficient to consider only two functions under the maximum operation. Denote $g:=\max\\{f_1,f_2\\}$ and get for $x,y\in X$ and $\lambda\in(0,1)$ that

f_i\big(\lambda x+(1-\lambda)y\big) \le \lambda f_i(x)+(1-\lambda)f_i(y) \le \lambda g(x)+(1-\lambda)g(y) \quad\text{as } i=1,2.

This readily implies that

\begin{aligned} g\big(\lambda x+(1-\lambda)y\big) &=\max\Big\lbrace f_1\big(\lambda x+(1-\lambda)y\big),\ f_2\big(\lambda x+(1-\lambda)y\big)\Big\rbrace \\\\ &\le \lambda g(x)+(1-\lambda)g(y), \end{aligned}

which therefore verifies the convexity of the maximum function on $X$ . $\square$

The next result concerns the preservation of convexity under compositions.

Proposition 2.37. (Convexity preserved under monotone convex composition) Let $X$ be a vector space. Suppose that $f:X\to\overline{\mathbb{R}}$ is convex, and let $\varphi:\overline{\mathbb{R}}\to\overline{\mathbb{R}}$ be nondecreasing and convex on a convex set containing the range of the function $f$ . Then the composition $\varphi\circ f$ is convex.

Proof. Picking $x_1,x_2\in X$ and $\lambda\in(0,1)$ , we have by the convexity of $f$ that

f\big(\lambda x_1+(1-\lambda)x_2\big)\le \lambda f(x_1)+(1-\lambda)f(x_2).

The nondecreasing and convexity properties of $\varphi$ imply that

\begin{aligned} (\varphi\circ f)\big(\lambda x_1+(1-\lambda)x_2\big) &=\varphi\!\left(f\big(\lambda x_1+(1-\lambda)x_2\big)\right) \\\\ &\le \varphi\big(\lambda f(x_1)+(1-\lambda)f(x_2)\big) \\\\ &\le \lambda \varphi(f(x_1))+(1-\lambda)\varphi(f(x_2)) \\\\ &=\lambda(\varphi\circ f)(x_1)+(1-\lambda)(\varphi\circ f)(x_2), \end{aligned}

which verifies the convexity of the composition $\varphi\circ f$ . $\square$

Now we consider the composition of a convex function and an affine mapping.

Proposition 2.38. (Convexity preserved under affine composition) Let $B:X\to Y$ be an affine mapping between vector spaces, and let $f:Y\to\overline{\mathbb{R}}$ be a convex function on $Y$ . Then the composition $f\circ B$ is convex on $X$ .

Proof. Taking any $x,y\in X$ and $\lambda\in(0,1)$ , we have

\begin{aligned} (f\circ B)\big(\lambda x+(1-\lambda)y\big) &=f\big(B(\lambda x+(1-\lambda)y)\big) \\\\ &=f\big(\lambda B(x)+(1-\lambda)B(y)\big) \\\\ &\le \lambda f(B(x))+(1-\lambda)f(B(y)) \\\\ &=\lambda(f\circ B)(x)+(1-\lambda)(f\circ B)(y), \end{aligned}

and therefore justify the convexity of the composition $f\circ B$ . $\square$

The next result deals with the supremum of convex functions over an arbitrary index set. It largely extends the statement of Proposition 2.36(iii).

Proposition 2.39. (Supremum of convex functions is convex) Let $X$ be a vector space, and let $f_i:X\to\overline{\mathbb{R}}$ for $i\in I$ be a collection of convex functions with a nonempty index set $I$ . Then the supremum function $f(x):=\sup_{i\in I} f_i(x)$ is convex on $X$ .

Proof. Fix $x_1,x_2\in X$ and $\lambda\in(0,1)$ . For every $i\in I$ we have

f_i\big(\lambda x_1+(1-\lambda)x_2\big) \le \lambda f_i(x_1)+(1-\lambda)f_i(x_2) \le \lambda f(x_1)+(1-\lambda)f(x_2),

which implies in turn that

\begin{aligned} f\big(\lambda x_1+(1-\lambda)x_2\big) &=\sup_{i\in I} f_i\big(\lambda x_1+(1-\lambda)x_2\big) \\\\ &\le \lambda f(x_1)+(1-\lambda)f(x_2), \end{aligned}

and thus verifies the convexity of the supremum function. $\square$

Further we turn to a major class of functions having a variational structure and being highly important in many aspects of analysis and applications, not only for those related to optimization. Recall that the notion and notation of set-valued mappings/multifunctions used below were introduced and partly discussed at the end of Subsection 2.1.1.

Definition 2.40. (Marginal / optimal value function) Given $F:X\rightrightarrows Y$ and $\varphi:X\times Y\to\overline{\mathbb{R}}$ , the optimal value (or marginal) function associated with $F$ and $\varphi$ is defined by

\mu(x):=\inf\\{\varphi(x,y)\mid y\in F(x)\\} \quad \text{for } x\in X. \qquad (2.14)

In this section we assume that $\mu(x)>-\infty$ for every $x\in X$ and also use the convention that $\inf(\emptyset):=\infty$ in this definition and throughout the book.

The following theorem shows that convexity is preserved in the general settings of marginal functions.

Theorem 2.41. (Convexity of the marginal optimal value function) Let $X$ and $Y$ be vector spaces. Assume that $\varphi:X\times Y\to\overline{\mathbb{R}}$ is a convex function and that $F:X\rightrightarrows Y$ is a convex set-valued mapping. Then the optimal value function $\mu$ in (2.14) is convex.

Proof. Pick $x_1,x_2\in \operatorname{dom}(\mu)$ , $\lambda\in(0,1)$ , and $\varepsilon>0$ . Then find $y_i\in F(x_i)$ with

\varphi(x_i,y_i) < \mu(x_i)+\varepsilon, \qquad i=1,2.

It directly implies the inequalities

\lambda\varphi(x_1,y_1) < \lambda\mu(x_1)+\lambda\varepsilon, \qquad (1-\lambda)\varphi(x_2,y_2) < (1-\lambda)\mu(x_2)+(1-\lambda)\varepsilon.

Summing up these inequalities and employing the convexity of $\varphi$ yield

\begin{aligned} \varphi\big(\lambda x_1+(1-\lambda)x_2,\ \lambda y_1+(1-\lambda)y_2\big) &\le \lambda\varphi(x_1,y_1)+(1-\lambda)\varphi(x_2,y_2) \\\\ &< \lambda\mu(x_1)+(1-\lambda)\mu(x_2)+\varepsilon. \end{aligned}

Furthermore, the convexity of $\operatorname{gph}(F)$ gives us

\big(\lambda x_1+(1-\lambda)x_2,\ \lambda y_1+(1-\lambda)y_2\big) =\lambda(x_1,y_1)+(1-\lambda)(x_2,y_2)\in \operatorname{gph}(F),

and therefore $\lambda y_1+(1-\lambda)y_2\in F(\lambda x_1+(1-\lambda)x_2)$ . This implies that

\begin{aligned} \mu\big(\lambda x_1+(1-\lambda)x_2\big) &\le \varphi\big(\lambda x_1+(1-\lambda)x_2,\ \lambda y_1+(1-\lambda)y_2\big) \\\\ &< \lambda\mu(x_1)+(1-\lambda)\mu(x_2)+\varepsilon. \end{aligned}

Letting now $\varepsilon\downarrow 0$ ensures the convexity of the optimal value function $\mu$ . $\square$

---

3 Convex Separation

3.1 Minkowski Functions, Sublinear Functions, and Seminorms

3.1.1 Algebraic Interior and Linear Closure

Given a subset $\Omega$ of a real vector space $X$ , define the following algebraic notions, known as the algebraic interior (or core) of $\Omega$ and the linear closure of $\Omega$ , respectively, by

\operatorname{core}(\Omega) := \{\, x \in \Omega \mid \forall v \in X,\ \exists \delta > 0,\ \forall t \text{ with } |t| < \delta : x + t v \in \Omega \,\}, \qquad (3.1)

\operatorname{lin}(\Omega) := \{\, x \in X \mid \exists w \in \Omega : [w, x) \subset \Omega \,\}, \qquad (3.2)

where $[w,x)$ is the line segment connecting $w$ and $x$ , excluding $x$ .

Note that, if $\operatorname{int}(\Omega)$ denotes the interior of $\Omega$ and $\overline{\Omega}$ its closure, then the following relationships hold:

\operatorname{int}(\Omega) \subset \operatorname{core}(\Omega) \subset \Omega \subset \operatorname{lin}(\Omega) \subset \overline{\Omega}, \qquad (3.3)

where all the inclusions can be strict.

Proposition 3.1. (Core characterized by absorbing translations) Let $\Omega$ be a nonempty subset of a vector space $X$ . Then $\bar{x} \in \operatorname{core}(\Omega)$ if and only if $\Omega - \bar{x}$ is an absorbing set.

Proposition 3.2. (Core of a convex set is convex) The core of every convex subset of a vector space $X$ is also a convex subset of $X$ .

Proof. Let $a,b \in \operatorname{core}(\Omega)$ and let $\lambda \in (0,1)$ . Take any $v \in X$ . Find $\delta>0$ such that $a+\gamma v \in \Omega$ and $b+\gamma v \in \Omega$ whenever $|\gamma|<\delta$ . For each such number $\gamma$ we have the relationships

\lambda a + (1-\lambda)b + \gamma v = \lambda(a+\gamma v) + (1-\lambda)(b+\gamma v) \in \lambda \Omega + (1-\lambda)\Omega \subset \Omega.

This implies that $\lambda a + (1-\lambda)b \in \operatorname{core}(\Omega)$ , and hence $\operatorname{core}(\Omega)$ is convex. $\square$

It is interesting to find verifiable conditions under which the interior and core agree for convex sets in normed vector spaces. To establish the first important result in this direction, we use again Lemma 2.12.

Theorem 3.3. (Core equals interior for convex sets in normed spaces) Let $X$ be a normed vector space, and let $\Omega \subset X$ be a convex set with nonempty interior. Then

\operatorname{int}(\Omega) = \operatorname{core}(\Omega).

Proof. We always have $\operatorname{int}(\Omega)\subset \operatorname{core}(\Omega)$ . So it is enough to show that $\operatorname{core}(\Omega) \subset \operatorname{int}(\Omega)$ . We proceed in two cases.

Case 1: $0 \in \operatorname{int}(\Omega)$ . Fix any $\bar{x} \in \operatorname{core}(\Omega)$ and by definition of cores find $t>0$ with $\bar{x} + t\bar{x} \in \Omega$ . Then we have $\bar{x} = \frac{1}{1+t}w$ for some $w \in \Omega$ . Employing Lemma 2.12 tells us that

\bar{x} = \frac{1}{1+t}w + \frac{t}{1+t}\,0 \in \operatorname{int}(\Omega),

which shows that $\operatorname{core}(\Omega) \subset \operatorname{int}(\Omega)$ .

Case 2: $0 \notin \operatorname{int}(\Omega)$ . Choose $a \in \operatorname{int}(\Omega)$ and define $\Theta = \Omega - a$ . Then $0 \in \operatorname{int}(\Theta)$ , and we get therefore that $\operatorname{core}(\Omega) - a = \operatorname{core}(\Theta) \subset \operatorname{int}(\Theta) = \operatorname{int}(\Omega) - a$ . This yields $\operatorname{core}(\Omega) \subset \operatorname{int}(\Omega)$ . $\square$

Next we consider the linear closure $\operatorname{lin}(\Omega)$ of a set $\Omega \subset X$ defined in (3.2). It is instrumental, in particular, for the study of the Minkowski function given below. Now we show that $\operatorname{lin}(\Omega)$ reduces to the closure of $\Omega$ for solid (i.e., with nonempty interior) convex subsets of normed vector spaces.

First we check the convexity of the set $\operatorname{lin}(\Omega)$ provided that $\Omega$ is convex.

Proposition 3.4. (Linear closure of a convex set is convex) If $\Omega$ is a convex subset of a vector space $X$ , then $\operatorname{lin}(\Omega)$ is a convex subset of $X$ .

Proof. Pick $a,b \in \operatorname{lin}(\Omega)$ and $\lambda \in (0,1)$ . Then there are vectors $u,v \in \Omega$ with $[u,a)\subset \Omega$ and $[v,b)\subset \Omega$ . Denoting $x_\lambda := \lambda a + (1-\lambda)b$ and $w_\lambda := \lambda u + (1-\lambda)v \in \Omega$ , we see that $[w_\lambda, x_\lambda)\subset \Omega$ , and so $x_\lambda \in \operatorname{lin}(\Omega)$ . This verifies the convexity of $\operatorname{lin}(\Omega)$ . $\square$

Now we are ready to verify the aforementioned relationship.

Proposition 3.5. (Linear closure equals closure for solid convex sets) Let $X$ be a normed vector space, and let $\Omega$ be a convex subset of $X$ with nonempty interior. Then we have

\operatorname{lin}(\Omega) = \overline{\Omega}.

The next property of cores in vector spaces is a precise counterpart of the one known for interiors of convex sets in spaces with normed structure.

Proposition 3.6. (Segments from core points stay in the core) Let $\Omega$ be a convex set in a vector space $X$ and let $a \in \operatorname{core}(\Omega)$ . Then

(1-\lambda)a + \lambda b \in \operatorname{core}(\Omega) \quad \text{for all } b \in \Omega \text{ and all } \lambda \in [0,1).

Proof. Take any $b \in \Omega$ and any $\lambda \in [0,1)$ . Put $x:=(1-\lambda)a + \lambda b \in \Omega$ . We need to show that $x \in \operatorname{core}(\Omega)$ . Indeed, for any $v \in X$ find $\delta>0$ with $a + \gamma v \in \Omega$ whenever $|\gamma|<\delta$ and observe that

x + \gamma v = (1-\lambda)(a+\gamma v) + \lambda b \in \Omega \quad \text{for all } \gamma \text{ with } |\gamma|<\delta,

which tells us that $x \in \operatorname{core}(\Omega)$ and completes the proof. $\square$

The obtained proposition leads to an interesting observation.

Corollary 3.7. (Idempotence of the core operator) For any convex set $\Omega$ in a vector space $X$ we have

\operatorname{core}(\operatorname{core}(\Omega)) = \operatorname{core}(\Omega).

Proof. The inclusion $\operatorname{core}(\operatorname{core}(\Omega)) \subset \operatorname{core}(\Omega)$ follows from the definition of core. To prove the opposite inclusion, take $a \in \operatorname{core}(\Omega)$ and pick any $v \in X$ . Find $\delta>0$ with $a+\gamma v \in \Omega$ whenever $|\gamma|<\delta$ . Then Proposition 3.6 tells us that $a+\gamma v \in \operatorname{core}(\Omega)$ for all scalar $\gamma$ with $|\gamma|<\delta/2$ , and thus we arrive at $a \in \operatorname{core}(\operatorname{core}(\Omega))$ . $\square$

3.1.2 Minkowski Gauges

Let $\Omega$ be a nonempty absorbing set in a vector space $X$ . The Minkowski function $p_\Omega: X \to \overline{\mathbb{R}}$ , known also as the Minkowski gauge, is defined by

p_\Omega(x) := \inf\{\, t \ge 0 \mid x \in t\Omega \,\}, \qquad x \in X. \qquad (3.4)

Definition 3.8. (Subadditive, positively homogeneous, and sublinear functions) Let $f : X \to \mathbb{R}$ be a function defined on a vector space $X$ .

(i) The function $f$ is said to be subadditive if

p(x+y) \le p(x) + p(y) \quad \text{for all } x,y \in X.

(ii) The function $f$ is said to be positively homogeneous if

p(\lambda x) = \lambda p(x) \quad \text{for all } x \in X \text{ and any scalar } \lambda > 0.

If $f$ is both subadditive and positively homogeneous, then it is called a sublinear function.

The next theorem presents some properties of the Minkowski gauge.

Theorem 3.9. (Properties of the Minkowski functional of a convex set) Let $\Omega$ be an absorbing convex set in a vector space $X$ . Then the Minkowski function $p_\Omega$ has the following properties:

(i) $p_\Omega$ is subadditive and positively homogeneous.

(ii) $\{x \in X \mid p_\Omega(x) < 1\} = \operatorname{core}(\Omega)$ .

(iii) $\{x \in X \mid p_\Omega(x) \le 1\} = \operatorname{lin}(\Omega)$ .

Proof. It follows from the definition of the Minkowski function that $p_\Omega$ is a real-valued function, i.e., $p_\Omega(x) < \infty$ for all $x \in X$ . Indeed, since $\Omega$ is absorbing, for any $x \in X$ there exists $\delta > 0$ such that $t x \in \Omega$ whenever $|t|<\delta$ . Taking $t := \delta/2$ yields $x \in \frac{2}{\delta}\Omega$ and thus $p_\Omega(x) \le 2/\delta < \infty$ .

(a) To check the subadditivity of $p_\Omega$ , for any $x,y \in X$ pick $\varepsilon>0$ and find numbers $s,t >0$ such that $s < p_\Omega(x)+\varepsilon$ , $t < p_\Omega(y)+\varepsilon$ , and $x \in s\Omega$ , $y \in t\Omega$ . Then, since $\Omega$ is convex, we have $x+y \in s\Omega + t\Omega = (s+t)\Omega$ , and so

p_\Omega(x+y) \le s+t < p_\Omega(x) + p_\Omega(y) + 2\varepsilon.

This implies $p_\Omega(x+y) \le p_\Omega(x) + p_\Omega(y)$ and thus shows that $p_\Omega$ is subadditive. Taking further $x \in X$ and $\lambda>0$ , we have

\begin{aligned} p_\Omega(\lambda x) &= \inf\{\, t>0 \mid \lambda x \in t\Omega \,\} = \inf\{\, t>0 \mid x \in (t/\lambda)\Omega \,\} \\\\ &= \lambda \inf\{\, s>0 \mid x \in s\Omega \,\} = \lambda p_\Omega(x), \end{aligned}

which justifies the positive homogeneity of Minkowski function.

(b) Pick any $x \in X$ with $p_\Omega(x) < 1$ and find $\lambda \in (0,1)$ such that $x \in \lambda\Omega$ . Since $\Omega$ is absorbing, for any $v \in X$ there exists $\gamma>0$ with $\alpha v \in \Omega$ whenever $|\alpha|<\gamma$ . Thus $(1-\lambda)\alpha v \in (1-\lambda)\Omega$ for all $\alpha \in \mathbb{R}$ with $|\alpha|<\gamma$ . It follows from the convexity of $\Omega$ that

x + (1-\lambda)\alpha v \in \lambda\Omega + (1-\lambda)\Omega = \Omega \quad \text{whenever } |\alpha|<\gamma.

This verifies the inclusion $x \in \operatorname{core}(\Omega)$ [^1].

Conversely, suppose that $x \in \operatorname{core}(\Omega)$ and find $\gamma>0$ with $x+\gamma x \in \Omega$ . Then we get $p_\Omega(x) \le \frac{1}{1+\gamma} < 1$ , which completes the proof of (b).

(c) Fix any $x \in X$ with $p(x) \le 1$ and any $\lambda \in (0,1)$ . Then $p(\lambda x) < 1$ and therefore $\lambda x \in \operatorname{core}(\Omega) \subset \Omega$ . It follows that $(1-\lambda)x \in \Omega$ for all $\lambda \in (0,1)$ , and hence $[0,x)\subset \Omega$ . Thus we arrive at $x \in \operatorname{lin}(\Omega)$ . To prove the opposite implication, take $x \in \operatorname{lin}(\Omega)$ and find $w \in \Omega$ such that $[w,x)\subset \Omega$ . Then we have the relationships

\begin{aligned} \left(1-\frac{1}{n}\right)p_\Omega(x) &= p_\Omega\left(\left(1-\frac{1}{n}\right)x\right) = p_\Omega\left(\left(1-\frac{1}{n}\right)x + \frac{1}{n}w + \left(-\frac{1}{n}w\right)\right) \\\\ &\le p_\Omega\left(\left(1-\frac{1}{n}\right)x + \frac{1}{n}w\right) + p_\Omega\left(-\frac{1}{n}w\right) \\\\ &\le 1 + \frac{1}{n}p_\Omega(-w). \end{aligned}

Letting finally $n \to \infty$ tells us that $p_\Omega(x) \le 1$ , which completes the proof. $\square$

[^1]: We can prove that $x \in \operatorname{core}(\Omega)$ iff for any $v \in X$ there exists $\delta > 0$ such that $x + c\lambda v \in \Omega$ whenever $|\lambda|<\delta$ , where $c>0$ is a constant.

In normed vector spaces we obtain the following useful consequences.

Corollary 3.10. (Continuity and level sets of the Minkowski functional) Let $X$ be a normed vector space, and let $\Omega$ be a convex set such that $0 \in \operatorname{int}(\Omega)$ . Then $p_\Omega$ is continuous, and we have

\operatorname{int}(\Omega) = \{x \in X \mid p_\Omega(x) < 1\} \quad\text{and}\quad \overline{\Omega} = \{x \in X \mid p_\Omega(x) \le 1\}.

Proof. Since $0 \in \operatorname{int}(\Omega)$ , there exists $r>0$ such that $B(0;r) \subset \Omega$ . Then

p_\Omega(x) \le p_{B(0;r)}(x) = \frac{1}{r}\|x\| \quad \text{for all } x \in X.

Now, for any $x,y \in X$ we have

p_\Omega(x) = p_\Omega(x-y+y) \le p_\Omega(x-y) + p_\Omega(y) \le \frac{1}{r}\|x-y\| + p_\Omega(y).

This implies that

p_\Omega(x) - p_\Omega(y) \le \frac{1}{r}\|x-y\|.

By changing the role of $x$ and $y$ we also have

p_\Omega(y) - p_\Omega(x) \le \frac{1}{r}\|x-y\|.

Thus,

|p_\Omega(x) - p_\Omega(y)| \le \frac{1}{r}\|x-y\|,

which justifies the continuity of $p_\Omega$ .

Using now Theorem 3.9(b) tells us that

\{x \in X \mid p_\Omega(x) < 1\} = \operatorname{core}(\Omega) = \operatorname{int}(\Omega)

due to $\operatorname{int}(\Omega) \ne \emptyset$ . Finally, the usage of Theorem 3.9(c) together with Proposition 3.5 ensures the fulfillment of

\{x \in X \mid p_\Omega(x) \le 1\} = \operatorname{lin}(\Omega) = \overline{\Omega}

and thus completes the proof of the corollary. $\square$

3.2 Hahn-Banach Theorems

Let $X$ be a vector space, let $Y$ be a linear subspace of $X$ , and let $f$ be a linear functional defined on $Y$ with some restraint. The Hahn-Banach theorems allow us to extend $f$ to a linear functional $F$ defined on the whole space $X$ such that $F$ also satisfies the restraint as for $f$ .

3.2.1 Hahn-Banach theorem in real vector spaces

Theorem 3.11. (Hahn-Banach theorem in real vector spaces) Let $X$ be a real vector space, let $Y$ be a subspace of $X$ , and let $p: X \to \mathbb{R}$ be a sublinear function on $X$ . Consider a linear functional $f : Y \to \mathbb{R}$ which satisfies the condition

f(y) \le p(y) \quad \text{for all } y \in Y.

Then there exists a linear functional $F : X \to \mathbb{R}$ such that

F(y) = f(y) \quad \text{for all } y \in Y,

F(x) \le p(x) \quad \text{for all } x \in X.

Proof. By an extension of $f$ we mean a linear functional $g : D_g \to \mathbb{R}$ , where $D_g$ is a linear subspace of $X$ containing $Y$ , and $g$ satisfies the following conditions:

g(y) = f(y) \quad \text{for all } y \in Y,

g(x) \le p(x) \quad \text{for all } x \in D_g.

Denote by $\mathcal{F}$ the set of all extensions of $f$ . Since $f \in \mathcal{F}$ , we see that $\mathcal{F}$ is not empty. For $g_1, g_2 \in \mathcal{F}$ we define the following binary relation:

g_1 \le g_2 \iff \begin{cases} D_{g_1} \subset D_{g_2},\\\\ g_1(x) = g_2(x) \text{ for all } x \in D_{g_1}. \end{cases}

Then " $\le$ " is a partially ordered relation on $\mathcal{F}$ . Let $\mathcal{N}$ be a totally ordered subset of $\mathcal{F}$ . Define the set

D^\ast = \bigcup_{g \in \mathcal{N}} D_g.

Fix any $x \in D^\ast$ . Then there is a functional $g \in \mathcal{N}$ such that $x \in D_g$ and we define $g^\ast (x) = g(x)$ . Since $\mathcal{N}$ is a totally ordered set, $D^\ast$ is a linear subspace of $X$ . Furthermore, $g^\ast$ is well-defined as a linear functional on $D^\ast$ . Then

g^\ast (x) = g(x) \le p(x), \quad \text{for all } x \in D_g,

and thus $g^\ast$ is an upper bound of $\mathcal{N}$ . By Zorn's lemma, there exists a maximal element $F$ in $\mathcal{F}$ .

Next, we will show the domain $D$ of $F$ is the entire space $X$ , and then we conclude that $F$ is a desire linear functional. On the contrary, suppose that $D \subsetneq X$ . Then there is an element $x_0 \in X \setminus D$ . Since $D$ is a linear subspace, $x_0 \ne 0$ . Denote

Z = D \oplus \operatorname{span}\{x_0\} = \{x + \lambda x_0 \mid x \in D,\ \lambda \in \mathbb{R}\},

where $\oplus$ denotes the direct sum.

Fix a real number $c$ . For any $z = x + \lambda x_0 \in Z$ let $E(z) = F(x) + \lambda c$ . Then $E$ is a linear functional which extends $F$ to the linear subspace $Z$ . Let us choose a number $c$ such that $E(z) \le p(z)$ for all $z \in Z$ and deduce that $E$ is an extension of $f$ . For any $x,x' \in D$ , we have

F(x) - F(x') = F(x-x') \le p(x-x') \le p(x+x_0) + p(-x' - x_0),

which implies that

-F(x') - p(-x' - x_0) \le p(x+x_0) - F(x).

Since this inequality holds for all $x,x' \in D$ , we have

\sup_{x \in D}\{-F(x) - p(-x - x_0)\} \le \inf_{x \in D}\{p(x+x_0) - F(x)\}.

Thus, we can choose $c \in \mathbb{R}$ such that

\sup_{x \in D}\{-F(x) - p(-x - x_0)\} \le c \le \inf_{x \in D}\{p(x+x_0) - F(x)\}. \qquad (3.5)

If $z \in Z\setminus D$ , then $z = \lambda x_0 + x$ for some $\lambda \ne 0$ . Consider the following cases:

Case 1: $\lambda > 0$ . Using the second inequality in (3.5), we have

c \le p\left(\frac{x}{\lambda} + x_0\right) - F\left(\frac{x}{\lambda}\right).

Multiplying both sides of this inequality by $\lambda$ , we obtain

\lambda c + F(x) \le p(x+\lambda x_0).

Case 2: $\lambda < 0$ . Using the first inequality in (3.5), we have

-F\left(\frac{x}{\lambda}\right) - p\left(-\frac{x}{\lambda} - x_0\right) \le c.

Multiplying both sides of this inequality by $-\lambda>0$ , we obtain

\lambda F\left(\frac{x}{\lambda}\right) - (-\lambda)p\left(-\frac{x}{\lambda} - x_0\right) \le -\lambda c.

Thus, $F(x) - p(x+\lambda x_0) \le -\lambda c$ , and hence $F(x) + \lambda c \le p(x+\lambda x_0)$ . In both cases, we all have $E(z) \le p(z)$ . Therefore, $F \le E$ and $F \ne E$ . This contradicts the maximality of the functional $F$ and thus completes the proof of the theorem. $\square$

3.2.2 Hahn-Banach theorem in general vector spaces

Definition 3.12. (Seminorm) A function $p : X \to \mathbb{R}$ defined on a vector space $X$ over a field $K$ (either $\mathbb{R}$ or $\mathbb{C}$ ) is called a seminorm if

(i) $p(x+y) \le p(x) + p(y)$ for all $x,y \in X$ .

(ii) $p(\lambda x) = |\lambda| p(x)$ for all $x \in X$ and scalar $\lambda$ .

From Theorem 3.11 we can prove the following theorem.

Theorem 3.13. (Hahn-Banach extension dominated by a seminorm (real case)) Let $X$ be a real vector space, let $Y$ be a linear subspace of $X$ , and let $p : X \to \mathbb{R}$ be a seminorm on $X$ . Let $f : Y \to \mathbb{R}$ be a linear functional which satisfies the condition:

|f(y)| \le p(y) \quad \text{for all } y \in Y.

Then there exists a linear functional $F$ defined on $X$ such that

F(y) = f(y) \quad \text{for all } y \in Y,

|F(x)| \le p(x) \quad \text{for all } x \in X.

We can obtain the following version of the Hahn-Banach theorem for complex vector spaces.

Theorem 3.14. (Hahn-Banach theorem in complex vector spaces) Let $X$ be a complex vector space, let $Y$ be a linear subspace of $X$ , and let $p : X \to \mathbb{R}$ be a seminorm on $X$ . Let $f : Y \to \mathbb{C}$ be a complex linear functional which satisfies the condition:

|f(y)| \le p(y) \quad \text{for all } y \in Y.

Then there exists a linear functional $F$ defined on $X$ such that

F(y) = f(y) \quad \text{for all } y \in Y,

|F(x)| \le p(x) \quad \text{for all } x \in X.

Proof. Since $f$ is a complex functional defined on $Y$ then $f(x)$ can be represented as

f(y) = f_1(y) + i f_2(y) \in \mathbb{C} \quad \text{for all } y \in Y.

It is easy to see that $f_1, f_2$ are real linear functionals on $Y$ satisfying

f_1(x) \le |f_1(y)| \le |f(y)| \le p(y) \quad \text{for all } y \in Y.

Moreover,

f(ix) = i f(x), \ \text{or}\ f_1(ix) + i f_2(ix) = i f_1(x) - f_2(x),

and thus $f_2(x) = -f_1(ix)$ . Therefore,

f(x) = f_1(x) - i f_1(ix).

Since $\mathbb{R} \subset \mathbb{C}$ , we are able to consider $X$ as a real vector space (by restricting the scalar multiplication on $\mathbb{R}$ ). Applying Hahn-Banach theorem for the functional $f_1(x)$ in the real vector space $X$ , one obtains a real linear functional $F_1$ defined on $X$ such that

F_1(x) = f_1(x),

F_1(x) \le p(x) \quad \text{for all } x \in X.

Furthermore,

-F_1(x) = F_1(-x) \le p(-x) = p(x).

Then we get $|F_1(x)| \le p(x)$ . Let $F(x) = F_1(x) - iF_1(ix)$ for all $x \in X$ . Then $F(x)$ is a complex linear functional defined on the complex vector space $X$ . It is obvious that $x \in Y$ then $F(x) = f(x)$ . For any $x \in X$ , by the polar form of a complex number, one has $F(x) = |F(x)|e^{i\theta}$ . Therefore

\begin{aligned} |F(x)| &= e^{-i\theta}F(x) = F(e^{-i\theta}x) = F_1(e^{-i\theta}x) \\\\ &\le p(e^{-i\theta}x) = |e^{-i\theta}|p(x) = p(x). \end{aligned}

Thus the complex linear functional $F$ is completely defined. $\square$

Remark 3.15. By these theorems, in order to define a linear functional on a vector space $X$ satisfying some conditions, it is necessary to construct a linear functional on some small subspace of $X$ then extend this functional to the whole space $X$ .

3.2.3 Hahn-Banach theorem in normed vector spaces

Let $X$ be a normed space over the field $K$ ( $\mathbb{R}$ or $\mathbb{C}$ ). Then $K$ is also a normed space where the norm is defined by $|\alpha| = |\alpha|$ (here $|\cdot|$ is the absolute value or module of a number in $K$ ). Remember that a linear operator from $X$ into $K$ is called a linear functional. Thus, a linear functional $f$ is bounded if

(\exists M>0)\ (\forall x \in X):\ |f(x)| \le M\|x\|.

This condition holds iff $f$ is continuous on $X$ . Then the norm of $f$ is defined by

\|f\| = \sup_{\|x\|\le 1} |f(x)|.

Theorem 3.16. (Hahn-Banach theorem in normed spaces) Let $X$ be a normed space, let $Y$ be a subspace of $X$ , and let $f : Y \to K$ be a bounded linear functional on $Y$ . Then there exists a linear bounded functional $F$ defined on $X$ such that

F(y) = f(y) \quad \text{for all } y \in Y,

\|F\| = \|f\|.

Proof. For any $x \in X$ , define $p(x) = \|f\|\|x\|$ . Then $p$ is a seminorm on $X$ and $|f(y)| \le p(y)$ for all $y \in Y$ . By the Hahn-Banach theorem in vector spaces, there exists a linear functional $F$ defined on $X$ such that

F(y) = f(y) \quad \text{for all } y \in Y,

|F(x)| \le p(x) = \|f\|\|x\| \quad \text{for all } x \in X.

Thus, $F$ is bounded and $\|F\| \le \|f\|$ . We also have

\|F\| = \sup_{\|x\|\le 1,\ x\in X} |F(x)| \ge \sup_{\|x\|\le 1,\ x\in Y} |F(x)| = \sup_{\|x\|\le 1,\ x\in Y} |f(x)| = \|f\|.

Therefore, we deduce that $\|F\| = \|f\|$ and complete the proof. $\square$

Theorem 3.17. (Separating a point and a subspace) Let $Y$ be a subspace of a normed space $X$ , let $x_0$ be a point in $X$ such that $d(x_0,Y) = \inf_{y\in Y}\|x_0 - y\| = d >0$ . Then there exists a bounded linear functional on $X$ such that:

(i) $f(y) = 0$ for all $y \in Y$ .

(ii) $\|f\| = 1/d$ .

(iii) $f(x_0) = 1$ .

Proof. Since $d>0$ , we see that $x_0 \notin Y$ . Let $Z = Y \oplus \operatorname{span}\{x_0\}$ (the direct sum of $Y$ and the span of $x_0$ ). Then any $z \in Z$ can be expressed as $z = y + \lambda x_0$ for $y \in Y$ , $\lambda \in K$ . Note that $z \in Y$ iff $\lambda = 0$ . Define a linear functional $g$ on $Z$ by

g(z) = g(y+\lambda x_0) = \lambda.

If $z = y+\lambda x_0 \notin Y$ , then $\lambda \ne 0$ and $\frac{y}{\lambda} \in Y$ . Thus,

\|z\| = \|y+\lambda x_0\| = |\lambda|\left\|\frac{y}{\lambda} + x_0\right\| \ge |\lambda|d.

This implies that $|g(z)| = |\lambda| \le \frac{1}{d}\|z\|$ and hence $\|g\| \le \frac{1}{d}$ . Since $d = \inf_{y\in Y}\|x_0 - y\|$ , there exists a sequence $\{y_n\} \subset Y$ such that $\|x_0 - y_n\| \to d$ . Letting $z_n = -y_n + x_0$ , we get $g(z_n) = 1$ . Furthermore,

1 = g(z_n) \le \|g\|\|z_n\| = \|g\|\|x_0 - y_n\| \to \|g\|d.

Thus, $\|g\| = \frac{1}{d}$ . By Theorem 3.16, there exists a bounded linear functional $f$ defined on $X$ which is an extension of $g$ and $\|f\| = \|g\| = \frac{1}{d}$ . Since $x_0 \in Z$ , $x_0 = 0 + 1x_0$ we see $g(x_0) = 1$ , and thus $f(x_0) = g(x_0) = 1.$ $\square$

Corollary 3.18. (Existence of a functional attaining its norm at a point) For any element $z_0 \in X \setminus \{0\}$ , there exists a bounded linear functional $f$ defined on $X$ such that $\|f\| = 1$ and $f(z_0) = \|z_0\|$ .

Proof. Using Theorem 3.17 for $Y = \{0\}$ and $x_0 = \frac{z_0}{\|z_0\|}$ , we deduce that there is a bounded linear functional $f$ defined on $X$ such that $f(x_0) = 1$ and $\|f\| = \frac{1}{d}$ . Thus, $f(z_0) = \|z_0\|$ and $\|f\| = 1$ . $\square$

Remark 3.19. By this corollary, we see that the the number of bounded linear functionals defined on a normed space $X$ is plenty enough in the sense that for any two distinct elements $x$ and $y$ in $X$ , there exists a bounded linear functional $f$ separating $x$ and $y$ , i.e., $f(x) - f(y) = f(x-y) = \|x-y\| \ne 0$ .

3.3 Quotient Spaces, Codimensions, Affine Sets, and Hyperplanes

3.3.1 Quotient spaces and codimensions

The main goal of this subsection is to discuss some basic facts about quotient spaces. Given a linear subspace $L$ of a topological vector space $X$ , recall that the quotient space $X/L$ is defined by

X/L := \{x+L \mid x \in X\}.

The addition and the scalar multiplication on $X/L$ are given by

(x+L) + (y+L) := (x+y) + L \quad \text{and} \quad \alpha(x+L) := \alpha x + L

for $x,y \in X$ and scalar $\alpha$ . Since $L$ is a linear subspace, both operations above are well-defined. It is easy to check that $X/L$ endowed with these operations is a vector space.

Definition 3.20. (Codimension) Let $L$ be a linear subspace of a vector space $X$ . The codimension of $L$ in $X$ , denoted by $\operatorname{codim}(L)$ , is the dimension of the quotient space $X/L$ , i.e.,

\operatorname{codim}(L) := \dim(X/L).

The following two propositions deal with vector spaces of codimension one.

Proposition 3.21. (Kernel of a nonzero linear functional has codimension one) Let $X$ be a vector space over a field $K$ (either $\mathbb{R}$ or $\mathbb{C}$ ), and let $f : X \to K$ be a nonzero linear function. Then we have

\operatorname{codim}(\ker f) = 1.

Proof. Denote $L := \ker(f)$ (the kernel of $f$ ) and fix $x_0 \in X$ with $f(x_0) = \alpha_0 \ne 0$ . To show that $\operatorname{span}\{x_0 + L\} = X/L$ , take $x \in X$ such that $x+L \in X/L$ and get $f(x) = \lambda f(x_0) = f(\lambda x_0)$ with $\lambda := \frac{f(x)}{f(x_0)}$ . It follows that $f(x-\lambda x_0) = 0$ , and so $x-\lambda x_0 \in L$ . Thus we get the equality

x+L = \lambda(x_0+L),

which shows that $\operatorname{span}\{x_0+L\} = X/L$ , and hence $\operatorname{codim}(L) = 1$ . $\square$

Proposition 3.22. (Codimension one subspaces yield direct sum decompositions) Let $L$ be a subspace of a vector space $X$ such that $\operatorname{codim}(L) = 1$ . If $x_0 \notin L$ , then we have

L \oplus \operatorname{span}\{x_0\} = X.

Proof. Since $\dim(X/L)=1$ and $x_0+L$ is a nonzero element in $X/L$ , we see that $\operatorname{span}\{x_0+L\} = X/L$ . Then for any $x \in X$ there exists a scalar $\lambda$ with $x+L = \lambda(x_0+L) = \lambda x_0 + L$ . It follows that $x \in \lambda x_0 + L \subset L + \operatorname{span}\{x_0\}$ . Thus $X = L + \operatorname{span}\{x_0\}$ since the opposite inclusion is obvious. We can easily check that $L \cap \operatorname{span}\{x_0\} = \{0\}$ . $\square$

3.3.2 Affine Sets and Hyperplanes

Fig. 3.1. An affine set (figure omitted).

Next we proceed with the definition and properties of affine sets; see the illustration in Figure 3.1. Given two elements $a$ and $b$ in a vector space $X$ , the line connecting them is defined by

\mathcal{L}[a,b] := \{\lambda a + (1-\lambda)b \mid \lambda \in \mathbb{R}\}.

If $a=b$ , then $\mathcal{L}[a,b]$ reduces to the singleton $\{a\}$ .

Definition 3.23. (Affine set) Let $\Omega$ be a subset of a vector space $X$ . We say that $\Omega$ is an affine set if for any $a,b \in \Omega$ we have $\mathcal{L}[a,b] \subset \Omega$ .

The intersection of affine sets is affine, and so we can define the smallest affine set containing $\Omega$ .

Definition 3.24. (Affine hull and affine combination) The affine hull of a set $\Omega$ is defined by

\operatorname{aff}(\Omega) := \bigcap\{\, C \mid C \text{ is affine and } \Omega \subset C \,\}.

An element $x \in X$ of the form

x = \sum_{i=1}^m \lambda_i \omega_i, \quad \text{where } \sum_{i=1}^m \lambda_i = 1,

is called an affine combination of $\omega_1,\dots,\omega_m$ .

The proof of the next proposition is straightforward and thus is omitted.

Fig. 3.2. The affine hull of a set (figure omitted).

Proposition 3.25. (Properties of affine sets and affine hulls) The following assertions are true.

(i) A set $\Omega$ in a vector space is affine if and only if $\Omega$ contains all affine combinations of its elements.

(ii) If $\Omega_1$ and $\Omega_2$ are affine subsets of a vector space $X$ , then the sum $\Omega_1 + \Omega_2$ and the scalar product $\lambda \Omega$ for a scalar $\lambda$ are also affine subsets.

(iii) Let $B : X \to Y$ be an affine mapping between vector spaces $X$ and $Y$ . If $\Omega$ is an affine subset of $X$ and $\hat{\Omega}$ is an affine subset of $Y$ , then the image $B(\Omega)$ is an affine subset of $Y$ and the inverse image $B^{-1}(\hat{\Omega})$ is an affine subset of $X$ .

(iv) Given a subset $\Omega$ of a vector space $X$ , its affine hull is the smallest affine set containing $\Omega$ . In addition, we have the representation

\operatorname{aff}(\Omega) = \left\{\ \sum_{i=1}^m \lambda_i \omega_i \ \middle|\ \sum_{i=1}^m \lambda_i = 1,\ \omega_i \in \Omega,\ m \in \mathbb{N} \right\}.

(v) A set $\Omega$ in a vector space is a linear subspace if and only if $\Omega$ is an affine set containing the origin.

Now we consider further relationships between affine sets and linear subspaces.

Lemma 3.26. (Affine sets are translates of subspaces) A nonempty subset $\Omega$ of a vector space $X$ is affine if and only if $\Omega - \omega$ is a linear subspace of $X$ for any $\omega \in \Omega$ .

Proof. Suppose that $\Omega$ is affine. Then it follows from the last assertion of Proposition 3.25 that the set $\Omega-\omega$ is a linear subspace for any $\omega \in \Omega$ . Conversely, fix $\omega \in \Omega$ and suppose that $\Omega-\omega$ is a linear subspace, denoted by $L$ . Then the set $\Omega = \omega + L$ is obviously affine. $\square$

Definition 3.27. (Parallel affine set) An affine set $\Omega$ in a vector space $X$ is said to be parallel to a linear subspace $L \subset X$ if $\Omega = \omega + L$ for some $\omega \in \Omega$ .

Proposition 3.28. (Parallel subspace to an affine set) Let $\Omega$ be a nonempty affine subset of a vector space $X$ . Then it is parallel to the unique linear subspace $L$ of $X$ defined by $L := \Omega - \Omega$ .

Proof. Given an affine set $\Omega \ne \emptyset$ , fix $\omega \in \Omega$ and consider the linear subspace $L := \Omega - \omega$ parallel to $\Omega$ . To verify its uniqueness, take any $\omega_1,\omega_2 \in \Omega$ and the corresponding linear subspaces $L_1,L_2$ with $\Omega = \omega_1 + L_1 = \omega_2 + L_2$ . Then $L_1 = \omega_2 - \omega_1 + L_2$ . Since $0 \in L_1$ , we have $\omega_1 - \omega_2 \in L_2$ . This yields $\omega_2 - \omega_1 \in L_2$ and thus $L_1 = \omega_2 - \omega_1 + L_2 \subset L_2$ . In the same way we have $L_2 \subset L_1$ , and so $L_1 = L_2$ .

Now we check the representation $L = \Omega - \Omega$ . We have $\Omega = \omega + L$ with the unique linear subspace $L$ parallel to $\Omega$ and some $\omega \in \Omega$ . Then $L = \Omega - \omega \subset \Omega - \Omega$ . Take any $x = u - w$ with $u,w \in \Omega$ and observe that $\Omega - w$ is a linear subspace parallel to $\Omega$ . Hence $\Omega - w = L$ by uniqueness of $L$ proved above. This ensures that $x \in \Omega - w = L$ , and thus we arrive at $\Omega - \Omega \subset L$ . $\square$

Definition 3.29. (Hyperplane) An affine subset $\Omega$ of a vector space $X$ is called a hyperplane if its codimension is one. This means that the codimension of the unique linear subspace of $X$ parallel to $\Omega$ is one.

Proposition 3.30. (Hyperplanes are level sets of nonzero linear functionals) A subset $\Omega$ of a vector space $X$ over $\mathbb{R}$ is a hyperplane if and only if there exist a nonzero linear function $f : X \to \mathbb{R}$ and a number $\alpha \in \mathbb{R}$ that provide the representation

\Omega = \{x \in X \mid f(x) = \alpha\}. \qquad (3.6)

Proof. Let $\Omega$ be a hyperplane. Then there exist a vector $w \in \Omega$ and a linear subspace $L \subset X$ of codimension one such that $\Omega = w + L$ . Picking any $x_0 \notin L$ and using Proposition 3.22 give us $L \oplus \operatorname{span}\{x_0\} = X$ . It says that for any $x \in X$ there exist a unique pair $(m,\lambda) \in L \times \mathbb{R}$ with

x = m + \lambda x_0.

For these fixed elements $x$ and $w$ we define $f(x) := \lambda$ and $\alpha := f(w)$ . It is easy to see that $f$ is a nonzero linear function on $X$ ensuring representation (3.6) with the selected number $\alpha \in \mathbb{R}$ .

Conversely, suppose that representation (3.6) holds with some nonzero linear function $f : X \to \mathbb{R}$ and a number $\alpha \in \mathbb{R}$ . Choose any $w \in \Omega$ and let $L := \ker(f)$ , which gives us $\Omega = w + L$ . Employing now Proposition 3.21, we have $\operatorname{codim}(L) = 1$ , and so the set $\Omega$ is a hyperplane in $X$ . $\square$

3.4 Convex Separation: Geometric Forms of Hahn-Banach Theorems

3.4.1 Convex separation in vector spaces

Definition 3.31. (Separation by a hyperplane) Let $\Omega_1$ and $\Omega_2$ be two nonempty sets in a real vector space $X$ . We say that $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane if there exists a nonzero linear functional $f \in X' \setminus \{0\}$ such that

f(x) \le f(y) \quad \text{whenever } x \in \Omega_1,\, y \in \Omega_2. \qquad (3.7)

Proposition 3.32. (Separation by hyperplanes via sup/inf inequality) Let $\Omega_1$ and $\Omega_2$ be two nonempty sets in a real vector space $X$ . Then $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane if and only if there exists a nonzero linear functional $f \in X' \setminus \{0\}$ such that

\sup_{x \in \Omega_1} f(x) \le \inf_{y \in \Omega_2} f(y). \qquad (3.8)

Proof. Suppose that $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane. Then there exists $f \in X'\setminus\{0\}$ such that (3.7) is satisfied. Fix any $y \in \Omega_2$ . By (3.7), the number $f(y)$ is an upper bound for the set $A = \{f(x)\mid x \in \Omega_1\} \subset \mathbb{R}$ . By the Completeness Axiom and the definition of supremum, $\sup_{x\in\Omega_1} f(x)$ is a real number and

\sup A = \sup_{x \in \Omega_1} f(x) \le f(y).

Then $\sup_{x\in\Omega_1} f(x)$ is a lower bound for the set $B = \{f(y)\mid y \in \Omega_2\} \subset \mathbb{R}$ . It follows that $\sup A \le \inf B$ , which implies that (3.8) is satisfied. $\square$

Remark 3.33. (i) If $f \in X'\setminus\{0\}$ is a nonzero linear functional such that (3.8) is satisfied, then both $\sup_{x\in\Omega_1} f(x)$ and $\inf_{y\in\Omega_2} f(y)$ are real numbers. Indeed, in the setting of Proposition 3.32, since $A$ is nonempty, we see that $-\infty < \sup A \le \inf B$ . Similarly, $\inf B < \infty$ . Thus, both $\sup A$ and $\inf B$ are real numbers such that $\sup A \le \inf B$ . Then $a \le b$ whenever $a \in A$ and $b \in B$ . Therefore, (3.7) is satisfied.

(ii) Suppose that $\Omega_1$ and $\Omega_2$ are two nonempty sets a real vector space that can be separated by a hyperplane. Then there exists $f \in X'\setminus\{0\}$ such that (3.8) is satisfied. Choose a real number $\alpha$ such that

\sup_{x \in \Omega_1} f(x) \le \alpha \le \inf_{y \in \Omega_2} f(y).

Then the set $H = \{x \in X \mid f(x) = \alpha\}$ is a hyperplane and

f(x) \le \alpha \le f(y) \quad \text{whenever } x \in \Omega_1,\, y \in \Omega_2.

Geometrically, $\Omega_1$ lies in one side of the hyperplane $H$ , and $\Omega_2$ lies in the other side.

(iii) Using the element $-f \in X'\setminus\{0\}$ in the definition of convex separation, we see that two nonempty sets $\Omega_1$ and $\Omega_2$ in a normed space can be separated by a hyperplane iff $\Omega_2$ and $\Omega_1$ can be separated by a hyperplane.

Theorem 3.34. (Separation of a point from a convex set via the core) Let $X$ be a real vector space, let $x_0 \in X$ , and let $\Omega$ be a convex set in $X$ . Suppose that $\operatorname{core}\Omega \ne \emptyset$ and $x_0 \notin \operatorname{core}\Omega$ . Then the sets $\Omega$ and $\{x_0\}$ can be separated by a hyperplane, i.e., there exists $f \in X'\setminus\{0\}$ such that

f(x) \le f(x_0) \quad \text{for all } x \in \Omega.

Proof. First consider the case where $0 \in \operatorname{core}\Omega$ . Let $p_\Omega$ be the Minkowski function associated with $\Omega$ and consider the linear subspace $Y = \operatorname{span}\{x_0\}$ of $X$ . Note that $x_0 \ne 0$ because $x_0 \notin \operatorname{core}\Omega$ . Define the linear function $g : Y \to \mathbb{R}$ by $g(\lambda x_0) = \lambda$ for $\lambda \in \mathbb{R}$ . Obviously, $g$ is a linear functional. Next, we will show that

g(y) \le p_\Omega(y) \quad \text{for all } y \in Y.

Indeed, take any $y \in Y$ and find $\lambda \in \mathbb{R}$ such that $y = \lambda x_0$ . If $\lambda \le 0$ , then $g(y) = \lambda \le p_\Omega(y)$ because $p_\Omega$ has non-negative values. Now, suppose that $\lambda > 0$ . Since $p_\Omega$ is positively homogeneous and $p_\Omega(x_0) \ge 1$ (why?), we have

g(y) = g(\lambda x_0) = \lambda \le \lambda p_\Omega(x_0) = p_\Omega(\lambda x_0) = p(y). \qquad (3.9)

By the Hahn-Banach theorem, there exists a linear function $f : X \to \mathbb{R}$ such that $f(y) = g(y)$ for all $y \in Y$ and

f(x) \le p_\Omega(x) \quad \text{for all } x \in X.

Observe that $f(x_0) = g(x_0) = 1$ , so $f \ne 0$ . For any $x \in \Omega$ we have

f(x) \le p_\Omega(x) \le 1 = f(x_0). \qquad (3.10)

Therefore, $\Omega$ and $\{x_0\}$ can be separated by a hyperplane in this case.

Now, consider the case where $x_0 \notin \operatorname{core}\Omega$ . Choose $a \in \operatorname{core}\Omega$ and let $\Theta = \Omega - a$ , $z_0 = x_0 - a$ . Then $\Theta$ is a nonempty convex set and we have

0 \in \operatorname{core}\Theta = \operatorname{core}\Omega - a \quad \text{and} \quad z_0 = x_0 - a \notin \operatorname{core}\Theta.

Thus, $\Theta$ and $\{z_0\}$ can be separated by a hyperplane. Then we can easily see that $\Omega$ and $\{x_0\}$ can be separated by a hyperplane. $\square$

Lemma 3.35. (Auxiliary separation lemma for disjoint convex sets with nonempty core) Let $X$ be a real vector space and let $\Omega_1,\Omega_2$ be two nonempty convex sets in $X$ . Suppose that $\operatorname{core}\Omega_1 \ne \emptyset$ and $\Omega_1 \cap \Omega_2 = \emptyset$ . Then $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane.

Proof. Let $\Omega = \Omega_1 - \Omega_2$ . Then $0 \notin \Omega$ , so $0 \notin \operatorname{core}\Omega$ . Fix $a \in \operatorname{core}\Omega_1$ and $b \in \Omega_2$ . Then for any $x \in X$ , there exists $\delta>0$ such that

a + \lambda x \in \Omega_1 \quad \text{whenever } |\lambda|<\delta.

This implies that

a - b + \lambda x = (a+\lambda x) - b \in \Omega_1 - \Omega_2 \quad \text{whenever } |\lambda|<\delta.

Thus, $a-b \in \operatorname{core}(\Omega_1 - \Omega_2) = \operatorname{core}\Omega$ , and hence $\operatorname{core}\Omega \ne \emptyset$ . By Theorem 3.34, the sets $\Omega$ and $\{0\}$ can be separated by a hyperplane, i.e., there exists $f \in X'\setminus\{0\}$ such that

f(z) \le f(0) = 0 \quad \text{whenever } z \in \Omega.

Now, if $x \in \Omega_1$ and $y \in \Omega_2$ , then $z = x-y \in \Omega$ . Hence $f(z) = f(x) - f(y) \le 0$ , so $f(x) \le f(y)$ . Therefore, by definition $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane. $\square$

Theorem 3.36. (Separation of two convex sets via the core condition) Let $X$ be a real vector space and let $\Omega_1,\Omega_2$ be two nonempty convex sets in $X$ . Suppose that $\operatorname{core}\Omega_1 \ne \emptyset$ and $(\operatorname{core}\Omega_1) \cap \Omega_2 = \emptyset$ . Then $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane.

Proof. Using Corollary 3.7, we see that $\operatorname{core}(\operatorname{core}\Omega_1) = \operatorname{core}\Omega_1 \ne \emptyset$ . By Lemma 3.35, the sets $\operatorname{core}\Omega_1$ and $\Omega_2$ can be separated by a hyperplane, i.e., there exists $f \in X'\setminus\{0\}$ such that

f(z) \le f(y) \quad \text{whenever } z \in \operatorname{core}\Omega_1,\, y \in \Omega_2.

Now, fix an element $a \in \operatorname{core}\Omega_1$ and any real number $t$ such that $0 < t \le 1$ . Now, take any $x \in \Omega_1$ and $y \in \Omega_2$ . By Proposition 3.6, we have $z = ta + (1-t)x \in \operatorname{core}\Omega_1$ and thus

f(z) = t f(a) + (1-t)f(x) \le f(y).

Letting $t \to 0+$ gives $f(x) \le f(y)$ . Therefore, $\Omega_1$ and $\Omega_2$ can be separated by a hyperplane. $\square$

Theorem 3.37. (Complex separation theorem (real parts)) Let $\Omega_1$ and $\Omega_2$ be two nonempty convex sets in a complex vector space $X$ . Suppose that $\operatorname{core}\Omega_1 \ne \emptyset$ and $(\operatorname{core}\Omega_1)\cap \Omega_2 = \emptyset$ . Then there exists a nonzero linear functional $F \in X'$ such that

\operatorname{Re}F(x) \le \operatorname{Re}F(y) \quad \text{whenever } x \in \Omega_1,\, y \in \Omega_2. \qquad (3.11)

Proof. Since $\mathbb{R} \subset \mathbb{C}$ , we are able to consider $X$ as a real vector space (by restricting the scalar multiplication on $\mathbb{R}$ ). Applying Theorem 3.36 to two convex sets $\Omega_1$ and $\Omega_2$ in the real vector space $X$ gives us a nonzero linear function $f : X \to \mathbb{R}$ such that (3.7) holds. Let $F(x) = f(x) - i f(ix)$ for all $x \in X$ . Then $F$ is a nonzero complex linear functional defined on the complex vector space $X$ such that $\operatorname{Re}F(x) = f(x)$ for all $x \in X$ . This clearly implies (3.11) and completes the proof. $\square$

3.4.2 Convex separation in normed spaces

Theorem 3.38. (Continuity of linear functionals via closed level sets) Let $X$ be a real normed space, let $f : X \to \mathbb{R}$ be a nonzero linear functional on $X$ , and let $\alpha \in \mathbb{R}$ . Then $f$ is continuous if and only if the set

A = \{x \in X \mid f(x) = \alpha\}

is a closed subset of $X$ .

Proof. We only need to prove the sufficient condition. Suppose that $A$ is a closed set. Note that $A$ is a proper subset of $X$ , so there exists $x_0 \in X\setminus A$ . Choose $r>0$ such that the open ball $B(x_0;r) \subset X\setminus A$ . Since $f(B(x_0;r))$ is a convex set, it is an interval in $\mathbb{R}$ that does not contain $\alpha$ . Without loss of generality, we can assume that

f(x) \le \alpha \quad \text{for all } x \in B(x_0;r) = x_0 + rB.

This implies that

f(x_0) + r f(u) \le \alpha \quad \text{whenever } u \in B.

Letting $\gamma = \frac{\alpha - f(x_0)}{r}$ and using the symmetric property of $B$ give us

|f(u)| \le \gamma \quad \text{whenever } u \in B.

Therefore, $f$ is bounded and hence it is continuous. $\square$

Let $X$ be a normed space and let $X^\ast$ represent the set of all continuous linear functionals on $X$ . For each $x^\ast \in X^\ast$ and $x \in X$ , the expression $\langle x^\ast ,x\rangle = x^\ast (x)$ defines the duality pairing between $x^\ast$ and $x$ .

Definition 3.39. (Separation by a closed hyperplane) Let $\Omega_1$ and $\Omega_2$ be two nonempty sets in a real normed space $X$ . We say that $\Omega_1$ and $\Omega_2$ can be separated by a closed hyperplane if there exists a nonzero continuous linear functional $x^\ast \in X^\ast \setminus\{0\}$ such that

\langle x^\ast ,x\rangle \le \langle x^\ast ,y\rangle \quad \text{whenever } x \in \Omega_1,\, y \in \Omega_2. \qquad (3.12)

Theorem 3.40. (Separation by closed hyperplane under interior condition) Let $X$ be a real normed space and let $\Omega_1,\Omega_2$ be two nonempty convex sets in $X$ . Suppose that $\operatorname{int}\Omega_1 \ne \emptyset$ and $(\operatorname{int}\Omega_1)\cap \Omega_2 = \emptyset$ . Then $\Omega_1$ and $\Omega_2$ can be separated by a closed hyperplane.

Proof. Since $\operatorname{int}\Omega \ne \emptyset$ , we have $\operatorname{core}\Omega = \operatorname{int}\Omega$ . By Theorem 3.36, there exists $x^\ast \in X'\setminus\{0\}$ such that (3.12) is satisfied. It remains to show that $x^\ast \in X^\ast$ , i.e., $x^\ast$ is continuous.

Choose $x_0 \in \operatorname{int}\Omega_1$ and $r>0$ such that $B(x_0;r) \subset \Omega_1$ . Then fix $y_0 \in \Omega_2$ and let $\alpha = \langle x^\ast ,y_0\rangle$ . We have

\langle x^\ast ,x\rangle \le \alpha \quad \text{for all } x \in B(x_0;r),

which implies the continuity of $x^\ast$ by following the proof of Theorem 3.38. $\square$

We continue with an enhanced version of convex separation when a set involved is open. The corollary below follows directly from Theorem 3.40 and the fact that the linear functional $x^\ast$ therein is an open mapping.

Corollary 3.41. (Strict separation with an open convex set) Let $X$ be a real normed space, and let $G,\Omega$ be two nonempty convex sets in $X$ . Suppose that $G$ is open. Then there exists $x^\ast \in X^\ast$ and $\beta \in \mathbb{R}$ such that

\langle x^\ast ,x\rangle < \beta \le \langle x^\ast ,y\rangle \quad \text{whenever } x \in G,\, y \in \Omega.

Definition 3.42. (Strict separation by a closed hyperplane) Let $\Omega_1$ and $\Omega_2$ be two nonempty sets in a real normed space $X$ . We say that $\Omega_1$ and $\Omega_2$ can be strictly separated by a closed hyperplane if there exist $x^\ast \in X^\ast$ and $\alpha,\beta \in \mathbb{R}$ such that

\langle x^\ast ,x\rangle \le \alpha < \beta \le \langle x^\ast ,y\rangle \quad \text{whenever } x \in \Omega_1,\, y \in \Omega_2. \qquad (3.13)

Note that in the setting of Definition 3.42, the sets $\Omega_1$ and $\Omega_2$ can be strictly separated by a closed hyperplane if and only if there exists $x^\ast \in X^\ast$ such that

\sup_{x \in \Omega_1} \langle x^\ast ,x\rangle < \inf_{y \in \Omega_2} \langle x^\ast ,y\rangle.

Theorem 3.43. (Strict separation of compact and closed convex sets) Let $K$ and $F$ be two nonempty convex sets in a real normed space $X$ . Suppose that $K$ is compact, $F$ is closed, and $K \cap F = \emptyset$ . Then $K$ and $F$ can be strictly separated by a closed hyperplane.

Proof. Consider the set $\Theta = F - K$ . Then $\Theta$ is a convex set and $0 \notin \Theta$ because $K\cap F=\emptyset$ . Since $K$ is compact and $F$ is closed, we see that $\Theta$ is closed. Choose $\delta > 0$ such that $B(0;\delta) \cap \Theta = \emptyset$ . Consider two nonempty convex sets: $\Omega_1 = B(0;\delta)$ and $\Omega_2 = \Theta$ . By Theorem 3.40, there exists $x^\ast \in X^\ast$ such that

\sup_{x \in B(0;\delta)} \langle x^\ast ,x\rangle \le \inf_{z \in \Theta} \langle x^\ast ,z\rangle.

This implies that

0 < \delta\|x^\ast\| \le \inf_{z \in \Theta} \langle x^\ast ,z\rangle.

Now, for any $x \in K$ and $y \in F$ we have $z = y - x \in \Theta$ . Thus,

\delta\|x^\ast\| \le \langle x^\ast ,y-x\rangle = \langle x^\ast ,y\rangle - \langle x^\ast ,x\rangle,

and hence $\delta\|x^\ast\| + \langle x^\ast ,x\rangle \le \langle x^\ast ,y\rangle$ whenever $x \in K$ and $y \in F$ . It follows that

\sup_{x \in K} \langle x^\ast ,x\rangle < \delta\|x^\ast\| + \sup_{x \in K} \langle x^\ast ,x\rangle \le \inf_{y \in F} \langle x^\ast ,y\rangle.

Therefore, $F$ and $K$ can be strictly separated by a closed hyperplane. $\square$

Core idea

Contents

1. A Review of Vector Spaces, Metric Spaces, and Normed Vector Spaces

1.1 Vector Spaces

1.1.1 Vector Spaces: Definition and Examples

1.1.2 Basis and Dimension

1.1.3 Operations on Subsets of a Vector Space

1.1.4 Linear Subspaces of a Vector Space

1.1.5 Linear Subspace Generated by a Set

1.1.6 Sums and Direct Sums of Linear Subspaces

1.1.7 Cartesian Products and Quotient Spaces

1.1.8 Linear Operators between Vector Spaces

1.2 Metric Spaces

1.2.1 Definitions, Basic Concepts, and Properties

1.2.2 Convergence and Completeness

1.3 Normed Vector Spaces

1.3.1 Definitions, Examples, and Basic Properties

1.3.2 Convergence in Normed Spaces

2 Convex Sets and Convex Functions

2.1 Convex Sets

2.1.1 Basic Definitions and Elementary Properties

2.1.2 Operations on Convex Sets and Convex Hulls

2.2 Convexity of Functions

2.2.1 Descriptions and Properties of Convex Functions

2.2.2 Convexity under Differentiability

2.2.3 Operations Preserving Convexity of Functions

3 Convex Separation

3.1 Minkowski Functions, Sublinear Functions, and Seminorms

3.1.1 Algebraic Interior and Linear Closure

3.1.2 Minkowski Gauges

3.2 Hahn-Banach Theorems

3.2.1 Hahn-Banach theorem in real vector spaces

3.2.2 Hahn-Banach theorem in general vector spaces

3.2.3 Hahn-Banach theorem in normed vector spaces

3.3 Quotient Spaces, Codimensions, Affine Sets, and Hyperplanes

3.3.1 Quotient spaces and codimensions

3.3.2 Affine Sets and Hyperplanes

3.4 Convex Separation: Geometric Forms of Hahn-Banach Theorems

3.4.1 Convex separation in vector spaces

3.4.2 Convex separation in normed spaces