44.01.03 · optimization-control / 01-convex-sets-functions

Recession Cones and Polyhedral Convexity (Minkowski-Weyl)

shipped3 tiersLean: none

Anchor (Master): Rockafellar 1970 Convex Analysis (Princeton) §8, §17-§19, §27; Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7-§8; Ziegler 1995 Lectures on Polytopes (Springer) Ch. 1

Intuition Beginner

Picture a shape sitting in space and ask a single question: if you stand inside it and start walking in a fixed direction, can you keep walking forever and never leave? For a filled disk the answer is always no — whichever way you head, you eventually hit the edge. For an infinite strip between two parallel lines, you can walk forever along the strip but not across it. The collection of all "walk-forever" directions is the recession cone of the shape. It is the catalogue of the set's escape routes to infinity.

This catalogue tells you instantly whether a shape is bounded. A shape is bounded exactly when it has no escape routes at all — its only recession direction is standing still. The moment even one genuine direction of unbounded travel exists, the shape runs off to infinity.

Why does an optimiser care? When you minimise a cost over a region, the danger is that the cost keeps dropping as you flee toward infinity, so no best point exists. The recession cone is precisely where you look for that danger: if every escape route makes the cost go up (or at least not down), the search is trapped in a bounded arena and a minimum must exist.

The second idea is about shapes built from flat faces — polyhedra. There are two ways to describe one. You can carve it out with finitely many flat cuts (each cut a halfspace: "stay on this side of this wall"). Or you can build it up from a few corner points plus a few directions you are allowed to slide along forever. A square is four cuts; it is also four corners with no slide directions. A wedge is two cuts; it is one corner plus two slide directions.

The Minkowski-Weyl theorem says these two descriptions — carve-down and build-up — always describe the same family of shapes. Every shape you can carve with finite cuts, you can also build from finite corners and slides, and the reverse. The corners that genuinely cannot be faked as blends of other points are the vertices, and they are where linear optimisers always find their answer.

Visual Beginner

Figure: left panel, an unbounded polyhedron (a "wedge" opening upward and to the right) drawn with its two boundary rays; its recession cone is shown separately as the same two rays anchored at the origin, the set of directions you can travel forever. Middle panel, a bounded polygon (a pentagon) whose recession cone is just the single point at the origin, signalling boundedness. Right panel, the two descriptions of the wedge side by side: as the intersection of two halfspaces (two shaded walls) and as one corner point plus two arrow-directions (the build-up picture).

  Unbounded wedge P            Recession cone 0^+P        Bounded pentagon Q
        \         /                \    |    /                  . . . . .
         \  P    /                  \   |   /                  .         .
          \     /                    \  |  /                  .   Q       .
           \   /                      \ | /                    .         .
            \ /                        \|/                      . . . . .
             v  corner                  O  (origin)
                                                            recession cone 0^+Q = { O }
                                                            (a single point => bounded)

  Two descriptions of the wedge (Minkowski-Weyl):
    carve-down:  P = halfspace_1  AND  halfspace_2     (two walls)
    build-up:    P = corner  +  ray_1  +  ray_2        (one point + two slide directions)

Worked example Beginner

We find the recession cone of a concrete unbounded region and read off whether it is bounded.

Take the region $C$ in the plane defined by two conditions: $x \geq 0$ and $y \geq 0$ . This is the first quadrant — everything with both coordinates non-negative.

Step 1. Pick a starting point inside. Start at the point $(2, 3)$ , which is in $C$ because both coordinates are positive.

Step 2. Try walking in the direction "right," meaning $(1, 0)$ . After time $t$ you are at $(2 + t, 3)$ . The first coordinate is $2 + t \geq 0$ and the second is $3 \geq 0$ , so you stay in $C$ for every $t \geq 0$ . The direction $(1, 0)$ is a recession direction.

Step 3. Try walking "down-left," meaning $(- 1, - 1)$ . After time $t$ you are at $(2 - t, 3 - t)$ . At $t = 4$ this is $(- 2, - 1)$ , which has a negative first coordinate, so you have left $C$ . The direction $(- 1, - 1)$ is not a recession direction.

