10.3 Convex Sets and Hulls

Much of analysis moves from one point to another along a segment. Here are three examples.

The mean value theorem compares $f(q)$ with $f(p)$ by walking from $p$ to $q$ .
A set is connected, in the simplest case, because any two of its points can be joined inside it.
Cauchy’s theorem in complex analysis is first proved on regions where every segment between two points stays inside.

Each of these arguments needs the segment $[p, q]$ of Definition 10.1.3 to lie in the set where the work is done. This section names the sets for which that holds for every pair of points, shows that balls, lines, segments, hyperplanes and half-spaces are among them, and describes the smallest such set containing a given one.

Before the definition, test the property on a few sets of the plane.

Quick check. Which of these subsets of $\mathbb{R}^2$ contain the segment between any two of their points?

the disc $\{x : \left\| x \right\| \le 1\}$ ;
the ring $\{x : 1 \le \left\| x \right\| \le 2\}$ ;
the line $\mathbb{R}(1, 1)$ ;
the two-point set $\{(0, 0), (1, 0)\}$ ;
the empty set;
the union of the two coordinate axes.

Solution. The disc: yes; this section proves it for every ball. The ring: no; $(3/2, 0)$ and $(-3/2, 0)$ lie in it, and the midpoint $(0, 0)$ of the segment between them has norm $0 < 1$ . The line: yes, since $(1 - t)(s, s) + t(u, u) = (v, v)$ with $v \mathrel{:=} (1 - t)s + tu$ . The two points: no; the midpoint $(1/2, 0)$ is neither of them. The empty set: yes, since there are no two points to test. The axes: no; $(1, 0)$ and $(0, 1)$ lie on them, and the midpoint $(1/2, 1/2)$ lies on neither axis.

10.3.1. Convex sets and balls

The property tested above deserves a name.

A set is convex when it never makes you leave it to walk straight from one of its points to another. In other words, the segment between any two of its points lies inside it.

Definition 10.3.1 (Convex Set)

A subset $C \subseteq \mathbb{R}^n$ is convex if $[p, q] \subseteq C$ for all $p, q \in C$ .

In words: whenever $p$ and $q$ are in $C$ , so is $(1 - t)p + tq$ for every $t \in [0, 1]$ (Definition 10.1.3). The quantifier over $t$ covers the whole interval $[0, 1]$ , not just the midpoint $t = 1/2$ . This matters: the set $\mathbb{Q}^2$ of points of the plane with rational coordinates contains every midpoint of two of its points and still is not convex (see the warning on midpoints below). The empty set is convex, since the condition has no instance to check. So is every one-point set $\{p\}$ , since $[p, p] = \{p\}$ . The ring and the axes tested above are not convex: in each, one pair of points already has a midpoint outside.

The sets of analysis on which estimates hold are balls. The words “open” and “closed” below are names for now. Analysis on the Real Line explains them and defines balls for any distance.

For instance, in $\mathbb{R}^2$ take the points at distance less than $1$ from $(1, 0)$ . The point $(1/2, 0)$ is one of them, at distance $1/2$ . The point $(1, 1)$ is not, since its distance is exactly $1$ ; it lies on the circle around the disc.

Definition 10.3.2 (Open and Closed Balls)

Let $c \in \mathbb{R}^n$ and $r > 0$ . The open ball and the closed ball of center $c$ and radius $r$ are $B(c, r) \mathrel{:=} \{ x \in \mathbb{R}^n : \left\| x - c \right\| < r \} , \qquad \overline{B}(c, r) \mathrel{:=} \{ x \in \mathbb{R}^n : \left\| x - c \right\| \le r \} .$

For $n = 1$ , $\left\| x - c \right\| = \left| x - c \right|$ (Proposition 9.4.1 (d)). So $B(c, r)$ is the interval $(c - r, c + r)$ , and $\overline{B}(c, r)$ is $[c - r, c + r]$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (d)). For $n = 2$ they are discs without and with their circle $S(c, r)$ (Definition 10.2.2).

Proposition 10.3.1 (Balls Are Convex)

For every $c \in \mathbb{R}^n$ and $r > 0$ , the balls $B(c, r)$ and $\overline{B}(c, r)$ are convex.

Idea (Scratch work). Unwind the goal. The definition of convexity says what to fix: two points of the ball and a parameter $t \in [0, 1]$ .

We know	We want
$\left\\| p - c \right\\| < r$ , $\left\\| q - c \right\\| < r$ , $t \in [0, 1]$	$\left\\| (1 - t)p + tq - c \right\\| < r$
the same; and $c = (1 - t)c + tc$	$\left\\| (1 - t)(p - c) + t(q - c) \right\\| < r$
the triangle inequality and $\left\\| sx \right\\| = \left\| s \right\|\left\\| x \right\\|$	each of the two pieces is at most its weight times $r$ ; the gap closes, since $(1 - t)r + tr = r$

The second row is the whole trick. The center is split with the same weights as the point. Then the vector inside the norm becomes a weighted sum of two vectors whose lengths we know.

Proof. Let $p, q \in B(c, r)$ and $t \in [0, 1]$ . By the laws of the vector operations, $(1 - t)p + tq - c = (1 - t)(p - c) + t(q - c)$ . Since $1 - t \ge 0$ and $t \ge 0$ , the triangle inequality (Theorem 9.5.3 (a)) gives $\left\| (1 - t)p + tq - c \right\| \le (1 - t)\left\| p - c \right\| + t\left\| q - c \right\| .$ If $t = 0$ or $t = 1$ , the point $(1 - t)p + tq$ is $p$ or $q$ , which lies in $B(c, r)$ . If $0 < t < 1$ , both weights are positive. Multiplying by a positive number keeps a strict inequality, so $(1 - t)\left\| p - c \right\| < (1 - t)r$ and $t\left\| q - c \right\| < tr$ . Adding these bounds the right side by $(1 - t)r + tr = r$ . Hence $(1 - t)p + tq \in B(c, r)$ , and $B(c, r)$ is convex.

