Linear Algebra › Section H · The geometry of vector spaces › Topic H.3

Convex combinations

Restrict the weights of an affine combination to be non-negative and lines shrink to segments, planes to triangles. These convex combinations describe blends, averages and centres of mass, and they define convex sets, the shapes at the heart of optimisation.

From lines to segments

The line through \(\mathbf{p}\) and \(\mathbf{q}\) is the set of points \((1 - t)\mathbf{p} + t\mathbf{q}\) for all real \(t\). Allow only \(0 \le t \le 1\) and you get just the piece between them, the line segment \(\overline{\mathbf{pq}}\). At \(t = 0.25\) the point is a quarter of the way from \(\mathbf{p}\) towards \(\mathbf{q}\). Both weights, \(1 - t\) and \(t\), are now non-negative as well as adding to 1. That extra condition turns every affine idea of the previous two topics into a convex one: affine hulls become convex hulls, and flat objects that go on forever become bounded pieces such as segments and triangles.

Definition and the convex hull

A convex combination of points \(\mathbf{v}_1, \dots, \mathbf{v}_k\) in \(\mathbb{R}^n\) is

c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k \quad \text{with} \quad c_1 + \cdots + c_k = 1 \ \text{and every} \ c_i \ge 0

So each weight lies between 0 and 1. The set of all convex combinations of points of a set \(S\) is the convex hull of \(S\), written \(\operatorname{conv} S\). The convex hull of two points is the segment between them; of three non-collinear points, the solid triangle they span; of four points in \(\mathbb{R}^3\) not in one plane, a solid tetrahedron. Every convex combination is an affine combination, so \(\operatorname{conv} S\) always lies inside \(\operatorname{aff} S\).

Convex sets

A set \(S\) is convex if, for any two points \(\mathbf{p}\) and \(\mathbf{q}\) in \(S\), the whole segment \(\overline{\mathbf{pq}}\) lies in \(S\). A solid disc, a solid cube, a half-plane, a triangle, any subspace and any flat are convex. An annulus, the ring between two circles, is not: the segment joining opposite points passes through the hole. A crescent and a five-pointed star are not convex either. Two basic facts make convex sets easy to work with. A set is convex exactly when it contains every convex combination of its points, so \(S\) is convex if and only if \(S = \operatorname{conv} S\). And the intersection of any collection of convex sets is convex.

The smallest convex set containing S

Since intersections of convex sets are convex, one can intersect every convex set that contains \(S\). The result is convex, contains \(S\), and sits inside every other convex set containing \(S\). It is exactly \(\operatorname{conv} S\). So there are two views of the convex hull: built from the inside as all convex combinations, or carved from the outside as the intersection of all convex sets containing \(S\). For a finite set of points in the plane, picture stretching a rubber band around pins at the points and letting it snap tight: the band and its interior form the convex hull, a convex polygon whose corners are some of the points.

Worked example: inside or outside a triangle?

Let \(\mathbf{a} = (1, 0)\), \(\mathbf{b} = (5, 2)\), \(\mathbf{c} = (2, 5)\). Is \(\mathbf{p} = (3, 2)\) in \(\operatorname{conv}\{\mathbf{a}, \mathbf{b}, \mathbf{c}\}\)? What about \(\mathbf{q} = (5, 4)\)? 1. Since the three points are affinely independent, each point of the plane has unique barycentric coordinates, as in "Affine independence". 2. For \(\mathbf{p}\), solving gives weights \(1/3\), \(4/9\), \(2/9\). Check:

\tfrac{1}{3}(1, 0) + \tfrac{4}{9}(5, 2) + \tfrac{2}{9}(2, 5) = \big(\tfrac{27}{9}, \tfrac{18}{9}\big) = (3, 2)

All are non-negative, so \(\mathbf{p}\) is in the convex hull. 3. For \(\mathbf{q}\), the weights are \(-1/3\), \(8/9\), \(4/9\). They add to 1, so \(\mathbf{q}\) is an affine combination, but the negative weight means it is not a convex one: \(\mathbf{q}\) lies outside the triangle.

Carathéodory's theorem

A point in the convex hull of a large set might seem to need many points to build it. Constantin Carathéodory proved in 1907 that it never needs more than \(n + 1\): if \(\mathbf{p}\) is in \(\operatorname{conv} S\) for \(S \subseteq \mathbb{R}^n\), then \(\mathbf{p}\) is a convex combination of at most \(n + 1\) points of \(S\). In the plane, every point of a convex hull lies in a triangle with corners in \(S\). The proof is constructive. If \(\mathbf{p}\) uses more than \(n + 1\) points, they are affinely dependent, so there is a relation \(\sum d_i\mathbf{v}_i = \mathbf{0}\) with \(\sum d_i = 0\) and some \(d_i > 0\). Subtracting a suitable multiple of it from the weights keeps them non-negative, still adding to 1, and makes at least one zero.