Step 4. Identify the whole catalogue. A direction $(d_{1}, d_{2})$ keeps you inside forever exactly when adding any positive multiple never makes a coordinate negative, which needs $d_{1} \geq 0$ and $d_{2} \geq 0$ . So the recession cone is again the first quadrant of directions: ${(d_{1}, d_{2}) : d_{1} \geq 0, d_{2} \geq 0}$ .

What this tells us. The recession cone contains more than the single zero direction, so the first quadrant is unbounded — which matches the picture. The escape routes are exactly "go right, go up, or any blend of the two." A cost that increased along every such direction would still attain a minimum here.

Check your understanding Beginner

Exercise (easy, multiple choice).

The Minkowski-Weyl theorem says that a polyhedron can be described in two equivalent ways. Which pair?

A. As a smooth curve, or as a list of tangent lines B. As the intersection of finitely many halfspaces (carve-down), or as finitely many corner points plus finitely many slide-directions (build-up) C. As a single point, or as the whole space D. As a circle, or as a square

Hint

One description cuts the shape out with walls; the other builds it from corners and directions.

Answer

B. Feedback-correct: correct — finitely-many-halfspaces (the H-description) and finitely-generated corners-plus-directions (the V-description) define exactly the same family of sets. Feedback-wrong: Minkowski-Weyl is about polyhedra specifically, equating the halfspace-intersection and finitely-generated descriptions, not about curves or single points.

Formal definition Intermediate+

Work in $R^{n}$ . Recall from 44.01.01 that a set $C$ is convex when it contains the segment between any two of its points, and from 01.01.18 that a halfspace is ${x : ⟨ a, x ⟩ \leq β}$ for some $a \neq = 0$ and $β \in R$ .

Definition (recession cone). Let $C \subseteq R^{n}$ be non-empty, closed, and convex. The recession cone (or asymptotic cone) of $C$ is

0^{+} C := {d \in R^{n} : x + t d \in C for all x \in C and all t \geq 0} .

A direction $d \in 0^{+} C$ is a direction of recession. The set $0^{+} C$ is a closed convex cone (closed under non-negative scaling and addition). For a closed convex $C$ it suffices to test recession from a single point: $d \in 0^{+} C$ if and only if $x_{0} + t d \in C$ for all $t \geq 0$ for one fixed $x_{0} \in C$ — closedness is what makes the choice of basepoint immaterial.

Definition (recession function). For a proper closed convex function $f : R^{n} \to (- \infty, + \infty]$ , the recession function $f 0^{+} : R^{n} \to (- \infty, + \infty]$ is the function whose epigraph is the recession cone of $epi f$ ; equivalently, for any $x \in dom f$ ,

(f 0^{+}) (d) = t \to \infty lim \frac{f ( x + t d ) - f ( x )}{t} = t > 0 sup \frac{f ( x + t d ) - f ( x )}{t} .

$f$ is coercive (the relevant level sets are bounded) precisely when $(f 0^{+}) (d) > 0$ for every $d \neq = 0$ .

Definition (polyhedron and polyhedral cone). A polyhedron is an intersection of finitely many halfspaces:

P = {x : ⟨ a_{i}, x ⟩ \leq β_{i}, i = 1, \dots, m} = {x : A x \leq b} .

A bounded polyhedron is a polytope. A polyhedral cone is a polyhedron of the form ${x : A x \leq 0}$ (each $β_{i} = 0$ ). A set is finitely generated if it has the form

conv {v_{1}, \dots, v_{p}} + cone {r_{1}, \dots, r_{q}},

the Minkowski sum of the convex hull of finitely many points $v_{j}$ and the conical hull $cone {r_{k}} = {\sum_{k} λ_{k} r_{k} : λ_{k} \geq 0}$ of finitely many directions $r_{k}$ .

Definition (faces, vertices, extreme points). A face of a convex set $C$ is a convex subset $F \subseteq C$ such that whenever a point of $F$ lies in the relative interior of a segment with endpoints in $C$ , both endpoints lie in $F$ . A vertex (or extreme point) is a face that is a single point: $x \in C$ is extreme if $x = \frac{1}{2} (y + z)$ with $y, z \in C$ forces $y = z = x$ . The set of extreme points is written $ext C$ .

Counterexamples to common slips

