Rockafellar, §29: Bifunctions and Generalized Convex Programs #
The generalization of an ordinary convex program to a convex bifunction — an objective function together with a distinguished family of perturbations of it — and the identification of its Kuhn–Tucker vectors with the subgradients of the perturbation function at the origin. This is the hinge of Part VI: §30's duality theory is stated entirely in this vocabulary.
All 12 numbered results of §29 are formalized: Theorems 29.1, 29.2, 29.3 and 29.4 and Corollaries 29.1.1–29.1.6, 29.3.1 and 29.4.1.
Almost all of §29's vocabulary is the backbone's under the book's own names: Bifun (Rn m) (Rn n),
graphFn, ConvexBifun, ClosedBifun, domBifun, infBifun for the perturbation function
inf F, KuhnTucker (pairing m) F, lagrangian (pairing m) F, Consistent,
StronglyConsistent, StrictlyConsistent, PolyhedralBifun, and clBifun for cl F. The
objective function F0 is F 0; the optimal value in (P) is infBifun F 0. IsOptimalSolution
is deliberately not argmin (F 0) — the book asks for (F0)(x) to be finite and equal to the
optimal value, so an inconsistent program has no optimal solutions although argmin (F 0) = ℝⁿ.
Corollary 29.4.1 is false as printed. Its perturbation clause — that the perturbation functions
of (P) and (cl P) agree on a neighbourhood of 0 — drops the properness that its own
Theorem 29.4 carries. corollary_29_4_1_perturbation transcribes the claim as printed and
corollary_29_4_1_perturbation_false refutes it, with the counterexample originBifun on ℝ¹.
The corrected statement is corollary_29_4_1_eventually, which adds Proper (graphFn F). Every
other clause of the corollary holds as printed and is proved here.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §29 (pp. 291–306). Corollary 29.4.1 is stated there with no printed proof.
The section's vocabulary #
The graph domain of a bifunction: the effective domain of its graph function, a convex
subset of ℝᵐ × ℝⁿ.
Instances For
dom F is the projection of the graph domain on ℝᵐ, and is therefore a convex set. This
is the identification every relative-interior step of Theorem 29.4 runs on.
The graph domain of a convex bifunction is convex.
An optimal solution to the convex program (P) associated with F: a vector x at which
(F0)(x) is finite and equal to the optimal value in (P). Not argmin (F 0): Rockafellar is
explicit that "we do not speak of optimal solutions to (P) when (P) is inconsistent", and an
optimal value of -∞ is excluded by the same clause.
Equations
- Rockafellar.IsOptimalSolution F x = (F 0 x ≠ ⊤ ∧ F 0 x ≠ ⊥ ∧ F 0 x = Tdaf.ConvexAnalysis.infBifun F 0)
Instances For
The bridge to the backbone's minimum set: the optimal solutions are empty unless F0 is
proper, and are its minimum set when it is. The second hypothesis is consistency.
A program whose optimal value is -∞ has no optimal solutions, whatever else is true of it: the
book's definition asks for a finite value.
The saddle-point condition of Theorem 29.3 as the book writes it:
L(u*, x̄) ≤ L(ū*, x̄) ≤ L(ū*, x) for every u* and every x.
The indicator bifunction of a linear transformation #
The (+∞) indicator bifunction of a linear transformation A: (Fu)(x) = δ(x | Au). It is
the backbone's indicator bifunction of the convex process ofLinearMap A.
Equations
Instances For
The graph function of linearIndicatorBifun A is the indicator of the graph of A, a subspace
of ℝᵐ⁺ⁿ.
Theorem 29.1 #
Theorem 29.1, first assertion: the perturbation function inf F of a convex program is
convex. Theorem 5.7 at the projection (u, x) ↦ u, of which inf F is the image.
Theorem 29.1, first assertion, second half: dom (inf F) = dom F. Needs no hypothesis on
F: inf F is +∞ at u only if Fu is the constant +∞.
The reformulation of the definition of a Kuhn–Tucker vector that the book records immediately
after giving it: inf F0 is finite and inf Fu + ⟨u*, u⟩ ≥ inf F0 for every u.
Theorem 29.1, second assertion: at a finite optimal value the Kuhn–Tucker vectors for (P)
are precisely the u* with -u* ∈ ∂(inf F)(0). No convexity is used, although the book states
the whole theorem for a convex bifunction: this assertion rearranges the definition.
Theorem 29.1, second assertion as an equation of sets: the Kuhn–Tucker set is the reflection
of ∂(inf F)(0). Corollaries 29.1.1–29.1.5 are subdifferential properties transported through
it.
Corollary 29.1.1 #
Corollary 29.1.1, first clause: the ε-subgradient description of the Kuhn–Tucker set, read as a monotone family.
Corollary 29.1.1, the directional derivative of inf F at the origin, written as the
infimum the book displays.
Corollary 29.1.1: (inf F)'(0; ·) is positively homogeneous — a reindexing of the infimum,
needing no hypothesis.
Corollary 29.1.1: (inf F)'(0; ·) is a convex function of the direction.
Corollary 29.1.1, second clause: the Kuhn–Tucker vectors form a convex set.
Corollary 29.1.1, second clause: the Kuhn–Tucker vectors form a closed set.
Corollary 29.1.1, last clause: the support function of the Kuhn–Tucker set is the
directional derivative of inf F at the origin, in the book's -inf {⟨u*, u⟩} form.
Corollary 29.1.2 #
Corollary 29.1.2. At a finite optimal value a Kuhn–Tucker vector fails to exist exactly when
some direction of perturbation makes the two-sided directional derivative of the optimal value
-∞: (inf F)'(0; u) = -∞ together with (inf F)'(0; -u) = +∞. In the equilibrium-price reading,
the program has one unless perturbation in some direction is "infinitely advantageous".
Corollary 29.1.3 #
Corollary 29.1.3. At a finite optimal value (P) has a unique Kuhn–Tucker vector exactly
when the perturbation function is differentiable at the origin. The book's hypotheses are kept even
though its proof cites Theorem 25.1, which needs properness that "finite optimal value" does not
give: properness is free on each side, from proper_of_mem_subgradient and
HasGradientAt.proper.
Corollary 29.1.3, the formula: where the perturbation function is differentiable at the
origin with gradient b, the unique Kuhn–Tucker vector is -b.
Corollary 29.1.3, the value of the gradient: the unique Kuhn–Tucker vector is
-∇(inf F)(0), coordinate by coordinate.
Strong and strict consistency #
(P) is strictly consistent iff for every u there is a λ > 0 with λu ∈ dom F — a
consistent program is strictly consistent unless some perturbation empties the feasible set at
once.
Corollary 29.1.4 #
Corollary 29.1.4, existence half: a strongly consistent convex program with a finite optimal
value has a Kuhn–Tucker vector. Theorem 23.4 applied to inf F, proper by Theorem 7.2.
Corollary 29.1.4, the formula: the directional derivative of the optimal value at 0 is
-inf {⟨u*, u⟩ | u* a Kuhn–Tucker vector}.
Corollary 29.1.5 #
Corollary 29.1.5, first clause: for a strictly consistent program with a finite optimal
value inf F is finite and continuous on the open convex neighbourhood int (dom F) of 0.
Corollary 29.1.5, last clause: the Kuhn–Tucker vectors form a non-empty set.
Corollary 29.1.5, last clause: the Kuhn–Tucker vectors form a closed set.
Corollary 29.1.5, last clause: the Kuhn–Tucker vectors are bounded. This is what
distinguishes Corollary 29.1.5 from Corollary 29.1.4: under mere strong consistency the
Kuhn–Tucker set need not be bounded, Theorem 23.4 bounding ∂f x only at interior points.
Corollary 29.1.5, last clause: the Kuhn–Tucker vectors form a convex set.
Corollary 29.1.5, last clause in one piece: for a strictly consistent program with a finite optimal value the Kuhn–Tucker set is non-empty, compact and convex.
Corollary 29.1.6 #
Corollary 29.1.6: if inf Fu = -∞ for some u, then inf Fu = -∞ for every
u ∈ ri (dom F).
Corollary 29.1.6, the parenthesis: inf Fu = +∞ for u ∉ dom F. Needs neither convexity
nor the corollary's hypothesis; it is Theorem 29.1's dom (inf F) = dom F.
Theorem 29.2 #
Theorem 29.2, first clause: every slice Fu of a polyhedral convex bifunction — the
objective function F0 in particular — is a polyhedral convex function.
Theorem 29.2, second clause: the perturbation function of a polyhedral convex program is
polyhedral — Corollary 19.3.1 at the projection (u, x) ↦ u.
Theorem 29.2, third clause: a polyhedral convex program with a finite optimal value has an
optimal solution. Less is needed than the book asks — inf F0 ≠ -∞ alone bounds F0 below and
Corollary 27.3.2 attains the infimum; finiteness is what the polyhedrality clause below needs.
Theorem 29.2, third clause: a polyhedral convex program with a finite optimal value has at
least one Kuhn–Tucker vector, by Theorem 23.10 applied to inf F at the origin.
Theorem 29.2, last clause: the optimal solutions form a polyhedral convex set, being a
sublevel set of the polyhedral F0 at the optimal value.
Theorem 29.2, last clause: the Kuhn–Tucker vectors form a polyhedral convex set.
Theorem 29.3 #
Theorem 29.3, as the book displays it: for a closed proper convex bifunction, ū* is a
Kuhn–Tucker vector and x̄ an optimal solution iff L(u*, x̄) ≤ L(ū*, x̄) ≤ L(ū*, x) for all u*
and all x — that is, iff (ū*, x̄) is a saddle-point of the Lagrangian.
Theorem 29.3, in the backbone's bundled form.
Corollary 29.3.1 #
Corollary 29.3.1, the strongly consistent case: x̄ is an optimal solution exactly when it
completes some ū* to a saddle-point of the Lagrangian.
Corollary 29.3.1, the strictly consistent case. A strictly consistent program is strongly consistent, so this is the previous corollary verbatim.
Corollary 29.3.1, the polyhedral case: for a polyhedral closed proper convex program plain consistency suffices, Theorem 29.2 supplying a Kuhn–Tucker vector with no interiority hypothesis.
Theorem 29.4 #
cl F, the bifunction whose graph function is cl (graph F), regularizes a program before
Theorem 29.3 or §30's duality theory is applied to it.
cl F is a closed convex bifunction, and proper when F is.
cl F is closed, for any F.
cl F is proper when F is.
Theorem 29.4, first assertion: (cl F)u = cl (Fu) for each u ∈ ri (dom F). Rockafellar's
closure of an improper convex function that is somewhere -∞ is the constant -∞ everywhere, not
the lower semicontinuous hull f̄; both proofs turn on that convention.
Theorem 29.4, second assertion: inf (cl F)u = inf Fu for u ∈ ri (dom F). A convex
function and its closure have the same infimum, so the content is the first assertion.
Theorem 29.4, third assertion, first inclusion: dom F ⊆ dom (cl F) for proper F.
Theorem 29.4, third assertion, second inclusion: dom (cl F) ⊆ cl (dom F) for proper F.
Properness is not decoration: originBifun below has dom F = {0} and dom (cl F) = ℝ¹.
Corollary 29.4.1 #
Corollary 29.4.1, the underlying domain fact: closing a proper convex bifunction leaves
ri (dom F) alone. Theorem 29.4 sandwiches dom (cl F) between dom F and cl (dom F), and
Corollary 6.3.1 says such a sandwich has the same relative interior.
Corollary 29.4.1, first clause: if (P) is strongly consistent then so is (cl P). This
clause does survive without properness: an improper F whose graph function is somewhere -∞
has dom (cl F) = ℝᵐ, and one with empty graph domain is not consistent at all.
Corollary 29.4.1, second clause: the objective function for (cl P) is the closure of the
objective function for (P). This is Theorem 29.4 read at the origin.
Corollary 29.4.1, third clause: (P) and (cl P) have the same optimal value.
Corollary 29.4.1, fourth clause, in the backbone's vocabulary: every minimiser of F0
minimises (cl F)0. The inclusion is strict in general — closing can create new minimisers.
Corollary 29.4.1, fourth clause, in the book's own vocabulary: every optimal solution to
(P) is an optimal solution to (cl P).
Corollary 29.4.1, fifth clause, with the properness hypothesis the book omits: the
perturbation functions of (P) and (cl P) agree on a neighbourhood of 0. Theorem 29.4 gives
agreement only on ri (dom F); what upgrades it is dom (cl F) ⊆ cl (dom F) ⊆ aff (dom F), so a
small enough ball meets only ri (dom F) and points off aff (dom F) where both are +∞. That
inclusion is where properness enters — see corollary_29_4_1_perturbation_false.
Corollary 29.4.1, last clause: (P) and (cl P) have the same Kuhn–Tucker vectors. The
book deduces this from the perturbation clause, which needs properness; the route here does not,
since the adjoint bifunction never sees the closure (adjointBifun_clBifun).
Corollary 29.4.1 as printed is false #
corollary_29_4_1_perturbation transcribes the corollary's fifth clause with the hypotheses the
book prints, and corollary_29_4_1_perturbation_false refutes it on ℝ¹.
The counterexample to Corollary 29.4.1 as printed: the bifunction on ℝ¹ that is -∞ when
u = 0 and +∞ otherwise. What the example must do is make dom F a proper affine subset with the
origin in its relative interior, and {0} ⊆ ℝ¹ is the cheapest such set.
Equations
- Rockafellar.originBifun u x✝ = ⨆ (_ : u ≠ 0), ⊤
Instances For
originBifun is convex: its epigraph is the preimage of {0} under a linear map, hence a
linear subspace of (ℝ¹ × ℝ¹) × ℝ.
dom F = {0}.
(P) is strongly consistent: ri {0} = {0} contains the origin.
cl F is the constant -∞: the graph function takes the value -∞, and Rockafellar's closure
convention makes the closure of such a function the constant -∞ everywhere.
inf (cl F) ≡ -∞.
inf F = +∞ away from the origin.
Corollary 29.4.1's perturbation clause with the hypotheses the book prints: "Let F be a
convex bifunction from Rᵐ to Rⁿ. … Assume that (P) is strongly consistent. … The perturbation
functions for (P) and (cl P) agree on a neighborhood of 0." No properness anywhere.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Corollary 29.4.1 is false as Rockafellar states it.
Take F = originBifun on ℝ¹: (Fu)(x) = -∞ for u = 0 and +∞ for u ≠ 0. It is convex and
dom F = {0} has 0 in its relative interior, so (P) is strongly consistent; but its graph
function takes the value -∞, so cl (graph F) is the constant -∞ and inf (cl F) ≡ -∞, while
inf F = +∞ at every u ≠ 0. The two perturbation functions agree at the single point 0.
Every other clause is Theorem 29.4 read at the origin, where 0 ∈ ri (dom F) is available; this
one needs agreement outside ri (dom F), which only dom (cl F) ⊆ cl (dom F) supplies, and that
is stated for proper F. With F proper the clause is corollary_29_4_1_eventually.