For $\overline{B}(c, r)$ the same display holds. Since all four factors are non-negative, $(1 - t)\left\| p - c \right\| \le (1 - t)r$ and $t\left\| q - c \right\| \le tr$ . Adding gives $\left\| (1 - t)p + tq - c \right\| \le r$ . This proves the proposition.

Uses: Proposition 9.2.1, Proposition 9.4.1 (b): rearrangements, $\left\| sx \right\| = \left| s \right|\left\| x \right\|$ ; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (b), (c): adding, multiplying by positives; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d): multiplying non-negative inequalities.

A ball is convex; its boundary is not.

Quick check. Is the sphere $S(0, 1) \subseteq \mathbb{R}^2$ convex?

Solution. No. The points $(1, 0)$ and $(-1, 0)$ lie on it, and the midpoint $(0, 0)$ of the segment between them has norm $0 \ne 1$ . Exercise B3 shows that no point strictly inside a segment between two different points of a sphere lies on the sphere.

The proof of Proposition 10.3.1 is the pattern for proving convexity from the definition.

Example (Method: the two-point test)

How it goes. To prove that $C$ is convex:

Take $p, q \in C$ and $t \in [0, 1]$ .
Write down the condition that $p$ and $q$ satisfy.
Split the vector, or the expression, belonging to $(1 - t)p + tq$ as $(1 - t)(\dots) + t(\dots)$ . Use the same weights on every term, including the center or the constant.
Conclude by the triangle inequality, or by linearity, using $1 - t \ge 0$ and $t \ge 0$ .

When to use it. Proving that a set is convex straight from the definition: balls, half-spaces, sets cut out by inequalities.

Common mistakes. Checking only the midpoint, $t = 1/2$ , is not enough: the set $\mathbb{Q}^2$ below passes that check and is not convex. Allowing $t$ outside $[0, 1]$ is also wrong, since then a weight is negative and the inequalities reverse.

Warning. Midpoints are not enough. The set $\mathbb{Q}^2$ of points of $\mathbb{R}^2$ with rational coordinates contains the midpoint $\bigl( (a + c)/2, (b + d)/2 \bigr)$ of any two of its points $(a, b)$ , $(c, d)$ . Yet it is not convex. The field $\mathbb{R}$ is a complete ordered field (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 5.5.2). So the real number $\sqrt 2$ exists (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 6.1.4). Since $1 < 2 < 4$ , comparing squares of non-negative numbers gives $1 < \sqrt 2 < 2$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (g)). So $t \mathrel{:=} \sqrt 2 / 2$ lies in $[0, 1]$ . Then $(\sqrt 2 / 2, 0) = (1 - t)(0, 0) + t(1, 0)$ is a point of $[(0, 0), (1, 0)]$ . It is not in $\mathbb{Q}^2$ : if $t \in \mathbb{Q}$ , then $\sqrt 2 = 2t \in \mathbb{Q}$ , against Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 3.3.1.

10.3.2. Examples and operations

The sets of Sections 10.1 and 10.2 are convex: lines and half-spaces pass the two-point test with linearity.

Proposition 10.3.2 (Lines, Segments, Hyperplanes and Half-Spaces Are Convex)

Each of the following is a convex subset of $\mathbb{R}^n$ :

every line (Definition 10.1.1);
every segment (Definition 10.1.3);
every hyperplane $H_{a,c}$ and each of its four half-spaces (Definition 10.2.1).

Idea. Use the two-point test of Example (Method: the two-point test), with linearity in place of the triangle inequality. The weights $1 - t$ and $t$ pass through the parameter of a line and through the dot product with $a$ .

Proof. Let $t \in [0, 1]$ .

Lines. For two points $p + sv$ and $p + uv$ of $p + \mathbb{R} v$ , the laws of the vector operations give $(1 - t)(p + sv) + t(p + uv) = p + \bigl( (1 - t)s + tu \bigr)v$ , a point of $p + \mathbb{R} v$ .

Segments. If $x, y \in [p, q]$ , then $[x, y] \subseteq [p, q]$ by Lemma 10.1.3; that is the definition of convexity for $[p, q]$ .

Hyperplanes and half-spaces. For $x, y \in \mathbb{R}^n$ , linearity of the dot product (Proposition 9.3.1 (b)) gives $c - \langle a, (1 - t)x + ty \rangle = (1 - t)\bigl( c - \langle a, x \rangle \bigr) + t\bigl( c - \langle a, y \rangle \bigr) .$ If $x, y \in H_{a,c}$ , the right side is $0$ , so $(1 - t)x + ty \in H_{a,c}$ . If $\langle a, x \rangle \le c$ and $\langle a, y \rangle \le c$ , both brackets are $\ge 0$ , and so are both weights. A product of two non-negative numbers is $\ge 0$ , and so is a sum of two such products; so the right side is $\ge 0$ . If both brackets are $> 0$ , the right side is $> 0$ . Indeed, one weight is positive, so its term is a product of two positive numbers and is positive, and the other term is $\ge 0$ . This settles $\{ \langle a, x \rangle \le c \}$ and $\{ \langle a, x \rangle < c \}$ . The half-spaces with $\ge$ and $>$ are those with $\le$ and $<$ for the normal $-a$ and the constant $-c$ , since multiplying by $-1$ reverses an inequality. Also $-a \ne 0$ .

Uses: Proposition 9.2.1 (vector rearrangements); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d): products of non-negatives; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (a), (b), (c): negation, sums, positive products.

New convex sets come from old ones by intersecting, translating and scaling, but not by joining. For example, $(1, 0) + B\bigl( (0, 0), 1 \bigr) = B\bigl( (1, 0), 1 \bigr)$ and $2B\bigl( (0, 0), 1 \bigr) = B\bigl( (0, 0), 2 \bigr)$ .