The single-basepoint test fails for non-closed sets. The recession-cone basepoint-independence relies on closedness. For the open halfplane ${(x, y) : y > 0}$ closed up to a non-closed convex set, testing recession from one point can admit a direction that escapes another point's reach; Rockafellar's theory restricts $0^{+} C$ to closed convex $C$ for exactly this reason.
Boundedness is not "no recession in the coordinate directions." A set can be bounded in every coordinate axis direction yet unbounded along a diagonal only if it is non-convex; for convex closed $C$ , boundedness is the clean statement $0^{+} C = {0}$ , but one must test all directions, not a finite spanning set, unless $C$ is polyhedral.
Not every boundary point is a vertex. An edge midpoint of a square is on the boundary but is the average of two distinct boundary points, so it is not extreme. Extreme points are the corners only.

Key theorem with proof Intermediate+

We prove the two pillars: the recession-cone criterion for boundedness with its existence-of-minimisers corollary, and the Minkowski-Weyl theorem identifying polyhedral with finitely generated sets.

Theorem (boundedness, existence of minimisers, and Minkowski-Weyl).

(i) (Boundedness.) A non-empty closed convex set $C \subseteq R^{n}$ is bounded if and only if $0^{+} C = {0}$ .

(ii) (Existence of minimisers.) Let $f : R^{n} \to (- \infty, + \infty]$ be proper, closed, and convex. If $(f 0^{+}) (d) > 0$ for every $d \neq = 0$ , then $f$ attains its infimum, and the set of minimisers is non-empty, compact, and convex.

(iii) (Minkowski-Weyl.) A set $P \subseteq R^{n}$ is a polyhedron (intersection of finitely many halfspaces) if and only if it is finitely generated, $P = conv {v_{1}, \dots, v_{p}} + cone {r_{1}, \dots, r_{q}}$ .

Proof of (i). If $C$ is bounded, no nonzero $d$ can satisfy $x_{0} + t d \in C$ for all $t \geq 0$ , since $∥ x_{0} + t d ∥ \to \infty$ ; hence $0^{+} C = {0}$ . Conversely, suppose $C$ is unbounded. Fix $x_{0} \in C$ and take $x_{k} \in C$ with $∥ x_{k} - x_{0} ∥ \to \infty$ . The unit vectors $d_{k} = (x_{k} - x_{0}) /∥ x_{k} - x_{0} ∥$ lie on the compact unit sphere, so a subsequence converges to a unit vector $d$ . For any fixed $t \geq 0$ and large $k$ , $∥ x_{k} - x_{0} ∥ \geq t$ , and convexity gives that the point $x_{0} + t d_{k} = (1 - t /∥ x_{k} - x_{0} ∥) x_{0} + (t /∥ x_{k} - x_{0} ∥) x_{k}$ lies in $C$ . Letting $k \to \infty$ along the subsequence, $x_{0} + t d \in C$ by closedness, for every $t \geq 0$ . So $d \in 0^{+} C$ with $∥ d ∥ = 1$ , and $0^{+} C \neq = {0}$ . $□$

Proof of (ii). Let $α = in f f > - \infty$ (finiteness follows below). Pick a value $γ$ with the sublevel set $L_{γ} = {x : f (x) \leq γ}$ non-empty; $L_{γ}$ is closed (lsc) and convex. Its recession cone is $0^{+} L_{γ} = {d : (f 0^{+}) (d) \leq 0}$ . The hypothesis $(f 0^{+}) (d) > 0$ for all $d \neq = 0$ forces $0^{+} L_{γ} = {0}$ , so by part (i) $L_{γ}$ is bounded, hence compact. The restriction of the lsc function $f$ to the compact set $L_{γ}$ attains its minimum at some $x^{*}$ , and $f (x^{*}) \leq γ$ together with $f \geq f (x^{*})$ on $L_{γ}$ and $f > γ \geq f (x^{*})$ off $L_{γ}$ shows $x^{*}$ is a global minimiser. The minimiser set is the sublevel set ${x : f (x) \leq f (x^{*})}$ , which is closed, convex, and contained in the bounded $L_{γ}$ , hence compact. $□$

