# Chapter 132. Convex Geometry

# 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:

1. \(C\) lies entirely on one side of \(H\),
2. \(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|\) | Yes |
| \(-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.