Rockafellar, §31: Fenchel's Duality Theorem #
Fenchel's Duality Theorem and the version of it that a linear transformation A allows, the same
pair of extremum problems read as a convex program and its dual in the sense of §§29–30, the two
dual-cone corollaries, and Moreau's decomposition theorem. This is where Part III's conjugacy and
Part VI's programs meet.
All 12 numbered results of §31 are formalized: Theorems 31.1, 31.2, 31.3, 31.4 and 31.5 and
Corollaries 31.2.1, 31.3.1, 31.4.1, 31.4.2, 31.4.3, 31.5.1 and 31.5.2, together with the polyhedral
strengthenings of Theorem 31.1, Theorem 31.4 and Corollary 31.2.1, and the unnumbered contraction
property of the proximation, prox_contraction.
Main definitions #
ClosedProperConcaveFn g— the concave mirror ofClosedProperConvexFn, the standing hypothesis ongfrom Corollary 31.2.1 onwards;closedProperConcaveFn_iff_negis the bridge to the backbone'sClosedProperConvexFn fun x => -(g x).fenchelBifun A f g— the bifunction(F u)(x) = f x - g (A x + u)of Theorem 31.2: the Fenchel problem perturbed by translating the concave function.
Everything else is a backbone object used without a surface copy. Rockafellar's dual cone K* is
-(polarCone (pairing n) K), whose useful unfolded form is theorem_31_4_dualCone; his A* is
LinearMap.adjoint A, and no adjointness hypothesis is carried anywhere in this file, because
on ℝⁿ the transpose is canonical and isAdjointPair_adjoint supplies the datum that the
pairing-parametrised backbone asks for.
Two assertions the book leaves unproved are proved here. Corollary 31.2.1's polyhedral
strengthening is announced with "the proof will not be given here"; both halves are
corollary_31_2_1_a_polyhedral_right and corollary_31_2_1_a_polyhedral_left. Corollary 31.5.1
is stated with no proof; corollary_31_5_1 is a genuine Homeomorph, its inverse continuous by the
contraction property of the proximation.
Several statements carry weaker hypotheses than the book's. Theorem 31.1's finiteness clause needs
only a point of dom f ∩ dom g and one of dom g* ∩ dom f*, not their relative interiors;
closedness is unused under condition (a) in Corollary 31.2.1, Theorem 31.3 and Corollary 31.3.1;
Theorem 31.2's properness clause needs no relative-interior hypothesis; and Corollary 31.4.3 needs
K closed only for the attainment of its first infimum.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §31 (pp. 327–341).
- J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965), 273–299 — Theorem 31.5 and Corollary 31.5.2.
Concave functions in the book's vocabulary #
Rockafellar's closed proper concave function on ℝⁿ, the standing hypothesis on g from
Corollary 31.2.1 onwards. The backbone spells this as ClosedProperConvexFn fun x => -(g x); the
bridge is closedProperConcaveFn_iff_neg.
- concave : Tdaf.ConvexAnalysis.ConcaveFn g
The hypograph is convex.
- closed : Tdaf.ConvexAnalysis.ClosedConcaveFn g
gequals its own concave closure. - proper : Tdaf.ConvexAnalysis.ProperConcave g
gis finite somewhere and never+∞.
Instances For
The bridge to the backbone: g is closed proper concave exactly when -g is closed proper
convex, clause by clause.
The bridge, in the direction every proof below uses.
Theorem 31.1: Fenchel's duality theorem #
Rockafellar's two conditions (a) and (b) are two sufficient conditions for one interface, the
backbone's IsExactSum; the polyhedral weakenings the theorem's last paragraph announces are two
more. The four private constructors below are exactly those four, and the numbered statements are
one line each after them.
Theorem 31.1, the inequality the proof opens with: every dual value g*(x*) - f*(x*) is
below every primal value f(x) - g(x). Fenchel's inequality used twice, and carrying no
hypothesis at all — both ∞ - ∞ collisions are absorbed on the correct side.
Theorem 31.1 under condition (a): for a proper convex f and a proper concave g whose
effective domains have relative interiors meeting, inf {f(x) - g(x)} = sup {g*(x*) - f*(x*)}.
Condition (a) enters only through Theorem 16.4.
Theorem 31.1: under condition (a) the supremum is attained at some x*. Specialises
exists_concaveConj_sub_conj_eq.
Theorem 31.1, the attainment clause packaged: under condition (a) the common value is the
greatest dual value. Specialises isGreatest_concaveConj_sub_conj.
Theorem 31.1 under condition (b): f and g closed, with ri (dom g*) meeting
ri (dom f*). The equality is the same one — condition (a) read on the dual pair together with
Fenchel–Moreau.
Theorem 31.1: the polyhedral strengthening #
"If g is actually polyhedral, ri (dom g) and ri (dom g*) can be replaced by dom g and
dom g* in (a) and (b), respectively (and the closure assumption in (b) is superfluous). Similarly
if f is polyhedral." All four readings are Theorem 20.1 in place of Theorem 16.4, and the closure
assumption really is superfluous: a proper polyhedral convex function is closed.
Theorem 31.1: the polyhedral strengthening #
"If g is actually polyhedral, ri (dom g) and ri (dom g*) can be replaced by dom g and
dom g* in (a) and (b), respectively (and the closure assumption in (b) is superfluous). Similarly
if f is polyhedral". All four readings are Theorem 20.1 (IsExactSum.of_polyhedral) in
place of Theorem 16.4, and the closure assumption really is superfluous, because a proper polyhedral
convex function is closed (Corollary 19.1.2).
Theorem 31.1, the polyhedral strengthening of condition (a) with f polyhedral:
ri (dom f) may be replaced by dom f.
Theorem 31.1: under the polyhedral form of (a) with f polyhedral, the supremum is still
attained.
Theorem 31.1, the polyhedral strengthening of condition (a) with g polyhedral:
ri (dom g) may be replaced by dom g.
Theorem 31.1: under the polyhedral form of (a) with g polyhedral, the supremum is still
attained.
Theorem 31.1, the polyhedral strengthening of condition (b) with f polyhedral:
ri (dom f*) may be replaced by dom f*, and f is not assumed closed — a proper polyhedral
convex function is closed automatically.
Theorem 31.1, the polyhedral strengthening of condition (b) with g polyhedral:
ri (dom g*) may be replaced by dom g*, and g is not assumed closed.
Theorem 31.1: "if (a) and (b) both hold, the infimum and supremum are necessarily finite".
Only the closures of the two conditions are used — a point of dom f ∩ dom g bounds the infimum
above, and one of dom g* ∩ dom f* bounds it below through weak duality — so the hypotheses here
are weaker than the book's, and (a) and (b) imply them.
Corollary 31.2.1: a linear transformation between the two functions #
Rockafellar's condition (a) — some x ∈ ri (dom f) with A x ∈ ri (dom g) — does two jobs at
once, and the backbone separates them: it makes f and -(g A) add exactly (Theorem 16.4,
IsExactSum) and it makes -g pull back exactly along A (Theorem 16.3, IsExactImage).
Corollary 31.2.1 under condition (a): for a proper convex f on ℝⁿ, a closed proper
concave g on ℝᵐ and a linear A : ℝⁿ → ℝᵐ, inf {f(x) - g(Ax)} = sup {g*(u*) - f*(A*u*)} as
soon as some x ∈ ri (dom f) has Ax ∈ ri (dom g). Closedness of f, which the book assumes, is
not used under (a).
Corollary 31.2.1: under (a) the supremum is attained at some u*. Specialises
exists_concaveConj_sub_conj_comp_eq.
Corollary 31.2.1, the polyhedral strengthening with g polyhedral — the clause whose proof
the book declines to give: "It can be shown that in Corollary 31.2.1, just as in Theorem 31.1, ri
can be omitted whenever the corresponding function f or g is actually polyhedral. However, the
proof will not be given here."
Both of condition (a)'s jobs have polyhedral constructors: -(g A) is polyhedral, so Theorem
20.1 replaces Theorem 16.4 in the sum, and IsExactImage.of_polyhedral — Corollary 19.3.1 in
place of Theorem 16.3 — replaces the pullback. Neither needs a relative interior on the g side,
and closedness of g is automatic.
Corollary 31.2.1, the polyhedral strengthening with f polyhedral, the other half of the
clause the book leaves unproved: ri (dom f) may be replaced by dom f. Only the sum half changes,
because the pullback is a statement about g alone.
Theorem 31.3: the Kuhn–Tucker conditions #
Theorem 31.3, weak duality for the transformed pair, which the proof uses as its "general
inequality": every value of g* - f*A* is below every value of f - gA. No hypothesis at all.
Theorem 31.3. For f proper convex on ℝⁿ, g proper concave on ℝᵐ and A linear, the
primal and dual values agree at (x, u*) if and only if x and u* satisfy the Kuhn–Tucker
conditions A*u* ∈ ∂f(x) and Ax ∈ ∂g*(u*).
The book's second condition uses the superdifferential of the concave g*, which is -∂(-g), so
it is spelled -u* ∈ ∂(-g)(Ax) here; theorem_31_3_kuhnTucker_concave is the dictionary back to
the book's Fenchel-equality form. Closedness of f and g is assumed by the book and not used.
Theorem 31.3, the book's own reading of the second Kuhn–Tucker
condition: Ax ∈ ∂g*(u*) says that Fenchel's inequality for the concave pair holds with equality,
g(Ax) + g*(u*) = ⟨Ax, u*⟩ (Theorem 23.5 on the concave side).
Specialises neg_mem_subgradient_neg_iff_add_concaveConj_eq.
Theorem 31.3, first consequence: a pair at which the two values agree already minimises
f - gA. Only weak duality is used.
Theorem 31.3, second consequence: the same pair maximises g* - f*A*.
Theorem 31.3, the case of Fenchel's duality theorem itself: with A
the identity the Kuhn–Tucker conditions reduce to x* ∈ ∂f(x) and x ∈ ∂g*(x*).
Specialises sub_eq_concaveConj_sub_conj_iff.
Corollary 31.3.1: in the notation of Theorem 31.3, and with A (ri (dom f)) meeting
ri (dom g), x minimises f - gA if and only if some u* makes (x, u*) a Kuhn–Tucker pair.
The book's one-line proof is "Apply Corollary 31.2.1", and that is what happens: the forward
direction consumes its attainment clause, the backward direction only weak duality.
Corollary 31.3.1 at the identity, which is the statement Fenchel's
duality theorem itself carries: x minimises f - g exactly when it carries a Kuhn–Tucker pair.
Specialises iInf_sub_eq_iff_exists_kuhnTucker.
Theorem 31.4: minimising a convex function over a convex cone #
Rockafellar's K* is -(polarCone (pairing n) K). Set negation is a preimage, so y ∈ -K°
unfolds to -y ∈ K°; theorem_31_4_dualCone states the useful form.
Theorem 31.4, the definition of the dual cone: K* = {x* | ⟨x*, x⟩ ≥ 0 for all x ∈ K} is
the negative of the polar cone K°.
Theorem 31.4 under condition (a): for a closed proper
convex f and a nonempty convex cone K whose relative interior meets ri (dom f),
inf {f(x) | x ∈ K} = -inf {f*(x*) | x* ∈ K*}.
Closedness of f and of K are not used here; they belong to condition (b). Specialises
iInf_mem_eq_neg_iInf_mem_neg_polarCone.
Theorem 31.4: under (a) the infimum of f* over K* is attained. Specialises
exists_mem_neg_polarCone_conj_eq_iInf.
Theorem 31.4, the polyhedral strengthening of (a): "if K is polyhedral, ri K and ri K*
can be replaced by K and K* in (a) and (b)".
Theorem 31.4: under the polyhedral form of (a) the dual infimum is still attained.
Theorem 31.4 under condition (b): the same equality, with
ri (dom f*) meeting ri K*.
This is condition (a) read on the dual pair: Theorem 31.4 applied to f* and K*, closed up by
K** = K (Theorem 14.1, neg_polarCone_neg_polarCone) and f** = f (Fenchel–Moreau). Both
are where f closed and K closed are used.
Theorem 31.4: under (b) the infimum of f over K is attained. Specialises
exists_mem_eq_iInf_of_isExactSum_conj.
Theorem 31.4, the polyhedral strengthening of (b): ri K* becomes K*. Polyhedrality of
K is what makes K* polyhedral (polyhedral_neg_polarCone), and a polyhedral set is closed, so
the closedness hypothesis is free.
Theorem 31.4: under the polyhedral form of (b) the primal infimum is still attained.
Theorem 31.4, the optimality conditions: for x ∈ K and x* ∈ K*,
the primal and dual values agree — f(x) = -f*(x*) — exactly when x* ∈ ∂f(x) and
⟨x, x*⟩ = 0.
Rockafellar reads this off Theorem 31.3's Kuhn–Tucker conditions at g = -δ(· | K), where
x ∈ ∂g*(x*) unfolds into the three conditions x ∈ K, x* ∈ K*, ⟨x, x*⟩ = 0. Specialises
add_conj_eq_zero_iff_mem_subgradient_and_pairing_eq_zero.
Theorem 31.4: the optimality conditions make x optimal for the primal cone program.
Theorem 31.4: the optimality conditions make x* optimal for the dual cone program.
Theorem 31.4, weak duality: every dual value is below every primal value. No hypothesis
beyond x ∈ K and x* ∈ K*.
Corollary 31.4.1: the non-negative orthant #
Rockafellar.nonnegOrthant n is the set {z | z ≥ 0} of §12. Rockafellar states Corollary 31.4.1's
conditions without a relative interior on the orthant side, which is the polyhedral form of
Theorem 31.4; polyhedral_nonnegOrthant is what licenses it.
The orthant is self-dual: K* = -K° = {y | y ≥ 0} for K the non-negative orthant.
polarCone_nonnegOrthant (Theorem 14.1, §14) gives K° as the non-positive orthant, and the
sign flip of Rockafellar's K* turns it back.
Corollary 31.4.1 under condition (a): for a closed proper
convex f on ℝⁿ with some x ∈ ri (dom f) satisfying x ≥ 0,
inf {f(x) | x ≥ 0} = -inf {f*(x*) | x* ≥ 0}.
This is Theorem 31.4 at the non-negative orthant, whose dual cone is itself
(neg_polarCone_nonnegOrthant). Rockafellar's condition asks only x ≥ 0, not x ∈ ri K, which
is the polyhedral form of Theorem 31.4 — the orthant is polyhedral.
Corollary 31.4.1: under (a) the second infimum is attained.
Corollary 31.4.1 under condition (b): the same equality from a point x* ∈ ri (dom f*)
with x* ≥ 0.
Corollary 31.4.1: under (b) the first infimum is attained.
Corollary 31.4.1, the complementary-slackness conditions: the two
infima are the negatives of each other and attained at x and x* exactly when x* ∈ ∂f(x) and
ξⱼ ≥ 0, ξⱼ* ≥ 0, ξⱼ ξⱼ* = 0 for every j.
Theorem 31.4's ⟨x, x*⟩ = 0 becomes the coordinatewise condition because both vectors are
non-negative (pairing_eq_zero_iff_of_mem_nonnegOrthant).
Corollary 31.4.2: a subspace #
The polar cone of a subspace is its orthogonal complement. Rockafellar writes L⊥; the
backbone's polarCone of a subspace is the annihilator (polarCone_coe_submodule'), and on ℝⁿ
the annihilator is Lᗮ.
Corollary 31.4.2 under condition (a): for a closed proper
convex f and a subspace L meeting ri (dom f),
inf {f(x) | x ∈ L} = -inf {f*(x*) | x* ∈ L⊥}.
This is Theorem 31.4 with K = L, where the dual cone K* = -K° collapses to L⊥. A subspace is
polyhedral, which is why Rockafellar's condition needs no relative interior on the L side.
Corollary 31.4.2: under (a) the infimum of f* on L⊥ is attained.
Corollary 31.4.2: under condition (b) the infimum of f on L is attained.
Corollary 31.4.2, the optimality conditions: over a subspace the orthogonality ⟨x, x*⟩ = 0
of Theorem 31.4 is automatic, so x and x* are jointly optimal exactly when x ∈ L, x* ∈ L⊥
and x* ∈ ∂f(x).
Corollary 31.4.3: the duality between a co-finite h and h* #
Corollary 31.4.3: for h convex on ℝⁿ, finite everywhere and co-finite, and K a
nonempty convex cone,
inf_{x ∈ K} {h(z + x) - ⟨z*, x⟩} + inf_{x* ∈ K*} {h*(z* + x*) - ⟨z, x*⟩} = ⟨z, z*⟩.
The proof is Theorem 12.3 followed by Theorem 31.4: f = h(z + ·) - ⟨·, z*⟩ has dom f = ℝⁿ
and dom f* = ℝⁿ, so both of Rockafellar's conditions hold in their strongest form. Closedness of
K, which the book assumes throughout the corollary, is needed only for the attainment of the
first infimum.
Corollary 31.4.3: the first infimum is finite.
Corollary 31.4.3: the second infimum is finite.
Corollary 31.4.3: the first infimum is attained. This is the clause that needs K
closed.
Corollary 31.4.3: the second infimum is attained. Co-finiteness is not needed for this half,
nor is closedness of K.
Theorem 31.5 (Moreau), proximations, and the two corollaries #
w is the backbone's quadFn (pairing n), and theorem_31_5_quadFn is the bridge to
Rockafellar's w(z) = ½|z|². □ is infConv, prox (z ∣ f) is prox (pairing n) f z, and
moreauObj (pairing n) f z is the objective x ↦ f(x) + w(z - x) whose infimum defines
(f □ w)(z).
Theorem 31.5: w(z) = ½|z|², in the book's own notation. Specialises quadFn_innerL.
Theorem 31.5 (Moreau), the identity (f □ w) + (f* □ w) = w as an equation between
functions. The backbone's proof is Theorem 27.1(a) applied to f + w(z - ·), with
IsExactSum.conj_add_apply splitting the conjugate of that sum at the origin — no separation and no
ri.
Theorem 31.5, the identity written out at a point:
inf_x {f(x) + w(z - x)} + inf_{x*} {f*(x*) + w(z - x*)} = w(z).
Theorem 31.5: "both infima are finite". Specialises infConv_quadFn_ne_bot and
infConv_quadFn_ne_top.
Theorem 31.5: the dual infimum is finite too.
Theorem 31.5: the two infima are uniquely attained, and the unique
minimisers are the unique pair with z = x + x* and x* ∈ ∂f(x).
The backbone's uniqueness is monotonicity of ∂f (Theorem 24.8) at the two pairs, not strict
convexity of w; attainment is Theorem 27.2, through the recession function of f + w(z - ·).
Specialises existsUnique_sub_mem_subgradient.
Theorem 31.5, the characterisation of the minimiser: x attains inf_x {f(x) + w(z - x)}
exactly when z - x ∈ ∂f(x). Specialises mem_argmin_moreauObj_iff.
Theorem 31.5: prox (z ∣ f) is the unique minimiser, so the minimum set is a singleton.
Specialises argmin_moreauObj_eq_singleton.
§31, the defining property of the proximation: prox (z ∣ f) is the unique x with
z - x ∈ ∂f(x). Specialises prox_eq_iff.
§31: the decomposition z = prox (z ∣ f) + prox (z ∣ f*).
§31: prox (z ∣ f*) = z - prox (z ∣ f). Specialises prox_conj_eq.
Theorem 31.5: x* = ∇(f □ w)(z), the gradient formula for the Moreau envelope of f. The
subdifferential of f □ w is the single point prox (z ∣ f*), so Theorem 25.1's converse upgrades
it to a gradient. Specialises gradient_infConv_quadFn.
Theorem 31.5: x = ∇(f* □ w)(z). Specialises gradient_infConv_conj_quadFn.
§31: prox (· ∣ f) is the gradient mapping of the differentiable convex function f* □ w,
hence continuous (Corollary 25.5.1). Specialises continuous_prox.
The contraction property of prox, which Rockafellar states and proves in unnumbered
running text and on which Corollary 31.5.2 is built: |prox (z₁ ∣ f) - prox (z₀ ∣ f)| ≤ |z₁ - z₀|.
With xᵢ = prox (zᵢ ∣ f) and xᵢ* = zᵢ - xᵢ, expanding |z₁ - z₀|² and dropping the cross term by
monotonicity of ∂f gives |z₁ - z₀|² ≥ |x₁ - x₀|².
The contraction property of prox, packaged as a Lipschitz bound with constant 1.
Specialises lipschitzWith_prox.
§31: "the range of prox (· ∣ f) is of course dom ∂f". Unnumbered, and one line in each
direction: z - prox (z ∣ f) ∈ ∂f (prox (z ∣ f)) gives ⊆, and a subgradient y ∈ ∂f(x) exhibits
x as prox (x + y ∣ f).
Corollary 31.5.1 — stated in the book with no proof at all. The mapping (x, x*) ↦ x + x*
is one-to-one from the graph of ∂f onto ℝⁿ and continuous in both directions, so that graph is
homeomorphic to ℝⁿ. A Homeomorph is that statement: bijectivity is Theorem 31.5, and
continuity of the inverse z ↦ (prox (z ∣ f), z - prox (z ∣ f)) is prox_contraction. Theorem 24.4
is not used.
Instances For
Corollary 31.5.2: ∂f is a maximal monotone mapping from ℝⁿ to ℝⁿ. Given (y, y*)
outside the graph, Theorem 31.5 produces (x, x*) in the graph with x + x* = y + y*, and then
⟨y - x, y* - x*⟩ = -|y - x|² < 0. This is monotone maximality, not the cyclically monotone
maximality of Theorem 24.9; the book warns explicitly that neither implies the other.
Theorem 31.2: Fenchel's problem as a convex program #
Rockafellar exhibits the Fenchel problem as the convex program of §29 attached to the bifunction
(F u)(x) = f x - g (A x + u): the perturbation translates the concave function. The whole
machinery of §§29–30 then applies, and Corollary 31.2.1 is what Theorem 30.4 and Corollary 30.5.2
give back.
The Fenchel bifunction (F u)(x) = f x - g (A x + u): the Fenchel problem inf (f - g ∘ A)
perturbed by translating the concave function.
Equations
- Rockafellar.fenchelBifun A f g u x = f x - g (A x + u)
Instances For
Theorem 31.2, first assertion: F is a convex bifunction.
Theorem 31.2, second assertion: F is proper. Properness is automatic — it needs no
relative-interior hypothesis, only a point of dom f and a point of dom g, which Proper and
ProperConcave supply.
Theorem 31.2, third assertion: F is closed when f and g are.
Theorem 31.2: the optimal value of the convex program attached to F is the Fenchel infimum
inf {f x - g (A x)}.
Theorem 31.2: dom F = dom g - A (dom f).
Theorem 31.2: ri (dom F) = ri (dom g) - A (ri (dom f)), by Theorem 6.6 and Corollary 6.6.2
(relint_sub_image).
Theorem 31.2: the primal program is strongly consistent exactly when A (ri (dom f)) meets
ri (dom g) — condition (a) of Theorem 31.1, in program form.
Theorem 31.2: the adjoint of the Fenchel bifunction is
(F* x*)(u*) = g*(u*) - f*(A* u* + x*).
Theorem 31.2: the optimal value of the dual concave program is sup {g*(u*) - f*(A* u*)}.
The concave effective domain of F* is dom f* - A* (dom g*): the mirror of
theorem_31_2_domBifun.
Theorem 31.2: the dual program is strongly consistent exactly when A* (ri (dom g*)) meets
ri (dom f*) — condition (b) of Corollary 31.2.1, in program form.
Corollary 31.2.1 under condition (b): if ri (dom g*) contains a u* with
A* u* ∈ ri (dom f*) then the Fenchel duality equation holds. This is Theorem 31.2 followed by
Theorem 30.4(b) and Theorem 30.3.
Corollary 31.2.1 under condition (b), attainment clause: the infimum is attained at some
x.