Proof of (iii). (Finitely generated $\Rightarrow$ polyhedral.) Let $P = conv {v_{j}} + cone {r_{k}}$ . Lift to a single cone in $R^{n + 1}$ : set $K = cone {(v_{j}, 1)} \cup cone {(r_{k}, 0)}$ , the conical hull of the lifted generators. Then $x \in P$ iff $(x, 1) \in K$ . A finitely generated cone is the image of the non-negative orthant under a linear map, $K = {M λ : λ \geq 0}$ where $M$ has the generators as columns. By Carathéodory's conic theorem 44.01.02, $K$ is a finite union of finitely-generated cones each spanned by a linearly independent subset, each of which is closed; a finite union of closed sets is closed, so $K$ is a closed convex cone. The polar $K^{\circ} = {y : ⟨ y, z ⟩ \leq 0 \forall z \in K}$ is again finitely generated (the same lift-and-Carathéodory argument applies to it once one knows it is the intersection $⋂_{j} {y : ⟨ y, (v_{j}, 1)⟩ \leq 0} \cap ⋂_{k} {y : ⟨ y, (r_{k}, 0)⟩ \leq 0}$ , a polyhedral cone). By the bipolar theorem for closed convex cones, $K = K^{\circ\circ} = {z : ⟨ y, z ⟩ \leq 0 \forall y \in K^{\circ}}$ , and since $K^{\circ}$ is finitely generated, $K$ is cut out by finitely many homogeneous inequalities — a polyhedral cone. Slicing $K$ at the last coordinate $= 1$ produces finitely many inequalities on $x$ , so $P$ is a polyhedron.

(Polyhedral $\Rightarrow$ finitely generated.) Let $P = {x : A x \leq b}$ . Homogenise: $P = {x : (x, 1) \in \tilde{K}}$ where $\tilde{K} = {(x, μ) : A x - μ b \leq 0, μ \geq 0}$ is a polyhedral cone in $R^{n + 1}$ . A polyhedral cone ${z : C z \leq 0}$ is finitely generated: this is Weyl's direction of the duality, proved by Fourier-Motzkin elimination, which successively projects out coordinates from the inequality system, each projection producing finitely many new inequalities, terminating in a finite generating set of extreme rays. Equivalently, the polar of the polyhedral cone $\tilde{K}$ is the finitely generated cone $cone {rows of C}$ , which is closed by the first half; the bipolar theorem then exhibits $\tilde{K} = (\tilde{K}^{\circ})^{\circ}$ as the polar of a finitely generated cone, and the first half shows such a polar is finitely generated. Generators of $\tilde{K}$ with last coordinate $μ = 1$ give the points $v_{j}$ ; generators with $μ = 0$ give the recession directions $r_{k}$ . Hence $P = conv {v_{j}} + cone {r_{k}}$ . $□$

Bridge. This theorem builds toward the existence theory of linear and convex programming and appears again in every statement that an optimal solution is attained at a vertex. This is exactly the structural dictionary — recession directions detect unboundedness, and a polyhedron is simultaneously a finite system of constraints and a finite list of generators — on which linear-programming duality and the simplex method rest. The recession cone $0^{+} C$ generalises the lineality and asymptotic behaviour that part (ii) converts into a coercivity test, and the Minkowski-Weyl equivalence is dual to itself under polarity: the H-description of $P$ is the V-description of its polar cone, so finite generation and finite constraint are two readings of one closed cone. The foundational reason an LP with a finite optimum attains it at a vertex is that the recession cone forbids escape to infinity along any improving ray, leaving a compact face on which the linear objective is minimised. Putting these together, the boundedness criterion and the Minkowski-Weyl theorem certify both that a minimiser exists and where — at a generator — and the bridge is the homogenisation that turns a polyhedron into a cone, where Carathéodory's conic bound from 44.01.02 does the finite-generation work.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Prove Minkowski's theorem on extreme points: a non-empty compact convex set $C \subseteq R^{n}$ is the convex hull of its extreme points, $C = conv (ext C)$ .

Hint

Induct on $dim C$ . A boundary point lies in a proper face (lower dimension) supported by a hyperplane; an interior point is a midpoint of two boundary points.

Answer

