Chapter 132. Convex Geometry

132.1 Introduction

Convex geometry studies convex sets, convex combinations, supporting hyperplanes, and geometric structures defined by linear inequalities.

A subset $C$ of a vector space is convex if every line segment joining two points of $C$ lies entirely inside $C$ .

Convex geometry is closely connected with linear algebra because convex sets are built from vectors, affine combinations, linear maps, and systems of inequalities. Many optimization problems, numerical methods, and machine learning algorithms rely fundamentally on convex structure.

Convexity appears naturally in:

Area	Role of convexity
Linear programming	Feasible regions
Optimization	Convex objective functions
Functional analysis	Convex subsets of normed spaces
Probability	Convex combinations of distributions
Machine learning	Loss minimization
Computational geometry	Convex hull algorithms
Economics	Feasible production and utility sets

Linear algebra provides the coordinate and transformation framework in which convex geometry operates.

132.2 Convex Sets

Let $V$ be a real vector space.

A subset

C\subseteq V

is convex if for every

x,y\in C

and every scalar

t\in[0,1],

the vector

tx+(1-t)y

also belongs to $C$ .

The expression

tx+(1-t)y

is called a convex combination of $x$ and $y$ .

Geometrically, convexity means that the entire line segment between any two points remains inside the set.

Examples of convex sets include:

Set	Convex?
Line	Yes
Plane	Yes
Sphere surface	No
Disk	Yes
Cube	Yes
Triangle	Yes
Annulus	No

The difference between a disk and a circle is important. The disk contains all segments between its points. The circle boundary alone does not.

132.3 Convex Combinations

A convex combination of vectors

v_1,\ldots,v_n

is an expression

a_1v_1+\cdots+a_nv_n,

where

a_i\ge0

and

a_1+\cdots+a_n=1.

These coefficients are nonnegative and sum to one.

Convex combinations differ from ordinary linear combinations because the coefficients are restricted.

The condition

a_1+\cdots+a_n=1

keeps the result inside the affine span of the vectors.

The condition

a_i\ge0

forces the point to lie “between” the vectors rather than extending arbitrarily outward.

For example, in $\mathbb{R}^2$ , the convex combinations of three noncollinear points form a triangle.

132.4 Convex Hulls

The convex hull of a subset

S\subseteq V

is the smallest convex set containing $S$ .

It is written

\operatorname{conv}(S).

Equivalently, it is the set of all finite convex combinations of points of $S$ :

\operatorname{conv}(S) = \left\{ \sum_{i=1}^n a_iv_i : v_i\in S,\ a_i\ge0,\ \sum a_i=1 \right\}.

For example:

Set $S$	Convex hull
Two points	Line segment
Three noncollinear points	Triangle
Four noncoplanar points	Tetrahedron
Circle boundary	Disk

The convex hull operation “fills in” missing interior regions.

Convex hulls are fundamental in computational geometry and optimization.

132.5 Affine Sets

An affine combination of vectors is an expression

a_1v_1+\cdots+a_nv_n,

where

a_1+\cdots+a_n=1,

but the coefficients may be negative.

An affine set is a subset closed under affine combinations.

Affine geometry generalizes linear geometry by allowing translations.

Examples include:

| Object | Linear? | Affine? | |—|—| | Subspace through origin | Yes | Yes | | Shifted line | No | Yes | | Shifted plane | No | Yes |

Affine sets are translated subspaces.

If $W$ is a subspace and $v\in V$ , then

v+W = \{v+w:w\in W\}

is an affine set.

Convex geometry naturally lives inside affine geometry.

132.6 Cones

A subset

K\subseteq V

is a cone if

x\in K,\qquad \lambda\ge0

imply

\lambda x\in K.

A convex cone is both convex and a cone.

Thus:

x,y\in K, \qquad a,b\ge0

imply

ax+by\in K.

Examples include:

Set	Convex cone?
Nonnegative orthant	Yes
Linear subspace	Yes
Ray from origin	Yes
Sphere	No

The nonnegative orthant in $\mathbb{R}^n$ ,

\mathbb{R}_{\ge0}^n,

is one of the most important convex cones.

Convex cones appear in optimization, duality theory, and matrix analysis.

132.7 Hyperplanes

A hyperplane in $V\cong\mathbb{R}^n$ is a set of the form

H = \{x\in\mathbb{R}^n : a^Tx=b\},

where

a\neq0.

The vector $a$ is normal to the hyperplane.

A hyperplane divides space into two half-spaces:

a^Tx\le b,

and

a^Tx\ge b.

Half-spaces are convex.

Hyperplanes are fundamental because many convex sets can be described as intersections of half-spaces.

132.8 Polyhedra

A polyhedron is a set defined by finitely many linear inequalities:

P = \{x\in\mathbb{R}^n : Ax\le b\}.

The matrix $A$ and vector $b$ determine the bounding half-spaces.

Examples include:

Object	Polyhedron?
Cube	Yes
Simplex	Yes
Polygon	Yes
Ball	No

A bounded polyhedron is called a polytope.

Polytopes generalize polygons and polyhedra to arbitrary dimensions.

Convex optimization often studies feasible regions that are polyhedra.

132.9 Extreme Points

Let $C$ be a convex set.

A point $x\in C$ is an extreme point if it cannot be written as a nontrivial convex combination of distinct points in $C$ .

That is, if

x=ty+(1-t)z, \qquad 0<t<1,

with

y,z\in C,

then

x=y=z.

For a polygon, the extreme points are the vertices.

For a disk, every boundary point is extreme.