Proposition 10.3.3 (Operations on Convex Sets)

(a) If $(C_i)_{i \in I}$ is a family of convex subsets of $\mathbb{R}^n$ , then $\bigcap_{i \in I} C_i$ is convex.
(b) If $C \subseteq \mathbb{R}^n$ is convex, $b \in \mathbb{R}^n$ and $\lambda \in \mathbb{R}$ , then $b + C \mathrel{:=} \{ b + x : x \in C \}$ and $\lambda C \mathrel{:=} \{ \lambda x : x \in C \}$ are convex.
(c) A union of two convex sets need not be convex: for $p \ne q$ , the sets $\{p\}$ and $\{q\}$ are convex and $\{p\} \cup \{q\}$ is not.

Idea. Each part checks one segment at a time. A segment that lies in every $C_i$ lies in their intersection, and translating or scaling moves a segment onto a segment.

Proof.

(a) The intersection is taken in $\mathbb{R}^n$ , as Sets and Functions defined the intersection of a family (Sets and Functions, Definition 1.3.4 (b)). For $I = \emptyset$ it is $\mathbb{R}^n$ , which is convex. Let $p, q \in \bigcap_{i} C_i$ . For each $i$ , $p, q \in C_i$ and $C_i$ is convex, so $[p, q] \subseteq C_i$ . Hence $[p, q] \subseteq \bigcap_i C_i$ .
(b) For $x, y \in C$ and $t \in [0, 1]$ , the laws of Proposition 9.2.1 give $(1 - t)(b + x) + t(b + y) = b + \bigl( (1 - t)x + ty \bigr) , \qquad (1 - t)\lambda x + t\lambda y = \lambda\bigl( (1 - t)x + ty \bigr) ,$ and $(1 - t)x + ty \in C$ .
(c) $[p, p] = \{p\}$ , so a one-point set is convex. The midpoint $m = (p + q)/2$ of $[p, q]$ is neither $p$ nor $q$ : $m = p$ would give $q = p$ , and likewise for $q$ .

Quick check. Show that the triangle $T \mathrel{:=} \{ x \in \mathbb{R}^2 : x_1 \ge 0, \ x_2 \ge 0, \ x_1 + x_2 \le 1 \}$ is convex.

Solution. $T$ is the intersection of the three closed half-spaces $\{ \langle (-1, 0), x \rangle \le 0 \}$ , $\{ \langle (0, -1), x \rangle \le 0 \}$ and $\{ \langle (1, 1), x \rangle \le 1 \}$ , each convex by Proposition 10.3.2. By Proposition 10.3.3 (a), $T$ is convex.

10.3.3. Convex combinations and the hull

A point of a segment is a sum of two points with non-negative weights adding up to $1$ . Allowing more than two points gives the general form. For example, the weights $\tfrac12, \tfrac14, \tfrac14$ are non-negative and add up to $1$ . On the points $(0, 0)$ , $(4, 0)$ , $(0, 4)$ they give $\tfrac12(0, 0) + \tfrac14(4, 0) + \tfrac14(0, 4) = (1, 1)$ .

Definition 10.3.3 (Convex Combination)

Let $k \ge 1$ and $p_1, \dots, p_k \in \mathbb{R}^n$ . A convex combination of $p_1, \dots, p_k$ is a point $\lambda_1 p_1 + \dots + \lambda_k p_k = \sum_{i=1}^{k} \lambda_i p_i \quad \text{with every } \lambda_i \ge 0 \text{ and } \sum_{i=1}^{k} \lambda_i = 1 .$ The numbers $\lambda_i$ are its weights.

For $k = 1$ the only convex combination of $p_1$ is $p_1$ itself. For $k = 2$ , the weights are $1 - t$ and $t$ with $t \in [0, 1]$ , and the convex combinations of $p_1, p_2$ form $[p_1, p_2]$ . The points need not be distinct.

A convex set is defined by a condition on two points. It controls combinations of any number of points.

Theorem 10.3.4 (Convex Sets Contain Their Convex Combinations)

Let $C \subseteq \mathbb{R}^n$ be convex. Then every convex combination of finitely many points of $C$ lies in $C$ .

Idea. Peel off the last point. Convexity speaks about two points at a time, so split one point off. Of $k + 1$ weighted points, keep the last one. Rescale the first $k$ weights so that they add up to $1$ again. By induction, the first $k$ points then give one point $y$ of $C$ , and the whole combination is a point of the segment $[y, p_{k+1}]$ . The rescaling divides by $1 - \lambda_{k+1}$ , so the case $\lambda_{k+1} = 1$ is set aside.

Proof. For $k \ge 1$ , let $P(k)$ be the statement: for all $p_1, \dots, p_k \in C$ , every convex combination of $p_1, \dots, p_k$ lies in $C$ . We prove $P(k)$ for every $k \ge 1$ by induction from the base $1$ (Sets and Functions, Theorem 3.2.1).

Base case. A convex combination of one point $p_1 \in C$ has $\lambda_1 = 1$ , so it is $p_1 \in C$ .

