Alexandrov's theorem: convex functions are twice differentiable almost everywhere #
Let E be a finite-dimensional real inner product space with an additive Haar measure μ, and
let f : E → EReal be convex (convex real epigraph, never ⊥), with real representative
F x = (f x).toReal. Alexandrov's theorem says that at μ-almost every point x of the
effective domain, F has a second-order Taylor expansion
F x' = F x + ⟪∇F x, x' - x⟫ + ⟪A (x' - x), x' - x⟫ / 2 + o(‖x' - x‖ ^ 2)
with a positive (symmetric, positive semidefinite) operator A, the Alexandrov Hessian of F at
x; it is the only symmetric operator giving such an expansion. The stronger statement proved
here is that the subdifferential ∂f itself is differentiable at x with derivative A: every
subgradient y' of f at a point x' near x satisfies y' = ∇F x + A (x' - x) + o(‖x' - x‖).
The proof goes through the resolvent of the subdifferential. If y₁ ∈ ∂f(x₁) and y₂ ∈ ∂f(x₂),
then ‖x₁ - x₂‖ ≤ ‖(x₁ + y₁) - (x₂ + y₂)‖, by monotonicity of ∂f; so x + y ↦ x is a
well-defined 1-Lipschitz map J on the set of points x + y with y ∈ ∂f(x), the resolvent
(I + ∂f)⁻¹. Extend it to a Lipschitz map on E. By Rademacher's theorem it is differentiable
off a null set, and Lipschitz maps send null sets to null sets; by Sard's lemma it sends the points
where its derivative is singular to a null set. At almost every x the real representative is
differentiable and x avoids both of these null images; since J (x + ∇F x) = x, the map J is
then differentiable at z = x + ∇F x with invertible derivative L. Inverting the expansion of
J at z gives the expansion of ∂f at x, with A = L⁻¹ - I.
The second-order expansion of F follows from that of ∂f with no convexity: on the segment from
x to x', split into n steps, the increments of F are squeezed between the subgradient
inequalities at the ends of each step, and summing them gives the expansion up to an error of
order (‖A‖ / n + ε) * ‖x' - x‖ ^ 2. Comparing that expansion with the subgradient inequality at
nearby points shows that A is symmetric and positive semidefinite. Both expansions determine
A: two derivatives of the subdifferential differ by a map that is o(‖x' - x‖), and two symmetric
second-order terms differ by a quadratic form that is o(‖x' - x‖ ^ 2), hence zero.
Main statements #
TauCeti.mul_norm_sub_le_norm_smul_add_smul_sub_of_mem_subdifferential— the interpolationx ↦ (1 - t) • x + t • y,y ∈ ∂f(x), expands distances by at least the factor1 - t;TauCeti.norm_sub_le_norm_add_sub_add_of_mem_subdifferential— the resolvent of the subdifferential is nonexpansive;TauCeti.isLittleO_of_forall_mem_subdifferential_norm_sub_le— a first-order expansion of the subdifferential atxgives a second-order Taylor expansion ofFatx;TauCeti.hasGradientAt_toReal_of_forall_mem_subdifferential_norm_sub_le— the centreyof a first-order expansion of the subdifferential atxis the gradient ofFatx;TauCeti.subdifferential_eq_singleton_gradient_of_forall_mem_subdifferential_norm_sub_le— the subdifferential at such a pointxis the single gradient∇F x;TauCeti.hasFDerivWithinAt_gradient_toReal_of_forall_mem_subdifferential_norm_sub_le— the derivative of the subdifferential atxis the derivative of∇Fatxwithin any set of points where∇Fis a subgradient;TauCeti.isPositive_of_forall_mem_subdifferential_norm_sub_le— the derivative of the subdifferential is a positive operator;TauCeti.eq_of_forall_mem_subdifferential_norm_sub_le— the derivative of the subdifferential is unique;TauCeti.apply_sub_eq_zero_of_forall_mem_subdifferential_norm_sub_le— the derivative of the subdifferential vanishes along a segment on which a subgradient is shared;TauCeti.ae_existsUnique_isPositive_forall_mem_subdifferential_norm_sub_le— Alexandrov's theorem for the subdifferential: it is differentiable, with a unique and positive derivative, almost everywhere on the effective domain;TauCeti.ae_existsUnique_isPositive_isLittleO— Alexandrov's theorem:Fhas a second-order Taylor expansion with a unique positive Hessian almost everywhere on the effective domain;ConvexOn.ae_existsUnique_isPositive_isLittleO— the same for a real convex function on a set.
References #
- A. D. Alexandrov, Almost everywhere existence of the second differential of a convex function and some properties of convex surfaces connected with it, Leningrad State Univ. Annals [Uchenye Zapiski] Math. Ser. 6 (1939), 3–35.
- F. Mignot, Contrôle dans les inéquations variationelles elliptiques, J. Functional Analysis 22 (1976), 130–185, for the route through the resolvent of a monotone operator.
- G. Alberti and L. Ambrosio, A geometrical approach to monotone functions in
ℝⁿ, Math. Z. 230 (1999), 259–316, Theorem 7.10. - R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren 317, Springer 1998, Theorem 13.51.
The interpolation towards the subdifferential is expanding. If y₁ ∈ ∂f(x₁),
y₂ ∈ ∂f(x₂) and 0 ≤ t, then
(1 - t) * ‖x₁ - x₂‖ ≤ ‖((1 - t) • x₁ + t • y₁) - ((1 - t) • x₂ + t • y₂)‖. In particular, for
t < 1 the interpolating map x ↦ (1 - t) • x + t • y, y ∈ ∂f(x), is injective.
The resolvent of the subdifferential is nonexpansive. If y₁ ∈ ∂f(x₁) and y₂ ∈ ∂f(x₂),
then ‖x₁ - x₂‖ ≤ ‖(x₁ + y₁) - (x₂ + y₂)‖. Thus x + y ↦ x, for y ∈ ∂f(x), is a well-defined
1-Lipschitz map, the resolvent (I + ∂f)⁻¹.
A first-order expansion of the subdifferential gives a second-order expansion of the
function. Suppose f : E → EReal has subgradients at every point near x, and that these
follow the expansion y' = y + A (x' - x) + o(‖x' - x‖) uniformly over the subdifferential at
x'. Then the real representative of f has the second-order Taylor expansion
F x' = F x + ⟪y, x' - x⟫ + ⟪A (x' - x), x' - x⟫ / 2 + o(‖x' - x‖ ^ 2). No convexity is
needed.
A first-order expansion of the subdifferential gives the gradient. Suppose f : E → EReal
has subgradients at every point near x, and that these follow the expansion
y' = y + A (x' - x) + o(‖x' - x‖) uniformly over the subdifferential at x'. Then the real
representative of f has gradient y at x. No convexity is needed.
A first-order expansion of the subdifferential makes it the single gradient. Suppose
f : E → EReal has subgradients at every point near x, and that these follow the expansion
y' = y + A (x' - x) + o(‖x' - x‖) uniformly over the subdifferential at x'. Then the
subdifferential of f at x is the single gradient of the real representative of f at x. No
convexity is needed.
The derivative of the gradient within a set of subgradients. Let t be a set at each point
of which the gradient of the real representative F of f : E → EReal is a subgradient of f.
If the subdifferential of f has the expansion y' = ∇F x + A (x' - x) + o(‖x' - x‖) at x,
then the gradient ∇F has derivative A within t at x. No convexity is needed.
The derivative of the subdifferential is positive. If the subgradients of f : E → EReal
near x follow the expansion y' = y + A (x' - x) + o(‖x' - x‖), and exist at every point near
x, then A is a positive operator: symmetric with ⟪A v, v⟫ ≥ 0.
The derivative of the subdifferential is unique. If f : E → EReal has subgradients at
every point near x, and these follow both expansions y' = y + A (x' - x) + o(‖x' - x‖) and
y' = y + B (x' - x) + o(‖x' - x‖), then A = B.
The derivative of the subdifferential kills the direction of a flat segment. Let
f : E → EReal be convex, and let y be a subgradient of f at both x₁ and x₂. If the
subgradients of f near x₁ follow the expansion y' = y + A (x' - x₁) + o(‖x' - x₁‖), then
A (x₂ - x₁) = 0. So when x₁ ≠ x₂ the operator A is singular: a point at which the
derivative of the subdifferential is invertible shares none of its subgradients with another
point.
Alexandrov's theorem for the subdifferential. Let f : E → EReal be convex (convex real
epigraph, never ⊥) on a finite-dimensional real inner product space with an additive Haar measure
μ. At μ-almost every point x of the effective domain, the subdifferential of f is
differentiable with a positive derivative A: every subgradient y' of f at a point x' near
x satisfies y' = ∇F x + A (x' - x) + o(‖x' - x‖), where F x = (f x).toReal. The operator A
is the only positive operator with this expansion; uniqueness among all operators is
eq_of_forall_mem_subdifferential_norm_sub_le.
Alexandrov's theorem. Let f : E → EReal be convex (convex real epigraph, never ⊥) on a
finite-dimensional real inner product space with an additive Haar measure μ, and let
F x = (f x).toReal. At μ-almost every point x of the effective domain, F has a
second-order Taylor expansion
F x' = F x + ⟪∇F x, x' - x⟫ + ⟪A (x' - x), x' - x⟫ / 2 + o(‖x' - x‖ ^ 2)
with a positive operator A, the only positive operator giving such an expansion.
Alexandrov's theorem for a real convex function. Let u be convex on a set Ω of a
finite-dimensional real inner product space with an additive Haar measure μ. At μ-almost every
point x of Ω, u is differentiable and has a second-order Taylor expansion
u x' = u x + ⟪∇u x, x' - x⟫ + ⟪A (x' - x), x' - x⟫ / 2 + o(‖x' - x‖ ^ 2) with a positive
operator A, the only positive operator giving such an expansion.