Rockafellar, §34: Closures and Equivalence Classes #
The lower and upper closures cl₂ cl₁ K and cl₁ cl₂ K, the effective domain dom K,
equivalence and closedness of saddle-functions, the class Ω (F), the kernel, and simple
saddle-functions. All ten numbered results of §34 are formalized: Theorems 34.1–34.5 (34.3 in six
clauses (a)–(f)), Corollaries 34.2.1–34.2.4 and Corollary 34.5.1.
The orientation convention for cl₁ and cl₂ is stated in Part7/Section33.lean and used here
unchanged; lowerCl K = cl₂ (cl₁ K) and upperCl K = cl₁ (cl₂ K).
Theorem 34.2 is stated before Theorem 34.1 because it licenses the reading everything downstream
uses: the natural primitive is not a saddle-function but a closed convex bifunction F, whose
order interval Ω (F) = {K | K̲ ≤ K ≤ K̄} is exactly one equivalence class of closed
concave-convex functions. Theorem 34.1 then says the two closures always land on such a pair.
Divergences from the book #
Theorem 34.2's dom K = dom F × dom F* is a product identity and only that: the book argues the
two factors separately, and that step fails for improper F — with graph function ≡ +∞,
dom₁ K = ∅ = dom F but dom₂ K = ℝⁿ while dom F* = ∅, and both products are empty. So
theorem_34_2_dom₁ and theorem_34_2_dom₂ carry a nonemptiness hypothesis the book suppresses.
Theorem 34.1 is proved with no hypothesis at all, stronger than the book's statement, and
Corollary 34.2.4 asks only for separate continuity of the slices where the book asks for joint.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §34, pp. 359–369.
The vocabulary of §34 #
Rockafellar's dom₁ K = {u | K (u, v) > −∞, ∀ v}.
Rockafellar's dom₂ K = {v | K (u, v) < +∞, ∀ u}.
Rockafellar's dom K = dom₁ K × dom₂ K, the effective domain of a saddle-function.
K is proper when dom K ≠ ∅.
On dom K a saddle-function is finite.
The lower simple extension of a finite saddle-function on a nonempty C × D has
dom K = C × D, and is proper.
The upper simple extension likewise.
Rockafellar's equivalent: cl₁ K = cl₁ L and cl₂ K = cl₂ L.
Rockafellar's closed: cl₁ cl₂ K = cl₁ K and cl₂ cl₁ K = cl₂ K. The book defines it as
"cl₁ K and cl₂ K are both equivalent to K", then reduces that to these two equations.
Theorem 34.2 #
Rockafellar's Ω (F): for a closed convex bifunction F, the collection of all
concave-convex K with ⟨Fu, x*⟩ ≤ K (u, x*) ≤ ⟨u, F*x*⟩. The concave-convexity is part of
the book's definition; the backbone's bifunSaddleClass is the same interval without it.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The bridge from Ω (F) to the backbone's order interval, which is what §37's statements about
a class are phrased against.
Theorem 34.2: K̲ (u, x*) = ⟨Fu, x*⟩ belongs to Ω (F).
Theorem 34.2: K̄ (u, x*) = ⟨u, F*x*⟩ belongs to Ω (F).
Theorem 34.2, second equation: cl₂ K = K̲ for every K ∈ Ω (F).
Theorem 34.2, first equation: cl₁ K = K̄ for every K ∈ Ω (F), with no closedness of
F needed.
Theorem 34.2: every member of Ω (F) is a closed saddle-function.
Theorem 34.2: any two members of Ω (F) are equivalent.
Theorem 34.2: Ω (F) is a whole equivalence class — a concave-convex function
equivalent to a member is itself a member.
Theorem 34.2, converse: a closed concave-convex function determines one and only one
closed convex bifunction whose two brackets are cl₂ K and cl₁ K.
Theorem 34.2, converse: and K lies in the class of that bifunction, so every equivalence
class of closed concave-convex functions is an Ω (F).
Theorem 34.2, dom clause, first factor: dom₁ K = dom F for K ∈ Ω (F). The
nonemptiness hypothesis is not in the book and cannot be dropped; see the module docstring.
Theorem 34.2, dom clause, second factor: dom₂ K = dom F* for K ∈ Ω (F), again with a
nonemptiness hypothesis the book suppresses.
Theorem 34.2: dom K = dom F × dom F*.
Theorem 34.2: F is recovered from any K ∈ Ω (F) as Fu = K (u, ·)*.
Theorem 34.2, third equation: (Fu)(x) = sup_{x*} {⟨x, x*⟩ − K (u, x*)}.
Theorem 34.2, fourth equation: (F*x*)(u*) = inf_u {⟨u, u*⟩ − K (u, x*)}. The book writes
this off the third by symmetry, but it is not symmetric: F* x* is the concave conjugate of
u ↦ (cl₂ K) (u, x*), and replacing cl₂ K by K under it is what closedness of K buys.
Theorem 34.2, last clause: K (u, x*) = ⟨Fu, x*⟩ = ⟨u, F*x*⟩ when u ∈ ri (dom F).
Theorem 34.2, last clause, second half: the same when x* ∈ ri (dom F*).
Theorem 34.1: the lower closure cl₂ cl₁ K is lower closed. Proved here from monotonicity
and idempotence of the two closures, so it needs no hypothesis at all — not concave-convexity,
not properness — which is strictly stronger than the book's statement.
Theorem 34.1: the upper closure cl₁ cl₂ K is upper closed, again with no hypothesis.
Theorem 34.1, first displayed equation: cl₂ cl₁ cl₂ cl₁ K = cl₂ cl₁ K.
Theorem 34.1, second displayed equation: cl₁ cl₂ cl₁ cl₂ K = cl₁ cl₂ K.
Corollary 34.2.1 #
Corollary 34.2.1, first clause: equivalent saddle-functions have the same effective domain.
Corollary 34.2.1: the dom L = dom K clause needs no closedness, which the book's
blanket hypothesis "K closed" suggests it does. dom₁ is already dom₁ (cl₂ ·) and dom₂
already dom₂ (cl₁ ·), so equivalence alone settles both factors.
Corollary 34.2.1, second clause: L (u, v) = K (u, v) whenever u ∈ ri (dom₁ K).
Corollary 34.2.1, second clause: L (u, v) = K (u, v) whenever v ∈ ri (dom₂ K).
Corollary 34.2.2 #
Corollary 34.2.2: a lower closed saddle-function is closed.
Corollary 34.2.2: an upper closed saddle-function is closed.
Corollary 34.2.2: a fully closed saddle-function is closed.
Corollary 34.2.2: the class of a closed saddle-function has a lower closed member,
cl₂ K.
Corollary 34.2.2: and an upper closed member of that class, cl₁ K.
Corollary 34.2.2: a lower closed member of the class of K is cl₂ K.
Corollary 34.2.2: an upper closed member of the class of K is cl₁ K.
Corollary 34.2.2: the lower closed member is the least member of the class.
Corollary 34.2.2: the upper closed member is the greatest member.
Corollary 34.2.3 #
Corollary 34.2.3: the only improper closed saddle-functions on ℝᵐ × ℝⁿ are the two
constants −∞ and +∞.
Corollary 34.2.3: and the two constants are not equivalent.
Corollary 34.2.4 #
The +∞/−∞ pattern is orientation-sensitive: +∞ where u ∈ C and v ∉ D, −∞ where
u ∉ C and v ∈ D. It is the opposite of what a convex-concave convention would give.
Corollary 34.2.4: the class of the corollary — the extensions of K by +∞ on C × Dᶜ
and −∞ on Cᶜ × D — is exactly the order interval between the two simple extensions. The values
on Cᶜ × Dᶜ are unconstrained. Stated without the concave-convexity the book's Ω also asks
for.
Corollary 34.2.4: every member of the class is a closed saddle-function.
Corollary 34.2.4: every member of the class is proper.
Corollary 34.2.4: the class is precisely one equivalence class.
Corollary 34.2.4: the lower simple extension is the least member.
Corollary 34.2.4: the upper simple extension is the greatest member.
Theorem 34.3 #
Six clauses, one declaration each, in the necessity direction; the sufficiency direction needs all
six at once and is theorem_34_3. Throughout, C = dom₁ K and D = dom₂ K.
Theorem 34.3 (a). For u ∈ ri C the convex function K (u, ·) is closed proper with
effective domain D.
Theorem 34.3 (b). For u ∈ C ∖ ri C the convex function K (u, ·) is proper and its
effective domain lies between D and cl D. The lower inclusion holds for every u whatsoever;
only the upper one uses the structure.
Theorem 34.3 (c). For u ∉ C the convex function K (u, ·) is improper, with value −∞
throughout ri D — throughout D itself if u ∉ cl C.
Theorem 34.3 (d). For v ∈ ri D the concave function K (·, v) is closed proper with
effective domain C.
Theorem 34.3 (e). For v ∈ D ∖ ri D the concave function K (·, v) is proper and its
effective domain lies between C and cl C.
Theorem 34.3 (f). For v ∉ D the concave function K (·, v) is improper, with value +∞
throughout ri C — throughout C itself if v ∉ cl D.
Theorem 34.3. A proper concave-convex function is closed if and only if it has the six
properties (a)–(f), bundled as SaddleStructure: (a)–(c) for K together with (a)–(c) for
saddleSwap K, which is what (d)–(f) are.
The kernel and simple saddle-functions #
ri (dom K) = ri (dom₁ K) × ri (dom₂ K), the rectangle the kernel lives on.
The kernel of K: its restriction to ri (dom K). Rockafellar's kernel is a partial
function on a rectangle that moves with K; here it is extended by +∞ off the rectangle, so that
kernel K = kernel L is one equation rather than a rectangle equality plus a transport.
Equality of kernels unpacked into the book's two facts: the same rectangle, same values.
Rockafellar's simple: over ri (dom₁ K) the convex slices stay inside cl (dom₂ K), and
over ri (dom₂ K) the concave slices stay inside cl (dom₁ K).
Every closed proper saddle-function is simple: clauses (b) and (e) of Theorem 34.3.
The two simple extensions of a finite saddle-function on a nonempty C × D are simple.
Every saddle-function of the form K (u, x*) = ⟨Fu, x*⟩ is simple, Rockafellar's exercise.
Stated here for F closed and K proper, where the book asks only that F be a convex or
concave bifunction: closedness makes K closed (Theorem 33.3) and properness lets Theorem 34.3
apply. Whether the unrestricted claim holds is not settled here.
Theorem 34.4 #
Theorem 34.4. Two closed proper concave-convex functions on ℝᵐ × ℝⁿ are equivalent if
and only if they have the same kernel.
Theorem 34.5 and Corollary 34.5.1 #
Theorem 34.5: cl₂ cl₁ K ≤ cl₁ cl₂ K for a simple proper concave-convex K.
Theorem 34.5: the lower and upper closures of such a K are equivalent.
Theorem 34.5: every saddle-function between the two closures is closed.
Theorem 34.5: every saddle-function between the two closures is proper.
Theorem 34.5: every concave-convex function between the two closures has the same kernel
as K.
Theorem 34.5, converse half: a closed proper concave-convex function with the same kernel
as K lies between the two closures, so the interval is the whole class.
Theorem 34.5, summary: the kernel of a simple proper concave-convex function is the kernel
of exactly one equivalence class of closed proper concave-convex functions, represented by
cl₂ cl₁ K.
Corollary 34.5.1 #
Corollary 34.5.1. For nonempty convex C ⊆ ℝᵐ, D ⊆ ℝⁿ and a finite concave-convex K
on C × D, there is one and only one equivalence class of closed proper concave-convex functions
on ℝᵐ × ℝⁿ whose kernel is the restriction of K to ri (C × D).