Fenchel's duality theorem #
Minimising a difference f - g, with f convex and g concave, is dual to maximising g* - f*,
where g* is the concave conjugate. Weak duality g*(y) - f*(y) ≤ f x - g x is Fenchel's
inequality used twice and needs no hypothesis at all; equality, and attainment on one of the two
sides, needs f and -g to add exactly. A linear transformation may be interposed between the two
functions; the Kuhn–Tucker conditions y ∈ ∂f x, -y ∈ ∂(-g) x characterise a jointly optimal
pair; and the whole specialises to minimising over a convex cone K, where the dual problem is
minimising f* over K* = -K°.
Main results #
concaveConj_sub_conj_le_sub— weak duality, pointwise.fenchel_duality,exists_concaveConj_sub_conj_eq— Fenchel's duality theorem under condition (a):inf (f - g) = sup (g* - f*), with the supremum attained (Theorem 31.1 in [^1]).fenchel_duality_of_closed,exists_sub_eq_iInf— the same under condition (b): the same equality, with the infimum attained.fenchel_duality_comp,exists_concaveConj_sub_conj_comp_eq— the same with a linear transformation interposed:inf (f - g A) = sup (g* - f* A'), with the supremum attained.sub_eq_concaveConj_sub_conj_iff,sub_comp_eq_concaveConj_sub_conj_iff— the Fenchel optimality conditions, with and without the transformation, read as a criterion for minimality byiInf_sub_eq_iff_exists_kuhnTuckerandiInf_sub_comp_eq_iff_exists_kuhnTucker.iInf_mem_eq_neg_iInf_mem_neg_polarCone— the cone form, withexists_mem_neg_polarCone_conj_eq_iInfandexists_mem_eq_iInf_of_isExactSum_conjfor attainment under (a) and (b),iInf_mem_submodule_eq_neg_iInf_mem_polarConefor a subspace.
Implementation notes #
The hypothesis throughout is IsExactSum B f (-g), not a constraint qualification. The book's
condition (a) ri (dom f) ∩ ri (dom g) ≠ ∅, its condition (b) on the conjugates, and the two
polyhedral weakenings of each are all ways of saying that f and -g add exactly, so the theorem
is proved once and every variant is an instance; condition (b) is condition (a) read on the dual
pair. The transformed statement likewise splits the book's transformed condition (a) into two
interfaces, IsExactSum for the sum and IsExactImage for the pullback along A.
References #
[^1]: R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §31.
Weak duality, pointwise: every dual value is below every primal value, by Fenchel's
inequality for f and for g added together. No hypothesis at all is needed — both ∞ - ∞
collisions send the left side to ⊥.
Fenchel's duality theorem: inf (f - g) = sup (g* - f*). This is inf h = -h*(0) applied
to h = f + (-g), with exact addition splitting the conjugate of that sum at the origin.
Attainment: under exact addition the supremum of g* - f* is attained.
The two clauses packaged: the common value is the greatest dual value.
A linear transformation between the two functions #
The concave face of the image rule: the concave conjugate of an inverse image g A is the
supremum of g* over the fibres of the transpose, where the convex statement has an infimum.
Both reflections are at work, so the fibre A' z = -y becomes A' z = y.
The transformed dual program lives on H, not on F. Duality gives a supremum over F;
the concave image rule rewrites each value as a supremum over a fibre of A', and the two suprema
collapse into one over H. Besides the exact-image hypothesis only conj B f ≠ ⊥ is used, so
both conditions (a) and (b) can call it.
Fenchel's duality theorem with a linear transformation:
inf (f - g A) = sup (g* - f* A').
The two hypotheses are the book's condition (a) split in two: hex makes f and -(g A) add
exactly, himg makes g pull back exactly along A, and
ri (dom f) ∩ A⁻¹ (ri (dom g)) ≠ ∅ delivers both.
Attainment: under exact addition and exact pullback the supremum of g* - f* A' is
attained. Two attainment statements chain — duality over F, then the image rule over the fibre —
with the degenerate common value -∞ taken separately.
Condition (b): the closed case, with the infimum attained #
The dual-side reading of the primal value: under condition (b), inf (f - g) is minus
inf (f* - g*). This is fenchel_duality on the pair (f*, g*) over B.flip.
Duality under condition (b): f and g closed, with the conjugates adding exactly. The
equality is the same; what (b) buys is attainment on the primal side.
Under condition (b) the infimum of f - g is attained.
The transformed pair under condition (b) #
The transformed duality equality under condition (b): f and g closed with the
conjugates adding exactly. Where condition (a) delivers attainment on the dual side, (b) delivers
it on the primal side (exists_sub_comp_eq_iInf).
Under condition (b) the infimum of f - g A is attained.
The Fenchel optimality conditions #
Equality in the concave Fenchel inequality: g x + g*(y) = ⟨x, y⟩ says -y ∈ ∂(-g) x.
The book writes this as x ∈ ∂g*(y) with the superdifferential of a concave function,
-∂(-g).
The optimality conditions at A = id: x and y are jointly optimal for the two problems
of Fenchel's duality theorem exactly when y ∈ ∂f x and -y ∈ ∂(-g) x. Both are Fenchel's
inequality holding with equality, and f x - g x = g*(y) - f*(y) squeezes the two inequalities
⟨x, y⟩ ≤ f x + f*(y) and g x + g*(y) ≤ ⟨x, y⟩ together.
A point where the primal and dual values agree already minimises f - g. Only weak duality is
used.
At A = id: under exact addition, x minimises f - g exactly when it carries a Kuhn–Tucker
pair.
Optimality conditions for the transformed pair of problems #
A pair (x, z) is jointly optimal for inf (f - g A) and sup (g* - f* A') exactly when
A' z ∈ ∂f x and A x lies in the superdifferential of g* at z. The superdifferential of a
concave function is -∂ of its negative, so the second condition reads -z ∈ ∂(-g)(A x) and no
new notion is needed.
These are the Kuhn–Tucker conditions for the transformed pair of programs.
Weak duality for the transformed problem: every value of g* - f* A' is below every value
of f - g A. Nothing is needed beyond the adjointness datum identifying ⟨A x, z⟩' with
⟨x, A' z⟩.
x and z are jointly optimal for the two transformed programs exactly when A' z ∈ ∂f x
and -z ∈ ∂(-g)(A x). The proof is the one at A = id, with the shared finite value
⟨x, A' z⟩ = ⟨A x, z⟩'.
A point where the primal and dual values agree already minimises f - g A.
The same pair maximises g* - f* A'.
Under the two exactness hypotheses, x minimises f - g A exactly when it carries a
Kuhn–Tucker pair. The forward direction needs the attainment clause to produce the multiplier; the
backward one is weak duality alone.
Minimising over a convex cone #
The cone form: minimising a convex function over a convex cone K is dual to minimising
its conjugate over K* = -K°. Rather than through duality with g = -δ(· | K), this goes to the
source both proofs share: inf h = -h*(0) applied to h = f + δ(· | K), with the sum's conjugate
split at the origin and the conjugate of an indicator evaluating the second factor. The 0 - y
produced by the splitting is the sign flip turning K° into K*.
The same in constrained notation: inf {f x | x ∈ K} = -inf {f*(y) | y ∈ K*}.
Weak duality for the cone program: every dual value is below every primal value.
Optimality conditions for the cone program: for x ∈ K and y ∈ K* the primal and dual
values agree exactly when y ∈ ∂f x and ⟨x, y⟩ = 0. These are the Fenchel conditions for
g = -δ(· | K).
The optimality conditions make x optimal for the primal cone program. Only ⟨x, y⟩ = 0 and
y ∈ K* are used.
The optimality conditions make y optimal for the dual cone program.
Attainment of the two infima #
The dual value read at the origin: (f + δ(·|K))* 0 is the dual infimum
inf {f*(y) | y ∈ K*}. This is what turns exactness of the sum into attainment.
Attainment under condition (a): as soon as f and δ(·|K) add exactly, the dual
infimum is attained. It is read straight off IsExactSum: the splitting 0 = y₁ + y₂ at the
origin already is a minimising y₁ ∈ K*, since the second conjugate factor is the indicator of
K°. The degenerate branch y₂ ∉ K° forces the dual infimum to ⊤, attained at the origin.
The two infima added rather than negated: when the dual infimum is finite the duality equation says the two values sum to zero.
Minimising over a subspace #
The polar cone of a subspace is closed under negation, so K* and K° coincide there:
both are the annihilator L^⊥ = {y | ∀ x ∈ L, ⟨x, y⟩ = 0}.
inf {f x | x ∈ L} = -inf {f*(y) | y ∈ L^⊥} for a subspace L, where K* = -K° collapses to
K° itself.
Over a subspace the orthogonality ⟨x, y⟩ = 0 is automatic, so the primal and dual values
agree exactly when y ∈ ∂f x.
Attainment of the primal infimum #
Attainment of the primal infimum is Rockafellar's condition (b), which is condition (a) read on
the dual pair. It is the previous section's statement applied to f* and K*, with K** = K
(neg_polarCone_neg_polarCone) and f** = f (Fenchel–Moreau) closing the circle; the bipolar is
what makes this section layer C rather than layer A.
Attainment under condition (b): when f* and δ(·|K*) add exactly, the primal infimum
is attained. biconj B f = f is taken as a hypothesis rather than derived, so that the statement
stays free of a compatibility assumption on the F side.