Extreme points encode the “corners” of convex sets.

132.10 Supporting Hyperplanes

A hyperplane

H=\{x:a^Tx=b\}

supports a convex set $C$ if:

$C$ lies entirely on one side of $H$ ,
$H\cap C\neq\emptyset$ .

Geometrically, the hyperplane touches the convex set without cutting through it.

Supporting hyperplanes are central in optimization because optimal points often occur where a supporting hyperplane meets the feasible region.

132.11 Separation Theorems

One of the most important results in convex geometry is the hyperplane separation theorem.

Roughly stated:

If two convex sets are disjoint, then there exists a hyperplane separating them.

That means there exists a vector $a$ and scalar $b$ such that

a^Tx\le b

for all points in one set and

a^Ty\ge b

for all points in the other.

Separation theorems connect geometry with optimization and duality.

They explain why linear functionals can distinguish convex regions.

132.12 Carathéodory’s Theorem

Carathéodory’s theorem states:

If a point $x\in\mathbb{R}^n$ lies in the convex hull of a set $S$ , then $x$ can be written as a convex combination of at most $n+1$ points of $S$ .

Thus in $\mathbb{R}^2$ , every point in a convex hull can be represented using at most three points.

In $\mathbb{R}^3$ , at most four points suffice.

This theorem gives a finite description of convex combinations in finite-dimensional spaces.

132.13 Helly’s Theorem

Helly’s theorem concerns intersections of convex sets.

If a finite collection of convex subsets of $\mathbb{R}^n$ has the property that every $n+1$ of them intersect, then the entire collection intersects.

This theorem is remarkable because it reduces a global intersection condition to a finite local condition.

Helly’s theorem is fundamental in combinatorial convexity.

132.14 Radon’s Theorem

Radon’s theorem states:

Every set of $n+2$ points in $\mathbb{R}^n$ can be partitioned into two disjoint subsets whose convex hulls intersect.

This theorem reveals an unavoidable overlap structure in sufficiently large point sets.

Radon’s theorem is closely related to Carathéodory’s theorem and Helly’s theorem.

Together they form the core of finite-dimensional convexity theory.

132.15 Convex Functions

A function

f:C\to\mathbb{R}

defined on a convex set $C$ is convex if

f(tx+(1-t)y) \le tf(x)+(1-t)f(y)

for all

x,y\in C, \qquad t\in[0,1].

Geometrically, the graph of a convex function lies below the secant lines connecting its points.

Examples include:

Function	Convex?
$x^2$	Yes
$e^x$	Yes
(	x
$-x^2$	No

Convex functions are important because local minima are automatically global minima.

132.16 Jensen’s Inequality

If $f$ is convex, then

f\left( \sum_{i=1}^n a_ix_i \right) \le \sum_{i=1}^n a_if(x_i),

whenever

a_i\ge0, \qquad \sum a_i=1.

This inequality generalizes the defining property of convexity.

Jensen’s inequality appears throughout probability, statistics, information theory, and optimization.

132.17 Convex Optimization

A convex optimization problem minimizes a convex function over a convex feasible region.

The standard form is:

\text{minimize } f(x)

subject to

x\in C,

where $C$ is convex and $f$ is convex.

Convex optimization is important because:

Property	Consequence
Local minimum	Global minimum
Convex feasible region	Stable geometry
Supporting hyperplanes	Duality theory
Linear constraints	Efficient algorithms

Linear programming is a special case in which:

f(x)=c^Tx

and the feasible region is a polyhedron.

132.18 Duality

Convex geometry naturally leads to duality.

Given a convex set $C$ , its dual cone is

C^* = \{y:\langle y,x\rangle\ge0 \text{ for all }x\in C\}.

Duality transforms geometric problems into algebraic inequalities.

In optimization, every primal problem has a dual problem. Under suitable conditions, solving one determines the other.

Duality theory is built from hyperplanes, convex cones, and linear functionals.

132.19 Norms and Convexity

Every norm defines a convex unit ball:

B = \{x:\|x\|\le1\}.

Conversely, many norms may be reconstructed from convex geometry.

Examples:

Norm	Unit ball
Euclidean norm	Sphere
$\ell^1$ -norm	Diamond
$\ell^\infty$ -norm	Cube

Different norms correspond to different convex geometries.

This connection is fundamental in functional analysis and optimization.

132.20 Convex Geometry in Linear Algebra

Convex geometry and linear algebra interact continuously.

Linear algebra concept	Convex geometry interpretation
Linear combinations	Affine structure
Positive coefficients	Convex combinations
Systems of inequalities	Polyhedra
Linear functionals	Supporting hyperplanes
Null spaces	Feasible directions
Eigenvalues	Spectral convexity
Positive semidefinite matrices	Convex cones

Much of modern optimization is the study of convex geometry using linear algebraic tools.

132.21 Summary

Convex geometry studies sets and functions preserved under convex combinations.

The central ideas are:

Concept	Meaning
Convex set	Contains all line segments between its points
Convex combination	Weighted average with nonnegative coefficients
Convex hull	Smallest convex set containing a given set
Affine set	Closed under affine combinations
Cone	Closed under nonnegative scaling
Hyperplane	Linear boundary surface
Polyhedron	Intersection of finitely many half-spaces
Extreme point	Nondecomposable boundary point
Supporting hyperplane	Boundary hyperplane touching a convex set
Convex function	Function below its secant lines
Duality	Correspondence between primal and dual structures

Convex geometry supplies the geometric foundation for optimization, numerical analysis, machine learning, and many parts of applied linear algebra.