Convex Set

analysis optimisation linear-algebra

Definition

Convex Set

A convex set is a set that contains every line segment between any two of its points.

Formally, for a set $C\subseteq {\mathbb{R}}^d$, convexity means

$$x,y\in C,\lambda \in [0,1]⟹(1-\lambda )x+\lambda y\in C.$$

The point $(1-\lambda )x+\lambda y$ is the convex combination of $x$ and $y$ at weight $\lambda$. Convexity says that mixing two feasible points never leaves the set.

Intuition

A convex set has no inward dents or holes. If two points are allowed, then every point on the straight path between them is also allowed.

This is why convex sets are central in optimisation: moving between two feasible solutions keeps the whole interpolation feasible.

Properties

• The intersection of any family of convex sets is convex.
• Every affine subspace is convex.
• The epigraph of a convex function is a convex set.