44.01.02 · optimization-control / convex-sets-functions

Carathéodory's Theorem and the Relative Interior of Convex Sets

shipped3 tiersLean: none

Anchor (Master): Rockafellar 1970 Convex Analysis (Princeton) §6, §11, §17, §18; Schneider 2014 Convex Bodies: The Brunn-Minkowski Theory 2nd ed. (Cambridge) §1.1; Hiriart-Urruty & Lemaréchal 2001 Fundamentals of Convex Analysis (Springer) Ch. A-B

Intuition Beginner

Picture a flat triangle lying on a tabletop, corners marked $A$ , $B$ , $C$ . Any point you can reach by mixing those three corners — say, two parts $A$ , one part $B$ — lands somewhere inside or on the edge of the triangle. The set of all such mixtures is the convex hull of the three corners: the filled triangle. Carathéodory's theorem answers a thrifty question. If you start with a huge cloud of points and form their filled-in shape, how many corners do you actually need to rebuild any single interior point? In the plane the answer is three. In ordinary space it is four. In $n$ dimensions it is $n + 1$ — never more.

So even a point built from a million scattered dots can always be re-expressed as a blend of just a handful of them. The cloud may be vast, but each point inside its shell has a short recipe.

The second idea is about the "inside" of a flat shape. A coin lying on the table has plenty of interior as a disk, but as a solid object in three-dimensional space it has no interior at all — it is paper-thin, so every point is on its surface. That is the wrong verdict for most purposes. The relative interior fixes this: it measures inside-ness within the thin slab the shape actually occupies, ignoring the empty directions. For the coin, the relative interior is the open disk minus its rim. This is the honest notion of "deep inside," and it is the one that makes the duality theory of optimisation work.

Why care? Constraints in an optimisation problem carve out a feasible region. Whether you can wiggle a candidate solution in every allowed direction — a question optimisation lives and dies by — is a question about relative interiors, not the misleading full-space interior.

Visual Beginner

Figure: left panel, a scatter of seven dots in the plane with their convex hull drawn as a shaded polygon; one interior target point is shown rebuilt as a blend of just three of the dots (a small shaded triangle inside the polygon), illustrating that three corners suffice in two dimensions. Right panel, a line segment sitting inside the plane: its "interior" as a subset of the plane is empty, but its relative interior is the open segment without its two endpoints.

  Caratheodory in the plane            Relative interior of a segment

      d2 . . . . . . . d3              full-space interior in R^2:  EMPTY
       \  shaded hull  /               (segment is paper-thin)
        \    * P      /
   d1 .  \  /^\      / . d4            o========================o
          \/   \    /                   relative interior =
          /\    \  /                    the open segment (no endpoints)
         /  \    \/                     o------------------------o
        / triangle picks 3 dots         endpoints  *  *  excluded
       d5 . . . . . . d6 . d7

Worked example Beginner

We rebuild a point inside a square using only three of its four corners — the Carathéodory count for the plane.

Take the unit square with corners $A = (0, 0)$ , $B = (1, 0)$ , $C = (1, 1)$ , $D = (0, 1)$ . Target the centre point $P = (0.5, 0.5)$ .

Step 1. The lazy four-corner recipe. Mixing all four equally gives $0.25 A + 0.25 B + 0.25 C + 0.25 D = (0.5, 0.5) = P$ . That uses four corners. Carathéodory promises three are enough.

Step 2. Split the square into two triangles. Draw the diagonal from $A$ to $C$ . The centre $P$ lies on that diagonal, which is the edge shared by triangle $A B C$ and triangle $A C D$ . So $P$ sits in triangle $A B C$ , whose corners are $A$ , $B$ , $C$ .

Step 3. Find the three-corner recipe. We want weights $a, b, c$ with $a + b + c = 1$ and $a A + b B + c C = (0.5, 0.5)$ . Since $A = (0, 0)$ , the $x$ -coordinate gives $b + c = 0.5$ and the $y$ -coordinate gives $c = 0.5$ . So $c = 0.5$ , then $b = 0$ , then $a = 0.5$ .

Step 4. Read the answer. The recipe is $0.5 A + 0 B + 0.5 C = 0.5 (0, 0) + 0.5 (1, 1) = (0.5, 0.5) = P$ . Only $A$ and $C$ carry weight — two corners, even fewer than the three allowed.