Inductive step. Let $k \ge 1$ and assume $P(k)$ . Let $p_1, \dots, p_{k+1} \in C$ and let $x = \sum_{i=1}^{k+1} \lambda_i p_i$ be a convex combination of them. If $\lambda_{k+1} = 1$ , then $\sum_{i=1}^{k} \lambda_i = 0$ with every $\lambda_i \ge 0$ , so every $\lambda_i$ with $i \le k$ is $0$ (Proposition 1.1.5 (e)). Then $0\,p_i = 0$ (Proposition 9.2.1 (i)), and $x = 1\,p_{k+1} = p_{k+1} \in C$ . Suppose now $\lambda_{k+1} \ne 1$ . The weights $\lambda_1, \dots, \lambda_k$ are non-negative, so $\sum_{i=1}^{k} \lambda_i \ge 0$ (Proposition 1.1.5 (a)), and $\sum_{i=1}^{k} \lambda_i = 1 - \lambda_{k+1}$ by the recursion for sums. Hence $s \mathrel{:=} 1 - \lambda_{k+1}$ satisfies $s \ge 0$ and $s \ne 0$ , so $s > 0$ , and $\lambda_{k+1} = 1 - s \in [0, 1]$ . The numbers $\lambda_i / s$ , for $i \le k$ , are non-negative and add up to $s/s = 1$ , since the constant $1/s$ comes out of the sum. So $y \mathrel{:=} \sum_{i=1}^{k} \frac{\lambda_i}{s} \, p_i$ is a convex combination of $p_1, \dots, p_k$ , and $y \in C$ by $P(k)$ . By the recursion for sums, and by taking the constant $s$ out of the sum in each coordinate, $x = \sum_{i=1}^{k} \lambda_i p_i + \lambda_{k+1} p_{k+1} = s\,y + \lambda_{k+1} p_{k+1} = (1 - \lambda_{k+1})\,y + \lambda_{k+1}\,p_{k+1} ,$ a point of $[y, p_{k+1}]$ . Since $y, p_{k+1} \in C$ and $C$ is convex, $x \in C$ . This proves $P(k + 1)$ , and the theorem follows.

Uses: Lemma 1.1.3 (b): constants come out; Lemma 9.2.2 (a): vector sums by coordinates; Proposition 1.1.5 (a), (e): sums of non-negatives; Proposition 9.2.1 (i): $0\,p = 0$ .

Among all convex sets containing a given set $S$ , there is a smallest one. It is built the way Sets and Functions built the smallest closed set (Sets and Functions, Proposition 1.3.2): intersect all candidates. For the two points $(0, 0)$ and $(1, 0)$ , every convex set containing both contains the segment between them. That segment is itself convex, so it is the smallest convex set containing the two points.

Definition 10.3.4 (Convex Hull)

Let $S \subseteq \mathbb{R}^n$ . The convex hull of $S$ is $\operatorname{conv} S \mathrel{:=} \bigcap \{ C \subseteq \mathbb{R}^n : C \text{ is convex and } S \subseteq C \} .$

The family being intersected is non-empty, since $\mathbb{R}^n$ is convex and contains $S$ . So $\operatorname{conv} S$ is a subset of $\mathbb{R}^n$ , and it has three properties:

it is convex, by Proposition 10.3.3 (a);
it contains $S$ , since every member of the family does;
it lies inside every convex set that contains $S$ , since it is the intersection of all of them.

In short, $\operatorname{conv} S$ is the smallest convex set containing $S$ . For example, $\operatorname{conv}\{p, q\} = [p, q]$ . Indeed, the segment is convex (Proposition 10.3.2) and contains $p$ and $q$ , and every convex set containing $p$ and $q$ contains $[p, q]$ .

The definition says what the hull is, but not how to find its points. The next theorem does.

Theorem 10.3.5 (The Convex Hull Is the Set of Convex Combinations)

Let $S \subseteq \mathbb{R}^n$ , and let $K$ be the set of all convex combinations of finitely many points of $S$ . Then $\operatorname{conv} S = K$ .

Try it first (ten minutes): for three points $p, q, r$ of the plane, describe $\operatorname{conv}\{p, q, r\}$ without the word “intersection”.

Idea. The first guess is the three sides, $[p, q] \cup [q, r] \cup [r, p]$ . It contains $p, q, r$ , but it is not convex. For $p = (0, 0)$ , $q = (2, 0)$ , $r = (0, 2)$ , the points $(1, 0) \in [p, q]$ and $(0, 1) \in [r, p]$ have midpoint $(1/2, 1/2)$ , which lies on none of the three sides. So the hull must also contain every segment $[x, r]$ with $x \in [p, q]$ . A point of such a segment is $(1 - t)\bigl( (1 - s)p + sq \bigr) + tr$ : a convex combination of $p, q, r$ . That suggests the theorem, and suggests its two halves:

① every convex combination of points of $S$ lies in $\operatorname{conv} S$ , which is Theorem 10.3.4 applied to the convex set $\operatorname{conv} S$ ;

② the set $K$ is itself convex and contains $S$ , so the smallest such set lies inside it. For ②, two convex combinations are mixed by writing their two lists of points one after the other.

Proof. $(\supseteq)$ The set $\operatorname{conv} S$ is convex and contains $S$ , as shown just after Definition 10.3.4. By Theorem 10.3.4, it contains every convex combination of finitely many of its points, in particular of points of $S$ . So $K \subseteq \operatorname{conv} S$ .

$(\subseteq)$ First, $S \subseteq K$ : each $p \in S$ is the convex combination $1\,p$ . Next, $K$ is convex. Let $x = \sum_{i=1}^{k} \lambda_i p_i$ and $y = \sum_{j=1}^{m} \mu_j q_j$ be in $K$ , with $p_i, q_j \in S$ , and let $t \in [0, 1]$ . Join the two lists: let $r_i \mathrel{:=} p_i$ and $\nu_i \mathrel{:=} (1 - t)\lambda_i$ for $1 \le i \le k$ , and $r_{k+j} \mathrel{:=} q_j$ and $\nu_{k+j} \mathrel{:=} t\mu_j$ for $1 \le j \le m$ . Each $\nu_i$ is a product of two non-negative numbers, so $\nu_i \ge 0$ . Split the sum over the joined list into its two parts, and take the constants out of the two sums. This gives $\sum_{i=1}^{k+m} \nu_i = (1 - t)\sum_{i=1}^{k} \lambda_i + t\sum_{j=1}^{m} \mu_j = (1 - t) + t = 1 .$ The same two rules, applied in each coordinate, give $\sum_{i=1}^{k+m} \nu_i r_i = (1 - t)\sum_{i=1}^{k} \lambda_i p_i + t\sum_{j=1}^{m} \mu_j q_j = (1 - t)x + ty .$ So $(1 - t)x + ty$ is a convex combination of the points $r_1, \dots, r_{k+m}$ of $S$ , and lies in $K$ . Thus $K$ is a convex set containing $S$ . Since $\operatorname{conv} S$ lies inside every such set, $\operatorname{conv} S \subseteq K$ . This proves $\operatorname{conv} S = K$ .