Induct on $k = dim C$ . For $k = 0$ , $C$ is a point, its own unique extreme point. Assume the result for dimension $< k$ . Let $x \in C$ . If $x \in ri C$ (relative interior, 44.01.02), any line through $x$ in $aff C$ meets the relative boundary in two points $u, w$ (compactness), and $x \in conv {u, w}$ ; so it suffices to handle relative-boundary points. If $x$ is on the relative boundary, a supporting hyperplane $H$ at $x$ gives a face $F = C \cap H$ with $dim F < k$ ; $F$ is compact convex, so by induction $x \in conv (ext F)$ . Every extreme point of the face $F$ is extreme in $C$ (a face of a face is a face). Hence $x \in conv (ext C)$ in either case, giving $C \subseteq conv (ext C)$ ; the reverse inclusion is immediate since $ext C \subseteq C$ and $C$ is convex. $□$

Exercise 8 (hard, symbolic).

Prove that a polyhedron $P = {x : A x \leq b}$ has at least one vertex if and only if it contains no line (its lineality space $0^{+} P \cap (- 0^{+} P)$ is ${0}$ ), and that in that case a linear function bounded below on $P$ attains its minimum at a vertex.

Hint

A vertex is a point where $n$ linearly independent active constraint normals meet; a contained line means a direction $d$ with $A d = 0$ , blocking full rank. For attainment, descend along edges.

Answer

A point $x \in P$ is a vertex iff the active rows ${a_{i} : ⟨ a_{i}, x ⟩ = b_{i}}$ span $R^{n}$ (rank $n$ ), since extremality forbids any direction $d \neq = 0$ with $⟨ a_{i}, d ⟩ = 0$ for all active $i$ . If $P$ contains a line with direction $d \neq = 0$ , then $A d = 0$ , so no set of active normals can have rank $n$ and there is no vertex. Conversely if $P$ has no line, the lineality ${d : A d = 0, - A d = 0} = {d : A d = 0} \cap 0^{+} P$ reduces and one can move from any point along the recession-free directions until $n$ independent constraints are active, producing a vertex. For attainment: let $c^{⊤} x$ be bounded below on $P$ . If $x_{0} \in P$ is not a vertex, there is a direction $d$ with $x_{0} \pm ϵ d \in P$ ; choosing the sign with $c^{⊤} d \leq 0$ and moving until a new constraint activates does not increase the objective and raises the active rank. Iterating reaches a vertex with objective $\leq c^{⊤} x_{0}$ ; the minimum over the finitely many vertices is attained. $□$

Advanced results Master

The recession cone of a level set and the Helly-type stability of intersections

For a proper closed convex $f$ , every non-empty sublevel set ${x : f (x) \leq α}$ has the same recession cone ${d : (f 0^{+}) (d) \leq 0}$ , independent of $α$ ^{[Rockafellar §8]}. This $α$ -independence is the analytic engine behind the existence theorem of the Key theorem section: coercivity is the single condition $(f 0^{+}) (d) > 0$ for $d \neq = 0$ , and it makes every level set compact at once. For a family of closed convex sets $C_{1}, \dots, C_{m}$ with a common point, the recession cone of the intersection satisfies $0^{+} (⋂_{i} C_{i}) = ⋂_{i} 0^{+} C_{i}$ , so the intersection is bounded as soon as the recession cones meet only at the origin — the recession-cone calculus reduces a boundedness question about an intersection to a homogeneous question about cones, which for polyhedra is a finite linear feasibility problem.

Decomposition: the Motzkin theorem and the lineality split

Every closed convex set $C$ with a vertex decomposes as $C = conv (ext C) + 0^{+} C$ when $C$ is line-free, and in full generality $C = (C \cap L^{⊥}) + L$ where $L = 0^{+} C \cap (- 0^{+} C)$ is the lineality space ^{[Rockafellar §18]}. For polyhedra this is Motzkin's decomposition theorem: every polyhedron is the Minkowski sum of a polytope (the convex hull of its vertices, after factoring out lineality) and its recession cone. The polytope-plus-cone splitting is the precise sense in which the bounded and unbounded parts of a polyhedron separate, and it is the structural input to the simplex method's distinction between optimal vertices and unbounded improving rays.

Faces, the face lattice, and dimensionality