What this tells us. The centre needed at most three corners, and a clever split found two. Carathéodory guarantees the ceiling of $n + 1 = 3$ corners in the plane; a specific point may need fewer.

Check your understanding Beginner

Exercise (easy, multiple choice).

Why does optimisation prefer the relative interior over the ordinary interior?

A. Because the ordinary interior is always larger B. Because feasible regions are often flat (lower-dimensional), so their ordinary interior is empty even when there is plenty of room to move within the flat C. Because the relative interior is easier to draw D. Because the ordinary interior is undefined for convex sets

Hint

Think about an equality constraint, which pins you to a flat slab inside the space.

Answer

B. Feedback-correct: correct — equality constraints make feasible sets flat, so the ordinary interior is empty and only the relative interior captures the real freedom to move. Feedback-wrong: the relative interior is generally a subset of (never larger than) any honest inside notion, and the ordinary interior is well defined; the point is that it is often empty.

Formal definition Intermediate+

Work throughout in $R^{n}$ as a finite-dimensional real vector space 01.01.03. A set $C \subseteq R^{n}$ is convex if $θ x + (1 - θ) y \in C$ whenever $x, y \in C$ and $θ \in [0, 1]$ . A convex combination of points $x_{1}, \dots, x_{m}$ is a sum $\sum_{i = 1}^{m} θ_{i} x_{i}$ with $θ_{i} \geq 0$ and $\sum_{i} θ_{i} = 1$ . The convex hull $conv S$ is the set of all finite convex combinations of points of $S$ , equivalently the smallest convex set containing $S$ .

The affine hull $aff C$ is the smallest affine subspace (a translate of a linear subspace) containing $C$ ; concretely it is the set of all affine combinations $\sum_{i} θ_{i} x_{i}$ with $\sum_{i} θ_{i} = 1$ (weights now permitted to be negative) of points of $C$ 01.01.18. The dimension of a convex set is $dim C := dim (aff C)$ , the dimension of the linear subspace parallel to its affine hull.

Definition (relative interior). The relative interior of a convex set $C$ is its interior taken relative to its affine hull:

ri C := {x \in aff C : \exists ε > 0, B (x, ε) \cap aff C \subseteq C} .

Here $B (x, ε)$ is the open Euclidean ball. The relative boundary is $cl C ∖ ri C$ , where $cl C$ denotes the closure. When $aff C = R^{n}$ (the full-dimensional case) the relative interior coincides with the ordinary interior $int C$ ; otherwise $int C = \emptyset$ while $ri C$ can be large.

Counterexamples to common slips

The interior is the wrong notion for flat sets. The segment $C = {(t, 0) : 0 \leq t \leq 1} \subseteq R^{2}$ has $int C = \emptyset$ , yet $ri C = {(t, 0) : 0 < t < 1}$ is the open segment. Using $int$ in a constraint qualification would wrongly declare every equality-constrained problem infeasible-in-interior.
Carathéodory's $n + 1$ is sharp, not loose. A point in the relative interior of an $n$ -simplex genuinely requires all $n + 1$ vertices with positive weight; no $n$ of them suffice. The bound cannot be lowered in general — it drops to $n$ only when the point lies on a proper face.
Closure and relative interior need not be reachable from a single description. For a non-closed convex set, $ri C$ is computed from $C$ but equals $ri (cl C)$ ; conflating $C$ with $cl C$ before taking the relative interior is safe, but conflating $C$ with $ri C$ before taking the closure loses nothing only because $cl (ri C) = cl C$ — a theorem, not a definition.

Key theorem with proof Intermediate+

We prove the two finite-dimensional pillars of this unit: Carathéodory's theorem, and the non-emptiness of the relative interior for any non-empty convex set. The first is a dimension count on convex combinations; the second supplies the standing object on which the entire duality theory rests.

Theorem (Carathéodory and relative-interior non-emptiness).

(i) (Carathéodory.) Let $S \subseteq R^{n}$ and $x \in conv S$ . Then $x$ is a convex combination of at most $n + 1$ points of $S$ .

(ii) (Non-emptiness.) If $C \subseteq R^{n}$ is convex and non-empty, then $ri C \neq = \emptyset$ , and $dim (ri C) = dim C$ .

