Chapter 17 — Differentiability of Convex Functions
Proofs omitted. Hover over highlighted terms to see their Lean types.
Definition 17.1
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 17.1: ξ is the directional derivative of a proper ]-∞,+∞]-valued function f at x in the direction y when x belongs to the domain of f and the difference quotient (f (x + α • y) - f x) / α tends to ξ as α ↓ 0.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
def HasDirectionalDerivativeAt
(f : H → Set.Ioi (⊥ : EReal)) (x y : H) (ξ : EReal) : Prop :=
x ∈ effectiveDomain f ∧
Filter.Tendsto
(fun α : ℝ ↦ ((f (x + α • y) : EReal) - (f x : EReal)) / α)
(nhdsWithin (0 : ℝ) (Set.Ioi 0)) (nhds ξ)Proposition 17.2
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.2 (1): clause (i). At an effective-domain point of a convex function, the directional derivative exists in the source sense, with value given by the infimum formula.
open scoped Pointwise
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
variable (f : H → Set.Ioi (⊥ : EReal))
notation:arg f "′(" x "; " y ")" => directionalDerivative f x y
notation:arg f "′₊(" x ")" => rightDerivative f x
notation:arg f "′₋(" x ")" => leftDerivative f x
theorem hasDirectionalDerivativeAt_directionalDerivative
(hconv : ConvexOn f (effectiveDomain f))
{x : H} (hx : x ∈ effectiveDomain f) (y : H) :
HasDirectionalDerivativeAt f x y (f′(x; y))Proposition 17.3
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.3: for a convex ]-∞,+∞]-valued function, an effective-domain point x is a global minimizer exactly when every directional derivative at x is nonnegative.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
-- Proof sketch: if `x` is a global minimizer, then every positive directional difference quotient
-- at `x` is nonnegative, so their infimum is nonnegative. Conversely, if every directional
-- derivative at `x` is nonnegative, apply Proposition 17.2 (2) with direction `y - x` to get
-- `f x ≤ f y` for every `y`.
theorem mem_argmin_iff_nonneg_directionalDerivative
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hx : x ∈ effectiveDomain f) :
x ∈ Argmin f.asEReal ↔ ∀ y : H, 0 ≤ f′(x; y)Proposition 17.4
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.4: if a convex ]-∞,+∞]-valued function is Gâteaux differentiable at an effective-domain point x with Gâteaux gradient gradf, then x is a global minimizer exactly when the gradient vanishes.
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: Fermat's rule identifies global minimizers with zeros of the subdifferential.
-- Proposition 17.31 identifies the subdifferential at `x` with the singleton `{gradf}`, so
-- `0 ∈ (∂ f) x` is equivalent to `gradf = 0`.
theorem mem_argmin_iff_gateauxGradient_eq_zero
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hx : x ∈ effectiveDomain f) (gradf : H)
(hgrad :
HasGateauxDerivativeAt (fun z ↦ (f z : EReal).toReal) (toDual ℝ H gradf) x) :
x ∈ Argmin f ↔ gradf = 0Proposition 17.5
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.5: for f ∈ Γ₀(H) and γ ∈ ℝ_{++}, the fixed points of Prox_{γ f} are exactly the points x where f x = {}^γ f x, i.e. the textbook set C.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
theorem fixedPoints_scaledProximityOperator_eq_moreauEnvelopeContactSet_of_mem_gammaZero
(f : H → Set.Ioi (⊥ : EReal)) (hf : f ∈ Γ₀(H)) (γ : PosReal) :
Function.fixedPoints (Prox[γ, f, hf]) = moreauEnvelopeContactSet f γProposition 17.6
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.6: at an effective-domain point of a convex extended-real-valued function, a Gâteaux gradient defines a supporting hyperplane to f at x.
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
variable {x : H} (hx : x ∈ effectiveDomain f) (gradf : H)
variable
(hgrad :
HasGateauxDerivativeAt (fun z ↦ (f z : EReal).toReal) (toDualMap ℝ H gradf) x)
include hconv hx hgrad
-- Proof sketch: identify the directional derivative of `f` at `x` in the direction `y - x` with
-- the derivative functional `toDualMap ℝ H gradf (y - x) = ⟪gradf, y - x⟫_ℝ` using the Gâteaux
-- differentiability hypothesis, then combine this identity with Proposition 17.2 (2).
theorem gateauxGradient_add_value_le
(y : H) :
(⟪y - x, gradf⟫_ℝ : EReal) + (f x : EReal) ≤ (f y : EReal)Proposition 17.7
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.7: on a nonempty open convex effective domain, convexity of f is equivalent to the first-order lower-support inequality and to monotonicity of a Gâteaux derivative field for the finite representative x ↦ (f x : EReal).toReal; moreover, for any second Gâteaux derivative field on the effective domain, these conditions are also equivalent to nonnegativity of its quadratic form.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
theorem convex_tfae_of_open_convex_effectiveDomain
(f : H → Set.Ioi (⊥ : EReal)) (DT : H → H →L[ℝ] ℝ)
(hdom : (effectiveDomain f).Nonempty) (hopen : IsOpen (effectiveDomain f))
(hconv : Convex ℝ (effectiveDomain f))
(hDT : HasGateauxDerivativeOn (fun x ↦ (f x : EReal).toReal) DT (effectiveDomain f)) :
List.TFAE
[ConvexOn f (effectiveDomain f),
GateauxSupportInequalityOn f DT,
GateauxDerivativeMonotoneOn DT (effectiveDomain f)] ∧
(∀ A₂ : H → H →L[ℝ] H →L[ℝ] ℝ,
HasGateauxDerivativeOn DT A₂ (effectiveDomain f) →
List.TFAE
[ConvexOn f (effectiveDomain f),
GateauxSupportInequalityOn f DT,
GateauxDerivativeMonotoneOn DT (effectiveDomain f),
GateauxSecondDerivativeNonnegativeOn A₂ (effectiveDomain f)])Example 17.8
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.8: for a bounded linear operator A on a real Hilbert space, the quadratic form x ↦ ⟪x, A x⟫_ℝ is convex on H if and only if the quadratic form of the symmetric part A + A† is pointwise nonnegative.
open ContinuousLinearMap
open scoped InnerProduct InnerProductSpace
universe u
theorem quadraticForm_convexOn_univ_iff_symmetricPart_nonnegative
{H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(A : H →L[ℝ] H) :
ConvexOn ℝ Set.univ (fun x : H ↦ ⟪x, A x⟫_ℝ) ↔
∀ x : H, 0 ≤ ⟪(A + A†) x, x⟫_ℝProposition 17.9
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Under the hypotheses of Proposition 17.9, the proper function h is convex on its effective domain. The second-order clause is stated directly in the language of Definition 2.56 on effectiveDomain h, rather than through a separately chosen global Hessian field.
open InnerProductSpace Set
open scoped InnerProductSpace Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: Proposition 17.7 supplies the first-order route on `effectiveDomain h`.
-- For clause (ii), the source-facing second-order hypothesis is expressed pointwise through
-- Definition 2.56: at each point of `effectiveDomain h`, the finite representative of `h` is
-- twice Fréchet differentiable and every second Fréchet derivative there has nonnegative
-- quadratic form. This pointwise source clause is then bridged to the canonical second-order
-- criterion used in Proposition 17.7.
theorem convexOn_effectiveDomain_of_gradientMonotone_or_pointwise_secondFrechet_nonnegative
(h : H → Set.Ioi (⊥ : EReal)) (hdom_nonempty : (effectiveDomain h).Nonempty)
(hopen : IsOpen (effectiveDomain h)) (hconv : Convex ℝ (effectiveDomain h))
(hdiff : DifferentiableOn ℝ (fun x ↦ (h x : EReal).toReal) (effectiveDomain h))
(hcriterion :
GateauxDerivativeMonotoneOn
(fun x ↦
toDual ℝ H
(gradientWithin (fun z ↦ (h z : EReal).toReal) (effectiveDomain h) x))
(effectiveDomain h) ∨
∀ x ∈ effectiveDomain h,
TwiceFrechetDifferentiableWithinAt ℝ
(fun z ↦ (h z : EReal).toReal) (effectiveDomain h) x ∧
∀ A₂ : H →L[ℝ] H →L[ℝ] ℝ,
HasSecondFrechetDerivWithinAt ℝ
(fun z ↦ (h z : EReal).toReal) (effectiveDomain h) x A₂ →
∀ z : H, 0 ≤ A₂ z z) :
ConvexOn h (effectiveDomain h)Proposition 17.10
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.10: on an open convex effective domain, strict convexity of f is equivalent to the strict first-order lower-support inequality and to strict monotonicity of a Gâteaux derivative field for the finite representative x ↦ (f x : EReal).toReal; moreover, for any second Gâteaux derivative field on the effective domain, strict positivity of its quadratic form implies strict monotonicity and hence these equivalent conditions.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
theorem strictlyConvex_tfae_of_open_convex_effectiveDomain
(f : H → Set.Ioi (⊥ : EReal)) (DT : H → H →L[ℝ] ℝ)
(hopen : IsOpen (effectiveDomain f)) (hconv : Convex ℝ (effectiveDomain f))
(hDT : HasGateauxDerivativeOn (fun x ↦ (f x : EReal).toReal) DT (effectiveDomain f)) :
List.TFAE
[StrictlyConvex f,
StrictGateauxSupportInequalityOn f DT,
StrictGateauxDerivativeMonotoneOn DT (effectiveDomain f)] ∧
(∀ A₂ : H → H →L[ℝ] H →L[ℝ] ℝ,
HasGateauxDerivativeOn DT A₂ (effectiveDomain f) →
GateauxSecondDerivativePositiveOn A₂ (effectiveDomain f) →
StrictGateauxDerivativeMonotoneOn DT (effectiveDomain f))Example 17.11
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.11: for a bounded linear operator A on a real Hilbert space, the quadratic form x ↦ ⟪x, A x⟫_ℝ is strictly convex on H if and only if the quadratic form of the symmetric part A + A† is strictly positive on every nonzero vector.
open ContinuousLinearMap
open ERealFunction
open InnerProductSpace
open scoped InnerProductSpace
universe u
theorem quadraticForm_strictConvexOn_univ_iff_symmetricPart_positive
{H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
(A : H →L[ℝ] H) :
StrictConvexOn ℝ Set.univ (fun x : H ↦ ⟪x, A x⟫_ℝ) ↔
∀ x : H, x ≠ 0 → 0 < ⟪(A + A.adjoint) x, x⟫_ℝCorollary 17.12
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.12 (1): if D = dom h is a nonempty open interval and the real-valued representative of h is differentiable on D with strictly positive second derivative, then the one-sided-limit extension of h across the boundary of D belongs to Γ₀(ℝ).
open Set
open Filter
open EReal
namespace ERealFunction
variable (h : ℝ → Set.Ioi (⊥ : EReal)) (α β : EReal)
theorem oneSidedLimitExtension_mem_gammaZero_of_deriv2_pos
(hαβ : α < β)
(hdom : effectiveDomain h = erealOpenInterval α β)
(hdiff : DifferentiableOn ℝ (fun x ↦ (h x : EReal).toReal) (effectiveDomain h))
(hderiv2_pos : ∀ x ∈ effectiveDomain h, 0 < (deriv^[2] fun t ↦ (h t : EReal).toReal) x) :
oneSidedLimitExtension h α β
(left_liminf_gt_bot_of_deriv2_pos h α β hαβ hdom hdiff hderiv2_pos)
(right_liminf_gt_bot_of_deriv2_pos h α β hαβ hdom hdiff hderiv2_pos) ∈
Γ₀(ℝ)Example 17.13
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.13: the counterexample function on ℝ² is f(ξ,η)=η^2+η^2/ξ for ξ > 0 and η ≥ 0, f(0,0)=0, and f=+∞ otherwise.
namespace ERealFunction
noncomputable def quadraticPerspectivePlusSquare : ℝ × ℝ → Set.Ioi (⊥ : EReal) :=
closedPerspective nonnegativeSquare nonnegativeSquare_effectiveDomain_nonempty +
(fun p : ℝ × ℝ ↦ p.2 ^ 2).toEReal
-- Proof sketch: unfold the canonical pointwise sum. The closed perspective of
-- `nonnegativeSquare` supplies the `η^2 / ξ` branch on `ξ > 0`, the recession-value branch at
-- `ξ = 0`, and `+∞` elsewhere; the added `toEReal` quadratic contributes the extra `η^2` term.Proposition 17.14
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.14 (1): at an effective-domain point of a convex function, a vector belongs to the subdifferential exactly when its inner-product functional is pointwise dominated by the directional derivative.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
-- Proof sketch: unfold membership in the subdifferential, apply Proposition 17.2 (2) to the
-- direction `y - x`, and use convexity to pass between the affine-minorant inequality and the
-- directional-derivative lower bound.
theorem mem_subdifferential_iff_inner_le_directionalDerivative
{x u : H} (hx : x ∈ effectiveDomain f) :
u ∈ (∂ f) x ↔ ∀ y : H, (⟪y, u⟫_ℝ : EReal) ≤ (f′(x; y))Corollary 17.15
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.15 (1): if x ∈ C ∩ D and convex subsets C and D agree on some open ball around x, then their normal cones at x coincide.
open scoped InnerProductSpace Pointwise Set
universe u
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable {C D : Set H} {x : H}
-- Proof sketch: assume `x ∈ C ∩ D`. For each `y` in one set, move from `x` a short convex
-- combination toward `y`; this point stays inside the local ball where `C` and `D` agree, so the
-- defining support inequalities for `N[C] x` and `N[D] x` transfer to each other.
theorem normalCone_eq_of_convex_inter_ball_eq
(hC_convex : Convex ℝ C) (hD_convex : Convex ℝ D)
(hx : x ∈ C ∩ D)
(hlocal : ∃ ε : ℝ, 0 < ε ∧ C ∩ Metric.ball x ε = D ∩ Metric.ball x ε) :
N[C] x = N[D] xProposition 17.16
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.16 (1): at an effective-domain point of a convex function on ℝ, the left derivative is bounded above by the right derivative.
namespace ERealFunction
variable (f : ℝ → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
-- Proof sketch: apply convexity to the midpoint identity
-- `x = ((x - α) + (x + α)) / 2`, rearrange the resulting inequality of secant quotients, and pass
-- to the infimum definitions of the one-sided directional derivatives.
theorem leftDerivative_le_rightDerivative
{x : ℝ} (hx : x ∈ effectiveDomain f) :
f′₋(x) ≤ f′₊(x)Proposition 17.17
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.17: for a convex ]-∞,+∞]-valued function and an effective-domain point x, the Fenchel conjugate of the directional derivative y ↦ f'(x; y) is the indicator of the subdifferential ∂ f(x).
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: use Proposition 17.14 to rewrite `u ∈ ∂ f(x)` as the pointwise domination
-- `⟪·,u⟫ ≤ f'(x;·)`. Then unfold the Fenchel conjugate of `f'(x;·)` and apply the
-- Fenchel--Young equality criterion from Proposition 16.10 together with Proposition 13.15 to
-- show that the conjugate value is `0` exactly on `∂ f(x)` and `⊤` off that set.
theorem conjugate_directionalDerivative_eq_setIndicator_subdifferential
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hx : x ∈ effectiveDomain f) :
(directionalDerivative f x)∗ = (ι[(∂ f) x]).asERealTheorem 17.18
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Theorem 17.18: for a convex ]-∞,+∞]-valued function, the directional derivative at a continuity point on the effective domain is the support function of the subdifferential there.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: Proposition 16.17 gives that `∂ f(x)` is nonempty and weakly compact at a
-- continuity point on the effective domain. Proposition 17.17 identifies the conjugate of
-- `f'(x; ·)` with the indicator of `∂ f(x)`, and Example 13.3 rewrites the conjugate of this
-- indicator as the support function of `∂ f(x)`. Fenchel--Moreau then yields the claimed identity.
theorem directionalDerivative_eq_supportFunction_subdifferential_of_continuousAtOnEffectiveDomain
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hxcont : ContinuousAtOnEffectiveDomain f x) :
directionalDerivative f x = σ[(∂ f) x]Corollary 17.19
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.19: for a lower semicontinuous convex real-valued function on a real Hilbert space, the following are equivalent: β-Lipschitz continuity, containment of the range of the subdifferential in B(0;β), containment of the effective domain of the Fenchel conjugate in B(0;β), and the recession bound rec f ≤ β ‖·‖.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: first use the canonical Chapter 9 owner theorem
-- `toEReal_mem_gammaZero_of_lowerSemicontinuous_convexOn_univ` to package `f.toEReal` as a
-- member of `Γ₀(H)`, then work with the canonical conjugate owner `(f.toEReal)∗[hf]` and the
-- recession owner `recessionFunction f.toEReal hf.2.nonempty`. Apply Corollary 16.57 for
-- `(ii) → (i)`, combine Corollaries 16.39 and 16.30 with the closedness of the ball for
-- `(ii) ↔ (iii)`, and use Proposition 13.49 together with the support function of the closed ball
-- for `(iii) ↔ (iv)`.
theorem lipschitzWith_tfae_subdifferential_range_conjugateDomain_recession_bound
(f : H → ℝ) (β : NNReal) (hlsc : LowerSemicontinuous f)
(hconv : _root_.ConvexOn ℝ Set.univ f) :
let hf := toEReal_mem_gammaZero_of_lowerSemicontinuous_convexOn_univ f hlsc hconv
List.TFAE
[LipschitzWith β f,
SetValuedOperator.range (∂ f.toEReal) ⊆ Metric.closedBall (0 : H) β,
effectiveDomain ((f.toEReal)∗[hf]) ⊆ Metric.closedBall (0 : H) β,
∀ y : H, (recessionFunction f.toEReal hf.2.nonempty y : EReal) ≤
((β : ℝ) * ‖y‖ : ℝ)]Definition 17.20
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Definition 17.20: a vector y is a descent direction of a proper convex ]-∞,+∞]-valued function f at a point x of its effective domain when there is a positive radius ε such that every step x + α • y with α ∈ ]0, ε] strictly decreases the value of f.
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
def IsDescentDirectionAt (f : H → Set.Ioi (⊥ : EReal)) (x y : H) : Prop :=
x ∈ effectiveDomain f ∧
∃ ε > (0 : ℝ), ∀ ⦃α : ℝ⦄, α ∈ Set.Ioc (0 : ℝ) ε →
f.asEReal (x + α • y) < f.asEReal xProposition 17.21
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.21 (1): for a proper convex ]-∞,+∞]-valued function, a vector y is a descent direction at an effective-domain point x exactly when the directional derivative f'(x; y) is strictly negative.
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [AddCommGroup H] [Module ℝ H]
variable (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
-- Proof sketch: combine the monotonicity of directional difference quotients from Proposition
-- 9.27 with the infimum formula from Proposition 17.2 (1); strict decrease on a short initial ray
-- is equivalent to the limit infimum, hence the directional derivative, being strictly negative.
theorem isDescentDirectionAt_iff_directionalDerivative_lt_zero
{x y : H} (hx : x ∈ effectiveDomain f) :
IsDescentDirectionAt f x y ↔ f′(x; y) < 0Proposition 17.22
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.22: if x is a continuity point on the effective domain of a convex function but not a global minimizer, then the steepest descent direction obtained by normalizing the negative metric projection of 0 onto (∂ f) x is the unique minimizer of f′(x; ·) on the closed unit ball.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable (f : H → Set.Ioi (⊥ : EReal))
-- Proof sketch: Proposition 16.17 gives that `∂ f(x)` is nonempty at a continuity point on the
-- effective domain. Proposition 16.4 supplies closedness and convexity, and Theorem 3.16.1 then
-- upgrades these properties to the Chebyshev condition needed for the metric projection.
theorem argminOn_closedUnitBall_directionalDerivative_eq_singleton_steepestDescentDirection
(hconv : ConvexOn f (effectiveDomain f))
{x : H} (hxcont : ContinuousAtOnEffectiveDomain f x)
(hxnotmin : x ∉ Argmin f.asEReal) :
Argmin[Metric.closedBall 0 1] (f′(x; ·)) =
{steepestDescentDirection f hconv x hxcont}Example 17.23
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.23: for f(ξ₁, ξ₂) = |ξ₁| + 2 |ξ₂|, x = (1,0), and u = (1, ±δ) with δ ∈ [1/2, 3/2], the vector u belongs to ∂ f(x) while -u is not a descent direction at x.
open scoped EuclideanSpace InnerProductSpace
namespace ERealFunction
local notation "ℝ²" => EuclideanSpace ℝ (Fin 2)
local notation "f" => example17_23Function.toEReal
theorem example17_23_subgradient_and_neg_not_descentDirection {δ ε : ℝ}
(hδ : δ ∈ Set.Icc (1 / 2 : ℝ) (3 / 2)) (hε : ε = 1 ∨ ε = -1) :
example17_23Subgradient ε δ ∈ (∂ f) example17_23Point ∧
¬ IsDescentDirectionAt f example17_23Point (-example17_23Subgradient ε δ)Proposition 17.24
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.24: if the directional derivative of a convex function at a continuity point on the effective domain is the support function of C, then the subdifferential at that point is the closed convex hull of C.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
theorem subdifferential_eq_closedConvexHull_of_directionalDerivative_eq_supportFunction
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hxcont : ContinuousAtOnEffectiveDomain f x) (C : Set H)
(hσ : directionalDerivative f x = σ[C]) :
(∂ f) x = closedConvexHull ℝ CProposition 17.25
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.25 (1): clause (i). For a nonempty compact set, the finite real representative of the Chebyshev-center objective is continuous.
open ERealFunction
open scoped InnerProductSpace Pointwise
universe u
variable {H : Type u} [NormedAddCommGroup H]
notation "Φ[" C "]" => chebyshevCenterActiveSet C
variable {C : Set H}
theorem continuous_chebyshevCenterObjective
(hC_nonempty : C.Nonempty) (hCcompact : IsCompact C) :
Continuous fun x ↦ (chebyshevCenterObjective C hC_nonempty x : EReal).toRealProposition 17.26
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.26 (1): if f is uniformly convex with modulus φ, then every effective-domain base point satisfies the first-order lower bound f'(x; y - x) + φ(‖y - x‖) + f(x) ≤ f(y) for every y.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [NormedSpace ℝ H]
-- Proof sketch: apply the uniform-convexity inequality from Definition 10.7 to the segment
-- `x + α • (y - x) = (1 - α) • x + α • y`, divide by `α`, and let `α ↓ 0` to identify the limit
-- with the directional derivative at `x` along `y - x`; if `y ∉ effectiveDomain f`, then the
-- right-hand side is `⊤`, so the inequality is immediate.
theorem directionalDerivative_add_modulus_add_value_le_of_uniformlyConvex
{f : H → Set.Ioi (⊥ : EReal)} {φ : NNReal → EReal} (huniform : UniformlyConvex f φ)
{x y : H} (hx : x ∈ effectiveDomain f) :
f′(x; y - x) + φ ‖y - x‖₊ + (f x : EReal) ≤ (f y : EReal)Proposition 17.27
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.27: if the restriction of f to [x0,x1] is lower semicontinuous, and if every directional derivative along x1 - x0 on [x0,x1[ exists with value at most 0, then f x1 ≤ f x0.
open Set
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [TopologicalSpace H] [AddCommGroup H] [IsTopologicalAddGroup H]
[Module ℝ H] [ContinuousSMul ℝ H]
-- Proof sketch: parametrize the segment by `g(t) = f (AffineMap.lineMap x0 x1 t)`. Lower
-- semicontinuity on the closed segment gives the corresponding endpoint control for `g` on
-- `[0,1]`, while the directional-derivative assumption on `[x0,x1[` yields right derivatives of
-- `g` on `[0,1[` with value at most `0`. The latter already forces every point of `[x0,x1[` to lie
-- in `effectiveDomain f`, so no separate domain hypothesis is needed there. The one-dimensional
-- interval argument then gives `g 1 ≤ g 0`, i.e. `f x1 ≤ f x0`.
theorem apply_right_le_left_of_nonpos_directionalDerivativeOn_segment
(f : H → Set.Ioi (⊥ : EReal)) {x0 x1 : H}
(hlsc : LowerSemicontinuousOn f.asEReal (segment ℝ x0 x1))
(hderiv : ∀ x ∈ closedOpenSegment x0 x1,
∃ ξ, HasDirectionalDerivativeAt f x (x1 - x0) ξ ∧ ξ ≤ 0) :
f.asEReal x1 ≤ f.asEReal x0Corollary 17.28
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.28: if f strictly increases from x₀ to x₁, if f is lower semicontinuous on the segment [x₀,x₁], and if every point of [x₀,x₁[ admits a directional derivative along x₁ - x₀, then some point of that half-open segment has strictly positive directional derivative in the direction x₁ - x₀.
open Set
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [TopologicalSpace H] [AddCommGroup H] [IsTopologicalAddGroup H]
[Module ℝ H] [ContinuousSMul ℝ H]
-- Proof sketch: if every directional derivative of `f` along `x₁ - x₀` on `[x₀,x₁[` were
-- nonpositive, Proposition 17.27 would force `f x₁ ≤ f x₀`, contradicting the strict increase.
-- Hence some point of the half-open segment has directional derivative strictly positive in the
-- direction `x₁ - x₀`.
theorem exists_positive_directional_derivative_on_half_open_segment
(f : H → Set.Ioi (⊥ : EReal)) (x0 x1 : H)
(hvalue : f.asEReal x0 < f.asEReal x1)
(hlsc : LowerSemicontinuousOn f.asEReal (segment ℝ x0 x1))
(hderiv : ∀ x ∈ closedOpenSegment x0 x1,
∃ ξ : EReal, HasDirectionalDerivativeAt f x (x1 - x0) ξ) :
∃ x ∈ closedOpenSegment x0 x1, ∃ ξ : EReal,
HasDirectionalDerivativeAt f x (x1 - x0) ξ ∧ 0 < ξProposition 17.29
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.29: an ]-∞,+∞]-valued function is convex on its effective domain if that domain is nonempty and convex, if the finite-valued restriction is lower semicontinuous on the effective domain, and if every pair of effective-domain points admits directional derivatives along the connecting segment that satisfy f'(x; y - x) ≤ -f'(y; x - y).
open scoped Topology
universe u
namespace ERealFunction
variable {H : Type u} [TopologicalSpace H] [AddCommGroup H] [IsTopologicalAddGroup H]
[Module ℝ H] [ContinuousSMul ℝ H]
-- Proof sketch: argue by contradiction. If `f` fails to be convex on its effective domain, choose
-- a segment with a strict Jensen violation and restrict `f` to that line. Corollary 17.28 then
-- yields two points on the segment with strictly positive opposite directional derivatives, which
-- contradicts the assumed inequality `f'(x; y - x) ≤ -f'(y; x - y)`. Since the codomain already
-- excludes `-∞`, the only primitive data needed from source-level properness is that the effective
-- domain is nonempty.
theorem convexOn_effectiveDomain_of_directionalDerivative_antisymmetry
(f : H → Set.Ioi (⊥ : EReal)) (hdom : (effectiveDomain f).Nonempty)
(hdom_convex : Convex ℝ (effectiveDomain f))
(hlsc : LowerSemicontinuousOn f.asEReal (effectiveDomain f))
(hderiv :
∀ ⦃x y : H⦄, x ∈ effectiveDomain f → y ∈ effectiveDomain f →
∃ ξ η : EReal,
HasDirectionalDerivativeAt f x (y - x) ξ ∧
HasDirectionalDerivativeAt f y (x - y) η ∧
ξ ≤ -η) :
ConvexOn f (effectiveDomain f)Corollary 17.30
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.30: an ]-∞,+∞]-valued function on ℝ is convex on its effective domain if that domain is a nonempty interval, if the finite-valued restriction is lower semicontinuous on the effective domain, and if every strict pair x < y of effective-domain points admits a right derivative at x and a left derivative at y with f'_+(x) ≤ f'_-(y).
namespace ERealFunction
theorem convexOn_effectiveDomain_of_rightDerivative_le_leftDerivative_of_lt
(f : ℝ → Set.Ioi (⊥ : EReal))
(hdom : (effectiveDomain f).Nonempty)
(hdom_convex : Convex ℝ (effectiveDomain f))
(hlsc : LowerSemicontinuousOn f.asEReal (effectiveDomain f))
(honeSided :
∀ ⦃x y : ℝ⦄, x ∈ effectiveDomain f → y ∈ effectiveDomain f → x < y →
HasRightDerivativeAt f x (f′₊(x)) ∧
HasLeftDerivativeAt f y (f′₋(y)) ∧
f′₊(x) ≤ f′₋(y)) :
ConvexOn f (effectiveDomain f)Proposition 17.31
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.31 (1): at an effective-domain point of a convex ]-∞,+∞]-valued function, the subdifferential of f is the singleton consisting of its Gâteaux gradient.
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable (f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
theorem subdifferential_eq_singleton_of_hasGateauxDerivativeAt
{x : H} (hx : x ∈ effectiveDomain f) (gradf : H)
(hgrad :
HasGateauxDerivativeAt (fun z ↦ (f z : EReal).toReal) (toDualMap ℝ H gradf) x) :
(∂ f) x = ({gradf} : Set H)Proposition 17.32
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.32: if f : H → ℝ is continuous and convex, and φ : ℝ → ℝ is convex, increasing on range f, and differentiable at f x, then the subdifferential of φ ∘ f at x is the scalar multiple φ'(f(x)) ∂ f(x), represented here via deriv φ (f x) and .toEReal.
open scoped Pointwise
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: apply Corollary 16.72 to the scalar composition `φ ∘ f`, viewed through
-- `.toEReal`, to rewrite its subdifferential as the union of the scaled sets
-- `α • (∂ f.toEReal) x` for `α ∈ (∂ φ.toEReal) (f x)`. Then use
-- Proposition 17.31 (1) in the scalar space `H = ℝ` together with the ordinary differentiability
-- of `φ` at `f x` to identify `(∂ φ.toEReal) (f x)` with the singleton
-- `{deriv φ (f x)}`, so the union collapses to the claimed scalar multiple.
theorem subdifferential_comp_eq_deriv_smul_of_differentiableAt
(f : H → ℝ) (φ : ℝ → ℝ) (x : H) (hcont : Continuous f)
(hconv : _root_.ConvexOn ℝ Set.univ f) (hφconv : _root_.ConvexOn ℝ Set.univ φ)
(hφdiff : DifferentiableAt ℝ φ (f x)) (hmono : MonotoneOn φ (Set.range f)) :
(∂ (φ ∘ f).toEReal) x = (deriv φ (f x)) • ((∂ f.toEReal) x)Example 17.33
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.33: if C is a nonempty closed convex subset of a real Hilbert space and φ : ℝ → ℝ is convex, differentiable on ℝ₊, and either increasing on ℝ₊ or even, then the subdifferential of x ↦ φ (d(x, C)) is the scaled projection residual outside C, the intersection N[C] x ∩ Metric.closedBall (0 : H) (φ′₊(0)) on frontier C, and {0} on the interior of C, encoded here by the corresponding piecewise formula; the boundary radius is the canonical right derivative of φ.toEReal at 0, rendered below as ((φ.toEReal)′₊(0)).toReal.
open scoped InnerProductSpace Pointwise Set
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable {C : Set H}
variable (hC_nonempty : C.Nonempty) (hC_closed : IsClosed C) (hC_convex : Convex ℝ C)
local notation "hC_cheb" =>
isChebyshev_of_nonempty_isClosed_convex hC_nonempty hC_closed hC_convex
local notation "P" => P[C, hC_cheb]
theorem
subdifferential_comp_distanceToSet_eq_piecewise_of_nonempty_isClosed_convex
(φ : ℝ → ℝ) (hφconv : _root_.ConvexOn ℝ Set.univ φ)
(hφdiff : DifferentiableOn ℝ φ (Set.Ici (0 : ℝ)))
(hφ_mono_or_even : MonotoneOn φ (Set.Ici (0 : ℝ)) ∨ Function.Even φ)
(x : H) :
(∂ (fun y : H ↦ φ (Metric.infDist y C)).toEReal) x =
if hxC : x ∈ C then
if hxbdry : x ∈ frontier C then
N[C] x ∩ Metric.closedBall (0 : H) (((φ.toEReal)′₊(0)).toReal)
else
({0} : Set H)
else
({(deriv φ (Metric.infDist x C) / Metric.infDist x C) • (x - P x)} : Set H)Proposition 17.34
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.34: for a convex function on a finite Hilbert sum, if x is a continuity point on the effective domain and every coordinate slice through x is Gâteaux differentiable at x i, then f is Gâteaux differentiable at x with gradient equal to the assembled family of the slice gradients.
open InnerProductSpace
open scoped InnerProductSpace
universe u v
namespace ERealFunction
variable {I : Type v} [Finite I]
variable {H : I → Type u}
variable [∀ i, NormedAddCommGroup (H i)]
variable [∀ i, InnerProductSpace ℝ (H i)]
-- Proof sketch: Proposition 16.7 sends every `u ∈ ∂ f(x)` to a family of slice subgradients.
-- Since `hconv.nonempty` and `SubdifferentiableAt f x` imply `x ∈ effectiveDomain f`, Proposition
-- 17.31 (1) makes each slice subdifferential the singleton `{grad i}` and identifies `x i` with
-- an effective-domain point of the `i`-th slice. Thus every subgradient of `f` at `x` must agree
-- coordinatewise with `grad`, hence equal `grad` itself in `lp H 2`; `SubdifferentiableAt f x`
-- supplies the nonemptiness needed to conclude equality with that singleton.
variable [∀ i, CompleteSpace (H i)]
-- Proof sketch: the previous theorem identifies `∂ f(x)` with the singleton `{grad}`.
-- Proposition 17.31 (2) then upgrades this singleton subdifferential, together with continuity on
-- the effective domain, to Gâteaux differentiability of `f` at `x` with gradient `grad`. Here
-- continuity is used only for the upgrade from singleton subdifferential to derivative, while
-- Proposition 16.17 (2) supplies the subdifferentiability input required by the preceding
-- singleton-subdifferential theorem.
theorem hasGateauxDerivativeAt_of_coordinatewise_hasGateauxDerivativeAt
{f : lp H 2 → Set.Ioi (⊥ : EReal)} (hconv : ConvexOn f (effectiveDomain f))
{x : lp H 2} (hxcont : ContinuousAtOnEffectiveDomain f x) (grad : lp H 2)
(hgrad : ∀ i,
HasGateauxDerivativeAt
(fun y ↦ (f (coordinateSlice x i y) : EReal).toReal)
(toDualMap ℝ (H i) (grad i)) (x i)) :
HasGateauxDerivativeAt (fun z ↦ (f z : EReal).toReal) (toDualMap ℝ (lp H 2) grad) xProposition 17.35
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.35: if a proper convex ]-∞,+∞]-valued function is Gâteaux differentiable at x with gradient gradf, then the Fenchel conjugate of f at gradf is ⟪x, gradf⟫ - f x.
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
theorem conjugate_gateauxGradient_eq_inner_sub_of_hasGateauxDerivativeAt
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hx : x ∈ effectiveDomain f) (gradf : H)
(hgrad :
HasGateauxDerivativeAt (fun z ↦ (f z : EReal).toReal) (toDualMap ℝ H gradf) x) :
f.asEReal∗ gradf = ((⟪x, gradf⟫_ℝ : ℝ) : EReal) - f xProposition 17.36
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.36 (1): clause (i). If A is monotone, then its quadratic potential q_A(x) = (1 / 2) ⟪x, A x⟫_ℝ is convex on all of H.
open ERealFunction
open scoped ContinuousLinearMap Gradient InnerProductSpace
universe u
namespace ContinuousLinearMap
variable {H : Type u}
variable [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: `q[A]` is continuous as a quadratic form built from a bounded
-- linear operator, so its `EReal` coercion is lower semicontinuous. Convexity is the monotone
-- quadratic-form criterion from Example 17.8, with the scalar factor `1 / 2` preserving convexity.
scoped notation:max "q⋆[" A:max ", " hA_mono:max "]" =>
(Function.toEReal (q[A]))∗[quadraticPotential_mem_gammaZero_of_isMonotone A hA_mono]
-- Proof sketch: rewrite `q[A]` as the positive scalar multiple
-- `(1 / 2) • (fun x ↦ ⟪x, A x⟫_ℝ)` and apply the monotone quadratic-form characterization from
-- Example 17.8.
theorem quadraticPotential_convexOn_univ_of_isMonotone
(A : H →L[ℝ] H) (hA_mono : A.toLinearMap.IsMonotone) :
ConvexOn ℝ Set.univ (q[A])Example 17.37
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.37: if φ : ℝ → ℝ is convex, even, and differentiable on ℝ \ {0}, then there exists ρ ∈ ℝ₊ such that the scalar subdifferential of φ at 0 is [-ρ, ρ], and the subdifferential of the radial function x ↦ φ ‖x‖ is the closed ball B(0; ρ) at the origin and the singleton {(φ'(‖x‖) / ‖x‖) • x} away from the origin.
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: Example 16.73(1) yields `ρ` with `(∂ φ.toEReal) 0 = [-ρ, ρ]`, and
-- Example 16.73(3) turns that scalar interval into the zero-branch radial formula
-- `(∂ (fun y ↦ φ ‖y‖).toEReal) 0 = B(0; ρ)`. For `x ≠ 0`, Example 16.73(2) rewrites the radial
-- subdifferential as `((∂ φ.toEReal) ‖x‖) • {‖x‖⁻¹ • x}`, while Proposition 17.31(i) makes the
-- scalar owner `(∂ φ.toEReal) ‖x‖` the singleton `{deriv φ ‖x‖}` because `φ` is differentiable
-- off `0`.
theorem exists_subdifferential_comp_norm_eq_closedBall_at_zero_and_singleton_of_ne
(φ : ℝ → ℝ) (hconv : _root_.ConvexOn ℝ Set.univ φ) (heven : Function.Even φ)
(hφdiff : DifferentiableOn ℝ φ (({0} : Set ℝ)ᶜ)) :
∃ ρ : NNReal,
(∂ φ.toEReal) 0 = Set.Icc (-(ρ : ℝ)) (ρ : ℝ) ∧
(∂ (fun y : H ↦ φ ‖y‖).toEReal) 0 = Metric.closedBall (0 : H) (ρ : ℝ) ∧
∀ x : H, x ≠ 0 →
(∂ (fun y : H ↦ φ ‖y‖).toEReal) x = ({(deriv φ ‖x‖ / ‖x‖) • x} : Set H)Example 17.38
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.38: if 0 ∈ C and the closed cone generated by C is the whole ambient real inner product space, then the indicator ι_C has subdifferential {0} at 0, hence a unique subgradient there.
open ERealFunction
open scoped InnerProductSpace Pointwise Set
universe u
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: rewrite `N[C] 0` as the polar cone of `C - {0} = C`. If `u ∈ N[C] 0`, then the
-- halfspace `{x | ⟪x, u⟫ ≤ 0}` contains `C`, hence also `cone C` by convex-cone hull minimality
-- and `closure (cone C)` by closedness. Since `closure (cone C) = univ`, it contains `u`, so
-- `⟪u, u⟫ ≤ 0`; positive-definiteness forces `u = 0`.
theorem subdifferential_setIndicator_eq_singleton_zero_at_zero_of_closure_cone_eq_univ
(C : Set H) (h0C : (0 : H) ∈ C)
(hclosure_cone : closure (cone C) = (Set.univ : Set H)) :
(∂ ι[C]) (0 : H) = ({0} : Set H)Proposition 17.39
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.39: for f ∈ Γ₀(H) and x ∈ interior (effectiveDomain f), the following are equivalent: (i) x ↦ (f x : EReal).toReal is Gâteaux differentiable at x; (ii) every selection of ∂ f is strong-to-weak continuous at x; (iii) there exists a selection of ∂ f with the same continuity property at x.
universe u
namespace ERealFunction
open SetValuedOperator
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: Proposition 17.31 identifies Gâteaux differentiability at `x` with singleton
-- subdifferential at `x`. Proposition 16.17 gives local boundedness and nonemptiness of nearby
-- subdifferentials on the interior effective domain, and Proposition 16.36 gives strong-weak
-- sequential closedness of `gra ∂ f`. These ingredients show that Gâteaux differentiability forces
-- every selection to converge weakly to the unique subgradient, while any weakly continuous
-- selection yields the directional-derivative inequalities needed to recover Gâteaux
-- differentiability.
theorem gateauxDifferentiableAt_tfae_subdifferentialSelections_strongToWeakContinuousAt
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {x : H}
(hx : x ∈ interior (effectiveDomain f)) :
List.TFAE
[GateauxDifferentiableAt (fun y ↦ (f y : EReal).toReal) x,
∀ G : Selection (∂ f),
SelectionContinuousAt (∂ f) (fun z : (∂ f).dom ↦ toWeakSpace ℝ H (G z : H)) x,
∃ G : Selection (∂ f),
SelectionContinuousAt (∂ f) (fun z : (∂ f).dom ↦ toWeakSpace ℝ H (G z : H)) x]Corollary 17.40
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.40: if f ∈ Γ₀(H) and gradf represents the Gâteaux gradient of x ↦ (f x : EReal).toReal on interior (effectiveDomain f), then gradf is strong-to-weak continuous on interior (effectiveDomain f).
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: this is the specialization of Corollary 17.42 to the open set
-- `D = interior (effectiveDomain f)`.
theorem gradientField_strongToWeakContinuousOn_interior_effectiveDomain_of_mem_gammaZero
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) (gradf : H → H)
(hgrad :
HasGateauxDerivativeOn (fun x ↦ (f x : EReal).toReal) (fun x ↦ toDual ℝ H (gradf x))
(interior (effectiveDomain f))) :
Continuous (fun x : interior (effectiveDomain f) ↦ toWeakSpace ℝ H (gradf x))Proposition 17.41
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.41: for f ∈ Γ₀(H) and x ∈ interior (effectiveDomain f), the following are equivalent: (i) x ↦ (f x : EReal).toReal is Fréchet differentiable at x; (ii) every selection of ∂ f is continuous at x; (iii) there exists a selection of ∂ f that is continuous at x.
universe u
namespace ERealFunction
open SetValuedOperator
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: use the interior-domain hypotheses together with the local boundedness and
-- nonemptiness results for `∂ f` to compare subgradient selections near `x`. Fréchet
-- differentiability forces all such selections to converge to the unique subgradient at `x`,
-- clause (ii) trivially implies clause (iii), and a continuous local selection yields the little-o
-- estimate characterizing Fréchet differentiability.
theorem frechetDifferentiableAt_tfae_subdifferentialSelections_continuousAt
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {x : H}
(hx : x ∈ interior (effectiveDomain f)) :
List.TFAE
[DifferentiableAt ℝ (fun y ↦ (f y : EReal).toReal) x,
∀ G : Selection (∂ f),
SelectionContinuousAt (∂ f) (fun z : (∂ f).dom ↦ (G z : H)) x,
∃ G : Selection (∂ f),
SelectionContinuousAt (∂ f) (fun z : (∂ f).dom ↦ (G z : H)) x]Corollary 17.42
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.42 (1): if f ∈ Γ₀(H) admits a Gâteaux gradient field gradf on an open set D ⊆ effectiveDomain f, then gradf is strong-to-weak continuous on D.
open InnerProductSpace
open scoped InnerProductSpace
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
theorem gradientField_strongToWeakContinuousOn_of_mem_gammaZero_of_hasGateauxDerivativeOn
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {D : Set H} (hD_open : IsOpen D)
(hD_dom : D ⊆ effectiveDomain f) (gradf : H → H)
(hgrad :
HasGateauxDerivativeOn (fun y ↦ (f y : EReal).toReal) (fun y ↦ toDual ℝ H (gradf y)) D) :
Continuous (fun y : D ↦ toWeakSpace ℝ H (gradf y))Corollary 17.43
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.43: if f ∈ Γ₀(H) is Fréchet differentiable on interior (effectiveDomain f), then its gradient is continuous on interior (effectiveDomain f).
open InnerProductSpace
open scoped Gradient InnerProductSpace Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
-- Proof sketch: for a function in `Γ₀(H)`, Fréchet differentiability on
-- `interior (effectiveDomain f)` gives a genuine gradient field there because the set is open.
-- Use the convex-analysis continuity theorem for gradients of differentiable convex functions on
-- the interior of the effective domain.
theorem gradient_continuousOn_interior_effectiveDomain_of_mem_gammaZero_of_differentiableOn
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H))
(hdiff : DifferentiableOn ℝ (fun x ↦ (f x : EReal).toReal) (interior (effectiveDomain f))) :
ContinuousOn (∇ fun x ↦ (f x : EReal).toReal) (interior (effectiveDomain f))Corollary 17.44
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Corollary 17.44: on a finite-dimensional real Hilbert space, Gâteaux differentiability and Fréchet differentiability coincide for a function in Γ₀(H) at every point of interior (effectiveDomain f).
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H]
theorem gateauxDifferentiableAt_iff_frechetDifferentiableAt_of_mem_gammaZero
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {x : H}
(hx : x ∈ interior (effectiveDomain f)) :
GateauxDifferentiableAt (fun y ↦ (f y : EReal).toReal) x ↔
DifferentiableAt ℝ (fun y ↦ (f y : EReal).toReal) xProposition 17.45
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.45: on a finite-dimensional real Hilbert space, the subdifferential of a function in Γ₀(H) at an interior point of its effective domain is the singleton {u} if and only if the finite representative of f has gradient u there.
open InnerProductSpace
open scoped Gradient
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [FiniteDimensional ℝ H]
theorem subdifferential_eq_singleton_iff_hasGradientAt_of_mem_gammaZero
{f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H)) {x : H}
(hx : x ∈ interior (effectiveDomain f)) (u : H) :
(∂ f) x = ({u} : Set H) ↔
HasGradientAt (fun y ↦ (f y : EReal).toReal) u xExample 17.46
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.46: the function x ↦ supₙ (⟪x, uₙ⟫_ℝ - αₙ) associated with a sequence of vectors and real offsets.
open Filter
open InnerProductSpace
open scoped InnerProductSpace Topology
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
noncomputable def affineInnerSupremum (u : ℕ → H) (α : ℕ → ℝ) : H → Set.Ioi (⊥ : EReal) :=
fun x ↦ ⟨affineInnerSupremumEReal u α x, affineInnerSupremum_value_mem_Ioi_bot u α x⟩Example 17.47
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.47 (1): if the origin lies in core C, then the subdifferential of the indicator ι_C at 0 is the singleton {0}.
open ERealFunction
open scoped InnerProductSpace Pointwise Set Topology
universe u
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
-- Proof sketch: `0 ∈ core C` means the cone generated by `C - {0}` is all of `H`, hence
-- `closure (cone C) = univ` and `0 ∈ C`. Apply Example 17.38 to identify the subdifferential of
-- `ι_C` at `0` with the singleton `{0}`.
theorem subdifferential_setIndicator_eq_singleton_zero_at_zero_of_mem_core
(C : Set H) (h0core : (0 : H) ∈ core C) :
(∂ ι[C]) (0 : H) = ({0} : Set H)Proposition 17.48
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.48 (1): clause (i). If a convex ]-∞,+∞]-valued function is Gâteaux differentiable at an effective-domain point x in the source Chapter 17 sense, then it is lower semicontinuous at x.
universe u
namespace ERealFunction
open InnerProductSpace
open scoped Pointwise Set
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H]
variable [CompleteSpace H]
-- Proof sketch: represent the chosen source derivative map by its Riesz vector `gradf`. For each
-- direction `y`, Proposition 17.2 rewrites the source derivative value as `f′(x; y)`, so
-- Proposition 17.14 identifies `gradf` as a subgradient at `x`. Proposition 16.4 (5) then yields
-- lower semicontinuity at `x`.
theorem lowerSemicontinuousAt_of_convexOn_of_gateauxDifferentiableAt
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f))
{x : H} (hdiff : GateauxDifferentiableAt f x) :
LowerSemicontinuousAt f.asEReal xExample 17.49
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Example 17.49 (1): if g = f^2 for a real linear functional f, then g is convex on the whole space.
universe u
variable {H : Type u} [AddCommMonoid H] [Module ℝ H]
-- Proof sketch: apply the canonical scalar owner `Even.convexOn_pow` to `t ↦ t ^ 2` on `ℝ`, then
-- compose with the linear owner `f` via `ConvexOn.comp_linearMap`.
theorem convexOn_univ_sq_linearForm (f : H →ₗ[ℝ] ℝ) :
ConvexOn ℝ (Set.univ : Set H) (fun x : H ↦ (f x) ^ 2)Proposition 17.50
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.50 (1): this is Proposition 17.48 (2) specialized to `hf.2 : ConvexOn f (effectiveDomain f)`.
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
variable {f : H → Set.Ioi (⊥ : EReal)} (hf : f ∈ Γ₀(H))
#check mem_interior_effectiveDomain_of_convexOn_of_gateauxDifferentiableAt
-- Proof sketch: Corollary 8.39 identifies the points where the finite real representative of a
-- convex lower semicontinuous function is continuous with `interior (effectiveDomain f)`. Since
-- membership in `Γ₀(H)` packages lower semicontinuity and convexity on the effective domain, this
-- yields continuity on the whole interior.Proposition 17.51
Lean contributors (project-level attribution): Yifan Bai, Zichen Wang, Zaiwen Wen.
Proposition 17.51: if a convex ]-∞,+∞]-valued function is Gâteaux differentiable on a nonempty open subset U of its effective domain, then its finite-valued representative is continuous on interior (effectiveDomain f).
universe u
namespace ERealFunction
variable {H : Type u} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H]
theorem continuousOn_interior_effectiveDomain_of_convexOn_of_nonempty_open_subset_gateauxDifferentiableOn
(f : H → Set.Ioi (⊥ : EReal)) (hconv : ConvexOn f (effectiveDomain f)) (U : Set H)
(hU_nonempty : U.Nonempty) (hU_open : IsOpen U) (hU_dom : U ⊆ effectiveDomain f)
(hgateaux : ∀ x ∈ U, GateauxDifferentiableAt f x) :
ContinuousOn (fun x ↦ (f x : EReal).toReal) (interior (effectiveDomain f))