---
title: Convex Combinations and Convex Sets
module: Geometry of Vector Spaces
moduleNumber: 9
lessonNumber: 3
order: 903
summary: >
  A convex combination is an affine combination with nonnegative weights, and the
  convex hull of a set is the smallest convex set containing it. Convex sets are
  closed under intersection, and Carathéodory's theorem bounds how many points a
  convex combination in $\mathbb{R}^n$ ever needs: at most $n+1$.
topics: [Geometry of Vector Spaces]
sources:
  - book: Lay
    ref: "Ch. 8 — The Geometry of Vector Spaces; §8.3 Convex Combinations"
draft: false
---

Affine combinations relax a subspace into a flat by letting the weights sum to
one. One more restriction, that the weights be nonnegative, cuts the flat down to
a bounded piece: a segment instead of a line, a triangle instead of a plane, a
solid body instead of all of space.[^lay-convex]

A **convex combination** of points $\mathbf{v}_1, \dots, \mathbf{v}_k$ in
$\mathbb{R}^n$ is a linear combination

$$
c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k
\qquad\text{with}\qquad
c_1 + \cdots + c_k = 1
\text{ and } c_i \ge 0 \text{ for all } i.
$$

The set of all convex combinations of points in $S$ is the **convex hull**
$\operatorname{conv} S$. For a single point the convex hull is that point, the
same as the affine hull. For two distinct points the constraint $0 \le t \le 1$
in $(1-t)\mathbf{v}_1 + t\mathbf{v}_2$ carves out the line segment
$\overline{\mathbf{v}_1\mathbf{v}_2}$, whereas the affine hull was the whole line.

$$
% caption: The affine hull of two points is the full line; the convex hull is the
% segment cut out by $0\le t\le 1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\draw[black] (-1.0,-0.4) -- (5.4,2.2);
\node[black, anchor=south east, font=\scriptsize] at (-0.4,-0.15) {whole line};
\draw[acc, very thick] (1.0,0.4) -- (3.4,1.36);
\fill[acc] (1.0,0.4) circle (1.8pt) node[anchor=north] {$\mathbf{v}_1$};
\fill[acc] (3.4,1.36) circle (1.8pt) node[anchor=north west] {$\mathbf{v}_2$};
\node[acc, anchor=south, font=\scriptsize] at (1.9,1.22) {conv (segment)};
\node[red, anchor=east, font=\scriptsize] at (0.82,0.55) {$t=0$};
\node[red, anchor=west, font=\scriptsize] at (3.75,1.02) {$t=1$};
\end{tikzpicture}
$$

## Convex sets

A set $S$ is **convex** if for every pair $\mathbf{p}, \mathbf{q} \in S$, the
segment $\overline{\mathbf{pq}}$ lies in $S$. Every two points can see each other
without the line of sight leaving the set. A disk, a half-plane, a triangle, and
any single point are convex; a crescent, an annulus, and a star polygon are not.

$$
% caption: Left and center are convex: every chord stays inside. Right is not:
% a chord between two points passes outside the set.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
% convex disk
\draw[thick] (1.0,1.0) circle (0.95);
\draw (0.4,0.55) -- (1.6,1.5);
\node[anchor=north] at (1.0,-0.1) {convex};
% convex polygon
\begin{scope}[shift={(3.3,0)}]
\draw[thick] (0,0.4) -- (1.2,0) -- (1.7,1.2) -- (0.7,1.9) -- cycle;
\draw (0.2,0.8) -- (1.5,1.0);
\node[anchor=north] at (0.85,-0.1) {convex};
\end{scope}
% non-convex crescent
\begin{scope}[shift={(6.4,0)}]
\fill[red!10] (1.0,1.0) circle (0.95);
\fill[white] (1.55,1.0) circle (0.85);
\draw[red, thick] (1.0,1.0) circle (0.95);
\draw[red, thick] (1.55,1.0) circle (0.85);
\draw[red!80, dashed] (0.5,1.6) -- (0.5,0.4);
\node[red, anchor=north] at (0.9,-0.1) {not convex};
\end{scope}
\end{tikzpicture}
$$

Convexity is closure under convex combinations, the
counterpart of the affine-closure theorem for affine sets.

> **Theorem (Convex sets contain their convex combinations).** A set $S$ is convex if and only if every convex combination of
> its points lies in $S$; equivalently, $S = \operatorname{conv} S$.

The induction copies the affine argument, with one adjustment: a convex
combination of $k+1$ points with $c_{k+1} < 1$ regroups as a convex combination
of $\mathbf{v}_{k+1}$ and an interior convex combination of the first $k$ points,
whose weights $c_i / t$ (with $t = 1 - c_{k+1} > 0$) are again nonnegative and
sum to $1$.