Proof of (i). Write $x = \sum_{i = 1}^{m} θ_{i} x_{i}$ with $θ_{i} > 0$ , $\sum_{i} θ_{i} = 1$ , and $m$ minimal. Discard any zero-weight terms, so all $θ_{i} > 0$ . Suppose $m > n + 1$ . Then the $m - 1$ vectors $x_{2} - x_{1}, \dots, x_{m} - x_{1}$ live in $R^{n}$ and number more than $n$ , so they are linearly dependent: there are scalars $μ_{2}, \dots, μ_{m}$ , not all zero, with $\sum_{i = 2}^{m} μ_{i} (x_{i} - x_{1}) = 0$ . Set $μ_{1} := - \sum_{i = 2}^{m} μ_{i}$ . Then $\sum_{i = 1}^{m} μ_{i} x_{i} = 0$ and $\sum_{i = 1}^{m} μ_{i} = 0$ , with the $μ_{i}$ not all zero.

For any real $t$ , $x = \sum_{i} (θ_{i} - t μ_{i}) x_{i}$ , and the new weights still sum to $1$ because $\sum_{i} μ_{i} = 0$ . Since some $μ_{i} > 0$ (the $μ_{i}$ sum to zero and are not all zero), increase $t$ from $0$ until the first weight hits zero: take $t^{*} = min {θ_{i} / μ_{i} : μ_{i} > 0}$ . At $t = t^{*}$ every weight $θ_{i} - t^{*} μ_{i} \geq 0$ , the weights still sum to $1$ , and at least one weight vanishes. This expresses $x$ as a convex combination of fewer than $m$ points, contradicting minimality. Hence $m \leq n + 1$ . $□$

Proof of (ii). Translate so that $0 \in C$ ; then $aff C = L$ is a linear subspace, say of dimension $k = dim C$ . Inside $L$ , pick $k + 1$ points $v_{0}, v_{1}, \dots, v_{k}$ of $C$ whose differences $v_{1} - v_{0}, \dots, v_{k} - v_{0}$ form a basis of $L$ — such points exist because $C$ affinely spans $L$ . Their convex hull is a $k$ -dimensional simplex $Δ \subseteq C$ . The barycentre $b = \frac{1}{k + 1} \sum_{i = 0}^{k} v_{i}$ has every barycentric coordinate strictly positive, so a small ball around $b$ within $L$ stays inside $Δ \subseteq C$ : explicitly, any point of $L$ near $b$ has barycentric coordinates near $\frac{1}{k + 1} > 0$ , hence non-negative, hence lies in $Δ$ . Thus $b \in ri C$ , so $ri C \neq = \emptyset$ . Since $ri C$ contains an open-in- $L$ ball, it affinely spans $L$ , giving $dim (ri C) = k = dim C$ . $□$

Bridge. This pair builds toward the entire convex-duality apparatus of the spine and appears again in every constraint-qualification hypothesis. This is exactly the structural guarantee — a non-empty convex set always has a genuine interior in the only sense that respects its flatness — that the Fenchel and Lagrangian duality theorems consume when they require $ri (dom f) \cap ri (dom g) \neq = \emptyset$ . The simplex construction generalises the finite-corner thrift of Carathéodory: where part (i) shrinks a convex combination down to $n + 1$ active points, part (ii) builds a full-dimensional simplex up from $k + 1$ affinely independent points to certify thickness. The foundational reason the relative interior is never empty is precisely that affine independence of $dim C + 1$ points produces a solid simplex inside $C$ , and putting these together, the Carathéodory bound and the simplex barycentre are two faces of the same finite-dimensional dimension count — the number $dim C + 1$ controls both how few corners reconstruct a point and how many are needed to certify an interior. The non-emptiness step is dual to the separation theorems: a relative-interior point cannot be separated from $C$ by a proper supporting hyperplane.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the line-segment principle: if $x \in ri C$ and $y \in cl C$ for a convex set $C \subseteq R^{n}$ , then $(1 - θ) x + θ y \in ri C$ for every $θ \in [0, 1)$ .

Hint

Work inside $aff C$ . Take a relative ball around $x$ inside $C$ ; convex-combine it with a point of $C$ near $y$ to produce a relative ball around the segment point.

Answer

