Rockafellar, §30: Adjoint Bifunctions and Dual Programs #
The adjoint F* of a convex bifunction, the dual program (P*) it defines, and the exact
circumstances — Rockafellar calls them normality — under which the two programs have the same
optimal value.
All 10 numbered results of §30 are formalized: Theorems 30.1, 30.2, 30.3, 30.4 and 30.5 and
Corollaries 30.2.1, 30.2.2, 30.2.3, 30.5.1 and 30.5.2, with one declaration per clause for the
multi-clause results. With them: the Gale–Kuhn–Tucker Duality Theorem, which the book names in
running text and never states as a numbered result; the adjoint of the indicator bifunction of a
linear transformation, which is what justifies the word "adjoint"; the Lagrangian reading of the
two objective functions that §36 takes up; and the section's two unnumbered counterexamples,
abnormalBifun and noDualSolutionBifun, placed at the end of the file because each cites a
theorem stated further on.
dualProgram F is an abbrev for the backbone's adjointBifun (pairing m) (pairing n) F, so
every backbone theorem about adjointBifun applies to it verbatim. Normal, ConcaveNormal,
ConcaveConsistent, ConcaveKuhnTucker, ConcavePolyhedralBifun, supBifun,
concaveAdjointBifun and clBifun are the backbone's under the book's own definitions.
Theorem 30.4(i) and (j) are false as the book states them. Rockafellar disposes of them in six
words — "Of course, (i) and (j) are contained in (g) and (h)" — and the containment needs the
objective to be proper. With F0 ≡ +∞ every point is an optimal solution, so that set is non-empty
and bounded while no sublevel set of F0 is. theorem_30_4_i therefore assumes Proper (F 0) and
theorem_30_4_j assumes Proper fun v => -(F* 0) v; with those the containment is right.
Four statements drop closedness that the book assumes — Corollary 30.2.1's first half, the first
formulas of Corollaries 30.2.2 and 30.2.3, and Theorem 30.3's (a) ⟺ (c). Each runs on
Fenchel–Moreau for inf F, and the adjoint cannot tell F from cl F.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §30 (pp. 307–326).
The adjoint bifunction and the dual program #
Rockafellar's adjoint bifunction F*: the bifunction from ℝⁿ to ℝᵐ given by
(F*x*)(u*) = inf_{u,x} {(Fu)(x) - ⟨x, x*⟩ + ⟨u, u*⟩}, which is the bifunction of the dual
program (P*). An abbrev for the backbone's adjointBifun at the two Euclidean pairings.
Equations
Instances For
The book's defining formula for the adjoint. Rockafellar writes the two brackets as
-⟨x, x*⟩ + ⟨u, u*⟩; the backbone groups them inside one real subtraction, which cannot meet
∞ - ∞.
The objective function of (P*): (F*0)(u*) = inf_u {⟨u, u*⟩ + inf Fu}.
Rockafellar's definition of a normal convex program: (P) is normal when its perturbation
function inf F is closed at u = 0. This is the backbone's Normal, unfolded.
Normality of the dual program: (P*) is normal when cl (sup F*) agrees with sup F* at
x* = 0.
Theorem 30.1 #
Theorem 30.1, the concavity clause: the adjoint of any bifunction from ℝᵐ to ℝⁿ is a
concave bifunction from ℝⁿ to ℝᵐ. No hypothesis on F is used.
Theorem 30.1, the closedness clause: F* is a closed concave bifunction, again with no
hypothesis on F.
Theorem 30.1, the properness clause: F* is proper if and only if F is, for a closed
convex F.
Theorem 30.1: F** = cl F for a convex bifunction.
Theorem 30.1: F** = F when F is closed — which is why the program dual to (P*) is
(P) again.
Theorem 30.1, the injectivity half of "the adjoint operation establishes a one-to-one
correspondence": two closed convex bifunctions with the same adjoint are equal. The
surjectivity half is theorem_30_1_surjective.
Theorem 30.1, the surjectivity half: every closed proper concave bifunction G from ℝⁿ
to ℝᵐ is the adjoint of a closed proper convex bifunction — namely of G's own lower adjoint.
Theorem 30.1, last clause: "If F is polyhedral, so is F*." The book's justification is
Theorem 19.2. Neither properness nor closedness is needed.
The adjoint of an indicator bifunction #
Rockafellar's first example of the adjoint operation, and the one that justifies the name: "the
adjoint operation for bifunctions can rightly be viewed as a generalization of the adjoint
operation for linear transformations". linearIndicatorBifun itself is §29's.
§30: the adjoint of the convex indicator bifunction of A is the concave indicator
bifunction of the adjoint transformation, F*x* = -δ(· | A*x*). Here A* is LinearMap.adjoint A;
on ℝⁿ the adjoint is canonical, so it is not carried as data.
Theorem 30.2 #
Theorem 30.2, first formula: (-inf F)* = F*0. The objective of the dual program is the
concave conjugate of the concave function -inf F — and not a statement about conj, since
g* ≠ -(-g)*.
Theorem 30.2, second formula: (F*0)* = -cl (inf F).
Theorem 30.2, third formula: (-sup F*)* = F0. For a closed convex F the objective of
(P) is the conjugate of the convex function -sup F*.
Theorem 30.2, fourth formula: (F0)* = -cl (sup F*).
The Lagrangian form of the two objectives #
§30, the remark after Theorem 30.2: the objective function of (P*) is the infimum of the
Lagrangian of (P) over the primal variable, (F*0)(u*) = inf_x L(u*, x).
§30: for a closed convex F the objective function of (P) is the supremum of the
Lagrangian over the price variable, (F0)(x) = sup_{u*} L(u*, x).
§30: the optimal value of (P*) is sup_{u*} inf_x L(u*, x).
§30: for a closed convex F the optimal value of (P) is inf_x sup_{u*} L(u*, x).
Together with supBifun_dualProgram_eq_maximin this is why normality is the existence of a
saddle-value, the reading §36 takes up.
Corollary 30.2.1 #
Corollary 30.2.1, first half: (P*) is inconsistent exactly when some perturbation of (P)
has no lower bound. Stated for an arbitrary convex F, although the book assumes closedness for the
whole corollary: the adjoint never sees the difference between F and cl F.
Corollary 30.2.1, first half, positively.
Corollary 30.2.1, second half: (P) is inconsistent exactly when some perturbation of
(P*) has no upper bound. This half really does need F closed — it is the first half read for the
dual pair, and F** = F is what identifies the objective of (P).
Corollary 30.2.1, second half, positively.
Corollary 30.2.2 #
Corollary 30.2.2, first formula: (cl (inf F))(0) = sup F*0. Closedness of F is not used:
the formula is Fenchel–Moreau for inf F, and F* does not distinguish F from cl F.
Corollary 30.2.2, second formula: (cl (sup F*))(0) = inf F0. Here closedness of F is
what turns F** back into F.
Corollary 30.2.2, weak duality: inf F0 ≥ sup F*0, always. No hypothesis at all — it is
⟨u, u*⟩ + inf Fu evaluated at u = 0.
Corollary 30.2.3 #
Corollary 30.2.3, first formula: unless both programs are inconsistent,
liminf_{u → 0} (inf Fu) = sup F*0. The excluded case is Rockafellar's own: the two sides differ
only when cl (inf F) is -∞, so (P*) is inconsistent, and the liminf is +∞, so (P) is.
Corollary 30.2.3, second formula: unless both programs are inconsistent,
limsup_{x* → 0} (sup F*x*) = inf F0.
Theorem 30.3 #
Theorem 30.3(a) ⟺ (c): a convex program is normal exactly when there is no duality gap.
Closedness of F is not needed, although the theorem carries it: only Corollary 30.2.2's first
formula is used.
Theorem 30.3(b) ⟺ (c).
Theorem 30.3(a) ⟺ (b): a convex program is normal exactly when its dual is.
Theorem 30.3, the three clauses as the book states them: for a closed convex bifunction F,
(P) is normal, (P*) is normal, and the two optimal values agree, are equivalent.
Theorem 30.4 #
Rockafellar argues (a), (c) and (e), says "Dually, (b), (d) and (f) imply that normality holds", gives one compressed sentence for (g), and disposes of (h), (i) and (j) as "special cases" and "of course … contained in". Each declaration below records what the book supplies for its own clause.
Theorem 30.4(a): a strongly consistent convex program is normal. The book proves this
clause, by the argument used here: 0 ∈ ri (dom (inf F)) by Theorem 29.1, and a convex function
agrees with its closure on the relative interior of its effective domain.
Theorem 30.4(a), the parenthetical strict form.
Theorem 30.4(b): if the dual program is strongly consistent then normality holds for the pair. The book does not argue this clause — "Dually, (b), (d) and (f) imply that normality holds". The route here is the dual of (a) composed with Theorem 30.3(a) ⟺ (b).
Theorem 30.4(c): if (P) has a Kuhn–Tucker vector — its optimal value being finite, which
is part of the definition — then (P) is normal. The book proves this clause, from Theorem 29.1
and Corollary 23.5.2; the route here is cheaper, weak duality pinning the dual optimal value.
Theorem 30.4(d): if the dual program has a Kuhn–Tucker vector then normality holds for the pair. The book does not argue this clause.
Theorem 30.4(e): a polyhedral convex program that is merely consistent is normal. The
book proves this clause: Theorem 29.2 makes inf F polyhedral, and a polyhedral convex function
agrees with its closure throughout its effective domain.
Theorem 30.4(f): if (P*) is polyhedral and consistent then normality holds for the pair.
The book does not argue this clause. By theorem_30_1_polyhedral the hypothesis follows from
polyhedrality of F, which is how the Gale–Kuhn–Tucker theorem below uses it.
Theorem 30.4(g): if some sublevel set of the objective F0 is non-empty and bounded, then
normality holds.
The book's one sentence hides the argument: "Condition (g) is equivalent by Theorem 27.1(d) to
having 0 ∈ int (dom (F0)*), i.e. (P*) strictly consistent." The "i.e." is not an abbreviation —
strict consistency of (P*) is an interior condition on an intersection over all perturbations —
and what closes it is that all slices of a closed convex bifunction have the same recession
function, so the two sets are in fact equal. No properness is assumed: an improper closed convex
bifunction has inf F0 = -∞ and is normal automatically.
Theorem 30.4(h): if some superlevel set of the dual objective F*0 is non-empty and
bounded, then normality holds. The book does not argue this clause. The route here is not the
book's: -F* is a closed convex bifunction with no hypothesis on F, so clause (g) applies to it
and Theorem 30.3 transports the conclusion back.
Theorem 30.4(i): if the optimal solutions to (P) form a non-empty bounded set — in
particular if there is exactly one — then normality holds.
As the book states it the clause is false: the asserted containment in (g) needs F0 proper,
since with F0 ≡ +∞ the set of optimal solutions is non-empty and bounded while no sublevel set is.
With Proper (F 0), argmin (F0) is a level set of F0 at its minimum value and (g) applies.
Theorem 30.4(j): if the optimal solutions to (P*) form a non-empty bounded set then
normality holds. As in (i), the containment the book asserts needs properness of the dual
objective.
The Gale–Kuhn–Tucker Duality Theorem, which Rockafellar names in running text with no
numbered statement of its own: for a polyhedral closed convex bifunction the optimal values of (P)
and (P*) are equal unless both programs are inconsistent.
Stated at the generality the argument actually has — the book applies it to a particular dual pair
of linear programs, saying "these are polyhedral convex programs, so it follows". Clause (e) covers
consistent (P) and clause (f), fed by theorem_30_1_polyhedral, consistent (P*). Closedness is
free in the intended application: a proper polyhedral convex bifunction is closed.
Theorem 30.5 #
Theorem 30.5, first assertion: under normality, u* is a Kuhn–Tucker vector for (P) if
and only if u* is an optimal solution to (P*).
Theorem 30.5, second assertion: under normality, x is a Kuhn–Tucker vector for (P*) if
and only if x is an optimal solution to (P). The book says only "the proof of the dual assertion
of the theorem is parallel" and does not carry it out.
Corollary 30.5.1 #
Corollary 30.5.1, (b) ⟺ (c): (ū*, x̄) is a saddle-point of the Lagrangian exactly when
(F0)(x̄) ≤ (F*0)(ū*) — in which case weak duality forces equality.
Corollary 30.5.1, (a) ⟺ (b): (ū*, x̄) is a saddle-point of the Lagrangian exactly when
normality holds and x̄, ū* are optimal solutions to (P) and (P*). The book's proof is
"immediate from Theorem 29.3", the existence of a Kuhn–Tucker vector implying normality.
Corollary 30.5.1, (a) ⟺ (c).
Corollary 30.5.1, the three clauses as the book states them.
Corollary 30.5.1, the parenthesis: when clause (c) holds, equality actually holds. This is weak duality (Corollary 30.2.2) in the other direction.
Corollary 30.5.2 #
Corollary 30.5.2, second assertion: if (P) is strongly consistent and (P*) is consistent
then (P*) has an optimal solution. Theorem 30.4(a) gives normality, so the common optimal value is
finite, Corollary 29.1.4 supplies a Kuhn–Tucker vector, and Theorem 30.5 makes it optimal.
Corollary 30.5.2, first assertion: if (P) is consistent and (P*) is strongly consistent
then (P) has an optimal solution. This is the assertion the book proves, through the concave
Corollary 29.1.4; the route here runs the convex one on -F* instead.
The section's two counterexamples: the toolkit #
Both of Rockafellar's unnumbered examples are bifunctions from R to R, so both live on Rn 1.
These are the coordinate lemmas they share.
An unnumbered counterexample: an abnormal program with a duality gap #
"There do exist convex programs which are not normal … For an example of abnormality consider the
closed proper convex bifunction F from R to R defined by (Fu)(x) = exp(-√(ux)) if
u ≥ 0, x ≥ 0, and +∞ otherwise."
§30, the abnormal example: (Fu)(x) = exp(-√(ux)) on the closed first quadrant, +∞ off
it. The domain condition is carried as a ⨅ over a proposition, which keeps Decidable out of the
statement.
Rockafellar calls this "the closed proper convex bifunction F". Convexity is not proved here:
it is the concavity of the geometric mean on the first quadrant composed with exp, elementary
two-variable real analysis with no convex-analytic content. What is proved is the perturbation
function the book displays, the duality gap abnormalBifun_duality_gap — inf F0 = 1 against
sup F*0 = 0 — and the failure of normality, the last from the perturbation function alone.
Equations
Instances For
The value of the abnormal example off the first quadrant.
Every value of the abnormal example is ≥ 0: the exponential is positive.
Hence every value of the perturbation function is ≥ 0.
§30: the optimal value of (P) is 1. At u = 0 the objective is exp(-√0) = 1 on the
whole non-negative axis.
§30: inf Fu = 0 for every u > 0.
§30: inf Fu = +∞ for u < 0 — the program is inconsistent for negative perturbations.
§30: the optimal value of (P*) is 0, so (P) and (P*) have a genuine duality gap:
inf F0 = 1 while sup F*0 = 0.
§30: the abnormal example really has a duality gap.
§30: the example is not normal — (cl (inf F))(0) = 0 while (inf F)(0) = 1. Proved
directly from the perturbation function with no appeal to convexity of F: the closure is below the
lower semicontinuous hull, and inf F vanishes along u_k = 1/(k+1) → 0.
An unnumbered counterexample: a normal program whose dual has no optimal solution #
"An example of a normal convex program (P), such that (P) has an optimal solution but (P*) has
no optimal solution, is obtained when F is the closed convex bifunction from R to R given by
(Fu)(x) = x if x² ≤ u, +∞ if x² > u."
§30. The example: (Fu)(x) = x on {x² ≤ u}, +∞ off it.
Instances For
The value of the example on its effective domain.
The value of the example off its effective domain.
The objective of (P) vanishes at the origin.
The objective of (P) is +∞ away from the origin: x² ≤ 0 forces x = 0.
§30: x = 0 is the unique optimal solution to (P).
The optimal value of (P) is 0.
The example is a convex bifunction: its graph function is a linear coordinate added to the
indicator of the convex set {(u, x) | x² ≤ u}.
The example is a closed bifunction: its epigraph is cut out by two continuous inequalities.
The objective of (P) is a proper convex function.
§30: the example is normal. Rockafellar reads this off the lower semicontinuity of
inf Fu = -√u at u = 0; here it is Theorem 30.4(i), since the set of optimal solutions is the
single point 0.
§30: inf Fu ≤ -√u for u ≥ 0. The infimum is attained at x = -√u, the left endpoint of
{x | x² ≤ u}; only this half of the book's display is needed.
§30: (P) has no Kuhn–Tucker vector. The perturbation function -√u is lower
semicontinuous at 0 but has derivative -∞ there, so no linear minorant exists; concretely,
⟨u, u*⟩ + inf Fu dips below inf F0 = 0 at u = s² with s = 1/(1 + |u*|).
§30: the dual program (P*) has no optimal solution, although (P) is normal and has
one. By Theorem 30.5 the optimal solutions to (P*) are the Kuhn–Tucker vectors for (P), and
there are none.