Uses: Proposition 1.1.4 (b): splitting a sum; Lemma 1.1.3 (b): constants come out; Lemma 9.2.2 (a): vector sums by coordinates; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d): products of non-negatives.

The theorem turns membership in a hull, a statement about all convex sets at once, into a search for weights.

Example (A Triangle as a Hull)

Let $p_1, p_2, p_3 \in \mathbb{R}^2$ . (a) Show that $\operatorname{conv}\{p_1, p_2, p_3\}$ is the set $T$ of points $\lambda_1 p_1 + \lambda_2 p_2 + \lambda_3 p_3$ with $\lambda_i \ge 0$ and $\lambda_1 + \lambda_2 + \lambda_3 = 1$ : the filled triangle with corners $p_1, p_2, p_3$ . (b) For $p_1 = (0, 0)$ , $p_2 = (3, 0)$ , $p_3 = (0, 3)$ , decide whether $(1, 1)$ and $(2, 2)$ lie in the hull.

Solution.

(a) $T \subseteq \operatorname{conv}\{p_1, p_2, p_3\}$ by Theorem 10.3.5. For the other inclusion it is enough that $T$ is convex, since it contains $p_1$ (weights $1, 0, 0$ ), $p_2$ and $p_3$ . For two points of $T$ with weights $\lambda_i$ and $\mu_i$ , and $t \in [0, 1]$ , $(1 - t)\sum_{i=1}^{3} \lambda_i p_i + t\sum_{i=1}^{3} \mu_i p_i = \sum_{i=1}^{3} \bigl( (1 - t)\lambda_i + t\mu_i \bigr) p_i ,$ and the new weights are non-negative and add up to $(1 - t) + t = 1$ . This is the proof of Theorem 10.3.5 with the two lists kept equal instead of joined.
(b) The weights $\lambda_1 = \lambda_2 = \lambda_3 = 1/3$ give $\tfrac13(0, 0) + \tfrac13(3, 0) + \tfrac13(0, 3) = (1, 1)$ , so $(1, 1)$ is in the hull. For $(2, 2)$ : any weights with $\lambda_1(0, 0) + \lambda_2(3, 0) + \lambda_3(0, 3) = (2, 2)$ have $3\lambda_2 = 2$ and $3\lambda_3 = 2$ , so $\lambda_2 + \lambda_3 = 4/3$ and $\lambda_1 = 1 - 4/3 < 0$ . No admissible weights exist, and $(2, 2)$ is not in the hull. In this example the hull is $\{ x_1 \ge 0, \ x_2 \ge 0, \ x_1 + x_2 \le 3 \}$ : by (a) its points are $(3\lambda_2, 3\lambda_3)$ with $\lambda_2, \lambda_3 \ge 0$ and $\lambda_2 + \lambda_3 = 1 - \lambda_1 \le 1$ , and conversely a point $x$ of the set has the weights $\lambda_2 = x_1/3$ , $\lambda_3 = x_2/3$ , $\lambda_1 = 1 - (x_1 + x_2)/3 \ge 0$ . It is three times the triangle $\{ x_1 \ge 0, \ x_2 \ge 0, \ x_1 + x_2 \le 1 \}$ shown convex earlier, and $(2, 2)$ breaks the third inequality.

10.3.4. Star-shaped sets

Some arguments need segments only from one fixed point, not between every pair of points. For instance, the union of the two axes of $\mathbb{R}^2$ is not convex. Yet every segment from $(0, 0)$ to one of its points stays inside it.

Definition 10.3.5 (Star-Shaped Set)

A set $S \subseteq \mathbb{R}^n$ is star-shaped about a point $c \in S$ if $[c, x] \subseteq S$ for every $x \in S$ . It is star-shaped if it is star-shaped about some point of $S$ .

A non-empty convex set is star-shaped about each of its points: that is the definition of convexity with $p = c$ . The converse fails.

Example (The Axes: Star-Shaped, Not Convex)

Let $A \mathrel{:=} \mathbb{R}(1, 0) \cup \mathbb{R}(0, 1) \subseteq \mathbb{R}^2$ , the union of the two axes. Show that $A$ is star-shaped about $0$ , is not convex, and is not star-shaped about $(1, 0)$ .

Solution. For $x = (s, 0) \in A$ and $t \in [0, 1]$ , $(1 - t)\,0 + t(s, 0) = (ts, 0) \in A$ ; points of the other axis are handled the same way. So $A$ is star-shaped about $0$ . The points $(1, 0)$ and $(0, 1)$ lie in $A$ , and the midpoint $(1/2, 1/2)$ of the segment between them has both coordinates non-zero, so it lies on neither axis. This shows at once that $A$ is not convex and that $[(1, 0), (0, 1)] \not\subseteq A$ , so $A$ is not star-shaped about $(1, 0)$ .

Convex and star-shaped sets return throughout the series. Analysis on the Real Line uses convex balls to join points by segments, for connectedness. Analysis in Several Variables uses segments inside convex sets for the mean value inequality. Complex Analysis proves Cauchy’s theorem first on convex and star-shaped regions. Analysis on Manifolds proves the Poincaré lemma on star-shaped sets.

10.3.5. Exercises

A. Check your understanding

Exercise (A1)

Decide which of these subsets of $\mathbb{R}^2$ are convex. Justify each answer that is “no” with two points.

