Rockafellar, §13: Support Functions #
The support function δ*(· | C) of a convex set, the bijection between closed convex sets and
closed proper positively homogeneous convex functions, and the derivation of the support functions
of dom f, dom f* and of a level set {x | f x ≤ 0} from the conjugate f*. All 15 numbered
results of §13 are formalized. Theorem 13.2's bijection is theorem_13_2_correspondence.
The section's definitions #
- The support function
δ*(x* | C) = sup {⟨x, x*⟩ | x ∈ C}is the backbone'ssupportFn;supportFn_apply_rnrecords that it is the book's formula verbatim. - The barrier cone of
Cisdom δ*(· | C), recorded asbarrierCone, with the bridgebarrierCone_eq_dom_supportFnand the unfolded formmem_barrierCone_iff. - Co-finite is the backbone's
Cofinite: closed, proper, convex, andf0⁺ = +∞in every non-zero direction — the epigraph contains no non-vertical half-line. - Rank is
rankFn f = dim (dom f) - lineality f, defined here rather than in §8 because it needs §1's affine-hull dimensiondim; Corollary 13.4.1 is its first consumer.
The unnumbered running text of the section is recorded too: the infimum formula
inf {⟨x, x*⟩ | x ∈ C} = -δ*(-x* | C) (infimum_eq_neg_supportFn_neg); the half-space description
C ⊆ {x | ⟨x, x*⟩ ≤ β} ↔ β ≥ δ*(x* | C) (subset_halfspace_iff); the invariance
δ*(·|C) = δ*(·|cl C) = δ*(·|ri C); the additivity δ*(·|C₁+C₂) = δ*(·|C₁) + δ*(·|C₂); the
recovery of a closed convex set from its support function (eq_setOf_le_supportFn); the
subadditivity noted after Theorem 13.2; and the Euclidean-norm example |x| = δ*(x | B) with its
translate-and-scale form.
References #
- R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §13.
The definitions of §13 #
Rockafellar's support function (§13, p. 112): δ*(x* | C) = sup {⟨x, x*⟩ | x ∈ C}. This is
the backbone's supportFn (pairing n) C, and the equation is the definition unfolded.
Rockafellar's barrier cone (§13, p. 112): the effective domain of δ*(· | C), the set of
directions in which a linear function is bounded above on C.
Equations
Instances For
The bridge: the barrier cone is dom δ*(· | C).
The barrier cone unfolded: x* is a barrier direction exactly when ⟨·, x*⟩ is bounded above
on C.
Rockafellar's co-finite convex functions (§13, p. 116): closed proper convex functions whose
epigraph contains no non-vertical half-line, i.e. with (f0⁺)(y) = +∞ for every y ≠ 0. This is
the backbone's Cofinite, transcribed without change.
Rockafellar's rank of a convex function (§8, p. 70): rank f = dim f - lineality f, where
dim f is the dimension of dom f and the lineality of f is the dimension of its lineality
space. Defined here rather than in §8 because it needs §1's dim; Corollary 13.4.1 is the first
result that uses it.
Equations
Instances For
Properness of the conjugate #
Rockafellar states Theorems 13.3 and 13.4 for a proper convex f; the backbone asks in addition
that f* be proper, which in ℝⁿ is automatic — Theorem 12.2, through Theorem 7.4.
The unnumbered running text of pp. 112–114 #
Rockafellar, §13, p. 112: minimisation of linear functions over C is covered too, since
inf {⟨x, x*⟩ | x ∈ C} = -δ*(-x* | C).
Rockafellar, §13, p. 112: the support function describes all the closed half-spaces
containing C — C ⊆ {x | ⟨x, x*⟩ ≤ β} if and only if β ≥ δ*(x* | C).
Rockafellar, §13, p. 112: the support function does not see the closure.
Rockafellar, §13, p. 112: nor does it see the relative interior, for convex C.
Rockafellar, §13, p. 113: addition of sets is converted into addition of functions.
Rockafellar, §13, p. 113: a closed convex set is the solution set of the system of inequalities given by its support function, so it is completely determined by it.
Rockafellar, §13, p. 114: the Euclidean norm is the support function of the unit ball.
Rockafellar, §13, p. 114: the support function of the ball a + λB, λ ≥ 0, is
⟨x, a⟩ + λ|x|.
Theorem 13.1 #
Theorem 13.1, first clause. Let C be a convex set. Then x ∈ cl C if and
only if ⟨x, x*⟩ ≤ δ*(x* | C) for every vector x*.
Specialises mem_closure_convexHull_iff_le_supportFn — Corollary 11.5.1 read through the
pairing.
Theorem 13.1, second clause. x ∈ ri C if and only if the same condition holds, with strict
inequality for each x* such that -δ*(-x* | C) ≠ δ*(x* | C). Specialises
mem_relint_iff_lt_supportFn — Corollary 11.6.2 read through the pairing.
Theorem 13.1, third clause. x ∈ int C if and only if ⟨x, x*⟩ < δ*(x* | C)
for every x* ≠ 0.
The book omits C ≠ ∅, and the clause is false without it — over the zero space the condition
is vacuous while int ∅ = ∅.
Theorem 13.1, fourth clause. Assuming C ≠ ∅, x ∈ aff C if and only if
⟨x, x*⟩ = δ*(x* | C) for every x* with -δ*(-x* | C) = δ*(x* | C).
It needs no convexity: the reversible directions describe the hyperplanes containing C, and
Corollary 1.4.1 intersects them.
Corollary 13.1.1. For convex sets C₁ and C₂ in ℝⁿ, one has
cl C₁ ⊆ cl C₂ if and only if δ*(· | C₁) ≤ δ*(· | C₂).
Theorem 13.2 #
Theorem 13.2, first assertion, one direction: the support function of a set is the conjugate of its indicator function.
Theorem 13.2, first assertion: the indicator function and the support function of a closed convex set are conjugate to each other.
Theorem 13.2, second assertion: the functions which are the support functions of non-empty convex sets are exactly the closed proper convex functions which are positively homogeneous.
Since δ* sees neither the closure nor the convex hull, the class of sets may be narrowed to the
non-empty closed convex ones, and that is what makes the correspondence one-to-one.
Theorem 13.2 as the "important one-to-one correspondence between the closed
convex sets in ℝⁿ and objects of quite a different sort, certain functions on ℝⁿ".
Equations
Instances For
Rockafellar, §13, p. 115, the consequence drawn immediately after Theorem 13.2:
δ*(· | C) is subadditive.
Corollary 13.2.1. Let f be a positively homogeneous convex function which is
not identically +∞. Then cl f is the support function of the closed convex set
C = {x* | ∀ x, ⟨x, x*⟩ ≤ f x}.
The improper case is included: if f takes -∞ then cl f ≡ -∞, C is empty, and both sides are
δ*(· | ∅).
Corollary 13.2.2. The support functions of the non-empty bounded convex sets are the finite positively homogeneous convex functions.
Closedness is not part of the statement, being free in ℝⁿ by Corollary 7.4.2; in general it is
not redundant, a discontinuous linear functional being finite, convex and positively homogeneous
without being a support function.
Theorem 13.3 #
Theorem 13.3, first assertion. Let f be a proper convex function. The support function of
dom f is the recession function f*0⁺ of f*. The extra properness hypothesis the backbone
carries is discharged here by proper_conj_of_proper.
Theorem 13.3, second assertion. If f is closed, the support function of
dom f* is the recession function f0⁺ of f.
Corollary 13.3.1. Let f be a closed convex function on ℝⁿ. In order that
f* be finite everywhere, so that dom f* = ℝⁿ, it is necessary and sufficient that f be
co-finite.
Corollary 13.3.2 #
The book leaves its key step as an exercise: a convex set is affine iff every linear function
bounded above on it is constant on it. That is affine_iff_forall_reversible below.
The step Rockafellar leaves as an exercise: a non-empty convex set C is
affine if and only if every linear function bounded above on C is constant on it — that is, if
and only if -δ*(-x* | C) = δ*(x* | C) whenever δ*(x* | C) < +∞.
Corollary 13.3.2. Let f be a closed proper convex function. In order that dom f* be an
affine set, it is necessary and sufficient that (f0⁺)(y) = +∞ for every y which is not actually
in the lineality space of f. The step the book leaves as an exercise is
affine_iff_forall_reversible above.
Corollary 13.3.3 #
Corollary 13.3.3, the quantitative half: for α ≥ 0, the Lipschitz condition
f(z) ≤ f(x) + α|z - x| holds for all x and z exactly when dom f* is contained in the ball
of radius α. This is what "the smallest such α is sup {|x*| : x* ∈ dom f*}" means.
Corollary 13.3.3, first assertion: dom f* is bounded if and only if f
satisfies a global Lipschitz condition.
Corollary 13.3.3, the "f is finite everywhere" clause: the Lipschitz
condition forces a proper f to be real-valued.
Corollary 13.3.4 #
The book sets g (x) = f (x) - ⟨x, x*⟩, so that (g0⁺)(y) = (f0⁺)(y) - ⟨y, x*⟩; the four clauses
below are stated through f0⁺ and ⟨y, x*⟩ directly, which makes the translation by -x*
disappear. Rockafellar's exception set in (b) is y-independent for this reason.
Corollary 13.3.4(a). x* ∈ cl (dom f*) if and only if (g0⁺)(y) ≥ 0 for
every y. Specialises mem_closure_dom_conj_iff.
Corollary 13.3.4(b). x* ∈ ri (dom f*) if and only if (g0⁺)(y) > 0 for all
y except those with -(g0⁺)(-y) = (g0⁺)(y) = 0. Specialises mem_relint_dom_conj_iff.
Corollary 13.3.4(c). x* ∈ int (dom f*) if and only if (g0⁺)(y) > 0 for
every y ≠ 0. Specialises mem_interior_dom_conj_iff.
Corollary 13.3.4(d). x* ∈ aff (dom f*) if and only if (g0⁺)(y) = 0 for
every y with -(g0⁺)(-y) = (g0⁺)(y). Specialises mem_affineSpan_dom_conj_iff.
Theorem 13.4 #
Theorem 13.4, first assertion. Let f be a proper convex function on ℝⁿ.
The lineality space of f* is the orthogonal complement of the subspace parallel to
aff (dom f).
In an inner-product space the annihilator of a subspace is its orthogonal complement, which is the
book's phrasing, and vectorSpan ℝ (dom f) is the subspace parallel to aff (dom f).
Theorem 13.4, second assertion. If f is closed, the subspace parallel to
aff (dom f*) is the orthogonal complement of the lineality space of f.
Stated in the equivalent form lineality f = (vectorSpan (dom f*))ᗮ; a subspace of ℝⁿ is its
own double complement, so this is the book's phrasing.
Theorem 13.4, first dimensionality formula:
lineality f* = n - dimension f.
Theorem 13.4, second dimensionality formula:
dimension f* = n - lineality f.
Corollary 13.4.1. Closed proper convex functions conjugate to each other have the same rank.
Immediate from the two dimensionality formulas of Theorem 13.4 and the definition of rank:
rank f* = (n - lineality f) - (n - dim f) = dim f - lineality f = rank f.
Corollary 13.4.2. Let f be a closed proper convex function. Then dom f* has
a non-empty interior if and only if there are no lines along which f is (finite and) affine.
Theorem 13.5 #
Theorem 13.5, first assertion. Let f be a closed proper convex function. The
support function of {x | f x ≤ 0} is cl g, where g is the positively homogeneous convex
function generated by f*.
Properness is not needed: Fenchel–Moreau in the form biconj_eq_self already covers the improper
cases.
Theorem 13.5, second assertion. The closure of the positively homogeneous convex function
k generated by f is the support function of {x* | f*(x*) ≤ 0}. It needs no hypothesis at
all.
Corollary 13.5.1. Let f be a closed proper convex function on ℝⁿ. The
function k on ℝⁿ⁺¹ given by k (λ, x) = (fλ)(x) for λ > 0, (f0⁺)(x) for λ = 0 and +∞
for λ < 0 is the support function of C = {(λ*, x*) | λ* ≤ -f*(x*)}.
Identifying the book's three-case k with cl (hom f) is Corollary 8.5.2, a §8 statement, and is
not repeated here.