Convex Sets — Mathematics Knowledge System

Overview

A convex set is a subset of a vector space with the property that for any two points in the set, the entire line segment between them also lies in the set. Convexity is a fundamental geometric concept that underpins a vast part of mathematical optimization: the feasible sets in linear programming, the domains of convex functions, and the constraint sets of convex programs are all convex. Convex sets possess rich structural properties — projections, supporting hyperplanes, separation theorems — that make them tractable to analyze and optimize over.

Intuition

A set is convex if you can draw a straight line between any two points inside it and never leave the set. A disk is convex; a crescent or doughnut is not. Convexity is the minimal condition needed to guarantee that a local minimum of a convex function over the set is also a global minimum.

Formal Definition

Definition

A subset C of a real vector space V is convex if for all x, y ∈ C and all θ ∈ [0,1], the convex combination θx + (1-θ)y lies in C.

C \subseteq V \text{ is convex} \iff \forall x, y \in C,\; \forall \theta \in [0,1]: \theta x + (1-\theta)y \in C

Definition of convexity

\operatorname{conv}(S) = \left\{\sum_{i=1}^k \theta_i x_i : x_i \in S,\; \theta_i \ge 0,\; \sum_i \theta_i = 1,\; k \in \mathbb{N}\right\}

Convex hull of S

Notation

Notation	Meaning
$\operatorname{conv}(S)$	Convex hull of S — smallest convex set containing S
$\operatorname{int}(C)$	Interior of C
$\operatorname{ri}(C)$	Relative interior of C (interior relative to its affine hull)
$\theta x + (1-\theta)y$	Convex combination of x and y, θ ∈ [0,1]

Properties

Intersection preserves convexity

\text{If } \{C_\alpha\}_\alpha \text{ are convex, then } \bigcap_\alpha C_\alpha \text{ is convex}

Affine images are convex

\text{If } C \text{ is convex and } f(x) = Ax + b, \text{ then } f(C) \text{ and } f^{-1}(C) \text{ are convex}

Separating hyperplane theorem

\text{If } C, D \text{ are nonempty disjoint convex sets, } \exists a \neq 0, b: a^T x \le b \; \forall x \in C,\; a^T y \ge b \; \forall y \in D

Supporting hyperplane theorem

\text{For } x_0 \in \partial C \text{ (boundary), } \exists a \neq 0: a^T x \le a^T x_0 \; \forall x \in C

Worked Examples

1
Let C₁ and C₂ be convex, and let x, y ∈ C₁ ∩ C₂.
$x, y \in C_1 \cap C_2$
2
Since x,y ∈ C₁ and C₁ is convex, θx+(1-θ)y ∈ C₁ for all θ ∈ [0,1].
$\theta x + (1-\theta)y \in C_1$
3
Similarly θx+(1-θ)y ∈ C₂.
$\theta x + (1-\theta)y \in C_2$
4
Therefore θx+(1-θ)y ∈ C₁ ∩ C₂.
$\theta x + (1-\theta)y \in C_1 \cap C_2$

✓ Answer

C₁ ∩ C₂ is convex since any convex combination of its elements lies in both C₁ and C₂.

Practice Problems

Mediumproof writing

Prove that every halfspace {x ∈ ℝⁿ : aᵀx ≤ b} is convex.

Common Mistakes

Common Mistake

Thinking convex sets must be bounded

Convex sets can be unbounded. Halfspaces, cones, and the entire space ℝⁿ are all convex.

Common Mistake

Assuming the union of convex sets is convex

The union of two convex sets is generally not convex. Only intersection preserves convexity.

Quiz

Which of the following sets is NOT convex?

The unit ball {x ∈ ℝⁿ : ‖x‖ ≤ 1}The set {(x,y) : x² + y² = 1} (unit circle)The positive orthant {x ∈ ℝⁿ : xᵢ ≥ 0}A halfspace

The convex hull of a set S is:

The smallest convex set containing SThe largest convex set contained in SThe closure of SThe interior of S

Historical Background

The systematic study of convex sets dates to the late 19th century, with contributions from Hermann Minkowski (convex bodies and the Minkowski functional) and Karl Hermann Brunn (the Brunn–Minkowski inequality). The modern theory was consolidated in the mid-20th century by Werner Fenchel and others, providing the geometric foundation for linear and convex programming.

1896
Minkowski develops the geometry of numbers, systematising convex body theory
Hermann Minkowski
1887
Brunn proves the inequality now bearing his name
Karl Hermann Brunn
1951
Dantzig introduces linear programming, placing convex set theory at the centre of optimisation
George Dantzig

Summary

A set C is convex if for any two points x,y ∈ C, the segment θx+(1-θ)y lies in C for all θ ∈ [0,1].
Key examples: halfspaces, balls, polyhedra, affine subspaces, positive semidefinite cone.
Intersections of convex sets are convex; unions generally are not.
The separating and supporting hyperplane theorems are fundamental geometric tools.

References

BookBoyd, S. and Vandenberghe, L. — Convex Optimization (2004), Chapter 2. Free at https://web.stanford.edu/~boyd/cvxbook/
WebsiteWikipedia — Convex set
WebsiteMathWorld — Convex Set