Duality between a co-finite function and a closed convex cone #
Let h be convex, finite everywhere and co-finite, let K be a nonempty closed convex cone and
let K* = -K°. Then for every z and z*
inf_{x ∈ K} {h (z + x) - ⟨z*, x⟩} + inf_{x* ∈ K*} {h* (z* + x*) - ⟨z, x*⟩} = ⟨z, z*⟩,
with both infima finite and attained: a duality between h and h* parametrised by a point of
each space.
The proof runs through the auxiliary function f = h (z + ·) - ⟨·, z*⟩, whose conjugate is the
dual objective shifted down by the constant ⟨z, z*⟩. Finiteness of h gives dom f = E and
co-finiteness of h gives dom f* = F; those are the two constraint qualifications for duality
between a convex function and a cone, each in its strongest form.
Main results #
iInf_mem_add_iInf_mem_neg_polarCone_eq_pairing— the identity (Corollary 31.4.3 in [^1]).exists_iInf_mem_eq_of_cofinite,exists_iInf_mem_neg_polarCone_eq_of_cofinite— both infima are attained.exists_iInf_mem_eq_coe_of_cofinite,exists_iInf_mem_neg_polarCone_eq_coe_of_cofinite— both infima are finite.
Implementation notes #
Closedness of K is used only for attainment of the primal infimum, whose proof runs through the
bipolar K** = K; the identity, finiteness of both infima and attainment of the dual infimum need
only that K is a nonempty convex cone. Finite-dimensionality enters only through continuity of a
convex function that is finite everywhere, and the everywhere-finite conjugate of a co-finite one.
References #
[^1]: R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §§12, 13, 31.
The translated, tilted function #
When h is finite everywhere so is f: the tilt is real.
f* is the dual objective shifted down by the constant ⟨z, z*⟩, with the two subtractions
collected into a single real summand.
The infimum of f* over K* is the dual infimum for h shifted down by ⟨z, z*⟩; the shift
is a real constant, so it slides out of the infimum.
The cone duality identity #
A co-finite h has an everywhere-finite conjugate.
The dual objective is finite at every point: h* is finite everywhere, and the tilt is real.
f* is finite everywhere, because the conjugate of a co-finite function is.
f is finite everywhere, hence continuous, so it adds exactly to δ(·|K): the constraint
qualification on the primal side.
f* is finite everywhere too, so it adds exactly to δ(·|K*): the constraint qualification on
the dual side, which is what co-finiteness of h supplies.
The dual infimum is not ⊤: the origin lies in K*, where the value is finite.
The dual infimum is not ⊥: its negative is the primal infimum, which is bounded above by a
finite value.
Cone duality. For h convex, finite everywhere and co-finite and K a nonempty convex
cone, the primal infimum over K and the dual infimum over K* = -K° add to ⟨z, z*⟩. Closedness
of K is not needed for the identity.
The dual infimum is attained. Only finiteness of h is used here, not co-finiteness.
The dual infimum is finite, being attained where the objective is.
The primal infimum is finite, being the negative of the dual infimum up to the constant
⟨z, z*⟩.
The primal infimum is attained; this is where co-finiteness of h and closedness of K are
used.