For an affinely independent set the convex hull is a simplex, and membership
reduces to a sign test on the barycentric coordinates: a point of the affine hull
lies in the convex hull exactly when all its barycentric coordinates are
nonnegative.

> **Worked example.** Let $\mathbf{v}_1 = (0,0)$, $\mathbf{v}_2 = (4,0)$,
> $\mathbf{v}_3 = (1,3)$, and $S = \{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3\}$.
> Decide whether $\mathbf{p} = (2,1)$ and $\mathbf{q} = (3,3)$ lie in
> $\operatorname{conv} S$.
>
> Solve for the barycentric coordinates through the homogeneous forms. For
> $\mathbf{p}$, row reducing $[\,\tilde{\mathbf{v}}_1\; \tilde{\mathbf{v}}_2\;
> \tilde{\mathbf{v}}_3 \mid \tilde{\mathbf{p}}\,]$ gives
> $$
> \mathbf{p} = \tfrac{1}{4}\mathbf{v}_1 + \tfrac{5}{12}\mathbf{v}_2 +
> \tfrac{1}{3}\mathbf{v}_3.
> $$
> All three weights are nonnegative, so $\mathbf{p} \in \operatorname{conv} S$;
> it is inside the triangle. For $\mathbf{q}$ the same reduction gives
> $$
> \mathbf{q} = -\tfrac{1}{2}\mathbf{v}_1 + \tfrac{1}{2}\mathbf{v}_2 +
> \mathbf{v}_3.
> $$
> The weights still sum to $1$, so $\mathbf{q}$ is in the affine hull (the plane
> of the triangle), but the negative weight on $\mathbf{v}_1$ places $\mathbf{q}$
> outside $\operatorname{conv} S$.

Convex sets are stable under intersection, which is what lets the convex hull be
defined from the outside as well as the inside.

> **Theorem (Intersections of convex and affine sets).** The intersection of any collection of convex sets is convex, and
> the intersection of any collection of affine sets is affine.

If $\mathbf{p}$ and $\mathbf{q}$ lie in every set of the collection, then each set
contains the segment $\overline{\mathbf{pq}}$, so the intersection does too.

> **Theorem (Convex hull as the smallest containing convex set).** For any set $S$, $\operatorname{conv} S$ is the intersection of
> all convex sets that contain $S$.

Call that intersection $T$. Since $\operatorname{conv} S$ is one of the convex
sets containing $S$, we get $T \subseteq \operatorname{conv} S$. Conversely, any
convex set $C \supseteq S$ contains every convex combination of points of $S$
(convex sets contain their convex combinations), so $\operatorname{conv} S \subseteq C$; intersecting over all such
$C$ gives $\operatorname{conv} S \subseteq T$. The convex-hull characterization makes
$\operatorname{conv} S$ the smallest convex set containing $S$. Stretch a rubber
band around a scatter of points in the plane and release it: the boundary it
settles on is the convex hull.

$$
% caption: The convex hull of a point cloud is the smallest convex set enclosing
% it, the shape a rubber band snaps to. Interior points are convex combinations
% of the boundary vertices.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\fill[acc!10] (0,0.5) -- (2.0,-0.3) -- (4.3,0.5) -- (4.6,2.3) -- (2.3,3.1) -- (0.3,2.2) -- cycle;
\draw[acc, thick] (0,0.5) -- (2.0,-0.3) -- (4.3,0.5) -- (4.6,2.3) -- (2.3,3.1) -- (0.3,2.2) -- cycle;
% boundary vertices
\foreach \p in {(0,0.5),(2.0,-0.3),(4.3,0.5),(4.6,2.3),(2.3,3.1),(0.3,2.2)}
  \fill[acc] \p circle (1.7pt);
% interior points
\foreach \p in {(1.5,1.2),(2.8,1.6),(2.0,0.7),(3.3,0.9),(1.2,2.0),(2.6,2.3)}
  \fill[black] \p circle (1.3pt);
\node[acc, anchor=west, font=\scriptsize] at (4.7,1.4) {conv $S$};
\node[black, anchor=north, font=\scriptsize] at (2.3,-0.45) {interior points are convex combinations};
\end{tikzpicture}
$$

The standard basis of $\mathbb{R}^3$ gives a clean three-dimensional hull: the
convex hull of $\{\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3\}$ is the triangular
patch with those three vertices, the piece of the plane $x_1 + x_2 + x_3 = 1$
lying in the first octant.

