Convex Combinations and Convex Sets

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.¹

A convex combination of points $v_{1}, \dots, v_{k}$ in $R^{n}$ is a linear combination

c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k} with c_{1} + \dots + c_{k} = 1 and c_{i} \geq 0 for all i .

The set of all convex combinations of points in $S$ is the convex hull $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 \leq t \leq 1$ in $(1 - t) v_{1} + t v_{2}$ carves out the line segment $\overline{v_{1} v_{2}}$ , whereas the affine hull was the whole line.

The affine hull of two points is the full line; the convex hull is the segment cut out by

0 \leq t \leq 1

Convex sets

A set $S$ is convex if for every pair $p, q \in S$ , the segment $\overline{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.

Left and center are convex: every chord stays inside. Right is not: a chord between two points passes outside the set.

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

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 $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.

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

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

Call that intersection $T$ . Since $conv S$ is one of the convex sets containing $S$ , we get $T \subseteq conv S$ . Conversely, any convex set $C \supseteq S$ contains every convex combination of points of $S$ (convex sets contain their convex combinations), so $conv S \subseteq C$ ; intersecting over all such $C$ gives $conv S \subseteq T$ . The convex-hull characterization makes $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.

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.

The standard basis of $R^{3}$ gives a clean three-dimensional hull: the convex hull of ${e_{1}, e_{2}, 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.

The convex hull of the standard basis is the triangle with vertices

e_{1}

e_{2}

e_{3}

, sitting on the plane

x_{1} + x_{2} + x_{3} = 1

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

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.

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 $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.

Suppose $p = c_{1} v_{1} + \dots + c_{k} v_{k}$ with $k > n + 1$ . Then ${v_{1}, \dots, v_{k}}$ is affinely dependent, so there are scalars $d_{i}$ , not all zero, with $\sum d_{i} v_{i} = 0$ and $\sum d_{i} = 0$ . Subtracting a carefully chosen multiple of this dependence relation from the combination $p = \sum c_{i} 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 $v_{1} = (1, 0)$ , $v_{2} = (2, 3)$ , $v_{3} = (5, 4)$ , $v_{4} = (3, 0)$ , and $p = (\frac{10}{3}, \frac{5}{2})$ , with

\frac{1}{4} v_{1} + \frac{1}{6} v_{2} + \frac{1}{2} v_{3} + \frac{1}{12} v_{4} = p .

Reduce this to three points. Since the four points lie in $R^{2}$ they are affinely dependent; solving gives the dependence relation

- 5 v_{1} + 4 v_{2} - 3 v_{3} + 4 v_{4} = 0, - 5 + 4 - 3 + 4 = 0.

The positive coefficients belong to $v_{2}$ and $v_{4}$ . Compare the ratios of the convex weights to these coefficients:

\frac{1/6}{4} = \frac{1}{24}, \frac{1/12}{4} = \frac{1}{48} .

The smaller ratio, $\frac{1}{48}$ , belongs to $v_{4}$ . Subtract $\frac{1}{48}$ times the dependence relation from the convex combination. Each weight becomes $c_{i} - \frac{1}{48} d_{i}$ :

(\frac{1}{4} + \frac{5}{48}) v_{1} + (\frac{1}{6} - \frac{4}{48}) v_{2} + (\frac{1}{2} + \frac{3}{48}) v_{3} + (\frac{1}{12} - \frac{4}{48}) v_{4} = p .

The weight on $v_{4}$ vanishes, leaving a convex combination of three points:

\frac{17}{48} v_{1} + \frac{4}{48} v_{2} + \frac{27}{48} v_{3} = p .

The three weights are nonnegative and sum to $1$ .

Carathéodory in

R^{2}

: a point written with four weights is rewritten with three. Dropping

v_{4}

leaves

p

inside the triangle on

v_{1}

v_{2}

v_{3}

The bound $n + 1$ cannot be lowered in general. The centroid of three non-collinear points in $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.

Lay, Linear Algebra and Its Applications, §8.3 — Convex Combinations: the definitions of convex combination and convex hull, Theorem 7 ( $S = conv S$ ), Theorem 8 (intersections), Theorem 9 (smallest convex set), and Theorem 10 (Carathéodory). Worked example adapts §8.3 Example 4. ↩

Convex sets

Carathéodory's theorem

Footnotes