Existence of subgradients #
A proper convex function is subdifferentiable at every relative interior point of its effective
domain, and a polyhedral convex function is subdifferentiable wherever it is finite. In both cases
the directional derivative f'(x; ·) is exactly the support function of ∂f x, not merely its
closure.
That cl (f'(x; ·)) = δ*(· | ∂f x) for any convex f finite at x is already known, so both
existence theorems reduce to one question: is f'(x; ·) closed? At a relative interior point
its effective domain is the subspace parallel to aff (dom f), and a proper convex function with
affine effective domain is closed. For polyhedral f, the epigraph of f'(x; ·) is the convex
cone generated by epi f - (x, f x), which is again polyhedral and in particular closed. Once
f'(x; ·) is closed, nonemptiness of ∂f x follows at once: the support function of the empty set
is the constant −∞, while f'(x; 0) = 0.
The first consumer of that identity on the other side is here too: the normal cone to the level set
{z | f z ≤ f x} is the closed convex cone generated by ∂f x. So is the non-existence
statement that where there is no subgradient the directional derivative is −∞ in every direction
pointing into ri (dom f).
Main results #
dirDeriv_eq_supportFn_of_mem_relint_dom,subgradient_nonempty_of_mem_relint_dom— subdifferentiability on the relative interior (Theorem 23.4 in [^1]);bddAbove_subgradient_iff_mem_interior_domis its last clause, that∂f xis bounded exactly whenxis an interior point ofdom f.dirDeriv_eq_supportFn_of_polyhedralFn,subgradient_nonempty_of_polyhedralFn,polyhedral_subgradient_of_polyhedralFn— the polyhedral case (Theorem 23.10 in [^1]).normalCone_setOf_le_eq_closure_coe_hull_subgradient— the normal cone to a level set;normalCone_setOf_le_eq_coe_hull_subgradientdrops the closure when∂f xis bounded.mem_interior_of_normalCone_eq_zero— a convex set is a neighbourhood of every point at which its normal cone is trivial.subgradient_eq_empty_iff_exists_dirDeriv_eq_bot— failure of subdifferentiability is exactly a−∞value off'(x; ·).
Implementation notes #
The two existence theorems share their last two steps: dirDeriv_eq_supportFn_of_closedFn and
subgradient_nonempty_of_closedFn_dirDeriv take ClosedFn (dirDeriv f x) as a hypothesis, and
only the supply of that hypothesis differs between the two.
References #
[^1]: R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §23.
The epigraph of the directional derivative as a cone #
The convex cone generated by epi f - (x, f x) always lies inside the epigraph of
f'(x; ·): the generators are there because f'(x; z - x) ≤ f z - f x, and the epigraph of a
positively homogeneous convex function is a cone.
If the convex cone generated by epi f - (x, f x) is closed, it is the epigraph of
f'(x; ·). Only this inclusion needs the closedness, and it cannot be dropped: for f y = y² at
x = 0 the cone is the open upper half plane together with the origin, while epi (f'(0; ·)) is
the closed upper half plane. For polyhedral f the cone is finitely generated, hence closed.
The epigraph of f'(x; ·) is the convex cone generated by epi f - (x, f x), whenever that
cone is closed.
The common ending: a closed directional derivative #
The closure removed. As soon as f'(x; ·) is closed it is the support function of
∂f x; this is the last step of both existence theorems.
Subdifferentiability from closedness. The support function of the empty set is the
constant −∞, but f'(x; 0) = 0; so a closed f'(x; ·) forces ∂f x ≠ ∅.
Subdifferentiability on the relative interior #
The effective domain of f'(x; ·) never leaves the subspace parallel to the affine hull of
dom f: a direction along which some difference quotient is finite points from x into dom f.
Unlike the reverse inclusion this needs nothing of x beyond finiteness of f x.
First step: at a relative interior point of dom f the effective domain of f'(x; ·) is the
subspace parallel to the affine hull of dom f.
Both inclusions are elementary: a direction along which the difference quotient is ever finite
points from x into dom f, and conversely a relative interior point can be moved a little in
any direction of the affine hull without leaving dom f.
Second step: at a relative interior point f'(x; ·) is proper. Its effective domain is a
subspace, hence relatively open, so a −∞ value anywhere would spread over all of it — including
the origin, where f'(x; 0) = 0. Relative interiority is essential: for f y = -√y on [0, ∞) and
+∞ elsewhere, f'(0; y) = −∞ for every y > 0 while f'(0; 0) = 0.
Third step: f'(x; ·) is closed, a proper convex function whose effective domain is affine
being closed.
At a relative interior point of dom f the directional derivative is exactly the support
function of the subdifferential.
A proper convex function is subdifferentiable at every relative interior point of its effective domain.
In terms of the directional derivative: f'(x; ·) is finite everywhere exactly when x is an
interior point of dom f.
∂f x is bounded — in the pairing sense, that every ⟨v, ·⟩ is bounded above on it —
exactly when x is an interior point of dom f.
What happens when there is no subgradient #
Every point of dom f gives a direction in the effective domain of f'(x; ·): the difference
quotient at a = 1 is f z - f x, which stays below ⊤ as soon as f x ≠ ⊥.
Directions pointing from x into the relative interior of dom f are relative interior points
of the effective domain of f'(x; ·). This is the geometric core of the non-existence statement
below, proved through the prolongation criterion for relative interiors.
Where a convex function is finite but has no subgradient, the directional derivative is −∞
in every direction pointing into the relative interior of dom f. No properness of f is needed,
the argument running entirely inside f'(x; ·).
The classical proof overshoots in its last sentence, concluding that f'(x; ·) is −∞ throughout
(dom f) - x. That is false: for f y = -√y on [0, ∞) at x = 0 one has ∂f 0 = ∅ and
f'(0; y) = −∞ for every y > 0, but f'(0; 0) = 0 and 0 ∈ (dom f) - x.
In its usual shape: where a convex function is finite but has no subgradient there is an
infinite two-sided directional derivative, f'(x; y) = -f'(x; -y) = −∞.
As a criterion: a convex function finite at x fails to be subdifferentiable there exactly
when f'(x; ·) takes the value −∞ somewhere. Only the forward direction needs the work above;
the converse needs no convexity.
Polyhedral functions #
First step: the directional derivative of a polyhedral convex function at a point where it is
finite is again polyhedral. The cone generated by epi f - (x, f x) is finitely generated, hence
closed, and a closed cone of this kind is epi (f'(x; ·)).
Second step: f'(x; ·) is proper. A lower semicontinuous convex function taking the value
−∞ somewhere is −∞ on the whole closure of its effective domain, and f'(x; 0) = 0.
For a polyhedral convex function the directional derivative is exactly the support function of the subdifferential.
A polyhedral convex function is subdifferentiable at every point where it is finite.
The subdifferential of a polyhedral convex function is a polyhedral convex set: ∂f x is the
effective domain of (f'(x; ·))*, which is the indicator of ∂f x, and the conjugate of a
polyhedral convex function is again polyhedral.
The normal cone to a level set #
Read backwards from the bipolar: cl (cone (∂f x)) is the bipolar (∂f x)°°, its inner polar is
the sublevel set {v | (cl f'(x; ·)) v ≤ 0}, and that set is cl {v | f'(x; v) < 0}.
The normal cone is closed: it is an intersection of half-spaces of F, one for each point
of C.
Every subgradient at x is normal to the level set through x: the elementary half of
the theorem below, being the subgradient inequality read at a point of the level set.
The polar of the subdifferential is a sublevel set of the closed directional derivative.
The normal cone to the level set {z | f z ≤ f x} at x is the closure of the convex cone
generated by the subdifferential at x, provided f x > inf f.
hne says that f is subdifferentiable at x, and hinf that f does not achieve its minimum
there. Neither can be dropped: for f y = -√y on [0, ∞) and +∞ elsewhere, at x = 0 the level
set is [0, ∞) with normal cone (-∞, 0], while ∂f 0 = ∅ generates only {0}; and without
hinf the level set is all of dom f around a minimizer. Properness of f is implied by hne
and so is not asked for separately.
Boundedness of ∂f x with "bounded" read in the norm rather than in the pairing sense. The
pairing form is all a general dual pair supports; the upgrade is what costs the
finite-dimensionality of F.
When ∂f x is bounded — which is the case x ∈ int (dom f) — the closure operation may be
dropped, the cone generated by a nonempty bounded closed convex set missing the origin being
already closed. That the origin is missed is not an extra hypothesis: it is exactly f x > inf f,
the standing hypothesis above.
The same under the hypothesis x ∈ int (dom f), which supplies both non-emptiness and
boundedness of ∂f x. Properness of f is assumed rather than deduced from ∂f x ≠ ∅, because
the relative-interior existence theorem needs it first.
A trivial normal cone means an interior point #
A convex set is a neighbourhood of every point whose normal cone is trivial: the converse of
the obvious x ∈ interior C ⇒ normalCone B C x = {0}, and the supporting-hyperplane theorem in
disguise, since a boundary point of a convex set carries a non-zero supporting functional.
Finite-dimensionality is not decoration. In an infinite-dimensional space a convex set can have empty interior and still be dense — the linear span of an orthonormal basis in a Hilbert space — and then no non-zero functional supports it anywhere, so the normal cone is trivial at every point while the interior is empty. In finite dimensions a convex set with no interior lies in a proper affine subspace, and a functional vanishing on that subspace is normal everywhere.