(a) $\{ (x, y) : y \ge x^2 \}$ .
(b) $\{ (x, y) : y \le x^2 \}$ .
(c) $\mathbb{Z}^2$ .
(d) $\{ x : 1 \le \left\| x \right\| \le 2 \}$ .

Solution.

(a) Convex; Exercise B1 proves it with the two-point test.
(b) Not convex: $(1, 1)$ and $(-1, 1)$ lie in the set ( $1 \le 1$ ), and their midpoint $(0, 1)$ does not, since $1 > 0 = 0^2$ .
(c) Not convex: $(0, 0), (1, 0) \in \mathbb{Z}^2$ , and the midpoint $(1/2, 0) \notin \mathbb{Z}^2$ .
(d) Not convex: $(3/2, 0)$ and $(-3/2, 0)$ lie in the ring, and the midpoint $(0, 0)$ has norm $0 < 1$ .

Exercise (A2)

(a) Is $(1, 2)$ in $\operatorname{conv}\{(0, 0), (3, 0), (0, 3)\}$ ?
(b) Consider the proof of Theorem 10.3.5. Which of its two inclusions uses Theorem 10.3.4, and what does it apply that theorem to? Why is the family of convex sets containing $S$ , in Definition 10.3.4, non-empty?

Solution.

(a) Yes: $0\,(0, 0) + \tfrac13(3, 0) + \tfrac23(0, 3) = (1, 2)$ , with non-negative weights adding up to $1$ .
(b) The inclusion $K \subseteq \operatorname{conv} S$ . It applies the theorem to the convex set $\operatorname{conv} S$ , which contains $S$ , so it contains every convex combination of points of $S$ . The family contains $\mathbb{R}^n$ , which is convex and contains $S$ .

B. Practice

Exercise (B1)

Prove that $P \mathrel{:=} \{ (x, y) \in \mathbb{R}^2 : y \ge x^2 \}$ is convex.

Solution. We use the two-point test (Example (Method: the two-point test)). Let $(a, b), (c, d) \in P$ , so $b \ge a^2$ and $d \ge c^2$ , and let $t \in [0, 1]$ . The point $(1 - t)(a, b) + t(c, d)$ has coordinates $(1 - t)a + tc$ and $(1 - t)b + td$ . Since $1 - t \ge 0$ and $t \ge 0$ , multiplying keeps the two inequalities, and adding them gives $(1 - t)b + td \ge (1 - t)a^2 + tc^2 .$ Expanding the square, $(1 - t)a^2 + tc^2 - \bigl( (1 - t)a + tc \bigr)^2 = t(1 - t)(a - c)^2 ,$ since $(1 - t) - (1 - t)^2 = t(1 - t) = t - t^2$ . The right side is $\ge 0$ : $t(1 - t) \ge 0$ and $(a - c)^2 \ge 0$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (e)). Hence $(1 - t)b + td \ge \bigl( (1 - t)a + tc \bigr)^2$ , and the point lies in $P$ .

Uses: Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.2 (d): multiplying non-negative inequalities; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (b): adding inequalities.

Exercise (B2)

For $C, D \subseteq \mathbb{R}^n$ , let $C + D \mathrel{:=} \{ x + y : x \in C, \ y \in D \}$ . Prove that if $C$ and $D$ are convex, so is $C + D$ .

Solution. Let $x + y$ and $x' + y'$ be points of $C + D$ , with $x, x' \in C$ and $y, y' \in D$ , and let $t \in [0, 1]$ . By the laws of Proposition 9.2.1, $(1 - t)(x + y) + t(x' + y') = \bigl( (1 - t)x + tx' \bigr) + \bigl( (1 - t)y + ty' \bigr) .$ The first bracket lies in $C$ and the second in $D$ , by convexity. So the point lies in $C + D$ .

Exercise (B3)

Let $c \in \mathbb{R}^n$ , $r > 0$ , and let $p \ne q$ be points of the sphere $S(c, r)$ . Prove that $\left\| (1 - t)p + tq - c \right\| < r$ for every $t$ with $0 < t < 1$ .

Solution. We use the equality case, as in Example (Method: use the equality case). Let $u \mathrel{:=} (1 - t)(p - c)$ and $w \mathrel{:=} t(q - c)$ , so $(1 - t)p + tq - c = u + w$ (Proposition 9.2.1). By Proposition 9.4.1 (b), $\left\| u \right\| = (1 - t)r$ and $\left\| w \right\| = tr$ . So the triangle inequality gives $\left\| u + w \right\| \le (1 - t)r + tr = r$ .

Suppose $\left\| u + w \right\| = r = \left\| u \right\| + \left\| w \right\|$ . Here $u \ne 0$ , since $\left\| u \right\| = (1 - t)r > 0$ . By the equality case of Theorem 9.5.3 (a), $w = \lambda u$ for some $\lambda \ge 0$ , that is, $t(q - c) = \lambda(1 - t)(p - c)$ . Dividing by $t > 0$ , $q - c = \mu(p - c)$ with $\mu \mathrel{:=} \lambda(1 - t)/t \ge 0$ . Taking norms, $r = \mu r$ , so $\mu = 1$ and $q = p$ , a contradiction. Hence $\left\| u + w \right\| < r$ .

The result depends on the equality case of the triangle inequality, which belongs to the Euclidean norm. Measure distances in $\mathbb{R}^2$ instead by $\max(\left| x_1 - y_1 \right|, \left| x_2 - y_2 \right|)$ : the “unit ball” about $0$ is the square $\{ \max(\left| x_1 \right|, \left| x_2 \right|) \le 1 \}$ , and its edge contains the whole segment $[(1, -1), (1, 1)]$ , so the analogue of this exercise fails. So does the analogue of Theorem 10.1.4: the point $(1, 1)$ is at distance $1$ from $(0, 0)$ and from $(2, 0)$ , and $1 + 1 = 2$ is the distance between them, yet $(1, 1)$ is not on the segment $[(0, 0), (2, 0)]$ . Analysis on the Real Line returns to this distance.

