Convex Sets, Hulls & Cones

Sets you cannot escape by walking straight: segments, hulls, and cones.

The idea

A convex set is a set that contains, along with any two of its points, the entire segment between them. Formally, $C \subseteq \mathbb{R}^{n}$ is convex when

$\theta x + (1-\theta) y \in C \quad \text{for all } x, y \in C \text{ and } 0 \le \theta \le 1.$

As $\theta$ runs from $0$ to $1$, the point $\theta x + (1-\theta) y$ sweeps from $y$ to $x$, so $\theta$ is the fraction of the way across. The condition matters for optimization: inside a convex set, we can walk from any point straight toward any better point without leaving the set.

The definition is a rule about coefficients, and loosening the rule produces the rest of the vocabulary. A weighted average $\theta_{1}x_{1} + \cdots + \theta_{k}x_{k}$ whose weights are nonnegative and sum to $1$ is a convex combination. Keeping the sign condition and dropping the sum condition gives a conic combination; keeping the sum and dropping the signs gives an affine combination. The sets closed under these three kinds of combination are exactly the convex sets, the convex cones, and the affine sets.

Ways to work on it

• Walkthrough. The segment definition, convex combinations and the hull, and what makes a cone.
• Practice. Classify sets as convex, conic, or neither; solve conic hulls; count hull corners.
• Hardest. The positive semidefinite cone, where only the definition itself will do.

Not sure where to start? Take the ten-question placement test.