Rockafellar, §8: Recession Cones and Unboundedness #
The directions in which an unbounded convex set recedes, and the recession function of a convex function. All 18 numbered results of §8 are formalized.
The section's definitions are recorded alongside: 0⁺C (recessionCone), the lineality space and
lineality of a set, f0⁺ (recessionFn), and the recession cone, constancy space and lineality
space of a function.
Rockafellar's direction is an equivalence class of closed half-lines under translation, a
quotient he never formally types. None is introduced here: every statement about "the direction of
y" is a statement about the vector y that is invariant under y ↦ λ y for λ > 0, and 0⁺C
is a cone precisely because of that invariance.
Two overloads to watch #
f0⁺ deliberately overloads §5's right scalar multiplication fλ. Here f0⁺ is
recessionFn f and fλ is smulRight f λ, and corollary_8_5_2 is the bridge: for a closed
proper convex f the value (f0⁺) y really is the limit of (fλ) y as λ ↓ 0.
The "recession cone of f" is neither 0⁺(dom f) nor 0⁺(epi f), as the book itself warns.
It is recessionConeFn f = {y | (f0⁺) y ≤ 0}: the horizontal slice {y | (y, 0) ∈ 0⁺(epi f)} of
the epigraph's recession cone (recessionConeFn_eq_slice), and a subset of 0⁺(dom f) that is
properly smaller in general — for f x = ⟪a, x⟫ with a ≠ 0 one has 0⁺(dom f) = ℝⁿ while
recessionConeFn f is a closed half-space.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §8.
The recession cone of a convex set #
Rockafellar: C recedes in the direction of y ≠ 0 when x + λ y ∈ C for every λ ≥ 0 and
every x ∈ C; the set of all such y, including y = 0, is the recession cone 0⁺C.
Rockafellar's 0⁺C. y ∈ 0⁺C exactly when every half-line {x + λ y | λ ≥ 0} issuing
from a point of C stays in C. This is the backbone's recessionCone verbatim; the surface
records the unfolding so that alignment with the book's sentence can be read off the file.
Theorem 8.1 #
Theorem 8.1, first assertion. The recession cone 0⁺C of a non-empty convex set is a
convex cone containing the origin — three claims, since IsCone is §2's, closed under positive
scaling only. Neither convexity nor non-emptiness of C is used.
Theorem 8.1, second assertion: 0⁺C = {y | C + y ⊆ C}. The book's standing non-emptiness
is not needed, but convexity is: it is what lets the condition be tested at λ = 1 alone.
Theorem 8.2 #
Theorem 8.2, first assertion: the recession cone of a closed convex set is closed. Neither
convexity nor non-emptiness is needed; closedness of C is essential — the book's C₄ is a convex
set whose recession cone is C₄ itself, which is not closed.
Theorem 8.2, second assertion: for non-empty closed convex C, 0⁺C is the set of limits
of sequences λᵢ xᵢ with xᵢ ∈ C and λᵢ ↓ 0. "λᵢ ↓ 0" is read as λᵢ > 0 with λᵢ → 0;
monotonicity is not used in the book's argument either.
Theorem 8.2, third assertion: for K the convex cone in ℝⁿ⁺¹ generated by
{(1, x) | x ∈ C}, cl K = K ∪ {(0, x) | x ∈ 0⁺C}.
This is the homogenisation picture: a point of ℝⁿ is the ray through (1, x), a direction is a
ray through (0, y) with y ≠ 0, and the directions adjoined to K in the limit are exactly those
in which C recedes. ℝⁿ⁺¹ is ℝ × Rn n, the homogenising coordinate first as in the book's
(λ, x).
Theorem 8.3 and its corollaries #
Theorem 8.3, first assertion: for closed convex C, if one half-line {x + λ y | λ ≥ 0}
lies in C then y ∈ 0⁺C, so every such half-line does. The book's y ≠ 0 is not needed — it is
its convention that the zero vector has no direction — nor is non-emptiness. Closedness is
essential: the book's C₄ contains a half-line in direction (1, 0) without receding in it.
Theorem 8.3, second assertion: under the same hypotheses {x + λ y | λ ≥ 0} ⊆ ri C for
each x ∈ ri C, so y ∈ 0⁺(ri C). Finite dimension enters here, through Theorem 6.2.
Corollary 8.3.1: for any non-empty convex set C, 0⁺(ri C) = 0⁺(cl C).
Non-emptiness is not needed. The inclusion 0⁺C ⊆ 0⁺(ri C) can be proper when C is not
closed: the book's C₄ has 0⁺(ri C₄) the closed first quadrant while 0⁺C₄ = C₄.
Corollary 8.3.1, second assertion: for x ∈ ri C, y ∈ 0⁺(cl C) iff x + λ y ∈ C for
every λ > 0.
Corollary 8.3.2: if C is a closed convex set containing the origin, then
0⁺C = ⋂_{ε > 0} ε C.
Corollary 8.3.2, in the book's first spelling:
0⁺C = {y | ε⁻¹ y ∈ C for every ε > 0}.
Corollary 8.3.3: if {Cᵢ | i ∈ I} is an arbitrary collection of closed convex
sets in ℝⁿ whose intersection is not empty, then 0⁺(⋂ᵢ Cᵢ) = ⋂ᵢ 0⁺Cᵢ.
Corollary 8.3.4: let A be a linear transformation from ℝⁿ to ℝᵐ and let C be a
closed convex set in ℝᵐ with A⁻¹C ≠ ∅. Then 0⁺(A⁻¹C) = A⁻¹(0⁺C). Continuity of A is not
used: Theorem 8.3 is applied to C, not to A⁻¹C.
Theorem 8.4: unboundedness #
Theorem 8.4. A non-empty closed convex set is bounded iff 0⁺C = {0}. The one place in
§8 where finite dimension is genuinely used on the set side.
Corollary 8.4.1. For closed convex C and an affine M with M ∩ C non-empty and
bounded, M' ∩ C is bounded for every affine M' parallel to M. "Parallel" is
M.direction = M'.direction, the book's own definition.
Lineality space, lineality and rank of a convex set #
Unnumbered.
Rockafellar's lineality space of C, (-0⁺C) ∩ 0⁺C: the zero vector together with the
y ≠ 0 such that, for every x ∈ C, the whole line through x in the direction of y lies in
C.
Rockafellar's "elementary exercise": the lineality space of a convex C
is the set of vectors y such that C + y = C.
Theorem 2.7 applied to 0⁺C: the lineality space of C is a subspace,
the largest subspace contained in the convex cone 0⁺C. Its dimension is the lineality of C,
lineality C.
The direct-sum decomposition: a convex set with lineality space L splits as
C = L + (C ∩ L^⊥). Any complement of L would do; the orthogonal one is the only place §8 would
need an inner product.
Examples of recession cones #
The recession cone of a non-empty affine set M is the subspace L parallel to M.
If C = {x | ⟪x, bᵢ⟫ ≥ βᵢ for all i} is non-empty, then 0⁺C is the solution set of the
corresponding homogeneous system.
The lineality space of such a C is the solution set of the equations
⟪x, bᵢ⟫ = 0, ∀ i ∈ I.
The recession function f0⁺ #
Let f be a convex function on ℝⁿ not identically +∞. Then
0⁺(epi f) is itself an epigraph, and the function it is the epigraph of is f0⁺.
The defining property of f0⁺: epi (f0⁺) = 0⁺(epi f). No hypothesis at all — the
recession cone of an epigraph is an epigraph for every f, so the book's "not identically +∞"
is only needed to make the interpretation interesting, never the identity.
Rockafellar's displayed characterisation: (y, ν) ∈ 0⁺(epi f) if and only
if f (x + λ y) ≤ f x + λ ν for every x and every λ ≥ 0.
Theorem 8.1 transported to epigraphs: for a convex f the
displayed inequality holds for every x and every λ ≥ 0 as soon as it holds for every x with
λ = 1.
Theorem 8.5 #
Theorem 8.5, first assertion: the recession function of a proper convex function is
positively homogeneous. It needs no hypothesis: 0⁺(λ C) = λ 0⁺C for λ > 0.
Theorem 8.5, first assertion continued: f0⁺ is convex. Again no hypothesis is needed,
since 0⁺ of any set is convex.
Theorem 8.5, first assertion continued: f0⁺ is proper when f is.
Properness of f is exactly what is needed: (f0⁺) 0 = 0 puts 0 in dom (f0⁺), and the book's
parenthetical "note that (f0⁺)(y) cannot be -∞" is recessionFn_ne_bot.
Theorem 8.5, the difference formula: (f0⁺)(y) = sup {f (x + y) - f x | x ∈ dom f}.
The ∞ - ∞ hazard is disarmed by the hypotheses, not by a convention. Mathlib totalises EReal
subtraction with ⊤ - ⊤ = ⊥, where the book leaves it undefined; here the junk value is never
consulted, since the supremum runs over x ∈ dom f and properness makes f x real.
Theorem 8.5, third assertion: if f is closed, f0⁺ is closed too.
Theorem 8.5, the difference-quotient formula: for closed proper convex f and any
x ∈ dom f, (f0⁺)(y) = sup_{λ > 0} [f (x + λ y) - f x] / λ. Closedness is what makes the answer
independent of x.
Theorem 8.5, limit form: (f0⁺)(y) = lim_{λ → ∞} [f (x + λ y) - f x] / λ. The supremum
is a limit because the difference quotient is nondecreasing in λ.
Corollary 8.5.1: for a proper convex f, f0⁺ is the least of the functions
h such that f z ≤ f x + h (z - x) for all z and all x.
Corollary 8.5.2. For closed proper convex f and y ∈ dom f,
(f0⁺)(y) = lim_{λ ↓ 0} (fλ)(y). This is what licenses the overload of f0⁺ with §5's right
scalar multiplication fλ: the notation names a limit that really exists.
Corollary 8.5.2, second assertion: if 0 ∈ dom f the formula holds for every
y ∈ ℝⁿ, with no condition on y.
Theorem 8.6 and its corollaries #
Theorem 8.6, first assertion: for convex f, if liminf_{λ → +∞} f (x + λ y) < +∞ for
one x, then f (x + λ y) is nonincreasing in λ on all of ℝ. Stated without the properness
the book assumes.
Theorem 8.6, second assertion: the property holds for every x if and only if
(f0⁺)(y) ≤ 0. It needs no hypothesis on f at all.
Theorem 8.6, third assertion: when f is closed, the property holds for every x as soon
as it holds for one x ∈ dom f.
Corollary 8.6.1. f (x + λ y) is constant in λ for every x iff (f0⁺)(y) ≤ 0 and
(f0⁺)(-y) ≤ 0. Stated without the properness and convexity the book assumes.
Corollary 8.6.1, second assertion: when f is closed, the condition holds as soon as
there is one x and one real α with f (x + λ y) ≤ α for every λ ∈ ℝ.
Corollary 8.6.2. A convex function is constant on any affine set where it is bounded above. Stated without the book's finiteness hypothesis, which the proof does not use.
The recession cone, constancy space and lineality space of a function #
The recession cone of f: the set of y with (f0⁺)(y) ≤ 0, a convex cone containing
0 and closed when f is. Not to be confused with 0⁺(epi f), as the book warns:
recessionConeFn_eq_slice gives the relation, the horizontal slice at height 0.
The recession cone of f is not 0⁺(dom f) either, only contained in it: if f does not
increase along y then dom f recedes in the direction y, but not conversely. The inclusion is
proper already for a nonzero linear functional f x = ⟪a, x⟫, where dom f = ℝⁿ and so
0⁺(dom f) = ℝⁿ, while the recession cone of f is the half-space {y | ⟪a, y⟫ ≤ 0}.
The recession cone of f is a convex cone containing the origin, in §2's vocabulary.
The recession cone of a closed function is closed.
Rockafellar's constancy space of f: the y with (f0⁺)(y) ≤ 0 and
(f0⁺)(-y) ≤ 0, which by Corollary 8.6.1 are the directions in which f is constant.
Theorem 2.7 applied to the recession cone of f: the constancy space is
the largest subspace contained in the recession cone of f.
Theorem 8.7 #
Theorem 8.7, first assertion: for a closed proper convex f, all the non-empty level
sets {x | f x ≤ α} have the same recession cone, namely that of f.
Theorem 8.7, second assertion: those level sets also all have the same
lineality space, namely the constancy space of f.
Corollary 8.7.1. For closed proper convex f, if one level set {x | f x ≤ α} is
non-empty and bounded then all of them are. The only place finite dimension enters on the function
side of §8.
Theorem 8.8 #
Theorem 8.8, (a) ⟺ (b): f (x + λ y) = f x + λ ν for every x and every λ ∈ ℝ iff
(y, ν) lies in the lineality space of epi f. Stated without the properness and convexity the
book assumes.
Theorem 8.8, (b) ⟺ (c), where (c) is -(f0⁺)(-y) = (f0⁺)(y) = ν. Properness is what
upgrades the two recession inequalities to equalities.
Theorem 8.8, the equivalence (a) ⟺ (c).
Specialises forall_eq_add_iff_recessionFn, composed with the change of spelling of
theorem_8_8_b_iff_c.
Theorem 8.8, last assertion: when f is closed, y satisfies the three conditions with
ν = (f0⁺)(y) as soon as f (x + λ y) is affine in λ for one x ∈ dom f.
Rockafellar's lineality space of f: the y with
(f0⁺)(-y) = -(f0⁺)(y). Theorem 8.8 identifies it with the image of the lineality space of
epi f under the projection (y, ν) ↦ y; its dimension is the lineality of f, linealityFn.
The lineality space of f is a subspace of ℝⁿ. Its proof is Theorem 8.8.
Examples of recession functions #
The recession function of an indicator is the indicator of the recession cone, so that "the
rank of a convex set coincides with the rank of its indicator function" has a
meaning. Non-emptiness of C is needed: for C = ∅ the left side is the constant -∞.
f0⁺ = δ(· | 0) for a proper convex function with bounded effective domain. No convexity
or closedness is needed: if (f0⁺)(y) < +∞ then dom f recedes in direction y, and a bounded
non-empty dom f recedes in no direction but 0.