The faces of a polyhedron $P = {x : A x \leq b}$ are exactly the sets $F_{I} = {x \in P : ⟨ a_{i}, x ⟩ = b_{i} \forall i \in I}$ for index subsets $I$ , and they form a finite lattice under inclusion with $\emptyset$ and $P$ as bounding elements ^{[Schrijver §8]}. The dimension of $F_{I}$ is $n$ minus the rank of ${a_{i} : i \in I}$ together with the implicit equalities, so vertices are the $0$ -dimensional faces (rank $n$ ), edges the $1$ -dimensional faces, and facets the $(n - 1)$ -dimensional faces. The minimal non-empty faces are translates of the lineality space; when $P$ is line-free they are the vertices, recovering the vertex-attainment principle. The face lattice is the combinatorial skeleton on which polyhedral algorithms — vertex enumeration, the simplex pivot, and the double-description method — operate.

Polyhedral functions and closure under the basic operations

A convex function is polyhedral if its epigraph is a polyhedron; equivalently it is a maximum of finitely many affine functions plus the indicator of a polyhedron ^{[Rockafellar §19]}. The class of polyhedra is closed under intersection, finite Minkowski sum, linear images and preimages, and polarity, and correspondingly polyhedral convex functions are closed under finite sums, pointwise maxima, infimal convolution, and Legendre-Fenchel conjugacy — the conjugate of a polyhedral function is polyhedral. This closure is what makes linear programming self-dual: the value function of an LP is polyhedral, its conjugate is the dual LP's value function, and Minkowski-Weyl guarantees both live in the same finitely-described class.

Synthesis. The recession cone and the Minkowski-Weyl theorem are exactly the two halves of the finite-dimensional structure theory that the existence and attainment results of optimisation consume: the recession cone certifies that an optimum exists by ruling out escape to infinity, and the polytope-plus-cone decomposition certifies where it lives — at a generator. The central insight is that homogenisation converts a polyhedron into a closed convex cone, so that finite generation and finite constraint, the V- and H-descriptions, become two readings of the same cone under polarity, and the conic Carathéodory bound from 44.01.02 supplies the finiteness. The foundational reason an LP attains its value at a vertex is that the recession cone forbids improving rays, leaving a compact bounded part whose extreme points are the vertices; putting these together with Motzkin's decomposition $C = conv (ext C) + 0^{+} C$ , the bounded and unbounded structure separate cleanly. The recession-function calculus generalises the boundedness criterion from sets to functions and is dual to the polarity that exchanges H- and V-descriptions; the closure of the polyhedral class under conjugacy is exactly the self-duality of linear programming, and this is exactly why Farkas' lemma, LP duality, and the simplex method all rest on one finite-generation theorem. The bridge is Fourier-Motzkin elimination, the constructive engine that turns a halfspace description into a generator list, and which appears again in quantifier elimination for the first-order theory of the reals and in the projection steps of polyhedral computation.

Full proof set Master

Proposition 1 (recession cone of a polyhedron). For $P = {x : A x \leq b}$ non-empty, $0^{+} P = {d : A d \leq 0}$ .

Proof. Let $d \in 0^{+} P$ and fix $x \in P$ . Then $A (x + t d) = A x + t A d \leq b$ for all $t \geq 0$ . For each row $i$ , $(A x)_{i} + t (A d)_{i} \leq b_{i}$ for all $t \geq 0$ forces $(A d)_{i} \leq 0$ (otherwise the left side $\to + \infty$ ). Conversely if $A d \leq 0$ and $x \in P$ , then for every $t \geq 0$ , $A (x + t d) = A x + t A d \leq A x \leq b$ , so $x + t d \in P$ , i.e. $d \in 0^{+} P$ . $□$

Proposition 2 (boundedness criterion). A non-empty closed convex $C \subseteq R^{n}$ is bounded iff $0^{+} C = {0}$ .

