Rockafellar, §6: Relative Interiors of Convex Sets #
Relative interiors and closures of convex sets: the line segment principle, the fact that a
non-empty convex set has a non-empty relative interior, and how ri and cl behave under
intersection, linear images and inverse images, products, and convex hulls of unions. All 18
numbered results of §6 are formalized.
The book's cl C is Mathlib's closure C, its int C is interior C, and its ri C is the
backbone's ri, that is intrinsicInterior ℝ.
Main definitions #
relbd C— the relative boundary(cl C) \ (ri C), bridged to Mathlib'sintrinsicFrontier ℝbyrelbd_eq_intrinsicFrontier.IsRelativelyOpen C— the book's relatively open:ri C = C.coneOver C— the convex cone of Corollary 6.8.1, generated by{(1, x) | x ∈ C}.
Theorem 6.2 is where finite-dimensionality enters, and it never leaves. That a non-empty
convex set has a non-empty relative interior is false in infinite dimensions — the positive cone
of ℓ² is the standard witness — and §§7, 9, 10, 11, 16, 18 and 20 use it without saying so.
Every statement below inherits FiniteDimensional ℝ (Rn n) from the ambient instance, so none of
them carries a dimension hypothesis of its own, which is what makes the dependence easy to miss.
theorem_6_9 is the two-set case, where the book states the result for m sets. ℝᵐ⁺ᵖ is
Rn m × Rn p here, as in §3, so Theorem 6.8 is stated on the product and Corollary 6.8.1 on
ℝ × ℝⁿ. Theorems 6.6 and 6.7 take a LinearMap, where the book remarks that affine
transformations work too. theorem_6_5_ri adds Finite ι to the book's arbitrary index set: the
intersection of ri [0, 1 + α] over all α > 0 is the book's own counterexample to dropping it.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §6.
The relative interior, the relative boundary and relatively open sets #
Rockafellar, §6 (p. 44). The relative boundary of C is (cl C) ∖ (ri C).
Equations
- Rockafellar.relbd C = closure C \ intrinsicInterior ℝ C
Instances For
The bridge: the book's relative boundary is Mathlib's intrinsicFrontier.
Membership in the relative boundary, spelled out.
Rockafellar, §6 (p. 44). C is relatively open when ri C = C.
Equations
- Rockafellar.IsRelativelyOpen C = (intrinsicInterior ℝ C = C)
Instances For
The bridge: relative openness is the equation ri C = C, by definition.
Rockafellar, §6 (p. 44). The sandwich ri C ⊆ C ⊆ cl C.
Rockafellar, §6 (p. 45). For an n-dimensional convex set aff C = ℝⁿ, and then
ri C = int C.
Rockafellar, §6 (p. 45). An affine set is relatively open.
Rockafellar, §6 (p. 45). Every affine set is closed. In the book this is read off from
Corollary 1.4.1 and Theorem 1.3; here it is the finite-dimensionality of ℝⁿ.
Rockafellar, §6 (p. 45). cl C ⊆ cl (aff C) = aff C, so a line through two points of
cl C lies in aff C.
Theorem 6.1: the line segment principle #
Theorem 6.1. Let C be a convex set in ℝⁿ, let x ∈ ri C and
y ∈ cl C. Then (1 - λ) x + λ y belongs to ri C (and hence in particular to C) for
0 ≤ λ < 1.
Theorem 6.2 #
Theorem 6.2. cl C is convex.
Theorem 6.2. ri C is convex. This is Theorem 6.1 with y taken in ri C.
Theorem 6.2. cl C has the same affine hull as C. No convexity is needed.
Theorem 6.2. ri C has the same affine hull as C.
Theorem 6.2. cl C has the same dimension as C.
Theorem 6.2. ri C has the same dimension as C.
Theorem 6.2, the parenthetical clause: ri C ≠ ∅ when C ≠ ∅. This is the single fact
that makes Part II finite-dimensional; it is false in infinite dimensions, and nothing weaker than
finite-dimensionality will do.
Theorem 6.3 and its corollaries #
Theorem 6.3. For any convex set C in ℝⁿ, cl (ri C) = cl C.
Theorem 6.3. For any convex set C in ℝⁿ, ri (cl C) = ri C.
Rockafellar, §6 (p. 46). ri (ri C) = ri C: the relative interior of a convex set is
relatively open. The book asserts this for arbitrary sets, before Theorem 6.3; the backbone proves
it for convex sets, through Theorem 6.3.
Corollary 6.3.1. Let C₁ and C₂ be convex sets in ℝⁿ. Then
cl C₁ = cl C₂ if and only if ri C₁ = ri C₂.
Corollary 6.3.2. If C is a convex set in ℝⁿ, then every open set which
meets cl C also meets ri C.
A non-empty convex set inside cl C₂ whose affine hull is that of C₂ already meets
ri C₂: a relative interior point of C₁ has a ball of aff C₁ = aff C₂ around it inside C₁,
and cl C₂ = cl (ri C₂) puts a point of ri C₂ in that ball. The step Corollary 6.3.3 needs.
Theorem 6.4: the prolongation criterion #
Theorem 6.4. Let C be a non-empty convex set in ℝⁿ. Then z ∈ ri C if and
only if, for every x ∈ C, there exists a μ > 1 such that (1 - μ) x + μ z belongs to C.
Corollary 6.4.1. Let C be a convex set in ℝⁿ. Then z ∈ int C if and only
if, for every y ∈ ℝⁿ, there exists some ε > 0 such that z + ε y ∈ C.
Theorem 6.5: intersections #
Theorem 6.5, the closure formula. Let Cᵢ be a convex set in ℝⁿ for
i ∈ I. Suppose that the sets ri Cᵢ have at least one point in common. Then
cl ⋂ᵢ Cᵢ = ⋂ᵢ cl Cᵢ. The index set is arbitrary.
Theorem 6.5, the relative interior formula: if in addition I is finite,
ri ⋂ᵢ Cᵢ = ⋂ᵢ ri Cᵢ. Finiteness cannot be dropped — the book's own counterexample is the family
[0, 1 + α] for α > 0.
Corollary 6.5.1. Let C be a convex set, and let M be an affine set (such
as a line or a hyperplane) which contains a point of ri C. Then ri (M ∩ C) = M ∩ ri C.
Corollary 6.5.1, the closure half: cl (M ∩ C) = M ∩ cl C.
Corollary 6.5.2. For convex C₂ ⊆ cl C₁ not entirely contained in the relative boundary
of C₁, ri C₂ ⊆ ri C₁. The hypothesis is the positive reading (C₂ ∩ ri C₁).Nonempty of "not
entirely contained in the relative boundary".
Theorem 6.6: images under a linear transformation #
Theorem 6.6. Let C be a convex set in ℝⁿ, and let A be a linear
transformation from ℝⁿ to ℝᵐ. Then ri (AC) = A (ri C).
Theorem 6.6. cl (AC) ⊇ A (cl C). This is just continuity of A and needs
no convexity.
Corollary 6.6.1. For any convex set C and any real number λ,
ri (λ C) = λ (ri C).
Rockafellar, §6 (p. 49). The direct-sum formula the book calls "elementary":
ri (C₁ ⊕ C₂) = ri C₁ ⊕ ri C₂.
Rockafellar, §6 (p. 49). cl (C₁ ⊕ C₂) = cl C₁ ⊕ cl C₂.
Corollary 6.6.2. For any convex sets C₁ and C₂ in ℝⁿ,
ri (C₁ + C₂) = ri C₁ + ri C₂.
Corollary 6.6.2. cl (C₁ + C₂) ⊇ cl C₁ + cl C₂. No convexity is needed. Corollary 9.1.1
sharpens this to an equality.
Theorem 6.7: inverse images under a linear transformation #
Theorem 6.7. Let A be a linear transformation from ℝⁿ to ℝᵐ. Let C be
a convex set in ℝᵐ such that A⁻¹(ri C) ≠ ∅. Then ri (A⁻¹C) = A⁻¹(ri C).
Theorem 6.7. Under the same hypothesis, cl (A⁻¹C) = A⁻¹(cl C).
Theorem 6.8: slices of a convex set in a product #
Theorem 6.8. For convex C ⊆ ℝᵐ⁺ᵖ with slices C_y = {z | (y, z) ∈ C} and
D = {y | C_y ≠ ∅}, (y, z) ∈ ri C iff y ∈ ri D and z ∈ ri C_y.
Corollary 6.8.1. The convex cone K in ℝⁿ⁺¹ generated by
{(1, x) | x ∈ C}. Rockafellar's cones need not contain the origin, so K is the set of positive
multiples of the cross-section, and nothing more.
Instances For
The bridge: coneOver C is exactly the set of positive multiples of {(1, x) | x ∈ C}, which
is what Corollary 2.6.3 identifies as the smallest convex cone containing that set.
Corollary 6.8.1. For non-empty convex C and K the convex cone in ℝⁿ⁺¹ generated by
{(1, x) | x ∈ C}, ri K is the set of (λ, x) with λ > 0 and x ∈ λ (ri C).
Theorem 6.9 #
Theorem 6.9, for two sets. For non-empty convex C₁, C₂ and C₀ = conv (C₁ ∪ C₂),
ri C₀ = ⋃ {λ₁ ri C₁ + λ₂ ri C₂ | λᵢ > 0, λ₁ + λ₂ = 1}, the union written in the parametrised
form λ₁ = 1 - a, λ₂ = a with a ∈ (0, 1). The book states the theorem for m sets.
The relatively open sets of §6 #
The book closes the section (p. 49) by noting that relative openness is preserved by the operations above, and that the relative interior and the closure of a convex cone are again convex cones.
Rockafellar, §6 (p. 49). The class of relatively open convex sets is preserved under finite intersections, provided the relative interiors meet — which for relatively open sets is just non-emptiness of the intersection.
Rockafellar, §6 (p. 49). The class of relatively open convex sets is preserved under addition.
Rockafellar, §6 (p. 50). The relative interior of a convex cone is a convex cone. This is
immediate from Corollary 6.6.1, because a convex set C is a cone exactly when λ C = C for every
λ > 0 (§2's isCone_iff_smul_set_eq).
Rockafellar, §6 (p. 50). The closure of a convex cone is a convex cone. Convexity is not used on either side.