Pass to $L = aff C$ ; all balls below are relative balls in $L$ . Fix $θ \in [0, 1)$ and set $z = (1 - θ) x + θ y$ . Since $x \in ri C$ , there is $ε > 0$ with $B (x, ε) \cap L \subseteq C$ . Since $y \in cl C$ , pick $y^{'} \in C$ with $∥ y - y^{'} ∥ < δ$ for any chosen $δ > 0$ . For any $w$ with $∥ w - z ∥ < (1 - θ) ε - θ δ$ (positive for small $δ$ ), write $w = (1 - θ) x^{'} + θ y^{'}$ where $x^{'} = (w - θ y^{'}) / (1 - θ)$ ; then $∥ x^{'} - x ∥ \leq (∥ w - z ∥ + θ ∥ y^{'} - y ∥) / (1 - θ) < ε$ , so $x^{'} \in C$ , and $w$ is a convex combination of $x^{'}, y^{'} \in C$ , hence $w \in C$ . Thus a relative ball around $z$ lies in $C$ , so $z \in ri C$ .

Exercise 6 (hard, symbolic).

Prove Carathéodory's conic version: if $x$ lies in the conical hull $cone S = {\sum_{i} λ_{i} s_{i} : λ_{i} \geq 0, s_{i} \in S}$ of $S \subseteq R^{n}$ , then $x$ is a non-negative combination of at most $n$ linearly independent points of $S$ .

Hint

Mimic the affine proof, but now the active vectors themselves must be linearly dependent if there are more than $n$ ; remove one along the dependency keeping all coefficients non-negative.

Answer

Write $x = \sum_{i = 1}^{m} λ_{i} s_{i}$ with all $λ_{i} > 0$ and $m$ minimal. If the $s_{i}$ were linearly dependent, $\sum_{i} μ_{i} s_{i} = 0$ with not all $μ_{i} = 0$ ; some $μ_{i} > 0$ (replace $μ$ by $- μ$ if needed). For $x = \sum_{i} (λ_{i} - t μ_{i}) s_{i}$ , increase $t$ to $t^{*} = min {λ_{i} / μ_{i} : μ_{i} > 0}$ ; all coefficients stay $\geq 0$ and at least one vanishes, contradicting minimality. So the active $s_{i}$ are linearly independent, forcing $m \leq n$ . (No normalisation $\sum λ_{i} = 1$ is imposed, which is why the count is $n$ rather than $n + 1$ .)

Exercise 7 (hard, symbolic).

Let $C, D \subseteq R^{n}$ be convex. Prove $ri (C + D) = ri C + ri D$ , where $C + D = {c + d : c \in C, d \in D}$ is the Minkowski sum.

Hint

One inclusion uses that the sum of two relative-interior points has a relative ball around it. The other uses the line-segment principle and that $aff (C + D) = aff C + aff D$ .

Answer

$(\supseteq)$ If $x \in ri C$ , $y \in ri D$ , take relative balls $B (x, ε) \cap aff C \subseteq C$ and $B (y, ε) \cap aff D \subseteq D$ ; their sum contains a relative ball of $C + D$ around $x + y$ within $aff (C + D) = aff C + aff D$ , so $x + y \in ri (C + D)$ . $(\subseteq)$ Let $z \in ri (C + D)$ and write $z = c + d$ with $c \in C, d \in D$ . Fix $c_{0} \in ri C$ , $d_{0} \in ri D$ ; then $c_{0} + d_{0} \in ri (C + D)$ by the first inclusion. Since $z$ is relatively interior, push slightly past $z$ along the segment from $c_{0} + d_{0}$ : there is $w = c^{'} + d^{'} \in C + D$ and $θ \in [0, 1)$ with $z = (1 - θ) (c_{0} + d_{0}) + θ w$ . Splitting coordinatewise, $z = [(1 - θ) c_{0} + θ c^{'}] + [(1 - θ) d_{0} + θ d^{'}]$ , and the line-segment principle applied in $C$ and in $D$ separately places each bracket in $ri C$ and $ri D$ . Hence $z \in ri C + ri D$ .

Advanced results Master

Carathéodory on connected sets and the Fenchel-Bunt sharpening

When $S \subseteq R^{n}$ has at most $n$ connected components — in particular when $S$ is connected — the Carathéodory bound improves: every point of $conv S$ is a convex combination of at most $n$ points of $S$ . This is the Fenchel-Bunt theorem ^{[Rockafellar §17]}. The mechanism is that the extra freedom from connectivity lets one of the $n + 1$ vertices be slid along a path inside $S$ until a coefficient degenerates without leaving $conv S$ . The general $n + 1$ bound is restored exactly when $S$ is allowed to be a generic finite point set with no such connecting structure, which is why the vertices of a simplex realise the sharp case.

Continuity of the relative interior and convexity of operators

The map $C \mapsto ri C$ interacts cleanly with the standard operations. For convex $C$ and a linear map $A$ , $ri (A C) = A (ri C)$ , and $ri (A^{- 1} C) = A^{- 1} (ri C)$ provided $A^{- 1} (ri C) \neq = \emptyset$ . For Minkowski sums, $ri (C + D) = ri C + ri D$ (Exercise 7). For intersections the relation $ri (C \cap D) = ri C \cap ri D$ holds precisely when $ri C \cap ri D \neq = \emptyset$ ^{[Rockafellar §6]}. This last hypothesis is the analytic shadow of the constraint qualifications in duality: two convex constraint sets compose well exactly when their relative interiors meet.

Supporting hyperplanes and the relative-boundary characterisation

A point $x \in C$ lies in $ri C$ if and only if it admits no proper supporting hyperplane: every hyperplane $H = {y : ⟨ a, y ⟩ = ⟨ a, x ⟩}$ with $C \subseteq {y : ⟨ a, y ⟩ \leq ⟨ a, x ⟩}$ must contain all of $C$ , i.e. $a ⊥ (aff C - x)$ . Equivalently, $x \in ri C$ iff for every direction $d$ in the parallel subspace of $aff C$ , the point $x$ can be perturbed both to $x + ϵ d$ and $x - ϵ d$ inside $C$ for small $ϵ$ . This bidirectional-perturbation criterion is the working definition in optimality theory: a feasible point is relatively interior to the feasible set exactly when no first-order constraint is active in a one-sided way, which is the geometric content of a constraint qualification holding.

The recession cone and unboundedness

For a closed convex set $C$ , the recession cone $0^{+} C = {d : x + t d \in C for all x \in C, t \geq 0}$ records the directions of unbounded freedom. Carathéodory's conic version (Exercise 6) controls representations in $0^{+} C$ , and the relative interior of the recession cone governs which asymptotic directions are "stable" under perturbation. A closed convex set is bounded iff $0^{+} C = {0}$ , and the interplay $ri (0^{+} C) = 0^{+} (ri C)$ for closed convex $C$ ties the finite and asymptotic structures together ^{[Rockafellar §8, §11]}.

Synthesis. The finite-dimensional structure theorems are exactly the load-bearing lemmas the duality theory rests on: Carathéodory bounds representations, and the relative interior supplies the non-empty interior every separation argument needs. The central insight is that one number, $dim C + 1$ , simultaneously caps the corners in a convex combination (Carathéodory) and counts the affinely independent points that certify a thick simplex inside $C$ (non-emptiness) — putting these together, the same dimension count is both the thrift theorem and the thickness theorem. The relative interior generalises the ordinary interior to flat sets, and the foundational reason optimisation insists on it is that equality constraints make feasible sets flat, so $ri$ is the only honest interior; the constraint qualification $ri (dom f) \cap ri (dom g) \neq = \emptyset$ is dual to the requirement that a separating hyperplane between epigraphs be non-vertical. The relative-interior calculus $ri (cl C) = ri C$ , $cl (ri C) = cl C$ is exactly the idempotence that lets one pass between a convex set and its canonical closed and relatively-open representatives without loss, and this is exactly what the Fenchel and Lagrangian theorems exploit when they replace a domain by its closure or relative interior at will. The bridge is the line-segment principle, from which the accessibility lemma, the closure identities, and the operator-commutation rules all descend, and which appears again in the proof that a convex function is continuous on the relative interior of its domain.

Full proof set Master

Proposition 1 (line-segment principle). Let $C \subseteq R^{n}$ be convex, $x \in ri C$ , $y \in cl C$ . Then $z_{θ} := (1 - θ) x + θ y \in ri C$ for all $θ \in [0, 1)$ .

Proof. Work in $L = aff C$ with relative balls. Choose $ε > 0$ with $B (x, ε) \cap L \subseteq C$ . Fix $θ \in [0, 1)$ . Given any $δ > 0$ , pick $y^{'} \in C$ with $∥ y^{'} - y ∥ < δ$ (possible as $y \in cl C$ ). Let $r = (1 - θ) ε - θ δ$ ; choose $δ$ small enough that $r > 0$ . For any $w \in L$ with $∥ w - z_{θ} ∥ < r$ , define $x^{'} = (w - θ y^{'}) / (1 - θ) \in L$ . Then

