Rockafellar, §37: Conjugate Saddle-Functions and Minimax Theorems #
The lower conjugate K̲* and the upper conjugate K̄* of a saddle-function, the conjugacy
correspondence among equivalence classes of closed saddle-functions, the effective domain C* × D*
of the conjugate class, the existence theorems for the saddle-value and for a saddle-point, and —
as their special cases — Rockafellar's two finite-dimensional minimax theorems. Minimax theory is
the conjugacy correspondence of §§33–34 read at the origin.
All eighteen numbered results of §37 are formalized: Theorems 37.1–37.6 and Corollaries 37.1.1, 37.1.2, 37.1.3, 37.2.1, 37.3.1, 37.3.2, 37.4.1, 37.5.1, 37.5.2, 37.5.3, 37.6.1, 37.6.2.
Orientation. The lower conjugate is sup_v inf_u and the upper is inf_u sup_v, with
K̲* ≤ K̄* by Lemma 36.1; swapping the extrema swaps the two conjugates. §33's cl₁/cl₂ and
§36's "minimise in the convex argument, maximise in the concave" are both in force. By Corollary
37.1.1 the conjugates depend only on the equivalence class, so results are stated for a member of
Ω (F) (§34) or for a closed concave-convex K, from which exists_mem_Ω_of_closed recovers F.
Divergences from the book #
The C* support-function half of Theorem 37.2 is not formalized; its D* half is
theorem_37_2_dom₂, and nothing downstream depends on the other.
Corollaries 37.3.2 and 37.6.2 are Rockafellar's finite-dimensional minimax theorems. The hypothesis
here is that C or D be closed and bounded, where the infinite-dimensional analogues
(Kneser–Fan, Sion) need compactness; in ℝⁿ the two coincide by Heine–Borel. Both also ask for
convexity, concavity and continuity slice by slice rather than jointly.
Corollary 37.4.1 carries a closedness hypothesis the book does not state, and Corollary 37.5.1's
homeomorphism comes out as (u − u*, v* + v) where the book prints (u − u*, v + v*).
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §37, pp. 388–400.
The two conjugates of a saddle-function #
Rockafellar's lower conjugate K̲* (u*, v*) = sup_v inf_u {⟨u, u*⟩ + ⟨v, v*⟩ − K (u, v)};
the supremum over the convex variable is outermost.
Equations
Instances For
Rockafellar's upper conjugate K̄* (u*, v*) = inf_u sup_v {⟨u, u*⟩ + ⟨v, v*⟩ − K (u, v)},
with the infimum over the concave variable outermost.
Equations
Instances For
The book's defining formula for K̲*.
The book's defining formula for K̄*.
K̲* ≤ K̄*, "of course, by Lemma 36.1". No hypotheses.
Rockafellar's dom ∂K = {(u, v) | ∂K (u, v) ≠ ∅}.
Equations
Instances For
pairing n separates on the left; on a self-paired space this is one line from
inner_self_eq_zero.
Theorem 34.2, packaged for §37: a closed concave-convex function on ℝᵐ × ℝⁿ belongs to the
class Ω (F) of a unique closed convex bifunction F. Properness of K is not needed, but
properness of the graph function of F is exactly ProperSaddleFn K.
Theorem 37.1 #
Theorem 37.1, first equation: for a closed convex bifunction F and any K ∈ Ω (F),
inf_u sup_x* {⟨u, u*⟩ + ⟨x, x*⟩ − K (u, x*)} = ⟨u*, F_* x⟩. The upper conjugate is the
Lagrangian, and the Lagrangian is the concave bracket of the inverse bifunction.
Theorem 37.1, second equation: sup_x* inf_u {⟨u, u*⟩ + ⟨x, x*⟩ − K (u, x*)} = ⟨F_*^* u*, x⟩, where F_*^* is the bifunction of the conjugate class.
The class conjugate to Ω (F) is Ω (F_*^*), and F_*^* is again a convex bifunction from
ℝᵐ to ℝⁿ.
And F_*^* is closed.
(F_*^*)_* = F^*: the inverse operation is an involution.
The biadjoint identity (F_*^*)^* = F_*, for a closed convex bifunction.
Theorem 37.1, third equation: for any K* ∈ Ω (F_*),
inf_u* sup_x {⟨u, u*⟩ + ⟨x, x*⟩ − K* (u*, x)} = ⟨u, F* x*⟩, the first equation at F_*^*.
Theorem 37.1, fourth equation: sup_x inf_u* {⟨u, u*⟩ + ⟨x, x*⟩ − K* (u*, x)} = ⟨Fu, x*⟩.
The second equation at F_*^*, using (F_*^*)^* = F_*, which is where closedness of F is
spent.
Corollary 37.1.1 #
The upper conjugate of a member of Ω (F) lies in the conjugate class Ω (F_*^*).
So does the lower conjugate.
Corollary 37.1.1: K̲* is concave-convex.
Corollary 37.1.1: K̲* is lower closed, cl₂ cl₁ K̲* = K̲* — Theorem 33.3 at
F_*^*.
Corollary 37.1.1: K̄* is concave-convex.
Corollary 37.1.1: K̄* is upper closed, cl₁ cl₂ K̄* = K̄*.
Corollary 37.1.1: K̲* and K̄* are equivalent, so by Theorem 36.4 they have the same
iterated extrema and the same saddle-points.
Corollary 37.1.1: the lower conjugate is a closed saddle-function — the two conjugates are
the ends of the closure pair of Ω (F_*^*).
Corollary 37.1.1: and so is the upper conjugate.
Corollary 37.1.1: the lower conjugate depends only on the equivalence class — two
members of Ω (F) have the same one, on the nose.
Corollary 37.1.1: and so does the upper conjugate.
A saddle-function conjugate to a closed proper saddle-function is proper: the only
improper closed saddle-functions are the constants ±∞, and those are conjugate to each other.
The same for the lower conjugate.
Corollary 37.1.1, last sentence: conjugacy is involutive up to equivalence — the lower
conjugate of a conjugate of K is equivalent to K. It is ⟨Fu, x*⟩, the lower end of
Ω (F).
Corollary 37.1.1, last sentence: and the upper conjugate of K* is ⟨u, F*x*⟩, the
upper end of Ω (F).
Corollary 37.1.2 #
Corollary 37.1.2, first equation: cl₁ K̲* = K̄*.
Corollary 37.1.2, second equation: cl₂ K̄* = K̲*.
Corollary 37.1.2: C* × D* is the effective domain of both conjugates.
Corollary 37.1.2, first sentence: the conjugates of a closed proper saddle-function have
the structural properties of Theorem 34.3 with respect to the nonempty convex C* × D*.
Corollary 37.1.2, last clause: K̲* = K̄* at (u*, v*) whenever u* ∈ ri C*.
Corollary 37.1.2, last clause: and whenever v* ∈ ri D*.
The saddle-value read at the origin, and Corollary 37.1.3 #
inf_v sup_u K (u, v) = −K̲* (0, 0). No hypotheses.
sup_u inf_v K (u, v) = −K̄* (0, 0). No hypotheses.
Corollary 37.1.3 (the book prints no proof): if the origin of ℝᵐ lies in ri C* then
inf_v sup_u K = sup_u inf_v K. The two displays above make the saddle-value exist exactly when
the conjugates agree at the origin, and Corollary 37.1.2 makes them agree on ri C* × ℝⁿ.
Corollary 37.1.3: the same when the origin of ℝⁿ lies in ri D*.
Corollary 37.1.3, last sentence: if both conditions hold the saddle-value is finite.
Theorem 37.2 and Corollary 37.2.1 #
Theorem 37.2, the D* formula: for a closed proper concave-convex K with effective
domain C × D, δ*(w | D*) = sup_{u ∈ ri C} sup_{v ∈ D} {K (u, v + w) − K (u, v)}. The C*
formula is not carried; see the module docstring.
Theorem 37.2, the D* formula in recession-function form: δ*(· | D*) is the pointwise
supremum over u ∈ ri C of the recession functions of the slices K (u, ·).
Corollary 37.2.1, first half: 0 ∈ int D* if and only if the convex functions K (u, ·),
u ∈ ri C, have no common direction of recession.
Corollary 37.2.1, second half: 0 ∈ int C* if and only if the convex functions −K (·, v),
v ∈ ri D, have no common direction of recession.
Theorem 37.3 and its two corollaries #
Theorem 37.3 (a): if the convex functions K (u, ·), u ∈ ri C, have no common direction
of recession, the saddle-value of K exists. It is Corollaries 37.1.3 and 37.2.1 combined.
Theorem 37.3 (b): if the convex functions −K (·, v), v ∈ ri D, have no common
direction of recession, the saddle-value of K exists.
Theorem 37.3, last sentence: if both conditions hold the saddle-value is finite.
Corollary 37.2.1 turns them into 0 ∈ int C* and 0 ∈ int D*.
Corollary 37.3.1, the half where D is bounded: the effective domain of K (u, ·) is D
for every u ∈ ri C (Theorem 34.3), so a bounded D fulfils condition (a).
Corollary 37.3.1, the half where C is bounded: condition (b) is fulfilled.
Corollary 37.3.2: the minimax theorem for a finite continuous saddle-function #
Corollary 37.3.2. For nonempty closed convex C ⊆ ℝᵐ, D ⊆ ℝⁿ and a continuous finite
concave-convex K on C × D with D bounded,
inf_{v ∈ D} sup_{u ∈ C} K (u, v) = sup_{u ∈ C} inf_{v ∈ D} K (u, v). The extrema are in EReal:
with only D bounded both can be infinite (C = {0}, D = ℝ, K (u, v) = v).
Corollary 37.3.2, the half where C is bounded. Same divergences as
corollary_37_3_2_right.
Theorem 37.4: subgradients are saddle-points of the tilted function #
Theorem 37.4, first sentence: (u*, v*) ∈ ∂K (u, v) exactly when (u, v) is a
saddle-point of the tilted function K − ⟨·, u*⟩ − ⟨·, v*⟩. The two inner products are combined
into one real coercion so that no ∞ − ∞ can arise, and there are no hypotheses at all — not
concavity, not convexity, not properness, where the book assumes concave-convexity.
∂K (u, v) is convex, with no hypothesis on K: it is a product of two convex sets.
∂K (u, v) is closed. The concave factor is assembled from §35's sign dictionary
mem_subgrad₁_iff_neg_mem_subgradient_neg and isClosed_subgradient.
Theorem 37.4, left-hand inclusion: ri (dom K) ⊆ dom ∂K for a closed proper concave-convex
function. Over ri C the slice K (u, ·) is proper with effective domain D (Theorem 34.3), so
Theorem 23.4 produces a subgradient; the concave half is the same statement for saddleSwap K.
Theorem 37.4, right-hand inclusion: dom ∂K ⊆ dom K. Only properness is used — a
subgradient pair makes p a saddle-point of the tilt, and Corollary 36.3.1 places it in
dom K.
Corollary 37.4.1 #
Corollary 37.4.1: equivalent saddle-functions have the same subdifferential, ∂K = ∂L, so
one may speak of the subdifferential of an equivalence class.
Rockafellar tilts both functions and appeals to Theorem 36.4, which needs cl₁ (K − ℓ) = cl₁ K − ℓ;
the route here is Theorem 37.5's (a) ⇔ (d), and the price is a closedness hypothesis the book's
statement does not carry.
Corollary 37.4.1, second sentence: equivalent saddle-functions moreover agree in value
on dom ∂K = dom ∂L. A subgradient pair at p says the conjugate of the convex slice is attained,
and that conjugate is F p.1 for every member of the class.
Theorem 37.5 #
Theorem 37.5, the function f: the graph function of the F of Theorem 34.2,
f (u, v*) = sup_v {⟨v, v*⟩ − K (u, v)}. It is closed proper convex on ℝᵐ⁺ⁿ, read here as a
function on ℝᵐ × ℝⁿ.
Theorem 37.5 (a), against condition (d): (u*, v*) ∈ ∂K (u, v) exactly when the pair
satisfies the class-level condition IsBifunSubgradientPair. Because the right-hand side mentions
only F, this is the statement that ∂K depends only on the equivalence class.
Theorem 37.5 (b), against condition (d): (u, v) ∈ ∂K* (u*, v*) for the canonical upper
conjugate. With (a) this says the subdifferentials of conjugate classes are inverse to each
other, as ∂(f*) = (∂f)⁻¹ is for convex functions.
Theorem 37.5 (c), against condition (d): (−u*, v) ∈ ∂f (u, v*). So ∂K is the partial
inversion of ∂f — second components of point and gradient swapped, first component of the
gradient negated. That is what transfers closedness, the Minty parametrisation and maximal
monotonicity to ∂K, and is the source of the asymmetry in Corollaries 37.5.1 and 37.5.2.
Theorem 37.5 (d): the condition (Fu)(v*) − ⟨v, v*⟩ = (F*v)(u*) − ⟨u, u*⟩, the equality
case of ⟨v, v*⟩ − (Fu)(v*) ≤ ⟨Fu, v⟩ ≤ K (u, v) ≤ ⟨u, F*v⟩ ≤ ⟨u, u*⟩ − (F*v)(u*). It mentions no
representative of the class, which is why (a), (b) and (c) are stated against it.
Corollaries 37.5.1 and 37.5.2 #
Corollary 37.5.1, closedness clause: the graph of ∂K is closed. Theorem 37.5 (c) makes it
the preimage of the graph of ∂f under a linear homeomorphism, and Theorem 24.4 applies.
Corollary 37.5.1, homeomorphism clause: the graph of ∂K is homeomorphic to ℝᵐ × ℝⁿ
under (u, v, u*, v*) ↦ (u − u*, v + v*). The map is asymmetric, being Corollary 31.5.1's Minty
parametrisation composed with the partial inversion of Theorem 37.5 (c). F is an explicit
argument because a Homeomorph is data; corollary_37_5_1_exists_homeomorph is the book's
form.
Equations
- Rockafellar.corollary_37_5_1_homeomorph hF hcl hpr hK = Tdaf.ConvexAnalysis.saddleSubgradientHomeomorph hF hcl hpr ⋯
Instances For
The homeomorphism is the book's map, with the two summands of the second component in the
other order: (u − u*, v* + v) against the printed (u − u*, v + v*).
Corollary 37.5.1 in the book's own quantification: for a closed proper concave-convex
K the graph of ∂K is homeomorphic to ℝᵐ × ℝⁿ.
Corollary 37.5.2: ρ : (u, v) ↦ {(−u*, v*) | (u*, v*) ∈ ∂K (u, v)} is a maximal
monotone mapping from ℝᵐ × ℝⁿ to itself. The u* ↦ −u* is inserted, not derived: ∂K carries
a superdifferential in the first argument and a subdifferential in the second, so it is monotone in
one variable and antitone in the other, and negating the first dual component repairs it.
Corollary 37.5.2, "in particular": if K is everywhere finite and differentiable then
(u, v) ↦ (−∇₁K (u, v), ∇₂K (u, v)) is maximal monotone. The gradient is a pair, not a vector
of ℝᵐ⁺ⁿ, because Mathlib gives a product of inner-product spaces the supremum norm.
Corollary 37.5.3 #
Corollary 37.5.3: ∂K* (0, 0) is the set of saddle-points of K. It is Theorem
37.5 (b) at the origin composed with Theorem 37.4, whose tilt by the origin is K itself.
Corollary 37.5.3: the saddle-points form a convex product set, being a value of
∂K* = ∂₁K* × ∂₂K*.
Corollary 37.5.3: and a closed set.
Corollary 37.5.3, last sentence: a saddle-point exists if and only if
(0, 0) ∈ dom ∂K*.
Corollary 37.5.3, "in particular": K has a saddle-point as soon as
(0, 0) ∈ ri (dom K*), by Theorem 37.4 applied to K*.
Theorem 37.6 and its two corollaries #
Theorem 37.6: if conditions (a) and (b) of Theorem 37.3 both hold, K has a
saddle-point. Corollary 37.2.1 turns the two recession conditions into (0, 0) ∈ ri (dom K*) and
Corollary 37.5.3 produces the point.
Theorem 37.6, parenthesis: a saddle-point of a proper saddle-function lies in
C × D = dom K.
Corollary 37.6.1: if C and D are bounded, K has a saddle-point — the slices over
the relative interiors have effective domains exactly D and C (Theorem 34.3).
Corollary 37.6.1, second clause: the saddle-value is then finite, being a value of K
at a saddle-point.
Corollary 37.6.2: the minimax theorem #
Corollary 37.6.2, the classical minimax theorem: for nonempty closed bounded convex
C ⊆ ℝᵐ, D ⊆ ℝⁿ and a continuous finite concave-convex K on C × D, there are ū ∈ C,
v̄ ∈ D with K (u, v̄) ≤ K (ū, v̄) ≤ K (ū, v) for all u ∈ C, v ∈ D. The lower simple
extension of K is closed proper with effective domain C × D, Corollary 37.6.1 gives it a
saddle-point, and Corollary 36.3.1 places that point in C × D.