Rockafellar, §36: Minimax Problems #
The two iterated extrema sup inf and inf sup, the saddle-value and the saddle-point, the
reduction of a minimax problem on C × D to one on all of ℝᵐ × ℝⁿ, the inverse bifunction F_*,
and the identification of the Lagrangians of closed convex programs with the upper closed
concave-convex functions. All seven numbered results of §36 are formalized: Lemmas 36.1 and 36.2,
Theorems 36.3–36.6 and Corollary 36.3.1.
Orientation. From here to the end of the book, minimization takes place in the convex argument
and maximization in the concave one. For a concave-convex K (u, v) — concave in the first
argument, convex in the second — that fixes both extrema: maximin K is sup_u inf_v K (u, v) and
minimax K is inf_v sup_u K (u, v), so Lemma 36.1 reads maximin K ≤ minimax K, and a
saddle-point is a p with K (u, p.2) ≤ K p ≤ K (p.1, v) — first argument maximised, second
minimised. Theorems 36.3–36.6 and every result of §37 are false verbatim under the opposite
convention.
HasSaddleValue is the bare equality of the two iterated extrema. Finiteness of the common value
is a separate conclusion, drawn where the book draws it, in Corollary 36.3.1.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §36, pp. 379–387.
The saddle-value and the saddle-point #
The two iterated extrema, and the saddle-value of K — their common value, when they are
equal. Nothing is said about that value being finite.
The definition of a saddle-point: K (u, v̄) ≤ K (ū, v̄) ≤ K (ū, v) for all u and v.
The first argument is the one K is maximised over.
Lemma 36.1 #
Lemma 36.1: sup inf ≤ inf sup, with no hypothesis at all — not even nonemptiness.
Lemma 36.1 in the book's own C × D form, for arbitrary subsets C and D. The ⨆ ∈
reading makes the book's nonemptiness assumption unnecessary.
Lemma 36.2 #
Lemma 36.2: (ū, v̄) is a saddle-point exactly when the supremum in sup inf is attained
at ū, the infimum in inf sup at v̄, and the two extrema are equal. Stated on ℝᵐ × ℝⁿ rather
than the book's C × D; IsSaddlePointOn carries the relative reading where it is wanted.
Lemma 36.2, last sentence: at a saddle-point both extrema equal K (ū, v̄).
The reduction to the whole space #
Where the book extends a finite K on C × D by ±∞, the outer supremum in sup inf may
always be restricted to C = dom₁ K, since inf_v K (u, v) = −∞ for u ∉ C.
The outer infimum in inf sup may always be restricted to D = dom₂ K.
Theorem 36.3 #
Theorem 36.3, first displayed equation: for a closed proper concave-convex K, with
C = dom₁ K and D = dom₂ K, sup_{ℝᵐ} inf_{ℝⁿ} K = sup_C inf_D K.
Theorem 36.3, second displayed equation: inf_{ℝⁿ} sup_{ℝᵐ} K = inf_D sup_C K. With
theorem_36_3_maximin this says the two problems have the same pair of iterated extrema.
Theorem 36.3, last sentence: the saddle-points of K on ℝᵐ × ℝⁿ are its saddle-points
relative to C × D = dom K.
Corollary 36.3.1 #
Corollary 36.3.1, first assertion: a saddle-point of a proper saddle-function lies in
dom K. The book states this for a closed proper saddle-function; closedness is not used.
Corollary 36.3.1, second assertion: a proper saddle-function with a saddle-point has a finite saddle-value.
Theorem 36.4 #
Theorem 36.4: equivalent saddle-functions have the same sup inf. Two concave functions
with the same closure have the same supremum, and the iterated extrema see only that.
Theorem 36.4: one of two equivalent saddle-functions has a saddle-value exactly when the other does.
Theorem 36.4: equivalent saddle-functions have the same saddle-points. This is what makes minimax theory a theory of equivalence classes, hence — by Theorem 36.5 — of convex programs.
The inverse bifunction F_* #
F_* is concave if F is convex: it is flipBifun composed with a change of sign.
The inverse operation is involutory, (F_*)_* = F.
The inverse operation commutes with the adjoint, (F_*)^* = (F^*)_*, so one may write
F_*^* for either. The left side is the concave adjoint of the concave bifunction F_*, the right
the inverse of F*; Rockafellar reads it as (A⁻¹)^* = (A^*)⁻¹ for a non-singular A.
Rockafellar's ⟨u*, F_* x⟩, the concave bracket of the inverse bifunction, as a function of
the pair (u*, x). It is the Lagrangian of (P), and by Theorem 37.1 the upper conjugate K̄*
of every member of Ω (F). An abbrev for concaveBifunBracket at inverseBifun F.
Equations
Instances For
The book's defining formula: ⟨u*, F_* x⟩ = inf_u {⟨u*, u⟩ + (Fu)(x)}.
Theorem 36.5 #
The Lagrangian L (u*, x) = inf_u {⟨u*, u⟩ + (Fu)(x)} of (P) is the bracket
⟨u*, F_* x⟩. The only step that is not definitional is symmetry of the Euclidean pairing.
The Lagrangian of a convex program is concave-convex: concave in the price variable u*,
convex in the primal variable x.
Theorem 36.5. L is the Lagrangian of a convex program associated with a closed convex
bifunction from ℝᵐ to ℝⁿ if and only if L is an upper closed concave-convex function on
ℝᵐ × ℝⁿ. So the regularized minimax problems of §36 and the closed proper convex programs of
§§29–30 are the same objects, read through the Lagrangian; with Corollary 34.2.2's unique upper
closed member per class, that names the canonical representative of a class.
Theorem 36.5, necessity alone: the Lagrangian of a closed convex bifunction is upper closed concave-convex.
An upper closed concave-convex L is the Lagrangian of one and only one closed convex
bifunction. The book determines it explicitly by (Fu)(x) = sup_{u*} {L (u*, x) − ⟨u*, u⟩}; the
statement here asserts existence and uniqueness without naming the witness.
The Kuhn–Tucker condition, and Theorem 36.6 #
(0, 0) ∈ ∂K (u, v) if and only if (u, v) is a saddle-point of K: the concave slice
attains its maximum at u and the convex slice its minimum at v. No hypothesis is needed.
The Kuhn–Tucker condition for (P): for a closed proper convex bifunction F,
(0, 0) ∈ ∂L (ū*, x̄) holds exactly when ū* is a Kuhn–Tucker vector for (P) and x̄ is an
optimal solution.
Theorem 36.6, the strongly consistent case: for (P) associated with a closed proper
convex bifunction and strongly consistent, x̄ is optimal if and only if (0, 0) ∈ ∂L (ū*, x̄) for
some ū*. The book prints no proof; this is the Kuhn–Tucker theorem, Corollary 29.3.1.
Theorem 36.6, the strictly consistent case, which is strongly consistent.
Theorem 36.6, the polyhedral case: plain consistency suffices, Theorem 29.2 supplying a Kuhn–Tucker vector with no interiority hypothesis.
Theorem 36.6, last sentence: for a given optimal x̄, the ū* satisfying the Kuhn–Tucker
condition are precisely the Kuhn–Tucker vectors for (P). No constraint qualification is used.