Exercise (B4: Prove or disprove)

Prove each statement or give a counterexample. Throughout, $C$ , $S$ , $T$ are subsets of $\mathbb{R}^n$ .

(a) The union of two convex sets is convex.
(b) The complement $\mathbb{R}^2 \setminus C$ of a convex set $C \subseteq \mathbb{R}^2$ is convex.
(c) $\operatorname{conv}(S \cup T) = \operatorname{conv} S \cup \operatorname{conv} T$ .
(d) For $p, q \in \mathbb{R}^n$ , the set $\{ x : \left\| x - p \right\| \le \left\| x - q \right\| \}$ is convex.
(e) If $C$ is convex and $\lambda, \mu \ge 0$ , then $\lambda C + \mu C = (\lambda + \mu)C$ (notation of Exercise B2 and Proposition 10.3.3 (b)).

Solution.

(a) False. Proposition 10.3.3 (c): $\{p\} \cup \{q\}$ with $p \ne q$ .
(b) False. $C = \overline{B}(0, 1)$ is convex (Proposition 10.3.1). The points $(2, 0)$ and $(-2, 0)$ lie outside it, and their midpoint $(0, 0)$ lies in it.
(c) False. Take $S = \{p\}$ , $T = \{q\}$ with $p \ne q$ . Then $\operatorname{conv} S = \{p\}$ and $\operatorname{conv} T = \{q\}$ , since one-point sets are convex; but $\operatorname{conv}(S \cup T) = [p, q]$ (the example after Definition 10.3.4) contains the midpoint, which is neither $p$ nor $q$ .
(d) True. If $p = q$ , the set is $\mathbb{R}^n$ . If $p \ne q$ , let $c \mathrel{:=} (\left\| q \right\|^2 - \left\| p \right\|^2)/2$ . By Proposition 10.2.2, $\left\| x - p \right\| < \left\| x - q \right\|$ if and only if $\langle q - p, x \rangle < c$ , and $\left\| x - p \right\| = \left\| x - q \right\|$ if and only if $\langle q - p, x \rangle = c$ . Since $\le$ means “ $<$ or $=$ ” (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (i)), the set is the closed half-space $\{ \langle q - p, x \rangle \le c \}$ . It is convex by Proposition 10.3.2.
(e) True. $(\supseteq)$ For $x \in C$ , $(\lambda + \mu)x = \lambda x + \mu x \in \lambda C + \mu C$ (Proposition 9.2.1 (h)). $(\subseteq)$ Let $\lambda x + \mu y \in \lambda C + \mu C$ , with $x, y \in C$ . If $\lambda + \mu > 0$ , let $s \mathrel{:=} \mu/(\lambda + \mu) \in [0, 1]$ ; then $\lambda x + \mu y = (\lambda + \mu)\bigl( (1 - s)x + sy \bigr) ,$ and $(1 - s)x + sy \in C$ by convexity. If $\lambda = \mu = 0$ , both sides are $\{0\}$ when $C \ne \emptyset$ and $\emptyset$ when $C = \emptyset$ . Convexity is needed: for $C = \{0, e_1\} \subseteq \mathbb{R}^n$ and $\lambda = \mu = 1$ , the point $e_1 = 0 + e_1$ lies in $C + C$ but not in $2C = \{0, 2e_1\}$ .

C. Going deeper

Exercise (C1: Chapter check: convex subsets of the line)

Let $C \subseteq \mathbb{R}$ be non-empty and convex. Let $\alpha \mathrel{:=} \inf C$ if $C$ is bounded below, and $\alpha \mathrel{:=} -\infty$ otherwise; let $\beta \mathrel{:=} \sup C$ if $C$ is bounded above, and $\beta \mathrel{:=} +\infty$ otherwise. Prove that every real $x$ with $\alpha < x < \beta$ lies in $C$ , and that every $c \in C$ satisfies $\alpha \le c \le \beta$ . (So $C$ is an interval with ends $\alpha$ and $\beta$ , each end included or not.)

Solution (Hint 1). For $x$ strictly between $\alpha$ and $\beta$ , look for two points of $C$ , one on each side of $x$ .

Solution (Hint 2). Since $x > \inf C$ , what can you say about $x$ as a bound of $C$ ? Then ask what that says about the elements of $C$ .

Solution. The supremum and the infimum. If $C$ is bounded above, $\sup C$ exists, since $C$ is non-empty and $\mathbb{R}$ is complete (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 5.5.2). If $C$ is bounded below, $\inf C$ exists, again since $C$ is non-empty (Proposition 8.3.1 (b)).

Two points around $x$ . Let $\alpha < x < \beta$ . If $C$ is bounded below, $x > \inf C$ , so $x$ is not a lower bound of $C$ ; if $C$ is not bounded below, no real number is a lower bound. Either way there is $a \in C$ with $a < x$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (i)). In the same way, $x$ is not an upper bound of $C$ , and there is $b \in C$ with $x < b$ .

The segment is the interval. For $n = 1$ , $(1 - t)a + tb = a + t(b - a)$ . Let $t \mathrel{:=} (x - a)/(b - a)$ , which is defined since $b - a > 0$ . It lies in $(0, 1)$ . First, $1/(b - a) > 0$ , since otherwise $1 = (b - a) \cdot 1/(b - a) \le 0$ , against $1 > 0$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (c), (e)). Now $0 < x - a < b - a$ , and multiplying by $1/(b - a) > 0$ keeps both inequalities, by the same rule (c). With this $t$ , we get $(1 - t)a + tb = x$ . So $x \in [a, b] \subseteq C$ , by convexity.