$$
% caption: The convex hull of the standard basis is the triangle with vertices
% $\mathbf{e}_1$, $\mathbf{e}_2$, $\mathbf{e}_3$, sitting on the plane
% $x_1+x_2+x_3=1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\coordinate (O) at (0,0);
% axes
\draw[->, black] (O) -- (0,2.6) node[anchor=east] {$x_3$};
\draw[->, black] (O) -- (3.4,-0.4) node[anchor=north] {$x_1$};
\draw[->, black] (O) -- (2.4,1.4) node[anchor=west] {$x_2$};
\coordinate (E1) at (2.6,-0.3);
\coordinate (E2) at (1.7,1.0);
\coordinate (E3) at (0,2.0);
\fill[acc!12] (E1) -- (E2) -- (E3) -- cycle;
\draw[acc, thick] (E1) -- (E2) -- (E3) -- cycle;
\fill[black] (E1) circle (1.7pt) node[anchor=north] {$\mathbf{e}_1$};
\fill[black] (E2) circle (1.7pt) node[anchor=west] {$\mathbf{e}_2$};
\fill[black] (E3) circle (1.7pt) node[anchor=east] {$\mathbf{e}_3$};
\fill[black] (O) circle (1.4pt) node[anchor=north east] {$O$};
\end{tikzpicture}
$$

A convex hull can also be described by an inequality rather than a list of
vertices.

> **Worked example.** Let $S$ be the set of points on the parabola $y = x^2$ with
> $x \ge 0$. Show that $\operatorname{conv} S$ is the region on and above the
> curve for $x > 0$, together with the origin.
>
> Take any point $\mathbf{p} = (a, b)$ with $a > 0$ and $b \ge a^2$. The line
> through $\mathbf{0}$ and $\mathbf{p}$ has slope $b/a$, and it meets $y = x^2$
> where
> $$
> \frac{b}{a}\,x = x^2, \qquad\text{that is, at}\qquad x = \frac{b}{a}.
> $$
> Since $b \ge a^2$ gives $b/a \ge a > 0$, that intersection point $\big(b/a,\,
> b^2/a^2\big)$ lies on $S$, and $\mathbf{p}$ sits on the segment from
> $\mathbf{0}$ to it. So every such $\mathbf{p}$ is a convex combination of two
> points of $S$. No point strictly above the $y$-axis other than the origin
> qualifies, since the origin is the only point of $S$ on that axis; the convex
> hull is therefore the region claimed.

$$
% caption: The convex hull of the right half of $y=x^2$ is the region on and
% above the curve. A point in the shaded region sits on a chord from the origin to
% a point of the parabola.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.0]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
% shaded region above parabola
\fill[acc!10] (0,0) .. controls (0.9,0.15) and (1.7,0.7) .. (2.1,2.6)
  -- (0,2.6) -- cycle;
% parabola
\draw[thick] (0,0) .. controls (0.9,0.15) and (1.7,0.7) .. (2.1,2.6);
\node[anchor=west] at (1.9,2.4) {$y=x^2$};
% axes
\draw[->, black] (-0.2,0) -- (3.0,0) node[anchor=north] {$x$};
\draw[->, black] (0,-0.2) -- (0,2.9) node[anchor=east] {$y$};
% a chord
\coordinate (P) at (0.85,1.7);
\coordinate (Q) at (1.35,1.82);
\draw[red, dashed] (0,0) -- (Q);
\fill[black] (P) circle (1.5pt) node[anchor=east, font=\scriptsize] {$\mathbf{p}$};
\fill[black] (Q) circle (1.5pt);
\node[black, anchor=west, font=\scriptsize] at (1.15,1.1) {conv $S$};
\end{tikzpicture}
$$

## Carathéodory's theorem

The definition of a convex combination places no limit on how many points it
uses. Carathéodory's theorem supplies one: in $\mathbb{R}^n$, no convex
combination ever needs more than $n+1$ points. A point in the convex hull of a
planar set is always a convex combination of at most three of them.

> **Theorem (Carathéodory).** If $S$ is a nonempty subset of $\mathbb{R}^n$,
> then every point of $\operatorname{conv} S$ is a convex combination of $n+1$ or
> fewer points of $S$.

Suppose $\mathbf{p} = c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k$ with $k > n+1$.
Then $\{\mathbf{v}_1, \dots, \mathbf{v}_k\}$ is affinely dependent, so there are
scalars $d_i$, not all zero, with $\sum d_i\mathbf{v}_i = \mathbf{0}$ and $\sum
d_i = 0$. Subtracting a carefully chosen multiple of this dependence relation
from the combination $\mathbf{p} = \sum c_i\mathbf{v}_i$ drives one weight to zero
while keeping the rest nonnegative and summing to $1$. The count drops by one, and
the process repeats until at most $n+1$ points remain.

The multiple is fixed by keeping every weight nonnegative. Among the indices with
$d_i > 0$, choose the one minimizing $c_i / d_i$; subtracting that ratio times the
dependence relation zeroes its weight first and leaves the others nonnegative.