Worked example: removing a point

Take the square corners \(\mathbf{v}_1 = (0, 0)\), \(\mathbf{v}_2 = (4, 0)\), \(\mathbf{v}_3 = (4, 4)\), \(\mathbf{v}_4 = (0, 4)\) and

\mathbf{p} = 0.1\mathbf{v}_1 + 0.2\mathbf{v}_2 + 0.3\mathbf{v}_3 + 0.4\mathbf{v}_4 = (2, 2.8)

1. A dependence relation is \(\mathbf{v}_1 - \mathbf{v}_2 + \mathbf{v}_3 - \mathbf{v}_4 = \mathbf{0}\), with \(d = (1, -1, 1, -1)\). 2. New weights are \(c_i - \alpha d_i\). Only the positive \(d_i\) can push a weight to zero, so take \(\alpha\) to be the smallest \(c_i / d_i\) among them: \(\min(0.1/1, 0.3/1) = 0.1\). 3. The weights become \((0, 0.3, 0.2, 0.5)\), still non-negative and adding to 1. 4. Check:

0.3(4, 0) + 0.2(4, 4) + 0.5(0, 4) = (2, 2.8)

Three points now suffice, as the theorem promises for \(\mathbb{R}^2\).

Blends and centres of mass

Convex combinations are mixtures. If 2 kg, 3 kg and 5 kg masses sit at points \(\mathbf{v}_1\), \(\mathbf{v}_2\), \(\mathbf{v}_3\), their centre of mass is \(0.2\mathbf{v}_1 + 0.3\mathbf{v}_2 + 0.5\mathbf{v}_3\), each weight being that mass divided by the total, 10 kg. Because the weights are non-negative and add to 1, the centre of mass always lies in the convex hull of the masses. Blends work the same way. Mixing 40% of a fertiliser with nitrogen and phosphorus contents \((20\%, 10\%)\) with 60% of one with \((10\%, 30\%)\) gives

0.4(20, 10) + 0.6(10, 30) = (14, 22)

percent. A recipe can only reach blends inside the convex hull of its ingredients, so a target outside that hull is impossible with those ingredients, a check that matters in diet and alloy planning.

Common mistakes to avoid

First, forgetting one of the two conditions: weights must be non-negative and must add to 1. The combination \(0.5\mathbf{v}_1 + 0.5\mathbf{v}_2 + 0.5\mathbf{v}_3\) has non-negative weights but is not convex. Second, treating an affine combination with a negative weight as a point of the convex hull, as with \(\mathbf{q}\) above. Third, calling a set convex because it looks round; an annulus is round but not convex. Fourth, assuming the union of convex sets is convex; two separate discs are a counterexample, although intersections are always convex. Fifth, in Carathéodory's reduction, choosing \(\alpha\) from a negative \(d_i\), which makes some weight negative.

Key takeaways

A convex combination is c₁v₁ + ⋯ + cₖvₖ with every cᵢ ≥ 0 and c₁ + ⋯ + cₖ = 1. The segment from p to q is (1 − t)p + tq for 0 ≤ t ≤ 1. conv S, the set of all convex combinations of points of S, is the smallest convex set containing S and the intersection of all such sets. A set is convex when it contains the segment between any two of its points, equivalently when S = conv S; intersections of convex sets are convex, unions need not be. A point is in the convex hull of an affinely independent set exactly when its barycentric coordinates are all non-negative. Carathéodory's theorem: in Rⁿ, at most n + 1 points are ever needed. Centres of mass and blends are convex combinations.

Flashcards

Flashcard

Convex combination

Σcᵢvᵢ with every cᵢ ≥ 0 and Σcᵢ = 1

An affine combination with no negative weights.

Test your understanding

Question 1 of 5

Which expression is a convex combination of v₁, v₂ and v₃?

Question 2 of 5

A point has barycentric coordinates (0.5, 0.7, −0.2) relative to a triangle. Is it in the triangle's convex hull?

Question 3 of 5

Which of these sets in R² is convex?

Question 4 of 5

By Carathéodory's theorem, what is the largest number of points of S that may be needed to write a point of conv S, for S in R³?

Question 5 of 5

Masses of 1 kg, 1 kg and 2 kg sit at (0, 0), (4, 0) and (0, 8). Where is their centre of mass?

← Previous topicNext topic →