Conclusion. Every $x$ with $\alpha < x < \beta$ lies in $C$ . For $c \in C$ , $\alpha \le c$ because $\inf C$ is a lower bound (or $\alpha = -\infty$ ), and $c \le \beta$ likewise. So $C$ is one of the intervals $(\alpha, \beta)$ , $[\alpha, \beta)$ , $(\alpha, \beta]$ , $[\alpha, \beta]$ , where an infinite end is never included.

What a complete answer needs. (10 points) - 3: handles the ends: $\sup C$ by completeness when bounded above, $\inf C$ when bounded below (Proposition 8.3.1), and the unbounded cases. - 3: finds $a, b \in C$ with $a < x < b$ , from “ $x$ is not a lower (upper) bound”. - 2: shows $x \in [a, b]$ by an explicit $t \in [0, 1]$ , or by the remark of Section 10.1 that a segment of $\mathbb{R}$ is an interval. - 2: concludes both inclusions. Slips that lose the step (0 for the step): using $\inf C$ or $\sup C$ without boundedness; assuming that $C$ contains its supremum or infimum.

Uses: Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Definition 5.5.1 (bounded sets have suprema).

R. Review

Exercise (R1)

Let $Q \mathrel{:=} \{ x \in \mathbb{R}^n : \left| x_k \right| \le 1 \text{ for every } k \}$ . Show that $Q$ is convex and that $\overline{B}(0, 1) \subseteq Q \subseteq \overline{B}(0, \sqrt n)$ .

Solution. By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 4.1.3 (d), $\left| x_k \right| \le 1$ if and only if $-1 \le x_k \le 1$ , that is, $x_k \le 1$ and $-x_k \le 1$ . Since $x_k = \langle e_k, x \rangle$ and $-x_k = \langle -e_k, x \rangle$ (Proposition 9.3.1 (a), (b), (d)), $Q$ is the intersection of the $2n$ closed half-spaces $\{ \langle e_k, x \rangle \le 1 \}$ and $\{ \langle -e_k, x \rangle \le 1 \}$ , whose normals $\pm e_k$ are non-zero. Each is convex by Proposition 10.3.2. So $Q$ , their intersection, is convex by Proposition 10.3.3 (a).

If $\left\| x \right\| \le 1$ , then $\left| x_k \right| \le \left\| x \right\| \le 1$ for every $k$ (Proposition 9.4.7 (a)), so $x \in Q$ . If $x \in Q$ , then $M \mathrel{:=} \max_k \left| x_k \right| \le 1$ , so $\left\| x \right\| \le \sqrt n \, M \le \sqrt n$ (Proposition 9.4.7 (b)), and $x \in \overline{B}(0, \sqrt n)$ . These two inclusions, a ball inside a box inside a larger ball, are the ones Analysis on the Real Line uses to compare balls and boxes.

Exercise (R2)

Identify the polynomial $a + bx + cx^2 \in \mathbb{R}[x]$ with the point $(a, b, c) \in \mathbb{R}^3$ . Show that the set $P$ of such polynomials $f$ with $f(t) \ge 0$ for every $t \in [0, 1]$ is a convex subset of $\mathbb{R}^3$ .

Solution. Fix $t \in [0, 1]$ . Evaluation respects sums and products, sends a constant to itself and $x$ to $t$ (Theorem 6.4.1). So for $f = a + bx + cx^2$ , by the definition of the dot product, $f(t) = a + bt + ct^2 = \langle (1, t, t^2), (a, b, c) \rangle .$ So $P_t \mathrel{:=} \{ f : f(t) \ge 0 \}$ is the closed half-space $\{ \langle (1, t, t^2), y \rangle \ge 0 \}$ of $\mathbb{R}^3$ . Its normal $(1, t, t^2)$ is non-zero, since its first coordinate is $1$ . So $P_t$ is convex by Proposition 10.3.2. Then $P = \bigcap_{t \in [0, 1]} P_t$ is convex by Proposition 10.3.3 (a).

The two-point test also works directly. Let $f = a + bx + cx^2$ and $g = a' + b'x + c'x^2$ be in $P$ and $s \in [0, 1]$ . Then $(1 - s)f(t) + sg(t) \ge 0$ for every $t \in [0, 1]$ . By the displayed formula, this is the value at $t$ of the polynomial with coefficient triple $(1 - s)(a, b, c) + s(a', b', c')$ . So that polynomial is in $P$ .

Uses: Definition 9.3.1 (the dot product).

Exercise (R3)

Let $c \in \mathbb{C}$ , $r > 0$ and $u \in \mathbb{T}$ . Show that $D \mathrel{:=} \{ z \in \mathbb{C} : \left| z - c \right| < r \}$ is convex as a subset of $\mathbb{R}^2$ , and that $z \mapsto uz$ maps $D$ onto $\{ w \in \mathbb{C} : \left| w - uc \right| < r \}$ .

Solution. Reading $\mathbb{C}$ as $\mathbb{R}^2$ , $\left| z - c \right| = \left\| z - c \right\|$ (Proposition 9.4.3 (a), (c)). So $D = B(c, r)$ , which is convex by Proposition 10.3.1.

For $z \in D$ , $\left| uz - uc \right| = \left| u \right|\,\left| z - c \right| = \left| z - c \right| < r$ by Theorem 3.2.2 (d) and $\left| u \right| = 1$ ; so $uz$ lies in the second disc. Onto: let $\left| w - uc \right| < r$ and put $z \mathrel{:=} \overline{u} w$ . Since $\overline{u} = u^{-1}$ (Proposition 3.5.1 (a)), $uz = w$ . Also $\overline{u}\,u\,c = c$ , and $\left| \overline{u} \right| = \left| u \right| = 1$ by Theorem 3.2.2 (d). Hence $\left| z - c \right| = \left| \overline{u}(w - uc) \right| = \left| \overline{u} \right|\,\left| w - uc \right| = \left| w - uc \right| < r ,$ and $z \in D$ . Multiplying the plane by a unit complex number turns it about $0$ , and Complex Analysis opens with this picture.