Proof. Boundedness gives $0^{+} C = {0}$ because a nonzero recession direction produces an unbounded ray inside $C$ . For the converse, suppose $C$ is unbounded; choose $x_{0} \in C$ and $x_{k} \in C$ with $ρ_{k} := ∥ x_{k} - x_{0} ∥ \to \infty$ , and set $d_{k} = (x_{k} - x_{0}) / ρ_{k}$ . By compactness of the unit sphere, pass to a subsequence with $d_{k} \to d$ , $∥ d ∥ = 1$ . Fix $t \geq 0$ ; for $k$ with $ρ_{k} \geq t$ , the point $x_{0} + t d_{k} = (1 - t / ρ_{k}) x_{0} + (t / ρ_{k}) x_{k}$ is a convex combination of $x_{0}, x_{k} \in C$ , hence in $C$ . Taking $k \to \infty$ and using closedness, $x_{0} + t d \in C$ . As $t \geq 0$ was arbitrary, $d \in 0^{+} C ∖ {0}$ . $□$

Proposition 3 (finitely generated cones are closed). If $K = cone {r_{1}, \dots, r_{q}} = {\sum_{k} λ_{k} r_{k} : λ_{k} \geq 0}$ , then $K$ is closed.

Proof. By the conic Carathéodory theorem 44.01.02, every element of $K$ is a non-negative combination of a linearly independent subset of the generators. There are finitely many such subsets $S \subseteq {r_{1}, \dots, r_{q}}$ ; for each, $cone (S) = {\sum_{r \in S} λ_{r} r : λ_{r} \geq 0}$ is the image of the closed orthant $R_{\geq 0}^{∣ S ∣}$ under the injective linear map sending the coordinate basis to $S$ . An injective linear map on a finite-dimensional space is a homeomorphism onto its (closed) image, and the orthant is closed, so $cone (S)$ is closed. Thus $K = ⋃_{S} cone (S)$ is a finite union of closed sets, hence closed. $□$

Proposition 4 (Minkowski-Weyl via polarity). A cone $K \subseteq R^{n}$ is polyhedral ( $K = {x : C x \leq 0}$ ) iff it is finitely generated.

Proof. (Finitely generated $\Rightarrow$ polyhedral.) By Proposition 3, $K = cone {r_{k}}$ is a closed convex cone, so the bipolar theorem gives $K = K^{\circ\circ}$ . The polar $K^{\circ} = {y : ⟨ y, r_{k} ⟩ \leq 0 \forall k}$ is a polyhedral cone (finitely many homogeneous inequalities), hence by the converse direction (below) finitely generated, say $K^{\circ} = cone {s_{j}}$ . Then $K = K^{\circ\circ} = {x : ⟨ s_{j}, x ⟩ \leq 0 \forall j}$ is polyhedral. (Polyhedral $\Rightarrow$ finitely generated.) For $K = {x : C x \leq 0}$ , apply Fourier-Motzkin elimination to the homogeneous system: introduce $K$ as the solution set and project out the variables one at a time. Eliminating a variable $x_{n}$ replaces each pair (a constraint with positive $x_{n}$ -coefficient, a constraint with negative coefficient) by their non-negative combination clearing $x_{n}$ , yielding a new finite homogeneous system in $x_{1}, \dots, x_{n - 1}$ describing the projection. The projection of a polyhedral cone is polyhedral, and tracking the eliminations back produces a finite set of extreme rays generating $K$ ; equivalently, $K^{\circ} = cone {rows of C}$ is finitely generated, closed by Proposition 3, so $K = K^{\circ\circ}$ is the polar of a finitely generated cone, which the first half shows is finitely generated. The lift-and-slice argument of the Key theorem upgrades the cone statement to general polyhedra and finitely generated sets. $□$

Connections Master

The conic Carathéodory bound and the relative-interior calculus of 44.01.02 are the finite-generation and interior engines this unit runs on: closedness of a finitely generated cone (Proposition 3) is a direct application of the conic Carathéodory theorem, and the relative interior controls which faces of a polyhedron are non-empty. The basic convex-set vocabulary, hulls, and convexity-preserving operations of 44.01.01, co-developed in this spine, are the substrate on which the recession-cone and Minkowski-sum constructions are built.
The affine-subspace and hyperplane machinery of 01.01.18 supplies the H-description of a polyhedron: each defining constraint is a halfspace bounded by a hyperplane, and the dimension of a face is computed from the rank of its active constraint normals, an affine-rank count in the sense of that unit. The lineality space of a polyhedron is the affine subspace along which it is translation-invariant.
Farkas' lemma and the theorems of the alternative (44.02.04, registered as a catalog stub for this spine) are the dual face of the Minkowski-Weyl theorem: the closedness of a finitely generated cone proved here is exactly the hypothesis that lets the second separation theorem strictly separate a point from a cone, and the H-V equivalence is the structural backbone of linear-programming duality and the simplex method's vertex-attainment guarantee.