> **Worked example.** Let $\mathbf{v}_1 = (1,0)$, $\mathbf{v}_2 = (2,3)$,
> $\mathbf{v}_3 = (5,4)$, $\mathbf{v}_4 = (3,0)$, and $\mathbf{p} =
> \big(\tfrac{10}{3}, \tfrac{5}{2}\big)$, with
> $$
> \tfrac{1}{4}\mathbf{v}_1 + \tfrac{1}{6}\mathbf{v}_2 + \tfrac{1}{2}\mathbf{v}_3 +
> \tfrac{1}{12}\mathbf{v}_4 = \mathbf{p}.
> $$
> Reduce this to three points. Since the four points lie in $\mathbb{R}^2$ they
> are affinely dependent; solving gives the dependence relation
> $$
> -5\mathbf{v}_1 + 4\mathbf{v}_2 - 3\mathbf{v}_3 + 4\mathbf{v}_4 = \mathbf{0},
> \qquad -5 + 4 - 3 + 4 = 0.
> $$
> The positive coefficients belong to $\mathbf{v}_2$ and $\mathbf{v}_4$. Compare
> the ratios of the convex weights to these coefficients:
> $$
> \frac{1/6}{4} = \frac{1}{24}, \qquad \frac{1/12}{4} = \frac{1}{48}.
> $$
> The smaller ratio, $\tfrac{1}{48}$, belongs to $\mathbf{v}_4$. Subtract
> $\tfrac{1}{48}$ times the dependence relation from the convex combination. Each
> weight becomes $c_i - \tfrac{1}{48}d_i$:
> $$
> \Big(\tfrac{1}{4} + \tfrac{5}{48}\Big)\mathbf{v}_1 +
> \Big(\tfrac{1}{6} - \tfrac{4}{48}\Big)\mathbf{v}_2 +
> \Big(\tfrac{1}{2} + \tfrac{3}{48}\Big)\mathbf{v}_3 +
> \Big(\tfrac{1}{12} - \tfrac{4}{48}\Big)\mathbf{v}_4 = \mathbf{p}.
> $$
> The weight on $\mathbf{v}_4$ vanishes, leaving a convex combination of three
> points:
> $$
> \tfrac{17}{48}\mathbf{v}_1 + \tfrac{4}{48}\mathbf{v}_2 +
> \tfrac{27}{48}\mathbf{v}_3 = \mathbf{p}.
> $$
> The three weights are nonnegative and sum to $1$.

$$
% caption: Carathéodory in $\mathbb{R}^2$: a point written with four weights is
% rewritten with three. Dropping $\mathbf{v}_4$ leaves $\mathbf{p}$ inside the
% triangle on $\mathbf{v}_1$, $\mathbf{v}_2$, $\mathbf{v}_3$.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=0.95]
\definecolor{acc}{HTML}{2F6DB5}
\definecolor{red}{HTML}{B23A48}
\coordinate (V1) at (0,0);
\coordinate (V2) at (1.6,3.0);
\coordinate (V3) at (4.6,3.8);
\coordinate (V4) at (2.6,0);
\coordinate (P) at (2.05,1.9);
\fill[acc!10] (V1) -- (V2) -- (V3) -- cycle;
\draw[acc, thick] (V1) -- (V2) -- (V3) -- cycle;
\draw[black, dashed] (V1) -- (V4) -- (V3);
\draw[black, dashed] (V2) -- (V4);
\fill[black] (V1) circle (1.7pt) node[anchor=north east] {$\mathbf{v}_1$};
\fill[black] (V2) circle (1.7pt) node[anchor=south east] {$\mathbf{v}_2$};
\fill[black] (V3) circle (1.7pt) node[anchor=south west] {$\mathbf{v}_3$};
\fill[black] (V4) circle (1.7pt) node[anchor=north] {$\mathbf{v}_4$};
\fill[black] (P) circle (1.8pt) node[anchor=south west] {$\mathbf{p}$};
\node[black, anchor=west, font=\scriptsize] at (2.7,0.4) {removed};
\end{tikzpicture}
$$

The bound $n+1$ cannot be lowered in general. The centroid of three
non-collinear points in $\mathbb{R}^2$ is a convex combination of all three but
of no two, so three points are genuinely needed there. Nonnegative weights that
sum to one, applied to finitely many points, produce bounded convex bodies whose
boundaries are cut by
[hyperplanes](/linear-algebra/geometry-of-vector-spaces/hyperplanes-and-polytopes).

[^lay-convex]: **Lay**, _Linear Algebra and Its Applications_, §8.3 — Convex
Combinations: the definitions of convex combination and convex hull, Theorem 7
($S = \operatorname{conv} S$), Theorem 8 (intersections), Theorem 9 (smallest
convex set), and Theorem 10 (Carathéodory). Worked example adapts §8.3 Example 4.