Rockafellar, §9: Some Closedness Criteria #
Criteria, built on §8's recession cones, for an operation on convex sets or convex functions to preserve closedness. The section introduces no new concepts. All 18 numbered results of §9 are formalized.
Where the book states a result for C₁, …, Cₘ (or f₁, …, fₘ) — Corollaries 9.1.1, 9.1.3 and
9.2.1, Theorem 9.3, and Theorem 9.8 with its corollaries — what is stated here is the m = 2
instance.
The λ ≥ 0⁺ convention #
Rockafellar writes λ₁C₁ + ⋯ + λₘCₘ where each λᵢ ranges over the non-negative reals together
with a formal symbol 0⁺, and where 0⁺Cᵢ denotes the recession cone rather than the {0} that
plain 0 • Cᵢ would give. The same convention governs the infimum in Theorem 9.7, where f0⁺ is
the recession function.
That is a genuine extra symbol, not a limit, and it is modelled here as one: ExtCoeff is the
disjoint union of ℝ and a formal 0⁺, with ExtCoeff.smulSet acting on sets and
ExtCoeff.smulFn on functions, each carrying its bridge to the backbone
(ExtCoeff.smulSet_ofReal, ExtCoeff.smulSet_zeroPlus, and the two smulFn analogues). Every
theorem below reduces to the backbone form rather than unfolding the convention;
iUnion_extCoeff_pair is where that reduction has content, identifying Rockafellar's
⋃ {λ₁C₁ + λ₂C₂ | λᵢ ≥ 0⁺, λ₁ + λ₂ = 1} with conv (C₁ ∪ C₂) + (0⁺C₁ + 0⁺C₂).
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §9.
Rockafellar's extended coefficient λ ≥ 0⁺ #
λ ≥ 0⁺: a real coefficient is admitted when it is non-negative, and 0⁺ always is.
Equations
Instances For
λ > 0 or λ = 0⁺, the index set of the unions in Theorems 9.6 and 9.7.
Equations
Instances For
The numerical value of λ, with 0⁺ counting as 0. This is what λ₁ + ⋯ + λₘ = 1 means in
Theorem 9.8.
Equations
Instances For
λC in the λ ≥ 0⁺ convention: 0⁺C is the recession cone of C, not {0}.
Equations
Instances For
fλ in the λ ≥ 0⁺ convention: f0⁺ is the recession function of f, and for a real
λ it is §5's right scalar multiple fλ.
Equations
Instances For
The numerical value of 0⁺ is 0: this is what makes λ₁ + λ₂ = 1 exclude λ₁ = λ₂ = 0⁺.
Bridge: on an ordinary coefficient the convention is plain scalar multiplication of sets.
Bridge: 0⁺C is the backbone's recessionCone C.
Bridge: on an ordinary coefficient the convention is §5's fλ.
Bridge: f0⁺ is the backbone's recessionFn f.
Theorem 9.1 and its corollaries #
Theorem 9.1. Let C be a non-empty convex set in ℝⁿ and A a linear
transformation from ℝⁿ to ℝᵐ. Assume that every non-zero z ∈ 0⁺(cl C) with Az = 0 belongs
to the lineality space of cl C. Then cl (AC) = A (cl C). C need not be non-empty.
Theorem 9.1, second conclusion: 0⁺(A (cl C)) = A (0⁺(cl C)).
Theorem 9.1, the "in particular" clause: if C is closed and z = 0 is the only
z ∈ 0⁺C with Az = 0 — spelled 0⁺C ∩ ker A ⊆ {0} — then AC is closed.
Corollary 9.1.1 for m = 2. If the only way a direction of recession of
cl C₁ and one of cl C₂ can cancel is inside the two lineality spaces, then
cl (C₁ + C₂) = cl C₁ + cl C₂. The book states this for m sets.
Corollary 9.1.1, second conclusion:
0⁺(cl C₁ + cl C₂) = 0⁺(cl C₁) + 0⁺(cl C₂).
Corollary 9.1.1, the "in particular" clause: under the same hypothesis
C₁ + C₂ is closed when C₁ and C₂ are.
Corollary 9.1.2. Let C₁ and C₂ be non-empty closed convex sets in ℝⁿ
with no direction of recession of C₁ whose opposite is a direction of recession of C₂. Then
C₁ + C₂ is closed.
Corollary 9.1.2, second conclusion:
0⁺(C₁ + C₂) = 0⁺C₁ + 0⁺C₂.
Corollary 9.1.2, the parenthetical clause: the hypothesis holds in particular when one of the two sets is bounded.
Corollary 9.1.3 for m = 2. For convex cones the recession cone of the
closure is the closure itself, so Corollary 9.1.1's hypothesis becomes a hypothesis about
cl K₁ and cl K₂, and cl (K₁ + K₂) = cl K₁ + cl K₂.
Theorem 9.2 and its corollaries #
Theorem 9.2. Let h be a closed proper convex function on ℝⁿ and A a
linear transformation from ℝⁿ to ℝᵐ. Assume Az ≠ 0 for every z with (h0⁺)(z) ≤ 0 and
(h0⁺)(-z) > 0. Then Ah, where (Ah)(y) = inf {h x | A x = y}, is a closed proper convex
function.
The hypothesis is transported by mk_zero_mem_linealitySpace_epi_iff: "(h0⁺)(z) ≤ 0 and
(h0⁺)(-z) > 0 force Az ≠ 0" is the contrapositive of "(h0⁺)(z) ≤ 0 and Az = 0 force
z ∈ constancySpace h".
Theorem 9.2, last sentence: for each y with (Ah)(y) ≠ +∞ the infimum defining
(Ah)(y) is attained.
Corollary 9.2.1 for m = 2. Let f₁, f₂ be closed proper convex functions on
ℝⁿ such that z₁ + z₂ ≠ 0 for every pair of vectors with
(f₁0⁺)(z₁) + (f₂0⁺)(z₂) ≤ 0 and (f₁0⁺)(-z₁) + (f₂0⁺)(-z₂) > 0.
Then the infimal convolute f₁ □ f₂ is a closed proper convex function.
This is genuinely weaker in hypothesis than Corollary 9.2.2, which demands
(f₁0⁺)(z) + (f₂0⁺)(-z) > 0 for every z ≠ 0: here f₁ = f₂ = 0 is admitted, there not.
Corollary 9.2.1, last formula: (f₁ □ f₂)0⁺ = f₁0⁺ □ f₂0⁺.
Corollary 9.2.1, attainment: the infimum defining (f₁ □ f₂)(x) is attained for each
x.
Corollary 9.2.2. Let f₁, f₂ be closed proper convex functions on ℝⁿ with
(f₁0⁺)(z) + (f₂0⁺)(-z) > 0 for every z ≠ 0. Then f₁ □ f₂ is a closed proper convex function.
Corollary 9.2.2, last formula: (f₁ □ f₂)0⁺ = f₁0⁺ □ f₂0⁺.
The same formula under the weaker hypothesis of Corollary 9.2.1 is
corollary_9_2_1_recession.
Corollary 9.2.2, attainment: the infimum in (f₁ □ f₂)(x) = inf_y {f₁(x - y) + f₂(y)} is
attained for each x.
Theorem 9.3: sums of functions #
Theorem 9.3 for m = 2, closed case. If f₁ and f₂ are closed proper
convex and f₁ + f₂ is not identically +∞, then f₁ + f₂ is a closed proper convex function.
Theorem 9.3 for m = 2, recession formula: (f₁ + f₂)0⁺ = f₁0⁺ + f₂0⁺.
Theorem 9.3 for m = 2, second half: if the fᵢ are not all closed but
their effective domains have a common relative interior point, then
cl (f₁ + f₂) = cl f₁ + cl f₂.
Theorem 9.4: pointwise suprema #
Theorem 9.4, closed case: a pointwise supremum of closed functions is closed, its epigraph being the intersection of theirs. Neither convexity nor finite dimension is needed.
Theorem 9.4, properness. f = sup {fᵢ | i ∈ I} is proper as soon as every
fᵢ is proper and f is finite somewhere.
"Finite somewhere" is spelled out as both ≠ ⊥ and ≠ ⊤ at one point; the ≠ ⊥ half is what
forces the book's index set I to be non-empty, since a supremum over an empty family is -∞
everywhere.
Theorem 9.4, recession formula: f0⁺ = sup {fᵢ0⁺ | i ∈ I}. This is Corollary 8.3.3 read
through epi_recessionFn.
Theorem 9.4, second half: if the fᵢ are not all closed but some x̄ lies in every
ri (dom fᵢ) and f x̄ is finite, then cl f = sup {cl fᵢ | i ∈ I}.
Theorem 9.5: composition with a linear transformation #
Theorem 9.5, closed case: if g is closed then so is gA. No relative interior
hypothesis is needed — epi (gA) is a preimage of epi g under a continuous linear map.
Theorem 9.5, recession formula: (gA)0⁺ = (g0⁺)A. This is Corollary 8.3.4 read through
epi_recessionFn.
Theorem 9.5, second half: if g is not closed but Ax ∈ ri (dom g) for some x, then
cl (gA) = (cl g)A.
Theorem 9.6: the convex cone generated by a set #
Theorem 9.6. For a non-empty closed convex C not containing the origin and K the
convex cone generated by C (modelled as PointedCone.hull ℝ C), cl K = K ∪ 0⁺C.
Theorem 9.6 in the book's λ ≥ 0⁺ form: cl K = ⋃ {λC | λ > 0 or λ = 0⁺}. The union is
indexed by ExtCoeff.Pos, and ExtCoeff.smulSet is what makes λ = 0⁺ contribute 0⁺C rather
than {0}.
Corollary 9.6.1. If C is a non-empty closed bounded convex set not
containing the origin, the convex cone generated by C is closed.
Theorem 9.7: the positively homogeneous convex function generated by f #
Theorem 9.7. For closed proper convex f with f 0 > 0, the positively homogeneous
convex function k generated by f — the backbone's posHomGen — is proper.
Theorem 9.7: (cl k)(x) = inf {(fλ)(x) | λ > 0 or λ = 0⁺}, in the λ ≥ 0⁺ convention,
with ExtCoeff.smulFn putting the λ > 0 and λ = 0⁺ parts under one index.
Theorem 9.7, attainment: the infimum inf {(fλ)(x) | λ > 0 or λ = 0⁺} is attained for
each x. Stated at each real bound μ, since the assertion is that the right-hand side is a
union of epigraphs and not merely the epigraph of the infimum.
Theorem 9.7, last sentence: if 0 ∈ dom f then k is itself closed.
Theorem 9.7, last sentence: if 0 ∈ dom f then λ = 0⁺ may be omitted from
the infimum — though the infimum then need not be attained.
Corollary 9.7.1. For a closed convex set C containing 0, the gauge γ(· | C) is
closed. gaugeFn is defined by the computed formula inf {λ ≥ 0 | x ∈ λC}, where the book defines
γ as the positively homogeneous convex function generated by δ(· | C) + 1.
Corollary 9.7.1, first formula: {x | γ(x | C) ≤ λ} = λC for λ > 0.
Corollary 9.7.1, second formula: {x | γ(x | C) = 0} = 0⁺C.
Theorem 9.8: the convex hull of a union #
The λ ≥ 0⁺ convention, reduced to the backbone. For non-empty closed convex C₁, C₂,
Rockafellar's ⋃ {λ₁C₁ + λ₂C₂ | λᵢ ≥ 0⁺, λ₁ + λ₂ = 1} is exactly
conv (C₁ ∪ C₂) + (0⁺C₁ + 0⁺C₂).
Both λᵢ = 0⁺ is excluded by λ₁ + λ₂ = 1; the mixed cases give the summands 0⁺C₁ + C₂ and
C₁ + 0⁺C₂; and with both λᵢ real and positive the recession cones are absorbed, since
Cᵢ + 0⁺Cᵢ = Cᵢ.
Theorem 9.8 for m = 2. Let C₁, C₂ be non-empty closed convex sets in ℝⁿ
such that the only way a direction of recession of one can cancel a direction of recession of the
other is inside the two lineality spaces, and let C = conv (C₁ ∪ C₂). Then
cl C = ⋃ {λ₁C₁ + λ₂C₂ | λᵢ ≥ 0⁺, λ₁ + λ₂ = 1},
where λᵢ ≥ 0⁺ means that λᵢCᵢ is taken to be 0⁺Cᵢ rather than {0} when λᵢ = 0.
Theorem 9.8, second conclusion: 0⁺(cl C) = 0⁺C₁ + 0⁺C₂.
Corollary 9.8.1 for m = 2. If C₁, C₂ are non-empty closed convex sets with
the same recession cone K, then C = conv (C₁ ∪ C₂) is closed.
Corollary 9.8.1, second conclusion: C has K as its recession cone.
Corollary 9.8.2. If C₁, C₂ are closed and bounded then conv (C₁ ∪ C₂) is closed and
bounded. Stated without the convexity or non-emptiness the book assumes; the book's own proof has
to discard an empty Cᵢ by hand.
Corollary 9.8.3 for m = 2. If f₁, f₂ are closed proper convex functions on
ℝⁿ all having the same recession function k, then f = conv {f₁, f₂} is closed and proper.
Corollary 9.8.3, second conclusion: f has k as its recession function.
Corollary 9.8.3, last sentence: the infimum in Theorem 5.6's formula for f(x) is
attained by some convex combination. Stated against a real upper bound, the EReal-faithful
reading: conv {f₁, f₂} x may itself be +∞, and then there is nothing to attain.