Historical & philosophical context Master

Hermann Minkowski, in Geometrie der Zahlen ^{[Minkowski 1896]} (Teubner, 1896), established the representation of convex bodies and polyhedral cones by their extreme points and extreme rays, introducing the systematic study of convex sets in $R^{n}$ that underlies the modern theory; the theorem that a compact convex set is the convex hull of its extreme points carries his name. Hermann Weyl, in Elementare Theorie der konvexen Polyeder ^{[Weyl 1934]} (Commentarii Mathematici Helvetici 7, 290-306), proved the converse direction — that an intersection of finitely many halfspaces is finitely generated — giving the two halves their joint name. The constructive elimination procedure that powers Weyl's direction was given by Fourier (1827) for inequalities and rediscovered and analysed by Theodore Motzkin in his 1936 dissertation, where the polytope-plus-cone decomposition of a polyhedron also appears.

The synthesis into the modern theory is due to R. Tyrrell Rockafellar, whose Convex Analysis ^{[Rockafellar §8, §18-§19]} (Princeton, 1970) organised recession cones, recession functions, polyhedral convexity, and the existence theory of minimisers into a single framework, and to Alexander Schrijver, whose Theory of Linear and Integer Programming ^{[Schrijver §7-§8]} (Wiley, 1986) gave the algorithmic and integer-programming account, including the complexity of the Minkowski-Weyl conversion and the fundamental theorem of linear inequalities.

Bibliography Master

@book{minkowski1896geometrie,
  author    = {Minkowski, Hermann},
  title     = {Geometrie der Zahlen},
  publisher = {Teubner},
  address   = {Leipzig},
  year      = {1896}
}

@article{weyl1934elementare,
  author  = {Weyl, Hermann},
  title   = {Elementare Theorie der konvexen Polyeder},
  journal = {Commentarii Mathematici Helvetici},
  volume  = {7},
  pages   = {290--306},
  year    = {1934}
}

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

@book{schrijver1986theory,
  author    = {Schrijver, Alexander},
  title     = {Theory of Linear and Integer Programming},
  series    = {Wiley-Interscience Series in Discrete Mathematics and Optimization},
  publisher = {Wiley},
  year      = {1986}
}

@book{ziegler1995lectures,
  author    = {Ziegler, G\"unter M.},
  title     = {Lectures on Polytopes},
  series    = {Graduate Texts in Mathematics},
  number    = {152},
  publisher = {Springer},
  year      = {1995}
}

@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

44.01.01
44.01.02
01.01.18

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2.1, §2.4-§2.5; Rockafellar 1970 Convex Analysis (Princeton) §8 — the picture of a set's directions of unbounded escape
intermediate: Rockafellar 1970 Convex Analysis (Princeton) §8, §18-§19; Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7-§8
master: Rockafellar 1970 Convex Analysis (Princeton) §8, §17-§19, §27; Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7-§8; Ziegler 1995 Lectures on Polytopes (Springer) Ch. 1

References

Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §8 recession cones and unboundedness; §17 the dimension of convex sets; §18 polyhedral convexity and faces; §19 polyhedral convex functions; §27 the recession/existence-of-minimisers theory
Schrijver, A. — Theory of Linear and Integer Programming (Wiley, 1986) · §7 fundamental theorem of linear inequalities; §8 the structure of polyhedra, Minkowski-Weyl, vertices and minimal faces
Weyl, H. — Elementare Theorie der konvexen Polyeder · Commentarii Mathematici Helvetici 7 (1934), 290-306
Minkowski, H. — Geometrie der Zahlen · (Teubner, 1896), §19 — the representation of polyhedral cones by extreme rays
Ziegler, G. M. — Lectures on Polytopes (Springer, 1995) · Ch. 1 the Minkowski-Weyl theorem (V- and H-representations); §2.2 faces and the face lattice

Estimated time

beginner: 16m
intermediate: 44m
master: 74m