∥ x^{'} - x ∥ = \frac{∥ w - z _{θ} + θ ( y - y ^{'} ) ∥}{1 - θ} \leq \frac{∥ w - z _{θ} ∥ + θ ∥ y - y ^{'} ∥}{1 - θ} < \frac{r + θ δ}{1 - θ} = ε,

so $x^{'} \in B (x, ε) \cap L \subseteq C$ . Since $w = (1 - θ) x^{'} + θ y^{'}$ is a convex combination of $x^{'}, y^{'} \in C$ , convexity gives $w \in C$ . Thus $B (z_{θ}, r) \cap L \subseteq C$ and $z_{θ} \in ri C$ . $□$

Proposition 2 (accessibility and the closure identity). For convex $C$ with $ri C \neq = \emptyset$ , $cl (ri C) = cl C$ .

Proof. From $ri C \subseteq C$ we get $cl (ri C) \subseteq cl C$ . For the reverse, fix $x_{0} \in ri C$ and let $y \in cl C$ . By Proposition 1, $z_{θ} = (1 - θ) x_{0} + θ y \in ri C$ for $θ \in [0, 1)$ , and $z_{θ} \to y$ as $θ ↑ 1$ . Hence $y \in cl (ri C)$ , so $cl C \subseteq cl (ri C)$ . $□$

Proposition 3 (relative-interior identity for closures). For convex $C$ with $ri C \neq = \emptyset$ , $ri (cl C) = ri C$ .

Proof. A closed affine set containing $C$ contains $cl C$ , and conversely, so $aff (cl C) = aff C =: L$ . From $C \subseteq cl C$ , any relative ball witnessing $x \in ri C$ also witnesses $x \in ri (cl C)$ , giving $ri C \subseteq ri (cl C)$ . For the reverse, let $z \in ri (cl C)$ and fix $x \in ri C$ . Because $z$ is relatively interior to $cl C$ , the point $u = z + η (z - x)$ lies in $cl C$ for some small $η > 0$ (move from $z$ away from $x$ along $L$ , staying in $cl C$ ). Then $z = (1 - θ) x + θ u$ with $θ = 1/ (1 + η) \in (0, 1)$ , and $u \in cl C$ , $x \in ri C$ ; Proposition 1 yields $z \in ri C$ . Hence equality. $□$

Proposition 4 (relative-interior of the image under a linear map). Let $C \subseteq R^{n}$ be convex and $A : R^{n} \to R^{m}$ linear. Then $ri (A C) = A (ri C)$ .

Proof. $A$ maps $aff C$ onto $aff (A C)$ , and the restriction of $A$ to the parallel subspace of $aff C$ is a surjection onto the parallel subspace of $aff (A C)$ (eigen/rank analysis of the restricted linear map 01.01.08). $(\supseteq)$ If $x \in ri C$ with relative ball $B (x, ε) \cap aff C \subseteq C$ , then $A$ being an open map onto $aff (A C)$ on the relevant subspace sends this ball to a relative neighbourhood of $A x$ in $aff (A C)$ contained in $A C$ , so $A x \in ri (A C)$ . $(\subseteq)$ Let $w \in ri (A C)$ , choose $x \in C$ with $A x = w$ and $x_{0} \in ri C$ . Then $A x_{0} \in ri (A C)$ by the first inclusion; push past $w$ from $A x_{0}$ inside $A C$ to write $w = (1 - θ) A x_{0} + θ A x^{'}$ with $x^{'} \in C$ , $θ \in [0, 1)$ ; lifting, $w = A [(1 - θ) x_{0} + θ x^{'}]$ , and the bracket is in $ri C$ by Proposition 1. $□$

Connections Master

The relative-interior calculus proved here is the standing hypothesis of the convex-duality and Karush-Kuhn-Tucker theory developed in 44.02.01; the constraint qualification $ri (dom f) \cap ri (dom g) \neq = \emptyset$ that makes Fenchel and Lagrangian duality strong is exactly the non-emptiness and intersection results established in this unit. The unit 44.01.01, co-produced in this wave, fixes the basic vocabulary of convex sets, hulls, and convexity-preserving operations that this unit's affine-hull and Minkowski-sum arguments build on.
The affine-hull machinery — affine combinations, the dimension of a convex set, and hyperplanes — is the finite-dimensional specialisation of the linear-manifold and affine-subspace theory of 01.01.18, while the rank/dimension counting in Carathéodory's proof and in the image-under-linear-map result rests on the eigen- and rank-structure of linear maps from 01.01.08.
The Legendre-Fenchel transform and biconjugation of 37.07.03 live on the same finite-dimensional convex substrate: the effective domain of a convex function is a convex set whose relative interior controls where the conjugate is sharp and where subgradients exist, so the non-emptiness theorem here is what guarantees that domain has a genuine interior to support the duality.

Historical & philosophical context Master

Carathéodory proved his bound in 1907 ^{[Carathéodory 1907]} (Mathematische Annalen 64, 95-115) in the course of studying the coefficient regions of bounded power series, where convex-hull representations of moment data were the operative tool; the theorem was a lemma in a problem of complex analysis before it became a cornerstone of convexity. Ernst Steinitz, in his 1913 study of conditionally convergent series and convex systems ^{[Steinitz 1913]} (Journal für die reine und angewandte Mathematik 143, 128-176), systematised convex hulls in $R^{n}$ and proved the relative-interior and accessibility results in essentially modern form, introducing the distinction between interior and relative interior that the finite-dimensional theory requires.

The synthesis into a self-contained discipline is due to R. Tyrrell Rockafellar, whose Convex Analysis ^{[Rockafellar §6, §17]} (Princeton, 1970) made the relative interior the central regularity notion and organised the structure theorems — Carathéodory, the line-segment principle, the closure-interior identities, and the recession calculus — into the toolkit on which the duality theory of the remainder of optimisation is built. Werner Fenchel's Princeton lectures of 1951 and the Fenchel-Bunt sharpening of Carathéodory for connected sets supplied the refinements that locate the sharp $n + 1$ case among the simplices.

Bibliography Master

@article{caratheodory1907variabilitatsbereich,
  author  = {Carath\'eodory, Constantin},
  title   = {\"Uber den Variabilit\"atsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen},
  journal = {Mathematische Annalen},
  volume  = {64},
  pages   = {95--115},
  year    = {1907}
}

@article{steinitz1913bedingt,
  author  = {Steinitz, Ernst},
  title   = {Bedingt konvergente Reihen und konvexe Systeme},
  journal = {Journal f\"ur die reine und angewandte Mathematik},
  volume  = {143},
  pages   = {128--176},
  year    = {1913}
}

@book{rockafellar1970convex,
  author    = {Rockafellar, R. Tyrrell},
  title     = {Convex Analysis},
  series    = {Princeton Mathematical Series},
  number    = {28},
  publisher = {Princeton University Press},
  year      = {1970}
}

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{schneider2014convex,
  author    = {Schneider, Rolf},
  title     = {Convex Bodies: The Brunn-Minkowski Theory},
  edition   = {2nd},
  series    = {Encyclopedia of Mathematics and its Applications},
  number    = {151},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@book{hiriarturruty2001fundamentals,
  author    = {Hiriart-Urruty, Jean-Baptiste and Lemar\'echal, Claude},
  title     = {Fundamentals of Convex Analysis},
  series    = {Grundlehren Text Editions},
  publisher = {Springer},
  year      = {2001}
}

Prerequisites

01.01.03
01.01.08
01.01.18

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2.1-§2.2; Steinitz 1913 — the picture of rebuilding a point from few corners
intermediate: Rockafellar 1970 Convex Analysis (Princeton) §2, §6, §17; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2.5
master: Rockafellar 1970 Convex Analysis (Princeton) §6, §11, §17, §18; Schneider 2014 Convex Bodies: The Brunn-Minkowski Theory 2nd ed. (Cambridge) §1.1; Hiriart-Urruty & Lemaréchal 2001 Fundamentals of Convex Analysis (Springer) Ch. A-B

References

Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §2 convex sets; §6 relative interiors of convex sets; §11 separation; §17 Carathéodory's theorem and the dimension of convex sets
Carathéodory, C. — Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen · Mathematische Annalen 64 (1907), 95-115
Steinitz, E. — Bedingt konvergente Reihen und konvexe Systeme · Journal für die reine und angewandte Mathematik 143 (1913), 128-176
Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §2.1-§2.5 affine and convex sets, operations preserving convexity
Schneider, R. — Convex Bodies: The Brunn-Minkowski Theory, 2nd ed. (Cambridge, 2014) · §1.1 the basic convexity notions; relative interior and closure

Estimated time

beginner: 16m
intermediate: 42m
master: 70m