Chapter 14 — Nonsmooth Optimization
Proofs omitted. Hover over highlighted terms to see their Lean types.
Exercise 14.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.1 is already owned by the Chapter 14 directional-derivative API in Definition_14_1_extra_1.lean and Lemma_14_1_1.lean. This file therefore stays at the recall layer and reuses those declarations directly instead of restating their types through anonymous function binders.
#check LocallyLipschitzWithinAtExercise 14.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.2 is already owned by the Chapter 14 semismoothness API in Definition_14_8_extra_2.lean. This file therefore stays at the recall layer and reuses those canonical source-facing declarations directly instead of restating their types through anonymous function binders.
#check LocallyLipschitzAtExercise 14.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.3: if f is continuously differentiable at x, then the Clarke generalized differential ∂ᶜ f(x) is the singleton generated by the Fréchet derivative fderiv ℝ f x, viewed intrinsically in StrongDual ℝ E.
open scoped ClarkeDirectionalDerivative ClarkeDifferential
variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
theorem clarkeDifferential_eq_singleton_fderiv_of_contDiffAt
(f : E → ℝ) (x : E) (hf : ContDiffAt ℝ 1 f x) :
(∂ᶜ f) x =
({fderiv ℝ f x} : Set (StrongDual ℝ E))Exercise 14.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.4 (1): if c i is continuously differentiable at x for every i in a nonempty finite family s and f(x) = max_(i ∈ s) c i x, then the Clarke differential ∂ f(x) is the convex hull of the active gradients ∇ c_i(x) at the indices attaining the maximum value.
open InnerProductSpace
open scoped BigOperators
open scoped ClarkeDirectionalDerivative ClarkeDifferential
variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
local notation "DualPoint" => StrongDual ℝ E
local notation "WeakDualPoint" => WeakDual ℝ E
variable [CompleteSpace E]
variable {ι : Type*} (s : Finset ι) (hs : s.Nonempty) (c : ι → E → ℝ) (x : E)
theorem clarkeDifferential_pointwiseMax
(hC1 : ∀ i ∈ s, ContDiffAt ℝ 1 (c i) x) :
clarkeDifferentialOfPointwiseMax s hs c x hC1 =
convexHull ℝ
((fun i ↦ toDual ℝ E (gradient (c i) x)) '' activeIndices s c x)Exercise 14.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.5: direct recall of the canonical Chapter 14 constant-step subgradient method liminf estimate from Theorem 14.3.3.
#check exists_pos_constant_subgradient_stepsize_liminf_le_optimalValue_add_of_convexOnExercise 14.6
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.6: if f is convex on ℝ^n, then at every x its value equals the double supremum of the supporting-affine values f y + ⟪g, x - y⟫ over all base points y and all subgradients g ∈ ∂ f(y).
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Layer triage:
-- * core/canonical: `subdifferential`, `cuttingPlaneAffineMinorant`
-- * source-facing: `convexOn_eq_sSup_subgradientAffineSupportValue`
-- * bridge/view: `subgradientAffineSupportValueSet`
theorem convexOn_eq_sSup_subgradientAffineSupportValue
(f : Point → ℝ)
(h_convex : ConvexOn ℝ Set.univ f)
(x : Point) :
f x =
sSup (Set.range fun y : Point ↦
sSup (subgradientAffineSupportValueSet f x y))
Exercise 14.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.7: direct recall of the canonical Chapter 14 Theorem 14.4.2 owner surface.
#check CuttingPlaneMethod.optimalValue_eq_sInf_image
Exercise 14.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.8: let method be a bundle-method run for a uniformly convex objective method.objective on Set.univ, with modulus φ strictly positive away from 0. Assume prior bundle-method theory shows that every accumulation point of the iterate sequence method.shiftedIterate is a global minimizer of method.objective, and that the iterate sequence is eventually contained in a compact set s. Then the bundle-method iterates converge globally to a global minimizer of method.objective.
open Filter
variable {n : ℕ}
open Chapter14
theorem bundleMethod_globalConvergence_of_uniformConvexOn
(method : BundleMethod n) (φ : ℝ → ℝ) {s : Set (Point n)}
(h_uniformConvex : UniformConvexOn Set.univ φ method.objective)
(h_phi_pos : ∀ r : ℝ, r ≠ 0 → 0 < φ r)
(h_accumulation_isMinOn :
∀ {y : Point n} {σ : ℕ → ℕ},
StrictMono σ →
Tendsto (fun k : ℕ ↦ method.shiftedIterate (σ k)) atTop (nhds y) →
IsMinOn method.objective Set.univ y)
(hs_compact : IsCompact s)
(h_iterate_eventually_mem :
∀ᶠ k : ℕ in atTop, method.shiftedIterate k ∈ s) :
∃ xStar : Point n,
IsMinOn method.objective Set.univ xStar ∧
Tendsto method.shiftedIterate atTop (nhds xStar)Exercise 14.9
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.9: recall the canonical Section 14.6 owners and the seven clauses of SunYuanOptimizationTheoryMethods.Chap14.Lemma_14_6_2.
#check compositeNonsmoothJacobianTranspose
Exercise 14.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Exercise 14.10 as a composite nonsmooth optimization problem with smooth map exercise1410SmoothMap eps and outer function exercise1410OuterMax.
open Filter open scoped CompositeNonsmooth local notation "Point" => EuclideanSpace ℝ (Fin 2) -- Domain-style sampling: -- * primary domain: norm-parametric composite nonsmooth trust-region methods on Euclidean space, -- specialized here to the `ℓ∞` trust-region constraint from Exercise 14.10; -- * inspected upstream owners in the minimal closure: -- `linftyNorm`, -- `trustRegionPenaltyFeasibleSet`, -- `CompositeNonsmoothOptimizationProblem`, -- `compositeNonsmoothJacobianTranspose`, -- `DF[problem](x, d)`, -- `compositeNonsmoothTrustRegionModel`, -- `trustRegionPredictedReduction`, -- `IsCompositeNonsmoothTrustRegionSolution`, -- `CompositeNonsmoothTrustRegionMethod`, -- `IsCompositeNonsmoothAcceptedStepMultiplier`, -- and mathlib's `IsMinOn`; -- * source-facing data kept local: the two smooth branches, the outer `max`, the explicit -- source Hessian matrices, and the initial point/radius; -- * bridge/view layer in this file: the exercise specializes the Chapter 14.7 method owner to -- `ρ = linftyNorm`, `problem = exercise1410Problem eps`, and the source initial data; -- * core/canonical owners reused: the Chapter 14 composite-problem/model/method API, the -- Chapter 13 trust-region feasible-set owner, and the Chapter 01 `linftyNorm` owner. -- Primitive data are the branch map, outer `max`, and component Hessians. The Jacobian, -- directional-value, `DF`, the trust-region subproblem predicate, the trust-region method API, -- and the `ℓ∞` feasible-set surface are derived from those owners rather than stored as parallel -- local definitions. def exercise1410Problem (eps : ℝ) : CompositeNonsmoothOptimizationProblem 2 2
Exercise 14.11
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.11: direct recall of the Chapter 14.7 accumulation-point theorem and its canonical HasSubsequenceTendstoTo bridge.
#check compositeNonsmoothTrustRegion_exists_stationaryAccumulationPoint
Exercise 14.12
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.12: a nonmonotone modification of Algorithm 14.7.1, still organized around the chosen trust-region norm ρ, keeps the same trust-region subproblem, stopping test, and radius-update thresholds as Algorithm 14.7.1, but replaces the monotone actual-reduction numerator h (f(x_k)) - h (f(x_k + d_k)) by the bounded-window nonmonotone numerator R_k - h (f(x_k + d_k)), where R_k is the reference value over the most recent objective values determined by referenceWindowSize k. The primitive data are the composite problem, the C² regularity of the component functions, the bounded reference-window recursion, and the recorded stage data. The Jacobian transpose, component Hessians, trust-region model, and accepted-step multiplier relation are reused canonically from the norm-parametric Chapter 14.7 owners rather than stored as parallel fields.
open scoped BigOperators CompositeNonsmooth
variable {n m : ℕ}
variable {ρ : (Fin n → ℝ) → ℝ} [IsVectorNorm ρ]
local notation "Point" => Chapter14.Point n
local notation "ValuePoint" => Chapter14.Point m
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * primary domain: Section 14.7 composite nonsmooth trust-region methods;
-- * inspected owner declarations in the minimal Chapter 14 closure:
-- `CompositeNonsmoothTrustRegion.hessianApproximationAt`,
-- `CompositeNonsmoothTrustRegion.modelAt`,
-- `CompositeNonsmoothTrustRegion.reductionRatioAt`,
-- `CompositeNonsmoothTrustRegionMethod`;
-- * inspected project finite-window-max owners for the new source-facing `R_k`:
-- `nonmonotoneArmijoWindow`,
-- `nonmonotoneArmijoReferenceValue`;
-- * source/core/bridge triage:
-- - source-facing here: the bounded reference-value recursion and the resulting
-- nonmonotone trust-region update rule;
-- - core/canonical reused here: the norm-parametric Chapter 14.7 trust-region stage owners,
-- the trust-region method subproblem predicate, the accepted-step multiplier relation, and
-- the Chapter 2 bounded recent-index window owner;
-- - bridge/view here: the Euclidean Hessian-matrix realization provided by `hessianMatrixAt`.
-- * primitive data vs derived API:
-- - primitive data here are the reference-window recursion and the stage data
-- `iterate`, `multiplier`, `direction`, and `trustRegionRadius`;
-- - the Jacobian transpose, component Hessians, trust-region model, and accepted-step
-- relation are derived from the Chapter 14.6/14.7 owners and are not stored again.
structure NonmonotoneCompositeNonsmoothTrustRegionMethod
(n m : ℕ) (ρ : (Fin n → ℝ) → ℝ) [IsVectorNorm ρ] where
problem : CompositeNonsmoothOptimizationProblem n m
componentContDiff :
∀ i : Fin m, ContDiff ℝ 2 (fun y : Chapter14.Point n ↦ problem.smoothMap y i)
initialPoint : Chapter14.Point n
initialMultiplier : Chapter14.Point m
initialRadius : ℝ
epsilon : ℝ
referenceWindowBound : ℕ
referenceWindowSize : ℕ → ℕ
iterate : ℕ → Chapter14.Point n
multiplier : ℕ → Chapter14.Point m
direction : ℕ → Chapter14.Point n
trustRegionRadius : ℕ → ℝ
initialRadius_pos : 0 < initialRadius
epsilon_nonneg : 0 ≤ epsilon
iterate_one : iterate 1 = initialPoint
multiplier_zero : multiplier 0 = initialMultiplier
trustRegionRadius_one : trustRegionRadius 1 = initialRadius
referenceWindowSize_one : referenceWindowSize 1 = 0
referenceWindowSize_succ_le
(k : ℕ) (_hk : 1 ≤ k) :
referenceWindowSize (k + 1) ≤
Nat.min (referenceWindowSize k + 1) referenceWindowBound
direction_subproblem_solution
(k : ℕ) (_hk : 1 ≤ k) :
IsCompositeNonsmoothTrustRegionSolution
ρ
problem
(iterate k)
(CompositeNonsmoothTrustRegion.hessianApproximationAt problem iterate multiplier k)
(trustRegionRadius k)
(direction k)
predictedReduction_pos
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp) :
0 <
trustRegionPredictedReduction
(CompositeNonsmoothTrustRegion.modelAt problem iterate multiplier k)
(direction k)
trustRegionRadius_succ
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp) :
trustRegionRadius (k + 1) =
if stageReductionRatio
problem
iterate
multiplier
direction
referenceWindowSize
k <
(1 / 4 : ℝ) then
ρ (direction k).ofLp / 4
else if (3 / 4 : ℝ) <
stageReductionRatio
problem
iterate
multiplier
direction
referenceWindowSize
k ∧
ρ (direction k).ofLp = trustRegionRadius k then
2 * trustRegionRadius k
else
trustRegionRadius k
iterate_succ_of_positive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
0 <
stageReductionRatio
problem
iterate
multiplier
direction
referenceWindowSize
k) :
iterate (k + 1) = CompositeNonsmoothTrustRegion.trialPoint iterate direction k
multiplier_of_positive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
0 <
stageReductionRatio
problem
iterate
multiplier
direction
referenceWindowSize
k) :
IsCompositeNonsmoothAcceptedStepMultiplier
problem
(CompositeNonsmoothTrustRegion.trialPoint iterate direction k)
(direction k)
(multiplier k)
iterate_succ_of_nonpositive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
stageReductionRatio
problem
iterate
multiplier
direction
referenceWindowSize
k ≤
0) :
iterate (k + 1) = iterate k
multiplier_of_nonpositive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
stageReductionRatio
problem
iterate
multiplier
direction
referenceWindowSize
k ≤
0) :
multiplier k = multiplier (k - 1)
Exercise 14.13
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Exercise 14.13: a semilocal closed-ball convergence companion for generalized Newton. If xStar is the unique zero of the stationarity map method.map in Metric.closedBall method.initialPoint r, if zeros of that map are Clarke stationary for the objective f, and the generalized Newton iteration satisfies the closed-ball convergence assumptions on that ball, then the generalized Newton iterates converge to the Clarke stationary point xStar.
open Filter
open scoped GeneralizedJacobian BigOperators
variable {n : ℕ}
theorem generalizedNewton_tendsto_of_closedBallConvergenceAssumptions
(objective : Point n → ℝ) (method : NonsmoothNewtonMethod n)
(semideriv : Point n → Point n → Point n)
(xStar : Point n) (r β γ δ : ℝ)
(h_assumptions :
HasGeneralizedNewtonClosedBallConvergenceAssumptions
method.map semideriv method.initialPoint r β γ δ)
(h_stationary :
∀ {x : Point n}, method.map x = 0 → IsClarkeStationaryPoint objective x)
(h_unique :
IsUniqueZeroOnClosedBall method.map method.initialPoint r xStar) :
Tendsto method.iterate atTop (nhds xStar) ∧
IsClarkeStationaryPoint objective xStar
14.1 — Generalized Gradients
Lemma 14.1.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.1.1 (1): if f is Lipschitz near x, then its Clarke generalized directional derivative fᵒ(x; d) is positively homogeneous in the direction variable.
open scoped Topology ClarkeDirectionalDerivative
variable {E : Type _} [NormedAddCommGroup E] [NormedSpace ℝ E]
variable (f : E → ℝ) (x : E)
theorem clarkeDirectionalDerivative_posHomogeneous
(h_lipschitz : LocallyLipschitzAt f x)
(d : E)
(lam : ℝ)
(h_lam : 0 ≤ lam) :
fᵒ(x; lam • d) = lam * fᵒ(x; d)Definition 14.1.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Definition 14.1.2 (1): if f is Lipschitz near x, encoded by a hypothesis LocallyLipschitzAt f x, the generalized differential (Clarke differential) of f at x is the set of continuous linear functionals ξ such that the EReal-valued Clarke directional derivative dominates the pairing ξ d in every direction d. Under local Lipschitz hypotheses this is the textbook Clarke differential, while the EReal codomain keeps the raw whole-space owner canonical outside that regime. An element of (∂ᶜ f) x is a generalized gradient at x.
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
local notation "DualSpace" => StrongDual ℝ E
open scoped ClarkeDirectionalDerivative
def clarkeDifferential (f : E → ℝ) (x : E) : Set DualSpace :=
{ξ | ∀ d : E, ξ d ≤ fᵒ(x; d)}Lemma 14.1.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.1.3 (1): if f is Lipschitz near x, then the Clarke differential (∂ᶜ f) x = ∂ᶜ f(x) is nonempty.
open Bornology
open scoped ClarkeDirectionalDerivative ClarkeDifferential
universe u
variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X]
local notation "DualSpace" => StrongDual ℝ X
theorem clarkeDifferential_nonempty_of_locallyLipschitzAt
(f : X → ℝ) (x : X) (h_local : LocallyLipschitzAt f x) :
((∂ᶜ f) x).NonemptyLemma 14.1.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.1.4 (1): recall the canonical Clarke-differential membership criterion.
open scoped BigOperators Pointwise ClarkeDifferential ClarkeDirectionalDerivative
universe u
variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E]
local notation "DualSpace" => StrongDual ℝ E
local notation "WeakDualSpace" => WeakDual ℝ E
#check mem_clarkeDifferential_iff
Theorem 14.1.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.1.5: if f attains a local extremum at xStar and f is Lipschitz near xStar, then the zero functional belongs to the Clarke differential (∂ᶜ f) xStar = ∂ᶜ f(xStar). The theorem is stated over the chapter's canonical real normed-space owners; the textbook ℝ^n case is recovered by specializing X.
open scoped ClarkeDirectionalDerivative ClarkeDifferential
universe u
variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X]
local notation "DualSpace" => StrongDual ℝ X
-- Domain sampling:
-- * primary domain: Clarke-stationary necessary conditions for local extrema on real normed spaces
-- * inspected Chapter 14 owners in the minimal closure:
-- `clarkeDifferential`,
-- `IsClarkeStationaryPoint`,
-- `isClarkeStationaryPoint_iff_zero_mem_clarkeDifferential`,
-- `IsLocalExtr.isClarkeStationaryPoint`
-- * inspected mathlib local-extremum owner:
-- `IsLocalExtr`,
-- `IsLocalExtr.elim`,
-- `IsLocalMax.neg`
-- * source/core/bridge triage:
-- - source-facing: `zero_mem_clarkeDifferential_of_isLocalExtr`
-- - core/canonical: `clarkeDifferential` and `IsClarkeStationaryPoint`
-- - bridge/view: local-extremum hypotheses transported to Clarke stationarity
-- * primitive data vs derived API:
-- - primitive data: the canonical local-extremum owner `IsLocalExtr f xStar` and local
-- Lipschitz regularity there
-- - derived API: the zero-functional membership conclusion in `(∂ᶜ f) xStar`
theorem zero_mem_clarkeDifferential_of_isLocalExtr
(f : X → ℝ)
(xStar : X)
(h_local : LocallyLipschitzAt f xStar)
(h_ext : IsLocalExtr f xStar) :
(0 : DualSpace) ∈ (∂ᶜ f) xStar
Lemma 14.1.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.1.6 (1): if f is convex and Lipschitz near x, then the Clarke generalized differential (∂ᶜ f) x coincides with the convex subdifferential ∂ f(x).
variable {X : Type*} [NormedAddCommGroup X] [NormedSpace ℝ X]
local notation "DualPoint" => StrongDual ℝ X
open scoped Subgradient ClarkeDirectionalDerivative ClarkeDifferential
theorem clarkeDifferential_eq_subdifferential_of_convexOn_of_locallyLipschitzAt
(f : X → ℝ)
(x : X)
(h_convex : ConvexOn ℝ Set.univ f)
(h_lipschitz : LocallyLipschitzAt f x) :
(∂ᶜ f) x = ∂ f xTheorem 14.1.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.1.7: if f : X → ℝ is convex on Set.univ and Lipschitz near xStar, and if the zero functional belongs to the Clarke generalized differential clarkeDifferential f xStar, then xStar is a local minimizer of f.
universe u
variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X]
local notation "DualSpace" => StrongDual ℝ X
open scoped ClarkeDifferential Subgradient
-- Domain sampling:
-- * primary domain: convex nonsmooth analysis on real normed spaces
-- * inspected chapter owners in the minimal closure:
-- `clarkeDifferential`,
-- `subdifferential`,
-- `mem_subdifferential_iff`,
-- `clarkeDifferential_eq_subdifferential_of_convexOn_of_locallyLipschitzAt`
-- * inspected mathlib minimizer owners:
-- `IsMinOn`,
-- `isMinOn_univ_iff`,
-- `IsMinOn.isLocalMin`
-- * source/core/bridge triage:
-- - source-facing: `isLocalMin_of_zero_mem_clarkeDifferential_of_convexOn`
-- - core/canonical: `subdifferential` together with `IsMinOn`
-- - bridge/view: Lemma 14.1.6 identifies `∂ᶜ f` with `∂ f` under convexity and local
-- Lipschitz regularity
-- * primitive data vs derived API:
-- - primitive data: convexity, local Lipschitz regularity, and the vanishing generalized
-- gradient `0 ∈ (∂ᶜ f) xStar`
-- - derived API: first a global minimizer on `Set.univ`, then the source-facing local
-- minimizer conclusion
theorem isLocalMin_of_zero_mem_clarkeDifferential_of_convexOn
(f : X → ℝ)
(xStar : X)
(h_convex : ConvexOn ℝ Set.univ f)
(h_local : LocallyLipschitzAt f xStar)
(h_zero : (0 : DualSpace) ∈ (∂ᶜ f) xStar) :
IsLocalMin f xStarTheorem 14.1.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.1.8: on a finite-dimensional real normed space, if f : X → ℝ is convex, Lipschitz on some closed ball centered at xStar, and every nonzero direction there has a positive line derivative, then f has a local linear growth bound above f xStar. The public derivative surface is the canonical HasLineDerivAt ℝ / lineDeriv ℝ owner, and the local Lipschitz hypothesis remains explicit instead of being absorbed into proof support.
universe u
-- Domain sampling:
-- * primary domain: finite-dimensional convex real-valued line derivatives and local growth;
-- * sampled canonical directional-derivative owners:
-- `HasLineDerivAt`, `lineDeriv`;
-- * sampled chapter owner-level precedent:
-- `Definition_1_2_27` uses `HasLineDerivAt` / `HasLineDerivWithinAt` as the canonical
-- directional-derivative API;
-- * sampled Chapter 14 local-Lipschitz surface:
-- `clarkeDirectionalDerivative_abs_le` and
-- `norm_le_of_mem_clarkeDifferential_of_closedBallLipschitz`, both stated with an explicit
-- closed-ball `LipschitzOnWith` hypothesis;
-- * sampled mathlib convex regularity owner:
-- `ConvexOn.locallyLipschitz`;
-- * source/core/bridge triage:
-- - source-facing: `convex_hasLinearLowerBound_near_of_pos_lineDeriv`
-- - core/canonical: `HasLineDerivAt`, `lineDeriv`, `ConvexOn`, and `LocallyLipschitzAt`
-- - bridge/view: the companion theorem
-- `convex_hasLinearLowerBound_near_of_pos_lineDeriv_of_locallyLipschitzAt`, which reuses
-- the source-facing closed-ball theorem through the canonical Chapter 14 local owner
-- * primitive data vs derived API:
-- - primitive data: finite-dimensional ambient space, convexity on `Set.univ`, and explicit
-- closed-ball Lipschitz control near `xStar`, together with positivity of the directional
-- line derivative in nonzero directions
-- - derived API: the theorem conclusion itself, plus the local-Lipschitz companion theorem
variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X] [FiniteDimensional ℝ X]
theorem convex_hasLinearLowerBound_near_of_pos_lineDeriv
(f : X → ℝ)
(xStar : X)
(h_convex : ConvexOn ℝ Set.univ f)
(h_lipschitz :
∃ ε : ℝ, 0 < ε ∧ ∃ K : NNReal, LipschitzOnWith K f (Metric.closedBall xStar ε))
(h_line : ∀ d : X, d ≠ 0 → HasLineDerivAt ℝ f (lineDeriv ℝ f xStar d) xStar d)
(h_pos : ∀ d : X, d ≠ 0 → 0 < lineDeriv ℝ f xStar d) :
∃ δ ε : ℝ, 0 < δ ∧ 0 < ε ∧
∀ x : X, ‖x - xStar‖ < ε → δ * ‖x - xStar‖ ≤ f x - f xStarDefinition 14.1.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Definition 14.1-extra-1: the global Lipschitz condition (14.1.1) on a set and the canonical local-on-a-set owner are the mathlib notions LipschitzOnWith K f Y and LocallyLipschitzOn Y f.
open Filter
universe u v
variable {X : Type u} {Z : Type v}
variable [PseudoEMetricSpace X] [PseudoEMetricSpace Z]
-- Domain sampling for the local-Lipschitz bridge:
-- - mathlib core owners: `LipschitzOnWith`, `LocallyLipschitzOn`
-- - project comparison owner: `LocallyLipschitzAt`
-- - owner abstraction here: `LocallyLipschitzOn Y f`
-- - primitive pointwise clause: `∃ K t, t ∈ nhdsWithin x Y ∧ LipschitzOnWith K f t`
-- - derived API here: the source-facing pointwise bridge name
-- `LocallyLipschitzWithinAt Y f x`
-- The later directional/Clarke layer is genuinely real-valued and starts in the next section.
#check LipschitzOnWithExample 14.1.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The absolute-value function is locally Lipschitz at every real point.
open ContinuousLinearMap
open scoped ClarkeDirectionalDerivative ClarkeDifferential
local notation "DualSpace" => StrongDual ℝ ℝ
instance absLocallyLipschitzAt (x : ℝ) : LocallyLipschitzAt abs xDefinition 14.1.extra.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Definition 14.1-extra-3: for a subset Ω ⊆ X, the support function is the supremum of the continuous-dual pairing ξ x over Ω, viewed in [-∞, ∞]. This keeps the textbook nonempty-set interpretation, while also giving the mathematically correct empty-set value ⊥.
universe u
open Set
variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X]
local notation "DualSpace" => X →L[ℝ] ℝ
namespace Set
noncomputable def supportFunction (Ω : Set X) : DualSpace → EReal :=
fun ξ ↦ sSup ((fun x : X ↦ (ξ x : EReal)) '' Ω)Definition 14.1.extra.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The lower Dini directional derivative is the liminf of the positive difference quotient (f (x + t • d) - f x) / t as t → 0, viewed in EReal so no finiteness hypothesis is silently imposed.
open Filter
open scoped ClarkeDirectionalDerivative ClarkeDifferential
universe u
variable {X : Type u} [NormedAddCommGroup X] [NormedSpace ℝ X]
-- Domain sampling:
-- * primary domain: nonsmooth stationarity on real normed spaces
-- * sampled project owners: `HasOneSidedDirectionalDerivAt`, `oneSidedDirectionalDeriv`,
-- `clarkeDirectionalDeriv`, `clarkeDifferential`
-- * source-facing layer here: the three stationary-point predicates and their optimality bridges
-- * core/canonical owners reused here: the upstream one-sided directional derivative and Clarke
-- differential APIs
-- * bridge/view retained here: the lower Dini directional derivative, which is not already owned
-- upstream in this whole-space form
-- * primitive data vs derived API: stationarity uses the upstream derivative owners directly;
-- only `diniDirectionalDeriv` is introduced as new primitive data in this file
local notation "DualSpace" => StrongDual ℝ X
def diniDirectionalDeriv (f : X → ℝ) (x d : X) : EReal :=
Filter.liminf
(fun t : ℝ ↦ (((f (x + t • d) - f x) / t : ℝ) : EReal))
(nhdsWithin (0 : ℝ) (Set.Ioi 0))
Example 14.1.extra.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The interval [-1, 1] on which Chapter14 Example 14.1-extra-5 is stated.
def example141Extra5Domain : Set ℝ :=
Set.Icc (-1 : ℝ) 114.2 — Nonsmooth Optimization Problem
Definition 14.2.extra.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
A global Lipschitz condition on f yields the local Lipschitz hypothesis required by the Chapter 14 Clarke differential at every point.
open scoped ClarkeDirectionalDerivative ClarkeDifferential
universe u
variable {X : Type u} [NormedAddCommGroup X]
theorem locallyLipschitzAt_of_lipschitzOnWith_univ
(f : X → ℝ) (x : X) {K : NNReal} (h_lipschitz : LipschitzOnWith K f Set.univ) :
LocallyLipschitzAt f x
Definition 14.2.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Definition 14.2-extra-2: for an objective f, feasible region Y, and penalty parameter σ, the associated nonsmooth unconstrained penalty objective is x ↦ f x + σ * infDist x Y, where infDist x Y is the canonical distance from x to Y.
open Metric
universe u
variable {X : Type u} [NormedAddCommGroup X]
-- Semantic recall: `Metric.infDist` is the canonical distance-to-set API, with lower-bound
-- characterization `Metric.isGLB_infDist`, and local Chapter 10 precedent records penalty
-- objectives as explicit definitions with companion `_apply` theorems.
def nonsmoothPenaltyObjective (f : X → ℝ) (Y : Set X) (σ : ℝ) : X → ℝ :=
fun x ↦ f x + σ * infDist x Y14.3 — The Subgradient Method
Algorithm 14.3.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Algorithm 14.3.1: the subgradient method for f : E → ℝ starts from an initial point x₁, and for each stage k ≥ 1 records the iterate x_k, a chosen dual subgradient g_k ∈ ∂ f(x_k), and a positive stepsize α_k. Step 3 uses the Riesz representative (InnerProductSpace.toDual ℝ E).symm g_k, so the update is x_(k + 1) = x_k + α_k • normalizedSubgradientDirection g_k, i.e. x_(k + 1) = x_k - (α_k / ‖g_k‖) • (InnerProductSpace.toDual ℝ E).symm g_k.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
local notation "DualSpace" => StrongDual ℝ E
-- Layer triage:
-- * source-facing: `sunYuanOptimalSolutionSet`, `optimalValue`, `SubgradientMethod`
-- * core/canonical: the Chapter 14 convex subdifferential owner `subdifferential`
-- from `Lemma_14_1_6`
-- * bridge/view: `normalizedSubgradientDirection` and `SubgradientMethod.directionAt`
open scoped Subgradient
variable [CompleteSpace E]
structure SubgradientMethod (E : Type u) [NormedAddCommGroup E] [InnerProductSpace ℝ E]
[CompleteSpace E] where
objective : E → ℝ
initialPoint : E
iterate : ℕ → E
subgradient : ℕ → StrongDual ℝ E
stepSize : ℕ → ℝ
iterate_one : iterate 1 = initialPoint
subgradient_mem (k : ℕ) (_ : 1 ≤ k) :
subgradient k ∈ ∂ objective (iterate k)
subgradient_norm_pos (k : ℕ) (_ : 1 ≤ k) :
0 < ‖subgradient k‖
stepSize_pos (k : ℕ) (_ : 1 ≤ k) :
0 < stepSize k
iterate_succ (k : ℕ) (_ : 1 ≤ k) :
iterate (k + 1) =
iterate k + stepSize k • normalizedSubgradientDirection (subgradient k)Lemma 14.3.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.3.2: let f : E → ℝ be convex, let xStar be a global minimizer of f, let xk be a nonoptimal point, and let gk ∈ ∂ f(xk). Then there exists Tk > 0 such that every positive stepsize α < Tk along the canonical Chapter 14 normalized subgradient direction normalizedSubgradientDirection gk = -gk / ‖gk‖ strictly decreases the Euclidean distance from xk to xStar.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
local notation "DualSpace" => StrongDual ℝ E
open scoped Subgradient
-- Layer triage:
-- * source-facing: this one-step distance-decrease lemma
-- * core/canonical: `subdifferential`
-- * bridge/view: `normalizedSubgradientDirection`
theorem exists_pos_subgradient_step_dist_lt_of_isMinOn_of_not_isMinOn_of_mem_subdifferential
(f : E → ℝ) (xk xStar : E) (gk : DualSpace)
(h_convex : ConvexOn ℝ Set.univ f)
(hxStar : IsMinOn f Set.univ xStar)
(hxk : ¬ IsMinOn f Set.univ xk)
(hgk : gk ∈ ∂ f(xk)) :
∃ Tk : ℝ, 0 < Tk ∧
∀ α : ℝ,
∀ hα_pos : 0 < α,
∀ hα_lt : α < Tk,
‖xk + α • normalizedSubgradientDirection gk - xStar‖ < ‖xk - xStar‖Theorem 14.3.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.3.3: if f is convex and S⋆[f] is nonempty, then for every δ > 0 there exists r > 0 such that every constant-step execution of Algorithm 14.3.1 for the fixed objective f with constant stepsize α < r satisfies liminf_(k → ∞) f (x_k) ≤ f⋆[f] + δ. The separate positivity assumption on α is redundant here, because method.HasConstantStepSize α together with Algorithm 14.3.1 already forces 0 < α. The execution is expressed through the canonical chapter owner SubgradientMethod E, and the liminf uses the owner companion method.objectiveValueAt.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
-- Source/core/bridge triage for this item:
-- * source-facing theorem: Theorem 14.3.3
-- * canonical upstream owners reused from `Algorithm_14_3_1`: `S⋆[f]`, `f⋆[f]`, `SubgradientMethod`
-- * bridge/view kept here: `SubgradientMethod.HasConstantStepSize`
theorem exists_pos_constant_subgradient_stepsize_liminf_le_optimalValue_add_of_convexOn
(f : E → ℝ)
(h_convex : ConvexOn ℝ Set.univ f)
(h_solution : Set.Nonempty (S⋆[f]))
{δ : ℝ} (hδ : 0 < δ) :
∃ r : ℝ, 0 < r ∧
∀ (method : SubgradientMethod E)
(h_objective : method.objective = f)
(α : ℝ)
(hα_lt : α < r)
(h_constant : method.HasConstantStepSize α),
Filter.liminf (fun k : ℕ ↦ method.objectiveValueAt (k + 1)) Filter.atTop ≤
f⋆[f] + δTheorem 14.3.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.3.4: let f be convex, let sunYuanOptimalSolutionSet f be nonempty and bounded, and let method be an Algorithm 14.3.1 execution for f. If the stepsizes satisfy (14.3.14) and (14.3.15), encoded by method.HasVanishingNonsummableStepSizes, then the distance from the iterates to the optimal solution set tends to 0.
open Filter Metric
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
theorem tendsto_infDist_sunYuanOptimalSolutionSet_zero_of_convexOn
(method : SubgradientMethod E)
(h_convex : ConvexOn ℝ Set.univ method.objective)
(h_solution : Set.Nonempty S⋆[method.objective])
(h_bounded : Bornology.IsBounded S⋆[method.objective])
(h_steps : method.HasVanishingNonsummableStepSizes) :
Tendsto
(fun k : ℕ ↦ infDist (method.iterate (k + 1)) S⋆[method.objective])
atTop
(nhds 0)Theorem 14.3.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.3.5: let f : E → ℝ be convex on a real Hilbert space, let xStar be a global minimizer of f, and assume the source angle condition, written intrinsically on the dual subgradient g ∈ ∂ f(x) as δ₁ * ‖g‖ * ‖x - xStar‖ ≤ g (x - xStar). Then for each initial iterate x1 there exist thresholds qBar ∈ (0, 1) and αBar > 0, depending on δ₁ and the source quantity ‖x1 - xStar‖, such that for every q ∈ (qBar, 1), every α0 > αBar, and every Algorithm 14.3.1 run with x₁ = x1 and geometric stepsizes α_(k + 1) = α0 * q ^ k, there exists a constant M > 0 such that the generated sequence satisfies the geometric bound ‖x (k + 1) - xStar‖ ≤ M * q ^ k for all k; here M is independent of k and is related to δ₁ and α0 as in the source statement.
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
local notation "DualSpace" => StrongDual ℝ E
open scoped Subgradient
-- Domain sampling:
-- * source-facing layer: the geometric-rate theorem for Algorithm 14.3.1 under the angle
-- condition from Theorem 14.3.5;
-- * core/canonical owners in this chapter: `SubgradientMethod`, `S⋆[f]`, and the dual
-- subgradient surface `∂ f(x)`;
-- * primitive data already live in `SubgradientMethod`;
-- * derived API refined here: the geometric-stepsize surface
-- `method.HasGeometricStepSize α0 q`.
theorem subgradientMethod_geometric_rate_of_angle_condition
(f : E → ℝ)
(xStar : E)
(h_convex : ConvexOn ℝ Set.univ f)
(hxStar : xStar ∈ S⋆[f])
(δ₁ : ℝ)
(hδ₁ : 0 < δ₁)
(h_angle :
∀ x (g : DualSpace),
g ∈ ∂ f(x) →
δ₁ * ‖g‖ * ‖x - xStar‖ ≤ g (x - xStar))
(x1 : E) :
∃ qBar : Set.Ioo (0 : ℝ) 1,
∃ αBar : Set.Ioi (0 : ℝ),
∀ (q α0 : ℝ)
(hq : q ∈ Set.Ioo qBar.1 1)
(hα0 : α0 ∈ Set.Ioi αBar.1)
(method : SubgradientMethod E)
(h_objective : method.objective = f)
(h_initial : method.initialPoint = x1)
(h_step : method.HasGeometricStepSize α0 q),
∃ M : Set.Ioi (0 : ℝ),
∀ k : ℕ, ‖method (k + 1) - xStar‖ ≤ M.1 * q ^ kTheorem 14.3.6
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.3.6: let f : E → ℝ be convex on a finite-dimensional real inner-product space, with nonempty optimal solution set. Assume that every subgradient on the sublevel-distance region infDist z (S⋆[f]) ≤ infDist (x 1) (S⋆[f]) is bounded by cBar and that f z - f⋆[f] dominates cHat * infDist z (S⋆[f]) there. Then every execution of the Polyak recursion converges to some xStar ∈ S⋆[f], and the source geometric estimate holds with rate q = polyakSubgradientLinearRate lam cBar cHat < 1, recorded by HasPolyakSubgradientGeometricRate.
open Filter Metric
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
local notation "DualSpace" => StrongDual ℝ E
open scoped Subgradient
-- Domain sampling for this item:
-- * primary domain: convex subgradient methods on real Hilbert spaces;
-- * core/canonical Chapter 14 owners reused here: the subgradient surface `∂ f(x)`,
-- `normalizedSubgradientDirection`, `sunYuanOptimalSolutionSet`, `optimalValue`, and the chapter owner
-- `SubgradientMethod`;
-- * source-facing bridge kept here: the Polyak recursion with the source stopping branch
-- "if the current iterate is optimal, keep it fixed";
-- * canonical bridge added below: under the stronger regime where every iterate remains
-- nonoptimal, the Polyak recursion refines to the chapter owner `SubgradientMethod`.
namespace IsPolyakSubgradientMethod
theorem exists_tendsto_with_geometricRate
[FiniteDimensional ℝ E]
(f : E → ℝ) (x : ℕ → E) (g : ℕ → DualSpace) (lam cBar cHat : ℝ)
(h_convex : ConvexOn ℝ Set.univ f)
(h_solution : Set.Nonempty S⋆[f])
(hLam_pos : 0 < lam)
(hLam_lt_two : lam < 2)
(hcBar : 0 < cBar)
(hcHat : 0 < cHat)
(h_method : IsPolyakSubgradientMethod f x g lam)
(h_subgradient_bound :
∀ z (ξ : DualSpace),
infDist z (S⋆[f]) ≤ infDist (x 1) (S⋆[f]) →
ξ ∈ ∂ f(z) →
‖ξ‖ ≤ cBar)
(h_error_bound :
∀ z : E,
infDist z (S⋆[f]) ≤ infDist (x 1) (S⋆[f]) →
cHat * infDist z (S⋆[f]) ≤ f z - f⋆[f]) :
∃ xStar ∈ S⋆[f],
Tendsto (fun k : ℕ ↦ x (k + 1)) atTop (nhds xStar) ∧
HasPolyakSubgradientGeometricRate x xStar
(polyakSubgradientLinearRate lam cBar cHat)Algorithm 14.3.7
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Algorithm 14.3.7: the space dilation method for f : ℝ^n → ℝ is only valid in dimension n ≥ 2. It starts from an initial point x₁, an initial scalar α > 0 with H₁ = α I, and for each stage k ≥ 1 records a chosen vector g_k whose Riesz functional lies in ∂ f(x_k). In Algorithm 14.3.7 the stepsize, rescaling factor, and coefficient are fixed by (14.3.40) as αₖ = 1 / (n + 1), rₖ = n^2 / (n^2 - 1), and βₖ = 2 / (n + 2) for every stage k ≥ 1, so their positivity properties are exposed as companion lemmas rather than as extra structure fields. The iterate update is x_(k + 1) = x_k - α_k • (g_kᵀ H_k g_k)^(-1 / 2) • (H_k g_k), and the matrix update is H_(k + 1) = r_k • (H_k - (β_k / (g_kᵀ H_k g_k)) • (H_k g_k) (g_kᵀ H_k)).
variable {n : ℕ}
open Chapter14 (IsSubgradientAt)
open scoped Subgradient
-- Domain sampling:
-- * source-facing owner in this file: `SpaceDilationMethod`
-- * chapter owner reused here: `Point` together with the bridge `IsSubgradientAt`
-- * mathlib owner reused here: `Matrix.toEuclideanLin`
-- Primitive data remain the source iterate, vector subgradient, and dilation matrix. The
-- coordinate-level matrix action wrapper has been deleted in favor of the canonical Euclidean
-- matrix action.
structure SpaceDilationMethod (n : ℕ) where
objective : Chapter14.Point n → ℝ
initialPoint : Chapter14.Point n
initialScale : ℝ
iterate : ℕ → Chapter14.Point n
subgradient : ℕ → Chapter14.Point n
dilation : ℕ → Matrix (Fin n) (Fin n) ℝ
dimension_two_le : 2 ≤ n
initialScale_pos : 0 < initialScale
iterate_one : iterate 1 = initialPoint
dilation_one : dilation 1 = initialScale • (1 : Matrix (Fin n) (Fin n) ℝ)
subgradient_mem {k : ℕ} (hk : 1 ≤ k) :
IsSubgradientAt objective (iterate k) (subgradient k)
denominator_pos {k : ℕ} (hk : 1 ≤ k) :
0 < spaceDilationDenominator (dilation k) (subgradient k)
iterate_succ {k : ℕ} (hk : 1 ≤ k) :
iterate (k + 1) =
iterate k + spaceDilationStepSize n • spaceDilationDirection (dilation k) (subgradient k)
dilation_succ {k : ℕ} (hk : 1 ≤ k) :
dilation (k + 1) =
spaceDilationMatrixUpdate
(dilation k)
(subgradient k)
(spaceDilationScaleFactor n)
(spaceDilationBeta n)Theorem 14.3.8
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.3.8: let method be a run of Algorithm 14.3.7 for a convex objective on ℝⁿ, and assume S⋆[method.objective] is nonempty. If infDist method.initialPoint S⋆[method.objective] ≤ method.initialScale, then its geometrically scaled objective error is bounded above along an unbounded subsequence, encoded by the owner-level predicate method.HasBoundedScaledObjectiveGapAlongSubsequence. This formalizes the source statement liminf_(k → ∞) ((f (x_k) - f*) / q^k) < +∞ by asserting the existence of C such that arbitrarily late indices satisfy method.scaledObjectiveGapAt (k + 1) ≤ C, where q = spaceDilationRateFactor n; the valid-dimension assumption n ≥ 2 is carried by the owner SpaceDilationMethod n itself.
open Filter Metric
variable {n : ℕ}
-- Domain sampling for this item:
-- * source-facing layer: the Theorem 14.3.8 subsequence bound for Algorithm 14.3.7
-- * core/canonical owner: `SpaceDilationMethod n`
-- * upstream Chapter 14 optimality owners: `S⋆[f]`, `f⋆[f]`, `spaceDilationRateFactor`
-- * primitive data already live in `SpaceDilationMethod`; the scaled objective-gap expression and
-- its subsequence boundedness are theorem-level derived API on that owner.
theorem exists_geometric_ratio_bound_along_subsequence_of_convexOn_spaceDilationMethod
(method : SpaceDilationMethod n)
(h_convex : ConvexOn ℝ Set.univ method.objective)
(h_solution : Set.Nonempty (S⋆[method.objective]))
(h_initial_dist : infDist method.initialPoint (S⋆[method.objective]) ≤ method.initialScale) :
method.HasBoundedScaledObjectiveGapAlongSubsequence14.4 — Cutting Plane Method
Algorithm 14.4.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Algorithm 14.4.1: the cutting-plane method for a convex objective f : ℝ^n → ℝ on a given polyhedral set S starts from an initial point x₁ ∈ S. For each stage k ≥ 1, it records the current iterate x_k, a chosen subgradient vector g_k ∈ ∂ f(x_k) in the chapter's Euclidean owner sense IsSubgradientAt, and the lower-model value v_(k+1) together with the next iterate x_(k+1) obtained by solving the Step-3 linear program over the first k affine cuts.
variable {n m : ℕ}
open Chapter14 (IsSubgradientAt Point)
open scoped Subgradient
-- Layer triage:
-- * source-facing: `CuttingPlaneMethod`, `isCuttingPlaneSubproblemSolution`
-- * core/canonical: `linearlyConstrainedPolyhedron`, `subdifferential`, `IsMaxOn`, `Prod.fst`
-- * bridge/view: `IsSubgradientAt`, `isCuttingPlaneSubproblemSolution_iff`
structure CuttingPlaneMethod (n : ℕ) where
objective : Point n → ℝ
feasibleSet : Set (Point n)
objective_convex : ConvexOn ℝ Set.univ objective
feasibleSet_polyhedral : IsPolyhedralSet feasibleSet
initialPoint : Point n
iterate : ℕ → Point n
subgradient : ℕ → Point n
lowerValue : ℕ → ℝ
iterate_one : iterate 1 = initialPoint
initialPoint_mem : initialPoint ∈ feasibleSet
subgradient_mem {k : ℕ} (hk : 1 ≤ k) :
IsSubgradientAt objective (iterate k) (subgradient k)
linearProgram_step {k : ℕ} (hk : 1 ≤ k) :
isCuttingPlaneSubproblemSolution
objective
feasibleSet
iterate
subgradient
k
(lowerValue (k + 1))
(iterate (k + 1))
Theorem 14.4.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.4.2 (1): for the sequence {v_k} generated by Algorithm 14.4.1, the tail v₂, v₃, ... is monotone increasing. The source indexing is encoded by k ↦ method.lowerValue (k + 2).
open Filter
open Chapter14
variable {n : ℕ}
local notation "Point" => Chapter14.Point n
-- Domain-style sampling:
-- * primary domain: convergence statements for the Chapter 14 cutting-plane owner
-- `CuttingPlaneMethod`
-- * inspected project owners: `Chapter14.Point`, `CuttingPlaneMethod`,
-- `CuttingPlaneMethod.optimalValue`, and the Chapter 12 accumulation-point theorem surface
-- `lagrangeNewtonMethod_accumulationPoint_isRoot`
-- * source-facing layer here: Theorem 14.4.2
-- * core/canonical owner reused here: `CuttingPlaneMethod`
-- * primitive data stay upstream in `Algorithm_14_4_1`; this file only adds derived monotonicity,
-- convergence, and accumulation-point theorems over that owner
namespace CuttingPlaneMethod
theorem lowerValue_tail_monotone
(method : CuttingPlaneMethod n) :
Monotone (fun k : ℕ ↦ method.lowerValue (k + 2))
14.5 — The Bundle Methods
Algorithm 14.5.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Algorithm 14.5.1: the conjugate subgradient method for f : ℝ^n → ℝ starts from an initial point x₁, a stagewise subgradient sequence g_k with g₁ ∈ ∂ f(x₁), parameters 0 < m₂ < m₁ < 1 / 2, 0 < m₃ < 1, ε > 0, η > 0, and the initial active set I₁ = {1}. Its Step-2 data are recorded directly by the restart formula d₁ = -g₁, the active-set combination (14.5.1) with coefficients β_(k,i), and the conjugacy relations (14.5.2)-(14.5.3) against the retained directions in I_k \\ {k}. On continuing stages η < ‖d_k‖, the recorded trial point y_k satisfies Step 3, Step 4 branches on the existential predicate HasAcceptingBundleSubgradient objective (trialPoint k) (direction k) m₁, the recorded g_(k + 1) ∈ ∂ f(y_k) is a witness on accepting stages, and Step 5 updates the active set by keeping exactly the indices whose iterates lie within ε of x_(k + 1).
variable {n : ℕ}
open Chapter14
open scoped BigOperators
local notation "Point" => Chapter14.Point n
-- Layer triage:
-- * core/canonical inherited from `Algorithm_14_3_1`: `subdifferential`
-- * source-facing: `ConjugateSubgradientMethod`
-- * bridge/view: `Chapter14.IsSubgradientAt`, Step-3/Step-4 predicates, and namespace accessors
structure ConjugateSubgradientMethod (n : ℕ) where
objective : EuclideanSpace ℝ (Fin n) → ℝ
initialPoint : EuclideanSpace ℝ (Fin n)
subgradient : ℕ → EuclideanSpace ℝ (Fin n)
m₁ : ℝ
m₂ : ℝ
m₃ : ℝ
ε : ℝ
η : ℝ
iterate : ℕ → EuclideanSpace ℝ (Fin n)
trialPoint : ℕ → EuclideanSpace ℝ (Fin n)
direction : ℕ → EuclideanSpace ℝ (Fin n)
stepSize : ℕ → ℝ
activeSet : ℕ → Finset ℕ
conjugateCoefficient : ℕ → ℕ → ℝ
m₂_pos : 0 < m₂
m₂_lt_m₁ : m₂ < m₁
m₁_lt_one_half : m₁ < 1 / 2
m₃_pos : 0 < m₃
m₃_lt_one : m₃ < 1
ε_pos : 0 < ε
η_pos : 0 < η
iterate_one : iterate 1 = initialPoint
subgradient_one_mem : IsSubgradientAt objective initialPoint (subgradient 1)
activeSet_one : activeSet 1 = ({1} : Finset ℕ)
direction_one : direction 1 = -subgradient 1
stepTwoSpec :
∀ k, 1 < k →
SatisfiesConjugateSubgradientStepTwo
subgradient
activeSet
conjugateCoefficient
direction
k
trialStep :
∀ k, 1 ≤ k → η < ‖direction k‖ →
IsConjugateSubgradientTrialStep
objective
(iterate k)
(trialPoint k)
(direction k)
(stepSize k)
m₂
m₃
ε
trialSubgradient_mem :
∀ k, 1 ≤ k → η < ‖direction k‖ →
IsSubgradientAt objective (trialPoint k) (subgradient (k + 1))
subgradient_succ_accepts_of_hasAcceptingBundleSubgradient :
∀ k, 1 ≤ k → η < ‖direction k‖ →
HasAcceptingBundleSubgradient objective (trialPoint k) (direction k) m₁ →
SatisfiesConjugateSubgradientAcceptanceTest (subgradient (k + 1)) (direction k) m₁
iterate_succ_of_accepting :
∀ k, 1 ≤ k → η < ‖direction k‖ →
HasAcceptingBundleSubgradient objective (trialPoint k) (direction k) m₁ →
iterate (k + 1) = trialPoint k
iterate_succ_of_rejecting :
∀ k, 1 ≤ k → η < ‖direction k‖ →
¬ HasAcceptingBundleSubgradient objective (trialPoint k) (direction k) m₁ →
iterate (k + 1) = iterate k
activeSet_succ :
∀ k, 1 ≤ k → η < ‖direction k‖ →
activeSet (k + 1) =
(insert (k + 1) (activeSet k)).filter
(fun i ↦ ‖iterate i - iterate (k + 1)‖ ≤ ε)Theorem 14.5.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.5.2: let method be a run of Algorithm 14.5.1 for a convex objective. Assume there is an open set U containing the initial sublevel set method.objective ⁻¹' Set.Iic (method.objective method.initialPoint) on which every subgradient of method.objective has norm at most C, and assume the shifted iterate-value sequence method.objective (method.shiftedIterate k) is bounded below. Then the algorithm terminates in finitely many iterations, i.e. there exists k ≥ 1 with method.stopsAt k.
variable {n : ℕ}
open Chapter14
local notation "Point" => Chapter14.Point n
theorem exists_stopping_stage_of_convexOn_of_bounded_subgradient_on_open_sublevelSet
(method : ConjugateSubgradientMethod n)
(C : ℝ)
(h_convex : ConvexOn ℝ Set.univ method.objective)
{U : Set Point}
(hU_open : IsOpen U)
(h_initialSublevel_subset :
method.objective ⁻¹' Set.Iic (method.objective method.initialPoint) ⊆ U)
(h_subgradient_bound :
∀ ⦃z ξ : Point⦄,
z ∈ U →
IsSubgradientAt method.objective z ξ →
‖ξ‖ ≤ C)
(h_shifted_values_bddBelow :
BddBelow (Set.range (method.objective ∘ method.shiftedIterate))) :
∃ k : ℕ, 1 ≤ k ∧ method.stopsAt kAlgorithm 14.5.3
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Algorithm 14.5.3: a bundle method for objective : ℝ^n → ℝ records the iterate sequence x_k, Step-2 bundle coefficients λ_i^(k), search directions d_k, Step-3 trial points y_k, trial subgradients g_(k + 1) ∈ ∂ objective(y_k), and linearization errors t_j^(k), together with the source initialization g₁ ∈ ∂ objective(x₁) and t_1^(1) = 1, the parameter bounds 0 < m₂ < m₁ < 1 / 2, ε > 0, η > 0, the Step-2 system (14.5.7)-(14.5.10) for the bundle weights and directions, the Step-3 admissibility rule y_k = x_k + α_k d_k with either (14.5.4) or (14.5.11), the accepted trial subgradient condition g_(k + 1) ∈ ∂ objective(y_k) together with ⟪g_(k + 1), d_k⟫ ≥ -(m₁ * ‖d_k‖ ^ 2), the Step-4 serious-step updates, the Step-5 null-step updates, and constancy of the iterate sequence after the stopping test ‖d_k‖ ≤ η.
open scoped BigOperators
open Chapter14
variable {n : ℕ}
-- Layer triage:
-- * core/canonical inherited from `Algorithm_14_3_1`: `subdifferential`
-- * source-facing: `BundleMethod`
-- * bridge/view: `Chapter14.IsSubgradientAt`, Step-2/Step-3 predicates, and namespace accessors
-- Semantic recall: `lean_leansearch` did not surface a canonical mathlib owner for bundle-method
-- runs in nonsmooth optimization. This file therefore keeps the Step-1 through Step-5 data and
-- update rules explicit in a local source-faithful `BundleMethod` owner.
structure BundleMethod (n : ℕ) where
objective : Point n → ℝ
initialPoint : Point n
iterate : ℕ → Point n
subgradient : ℕ → Point n
trialPoint : ℕ → Point n
trialStepSize : ℕ → ℝ
bundleWeight : (k : ℕ) → Fin k → ℝ
direction : ℕ → Point n
linearizationError : (k : ℕ) → Fin k → ℝ
m1 : ℝ
m2 : ℝ
epsilon : ℝ
eta : ℝ
m2_pos : 0 < m2
m2_lt_m1 : m2 < m1
m1_lt_half : m1 < (1 / 2 : ℝ)
epsilon_pos : 0 < epsilon
eta_pos : 0 < eta
iterate_one : iterate 1 = initialPoint
subgradient_one_mem : IsSubgradientAt objective initialPoint (subgradient 1)
linearizationError_one : linearizationError 1 (0 : Fin 1) = 1
stepTwoSpec (k : ℕ) (hk : 1 ≤ k) :
SolvesBundleStepTwoSystem
subgradient
linearizationError
epsilon
k
(bundleWeight k)
(direction k)
trialStepSpec (k : ℕ) (hk : 1 ≤ k) (hcont : eta < ‖direction k‖) :
IsBundleTrialStep
objective
(iterate k)
(trialPoint k)
(subgradient (k + 1))
(direction k)
(trialStepSize k)
m2
epsilon
trialSubgradientSpec (k : ℕ) (hk : 1 ≤ k) (hcont : eta < ‖direction k‖) :
IsAcceptingBundleSubgradient
objective
(trialPoint k)
(subgradient (k + 1))
(direction k)
m1
iterate_succ_of_serious
(k : ℕ)
(hk : 1 ≤ k)
(hcont : eta < ‖direction k‖)
(hserious :
SatisfiesSufficientDescentStep
objective
(iterate k)
(trialPoint k)
(direction k)
(trialStepSize k)
m2) :
iterate (k + 1) = trialPoint k
linearizationError_succ_of_serious_old
(k : ℕ)
(hk : 1 ≤ k)
(hcont : eta < ‖direction k‖)
(hserious :
SatisfiesSufficientDescentStep
objective
(iterate k)
(trialPoint k)
(direction k)
(trialStepSize k)
m2)
(i : Fin k) :
linearizationError (k + 1) (Fin.castSucc i) =
linearizationError k i +
objective (iterate (k + 1)) -
objective (iterate k) -
trialStepSize k * inner ℝ (subgradient (i.1 + 1)) (direction k)
linearizationError_succ_of_serious_new
(k : ℕ)
(hk : 1 ≤ k)
(hcont : eta < ‖direction k‖)
(hserious :
SatisfiesSufficientDescentStep
objective
(iterate k)
(trialPoint k)
(direction k)
(trialStepSize k)
m2) :
linearizationError (k + 1) (Fin.last k) = 1
iterate_succ_of_null
(k : ℕ)
(hk : 1 ≤ k)
(hcont : eta < ‖direction k‖)
(hnull :
¬ SatisfiesSufficientDescentStep
objective
(iterate k)
(trialPoint k)
(direction k)
(trialStepSize k)
m2) :
iterate (k + 1) = iterate k
linearizationError_succ_of_null_old
(k : ℕ)
(hk : 1 ≤ k)
(hcont : eta < ‖direction k‖)
(hnull :
¬ SatisfiesSufficientDescentStep
objective
(iterate k)
(trialPoint k)
(direction k)
(trialStepSize k)
m2)
(i : Fin k) :
linearizationError (k + 1) (Fin.castSucc i) = linearizationError k i
linearizationError_succ_of_null_new
(k : ℕ)
(hk : 1 ≤ k)
(hcont : eta < ‖direction k‖)
(hnull :
¬ SatisfiesSufficientDescentStep
objective
(iterate k)
(trialPoint k)
(direction k)
(trialStepSize k)
m2) :
linearizationError (k + 1) (Fin.last k) =
objective (iterate k) -
objective (trialPoint k) +
trialStepSize k * inner ℝ (subgradient (k + 1)) (direction k)
iterate_tail_eq_of_stop (k : ℕ) (hk : 1 ≤ k) (hstop : ‖direction k‖ ≤ eta)
(l : ℕ) (hkl : k ≤ l) :
iterate (l + 1) = iterate kTheorem 14.5.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.5.4: let method be a run of Algorithm 14.5.3. Assume the same convexity, open-sublevel-set, bounded-subgradient, and shifted-iterate-value lower-boundedness hypotheses as in Chapter14 Theorem 14.5.2. Then the bundle method terminates in finitely many iterations in the source sense: there exists a positive integer k such that method.isEpsilonOptimalAt k.
variable {n : ℕ}
open Chapter14
local notation "Point" => Chapter14.Point n
theorem exists_epsilonOptimal_stage_of_convexOn_of_bounded_subgradient_on_open_sublevelSet
(method : BundleMethod n)
(C : ℝ)
(h_convex : ConvexOn ℝ Set.univ method.objective)
{U : Set Point}
(hU_open : IsOpen U)
(h_initialSublevel_subset :
method.objective ⁻¹' Set.Iic (method.objective method.initialPoint) ⊆ U)
(h_subgradient_bound :
∀ ⦃z ξ : Point⦄,
z ∈ U →
IsSubgradientAt method.objective z ξ →
‖ξ‖ ≤ C)
(h_shifted_values_bddBelow :
BddBelow (Set.range (method.objective ∘ method.shiftedIterate))) :
∃ k : ℕ, 1 ≤ k ∧ method.isEpsilonOptimalAt k14.6 — Composite Nonsmooth Function
Lemma 14.6.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.6.1: for the composite objective h ∘ f, the source stationary condition that every Clarke generalized directional derivative at x is nonnegative is equivalent to nonnegativity of the source first-order model DF(x, d) in every direction.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
local notation "JacobianTranspose" => Matrix (Fin n) (Fin m) ℝ
-- Domain-style sampling:
-- * primary domain: Section 14.6 composite first-order models;
-- * inspected canonical surfaces: `clarkeDirectionalDeriv`, `clarkeDifferential`,
-- `CompositeNonsmoothOptimizationProblem`,
-- the chapter's convex subdifferential owner `∂`, and the Euclidean bridge
-- `Chapter14.IsSubgradientAt`;
-- * source-facing owners kept here: the Jacobian-transpose field, the directional-value set,
-- `compositeNonsmoothDF`, the owner-specialized model `problem.firstOrderModel`, and the
-- notation `DF[problem](x, d)`;
-- stationary-condition equivalence of Lemma 14.6.1;
-- * bridge/view: the identification of the Clarke generalized directional derivative of `h ∘ f`
-- with the source quantity `DF(x, d)`.
open scoped CompositeNonsmooth
theorem compositeNonsmoothStationaryCondition_iff_nonneg_compositeNonsmoothDF
(h : ValuePoint → ℝ) (f : Point → ValuePoint) (x : Point)
(h_contDiff : ContDiff ℝ 1 f)
(h_convex : ConvexOn ℝ Set.univ h) :
(∀ d : Point, 0 ≤ clarkeDirectionalDeriv (h ∘ f) x d) ↔
∀ d : Point, 0 ≤ compositeNonsmoothDF h f x d
Lemma 14.6.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.6.2 bundle (remaining clauses (2)-(7)) Bundle for the remaining clauses (2)-(7): if h is convex, then the source properties of χ(x, d) and ψ_t(x) hold, and the continuity clause holds when f is ContDiff ℝ 1.
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
-- Layer triage:
-- * source-facing new owner here: `compositeNonsmoothChi`, `compositeNonsmoothPsiValueSet`,
-- `compositeNonsmoothPsi`
-- * reused core mathlib directional-derivative owner: `HasDerivWithinAt` on `Set.Ici 0`
-- * reused core/canonical Section 14.6 owners from `Lemma_14_6_1`:
-- `subdifferential`, `compositeNonsmoothJacobianTranspose`,
-- `compositeNonsmoothDirectionalValueSet`, `compositeNonsmoothDF`
-- * reused earlier Chapter 14 owner via `Lemma_14_6_1`: `subdifferential` from
-- `Algorithm_14_3_1`
theorem compositeNonsmoothChiPsiBasicProperties
(h : ValuePoint → ℝ) (f : Point → ValuePoint)
(h_convex : ConvexOn ℝ Set.univ h) :
(∀ x : Point,
ConcaveOn ℝ Set.univ (fun d : Point ↦ compositeNonsmoothChi h f x d)) ∧
(∀ x d : Point,
HasDerivWithinAt
(fun t : ℝ ↦ compositeNonsmoothChi h f x (t • d))
(-compositeNonsmoothDF h f x d) (Set.Ici 0) 0) ∧
(∀ x : Point, ∀ {t : ℝ}, 0 ≤ t → 0 ≤ compositeNonsmoothPsi h f t x) ∧
(∀ x : Point,
compositeNonsmoothPsi h f 1 x = 0 ↔
∀ d : Point, 0 ≤ compositeNonsmoothDF h f x d) ∧
(∀ x : Point,
ConcaveOn ℝ (Set.Ici 0) (fun t : ℝ ↦ compositeNonsmoothPsi h f t x)) ∧
(∀ {t : ℝ}, 0 ≤ t → ∀ _ : ContDiff ℝ 1 f,
Continuous (fun x : Point ↦ compositeNonsmoothPsi h f t x))
Theorem 14.6.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.6.3: if xStar is a local minimizer of the composite objective outerFunction ∘ smoothMap, then there exists lamStar ∈ ∂ outerFunction (smoothMap xStar) such that (fderiv ℝ smoothMap xStar).adjoint ((InnerProductSpace.toDual ℝ F).symm lamStar) = 0, which is the Hilbert-space form of A(xStar) λStar = 0.
open scoped Subgradient ClarkeDifferential
universe u v
variable {E : Type u} {F : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
[FiniteDimensional ℝ E] [NormedAddCommGroup F] [InnerProductSpace ℝ F]
[FiniteDimensional ℝ F]
local notation "CoordE" => EuclideanSpace ℝ (Fin (Module.finrank ℝ E))
local notation "CoordF" => EuclideanSpace ℝ (Fin (Module.finrank ℝ F))
theorem exists_subgradient_adjoint_eq_zero_of_isLocalMin_hilbert
(smoothMap : E → F) (outerFunction : F → ℝ) (xStar : E)
(h_contDiff : ContDiff ℝ 1 smoothMap)
(h_convex : ConvexOn ℝ Set.univ outerFunction)
(h_localMin : IsLocalMin (outerFunction ∘ smoothMap) xStar) :
∃ lamStar : StrongDual ℝ F,
lamStar ∈ ∂ outerFunction (smoothMap xStar) ∧
(fderiv ℝ smoothMap xStar).adjoint ((InnerProductSpace.toDual ℝ F).symm lamStar) =
(0 : E)
Theorem 14.6.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.6.4: for a composite nonsmooth problem problem, if the source first-order quantity DF(xStar, d) represented in Lean by DF[problem](xStar, d) is strictly positive for every nonzero direction d, then xStar is a strict local minimizer of the composite objective problem.
open scoped CompositeNonsmooth
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
-- Domain-style sampling:
-- * primary domain: composite nonsmooth optimization in Chapter 14.6
-- * source-facing layer kept here: the strict-local-minimum theorem for the Chapter 14.6
-- composite problem owner
-- * core/canonical owners reused here:
-- `CompositeNonsmoothOptimizationProblem`,
-- `CompositeNonsmoothOptimizationProblem.firstOrderModel`, `DF[problem](x, d)`,
-- `IsStrictLocalMin`
-- * inspected related declarations:
-- `CompositeNonsmoothOptimizationProblem`,
-- `CompositeNonsmoothOptimizationProblem.objective`,
-- `CompositeNonsmoothOptimizationProblem.coe_apply`, `compositeNonsmoothDF`,
-- `IsStrictLocalMin`
-- * primitive data for this theorem: the Chapter 14.6 problem owner and the positivity
-- hypothesis on the source first-order model `DF(xStar, d)`
-- * derived API reused from the owner/bridge files: the composite objective coercion and the
-- Section 14.6 first-order model `problem.firstOrderModel`, written as
-- `DF[problem](xStar, d)`
theorem isStrictLocalMin_of_pos_compositeFirstOrderModel
(problem : CompositeNonsmoothOptimizationProblem n m) (xStar : Point)
(h_positive :
∀ d : Point, d ≠ 0 →
0 < DF[problem](xStar, d)) :
IsStrictLocalMin problem xStar
Definition 14.6.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Definition 14.6-extra-1: a composite nonsmooth optimization problem on ℝ^n with m component functions consists of a continuously differentiable inner map f : Point → ValuePoint and a convex outer function h : ValuePoint → ℝ; its objective is the composite function x ↦ h (f x).
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
-- Domain-style sampling:
-- * primary domain: composite nonsmooth optimization problems in Euclidean spaces;
-- * inspected canonical surfaces: `Function.comp`, `OptimizationProblem`,
-- `OptimizationProblem.coeFn_apply`, `OptimizationProblem.IsUnconstrained`;
-- * source-facing owner: the composite decomposition with regularity hypotheses in this file;
-- * core/canonical owner: `OptimizationProblem` from `Chapter01.Definition_1_1_extra_1`;
-- * bridge/view: `toOptimizationProblem`, using the Euclidean coordinate equivalence.
-- Primitive data are `smoothMap`, `outerFunction`, and the Section 14.6 regularity hypotheses
-- used by the surrounding API. The objective-function and unconstrained-problem surfaces are
-- derived API and should not be stored as additional primitive data here.
structure CompositeNonsmoothOptimizationProblem (n m : ℕ) where
smoothMap : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin m)
outerFunction : EuclideanSpace ℝ (Fin m) → ℝ
smoothMap_contDiff : ContDiff ℝ 1 smoothMap
outerFunction_convex : ConvexOn ℝ Set.univ outerFunctionExample 14.6.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The residual vector A x - b for the linear system A x = b, viewed as a point of EuclideanSpace ℝ (Fin m).
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ResidualPoint" => EuclideanSpace ℝ (Fin m)
-- Source-facing layer: the residual vector and its norm-minimization objective for `A x = b`.
-- Core/canonical owner: the Euclidean matrix action `Matrix.toEuclideanLin A`.
-- Bridge/view: the coordinate formula `WithLp.toLp 2 (A.mulVec x.ofLp - b.ofLp)`, together with
-- the Chapter 7 squared least-squares owner specialized to the linear residual.
def linearSystemResidual
(A : Matrix (Fin m) (Fin n) ℝ) (b : ResidualPoint) (x : Point) : ResidualPoint :=
Matrix.toEuclideanLin A x - bNotation 14.6.extra.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Notation 14.6-extra-3: the source quantities (14.6.4)-(14.6.6) are the canonical Section 14.6 owners already introduced in Lemma_14_6_2.
open scoped CompositeNonsmooth
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
-- Domain sampling across the local Section 14.6 files shows that `Lemma_14_6_2` already owns
-- the canonical specialized composite nonsmooth API:
-- * `subdifferential`
-- * `compositeNonsmoothJacobianTranspose`
-- * `compositeNonsmoothChi`
-- * `compositeNonsmoothPsiValueSet`
-- * `compositeNonsmoothPsi`
-- * `compositeNonsmoothDirectionalValueSet`
-- * `compositeNonsmoothDF`
-- This notation item is therefore a bridge/view layer: it keeps only the extra
-- maximal-attainment companions for `(14.6.5)`.
#check
fun (h : ValuePoint → ℝ) (f : Point → ValuePoint) (x d : Point) ↦
compositeNonsmoothChi h f x d
14.7 — Trust Region Method for Composite Problems
Algorithm 14.7.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Algorithm 14.7.1, refined to the chosen trust-region norm ρ: a trust-region run for a composite nonsmooth optimization problem records an initial point x₁, an initial multiplier vector λ₀, an initial trust-region radius Δ₁ > 0, a tolerance ε ≥ 0, the iterate sequence x_k, the multiplier sequence λ_k, the directions d_k, and the trust-region radii Δ_k. The source hypothesis that each scalar component f_i is twice continuously differentiable is recorded directly through componentContDiff; the Hessian matrices ∇² f_i(x) and the Step-1 approximation B_k = ∑ i, λ_(k - 1, i) ∇² f_i(x_k) from (14.7.7) are then derived canonically through the Chapter 3 Hessian-matrix bridge. The Jacobian-transpose field A(x) = ∇ f(x)ᵀ and the model functions φ_k are likewise derived from the composite problem and the stage data. At each stage k ≥ 1, the recorded direction solves the trust-region subproblem built from that canonical Jacobian data, the current Hessian approximation, and the chosen norm ρ; the source Algorithm 14.7.1 is the specialization ρ = l2Norm. The stopping case ρ (d_k.ofLp) ≤ ε is allowed; only continuing stages with ε < ρ (d_k.ofLp) satisfy the Step-3 radius update and the Step-4/Step-5 iterate and multiplier rules. On accepted steps x_(k + 1) = x_k + d_k, and the new multiplier λ_k satisfies the Step-5 relation (14.7.5).
open scoped BigOperators CompositeNonsmooth
variable {n m : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- Domain sampling:
-- * source-facing owners in this file: the trust-region model, its chosen-norm subproblem solver
-- predicate, the accepted-step multiplier relation, and the method structure;
-- * core/canonical owner reused from `Definition_14_6_extra_1`:
-- `CompositeNonsmoothOptimizationProblem`;
-- * chosen trust-region-norm owners reused from Chapter 01/13:
-- `IsVectorNorm` and `trustRegionPenaltyFeasibleSet`;
-- * core/canonical Hessian owner reused from Chapter 3:
-- `hessianAt`;
-- * reused matrix bridge from Chapter 3:
-- `hessianMatrixAt`;
-- * reused Euclidean bridge from `EuclideanSubgradient`:
-- `Chapter14.IsSubgradientAt`.
-- Primitive data here are the composite problem, the `C²` regularity of the scalar components
-- `x ↦ problem.smoothMap x i`, the chosen trust-region norm `ρ`, and the stage records; the
-- Euclidean Hessian matrices
-- `∇² f_i(x)` and the trust-region matrices `B_k` are derived from the Chapter 3 owners rather
-- than stored as extra representative data. The Section 14.6 directional quantity is reused
-- directly from the owner-specialized surface `problem.firstOrderModel`, written as
-- `DF[problem](x, d)`.
structure CompositeNonsmoothTrustRegionMethod
(n m : ℕ) (ρ : (Fin n → ℝ) → ℝ) [IsVectorNorm ρ] where
problem : CompositeNonsmoothOptimizationProblem n m
componentContDiff :
∀ i : Fin m, ContDiff ℝ 2 (fun y : Chapter14.Point n ↦ problem.smoothMap y i)
initialPoint : Chapter14.Point n
initialMultiplier : Chapter14.Point m
initialRadius : ℝ
epsilon : ℝ
iterate : ℕ → Chapter14.Point n
multiplier : ℕ → Chapter14.Point m
direction : ℕ → Chapter14.Point n
trustRegionRadius : ℕ → ℝ
initialRadius_pos : 0 < initialRadius
epsilon_nonneg : 0 ≤ epsilon
iterate_one : iterate 1 = initialPoint
multiplier_zero : multiplier 0 = initialMultiplier
trustRegionRadius_one : trustRegionRadius 1 = initialRadius
direction_subproblem_solution
(k : ℕ) (_hk : 1 ≤ k) :
IsCompositeNonsmoothTrustRegionSolution
ρ
problem
(iterate k)
(CompositeNonsmoothTrustRegion.hessianApproximationAt problem iterate multiplier k)
(trustRegionRadius k)
(direction k)
predictedReduction_pos
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp) :
0 <
trustRegionPredictedReduction
(CompositeNonsmoothTrustRegion.modelAt problem iterate multiplier k)
(direction k)
trustRegionRadius_succ
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp) :
trustRegionRadius (k + 1) =
if CompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
multiplier
direction
k <
(1 / 4 : ℝ) then
ρ (direction k).ofLp / 4
else if (3 / 4 : ℝ) <
CompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
multiplier
direction
k ∧
ρ (direction k).ofLp = trustRegionRadius k then
2 * trustRegionRadius k
else
trustRegionRadius k
iterate_succ_of_positive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
0 <
CompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
multiplier
direction
k) :
iterate (k + 1) = CompositeNonsmoothTrustRegion.trialPoint iterate direction k
multiplier_of_positive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
0 <
CompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
multiplier
direction
k) :
IsCompositeNonsmoothAcceptedStepMultiplier
problem
(CompositeNonsmoothTrustRegion.trialPoint iterate direction k)
(direction k)
(multiplier k)
iterate_succ_of_nonpositive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
CompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
multiplier
direction
k ≤
0) :
iterate (k + 1) = iterate k
multiplier_of_nonpositive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
CompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
multiplier
direction
k ≤
0) :
multiplier k = multiplier (k - 1)
Theorem 14.7.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.7.2: let method be a run of Algorithm 14.7.1 for a composite nonsmooth optimization problem with twice continuously differentiable component functions f_i. If the iterate sequence {x_k} generated by method is bounded, then there exists an accumulation point xStar of {x_k}, formalized by a convergent subsequence φ, and that limit is a stationary point of the underlying optimization problem (14.6.1).
open Filter
open scoped CompositeNonsmooth
variable {n m : ℕ}
variable {ρ : (Fin n → ℝ) → ℝ} [IsVectorNorm ρ]
local notation "Point" => Chapter14.Point n
local notation "Method" => @_root_.CompositeNonsmoothTrustRegionMethod n m ρ _
variable (method : Method)
-- Domain sampling:
-- * primary domain: accumulation-point existence for composite nonsmooth trust-region runs;
-- * inspected owner declarations in this domain:
-- `HasSubsequenceTendstoTo` from `Chapter05.Definition_5_4_extra_1` for convergent-subsequence
-- data;
-- `CompositeNonsmoothTrustRegionMethod` from `Algorithm_14_7_1` for the algorithm owner;
-- `IsClarkeStationaryPoint` from `Definition_14_1_extra_4` for the stationary-point owner;
-- `DF[problem](x, d)` from `Lemma_14_6_2` / `Definition_14_6_extra_1` for the owner-level
-- first-order model;
-- * best owner abstraction for the accumulation data: `HasSubsequenceTendstoTo`;
-- * core/canonical owner reused from `Algorithm_14_7_1`:
-- `CompositeNonsmoothTrustRegionMethod`;
-- * canonical stationary-point owner reused from Section 14.1:
-- `IsClarkeStationaryPoint`;
-- * layer triage:
-- - source-facing: `compositeNonsmoothTrustRegion_exists_stationaryAccumulationPoint`, which
-- keeps the textbook convergent-subsequence formulation;
-- - bridge/view:
-- `compositeNonsmoothTrustRegion_exists_clarkeStationaryAccumulationPoint`, which rewrites
-- the same content through the Chapter 5 owner `HasSubsequenceTendstoTo`;
-- - core/canonical owners remain `CompositeNonsmoothTrustRegionMethod`,
-- `HasSubsequenceTendstoTo`, and `IsClarkeStationaryPoint`.
theorem compositeNonsmoothTrustRegion_exists_stationaryAccumulationPoint
(method : Method)
(h_bounded : Bornology.IsBounded (Set.range method.iterate)) :
∃ xStar : Point, ∃ φ : ℕ → ℕ,
StrictMono φ ∧
Tendsto (method.iterate ∘ φ) atTop (nhds xStar) ∧
IsClarkeStationaryPoint method.problem xStar
Corollary 14.7.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Corollary 14.7.3: once Theorem 14.7.2 is stated through the canonical accumulation owner HasSubsequenceTendstoTo, the extra bounded-B_k hypothesis does not supply additional mathematical data for the conclusion. The corollary is therefore a direct recall of the existing Chapter 14 theorem surface rather than a second parallel theorem wrapper.
#check compositeNonsmoothTrustRegion_exists_clarkeStationaryAccumulationPoint
Lemma 14.7.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.7.4: if dk solves the composite nonsmooth trust-region subproblem (14.7.1)-(14.7.2) built from the canonical Jacobian transpose A(x) = ∇ f(x)ᵀ, then the canonical predicted reduction φ_k(0) - φ_k(dk) is bounded below by the standard trust-region expression involving ψ_(Δ_k)(x_k). To avoid Lean's / 0 = 0 convention from silently weakening the source formula when ‖Bk‖ = 0, the zero-operator-norm case is stated explicitly.
open scoped Matrix.Norms.L2Operator
variable {n m : ℕ}
variable {ρ : (Fin n → ℝ) → ℝ} [IsVectorNorm ρ]
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
variable (problem : CompositeNonsmoothOptimizationProblem n m)
variable (xk dk : Point) (Bk : MatrixN) (Δk : ℝ)
local notation "ψₖ" => compositeNonsmoothPsi problem.outerFunction problem.smoothMap Δk xk
-- Domain sampling:
-- * primary domain: Chapter 14's composite nonsmooth trust-region model and its predicted
-- reduction bound;
-- * core/canonical owners inspected upstream:
-- `compositeNonsmoothTrustRegionModel`,
-- `IsCompositeNonsmoothTrustRegionSolution` from `Algorithm_14_7_1`,
-- `compositeNonsmoothPsi` from `Lemma_14_6_2`,
-- and the Section 14.6 Jacobian owner `compositeNonsmoothJacobianTranspose` from
-- `Lemma_14_6_1`;
-- * layer triage for this file: the theorem remains source-facing, while its inputs now reuse the
-- existing chapter owners instead of redeclaring parallel local wrappers.
theorem compositeNonsmoothTrustRegionPredictedReductionLowerBound
(hdk : IsCompositeNonsmoothTrustRegionSolution
ρ
problem
xk
Bk
Δk
dk) :
trustRegionPredictedReduction
(compositeNonsmoothTrustRegionModel
problem
xk
Bk)
dk ≥
if ‖Bk‖ = 0 then
(1 / 2 : ℝ) * ψₖ
else
(1 / 2 : ℝ) * ψₖ * min (1 : ℝ) (ψₖ / (‖Bk‖ * Δk ^ 2))
Theorem 14.7.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.7.5 works with the source-facing generalization of Algorithm 14.7.1 in which the Hessian approximation sequence B_k is primitive data rather than the special choice from (14.7.7). The remaining trust-region subproblem, radius update, iterate update, and accepted-step multiplier rules are unchanged, but they use the recorded B_k directly. The specialized Chapter 14.7 owner is recovered by the bridge CompositeNonsmoothTrustRegionMethod.toGeneralizedCompositeNonsmoothTrustRegionMethod.
open Filter
open scoped BigOperators Matrix.Norms.L2Operator
variable {n m : ℕ}
variable {ρ : (Fin n → ℝ) → ℝ} [IsVectorNorm ρ]
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
local notation "MonotoneMethod" => @_root_.CompositeNonsmoothTrustRegionMethod n m ρ _
-- Domain sampling:
-- * primary domain: accumulation-point existence for composite nonsmooth trust-region runs whose
-- Hessian approximation sequence `B_k` is primitive and only required to satisfy `(14.7.12)`;
-- * inspected owner declarations in the minimal semantic closure:
-- `CompositeNonsmoothTrustRegionMethod` and
-- `CompositeNonsmoothTrustRegionMethod.hessianApproximationAt` from `Algorithm_14_7_1`,
-- `HasSubsequenceTendstoTo` from `Chapter05.Definition_5_4_extra_1`,
-- `IsClarkeStationaryPoint` from `Definition_14_1_extra_4`,
-- and `compositeNonsmoothTrustRegion_exists_clarkeStationaryAccumulationPoint` from
-- `Theorem_14_7_2`;
-- * best owner abstraction: the source-facing generalized method owner below, whose primitive
-- stage data includes the matrix sequence `B_k`;
-- * primitive data vs derived API:
-- primitive data are the composite problem, the `C²` regularity of the component functions,
-- the stage sequences `x_k`, `λ_k`, `d_k`, `Δ_k`, and the primitive Hessian approximation
-- sequence `B_k`;
-- derived API is the trust-region model, reduction ratio, accumulation-point packaging through
-- `HasSubsequenceTendstoTo`, and Clarke stationarity;
-- * layer triage:
-- - source-facing: `GeneralizedCompositeNonsmoothTrustRegionMethod`,
-- `SatisfiesHessianApproximationCondition14712`, and Theorem 14.7.5 below;
-- - core/canonical: `HasSubsequenceTendstoTo` and `IsClarkeStationaryPoint`;
-- - bridge/view:
-- `CompositeNonsmoothTrustRegionMethod.toGeneralizedCompositeNonsmoothTrustRegionMethod`,
-- which embeds the stricter `(14.7.7)` owner into this more general source-facing owner.
structure GeneralizedCompositeNonsmoothTrustRegionMethod
(n m : ℕ) (ρ : (Fin n → ℝ) → ℝ) [IsVectorNorm ρ] where
problem : CompositeNonsmoothOptimizationProblem n m
componentContDiff :
∀ i : Fin m, ContDiff ℝ 2 (fun y : EuclideanSpace ℝ (Fin n) ↦ problem.smoothMap y i)
initialPoint : EuclideanSpace ℝ (Fin n)
initialMultiplier : EuclideanSpace ℝ (Fin m)
initialRadius : ℝ
epsilon : ℝ
iterate : ℕ → EuclideanSpace ℝ (Fin n)
multiplier : ℕ → EuclideanSpace ℝ (Fin m)
hessianApproximation : ℕ → Matrix (Fin n) (Fin n) ℝ
direction : ℕ → EuclideanSpace ℝ (Fin n)
trustRegionRadius : ℕ → ℝ
initialRadius_pos : 0 < initialRadius
epsilon_nonneg : 0 ≤ epsilon
iterate_one : iterate 1 = initialPoint
multiplier_zero : multiplier 0 = initialMultiplier
trustRegionRadius_one : trustRegionRadius 1 = initialRadius
direction_subproblem_solution
(k : ℕ) (_hk : 1 ≤ k) :
IsCompositeNonsmoothTrustRegionSolution
ρ
problem
(iterate k)
(hessianApproximation k)
(trustRegionRadius k)
(direction k)
predictedReduction_pos
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp) :
0 <
trustRegionPredictedReduction
(GeneralizedCompositeNonsmoothTrustRegion.modelAt
problem
iterate
hessianApproximation
k)
(direction k)
trustRegionRadius_succ
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp) :
trustRegionRadius (k + 1) =
if GeneralizedCompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
hessianApproximation
direction
k <
(1 / 4 : ℝ) then
ρ (direction k).ofLp / 4
else if (3 / 4 : ℝ) <
GeneralizedCompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
hessianApproximation
direction
k ∧
ρ (direction k).ofLp = trustRegionRadius k then
2 * trustRegionRadius k
else
trustRegionRadius k
iterate_succ_of_positive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
0 <
GeneralizedCompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
hessianApproximation
direction
k) :
iterate (k + 1) = CompositeNonsmoothTrustRegion.trialPoint iterate direction k
multiplier_of_positive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
0 <
GeneralizedCompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
hessianApproximation
direction
k) :
IsCompositeNonsmoothAcceptedStepMultiplier
problem
(CompositeNonsmoothTrustRegion.trialPoint iterate direction k)
(direction k)
(multiplier k)
iterate_succ_of_nonpositive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
GeneralizedCompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
hessianApproximation
direction
k ≤
0) :
iterate (k + 1) = iterate k
multiplier_of_nonpositive_ratio
(k : ℕ) (_hk : 1 ≤ k) (_hContinue : epsilon < ρ (direction k).ofLp)
(_hrk :
GeneralizedCompositeNonsmoothTrustRegion.reductionRatioAt
problem
iterate
hessianApproximation
direction
k ≤
0) :
multiplier k = multiplier (k - 1)
14.8 — Nonsmooth Newton’s Method
Lemma 14.8.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.8.1 (1): if F : ℝ^n → ℝ^m is locally Lipschitz at x and has a right directional derivative in every direction at x, then the map h ↦ F'(x; h) is Lipschitz.
variable {n m : ℕ}
open scoped GeneralizedJacobian
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "ValuePoint" => EuclideanSpace ℝ (Fin m)
local notation "JacobianMap" => Point →L[ℝ] ValuePoint
local notation "JacobianMatrix" => Matrix (Fin m) (Fin n) ℝ
-- Domain sampling / source-core-bridge triage:
-- * source-facing: Lemma 14.8.1, a directional-derivative regularity and generalized-Jacobian
-- representation statement for maps `ℝ^n → ℝ^m`
-- * core/canonical Chapter 14 owners already present upstream:
-- the generalized-Jacobian owner `∂ F` and the matrix bridge `generalizedJacobianMatrix F x`
-- from
-- `Definition_14_8_extra_1`, together with the Euclidean matrix bridge
-- `jacobianMatrixOfMap`, `LocallyLipschitzAt` from `Definition_14_8_extra_4`, and the
-- Euclidean matrix action `Matrix.toEuclideanLin`
-- * primitive data in this file: local Lipschitz regularity at `x` and one-sided directional
-- differentiability in every direction
-- * derived API: the Lipschitz regularity of `h ↦ F'(x; h)`, the intrinsic operator-level
-- generalized-Jacobian representation, and the matrix-coordinate bridge for files that
-- genuinely need `generalizedJacobianMatrix`
variable (F : Point → ValuePoint) (x : Point)
theorem oneSidedDirectionalDeriv_lipschitz
(h_local : LocallyLipschitzAt F x)
(h_dir :
∀ h : Point, HasOneSidedDirectionalDerivAt F (oneSidedDirectionalDeriv F x h) x h) :
∃ L : NNReal, LipschitzWith L (fun h ↦ oneSidedDirectionalDeriv F x h)Lemma 14.8.2
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Lemma 14.8.2: if F is Lipschitz on some closed ball centered at x and every V ∈ (∂ F) x = ∂F(x) is nonsingular, then there is a positive-radius neighborhood of x and a constant C such that every nearby generalized Jacobian (∂ F) y = ∂F(y) is nonempty, and every V ∈ (∂ F) y with y in that neighborhood is nonsingular and satisfies (14.8.20): ‖V.inverse‖ ≤ C.
open Filter
variable {n : ℕ}
open scoped GeneralizedJacobian
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "Operator" => Point →L[ℝ] Point
-- Source/core/bridge triage:
-- * source-facing: Lemma 14.8.2, a neighborhood inverse-bound statement for `∂F`
-- * core/canonical: `generalizedJacobian F x : Set Operator`
-- from `Chapter14.Definition_14_8_extra_2`
-- * bridge/view: the deleted matrix-coordinate presentation, which carried no extra mathematics
theorem exists_ball_bound_of_generalizedJacobian_nonsingularAt
(F : Point → Point)
(x : Point)
(h_local : LocallyLipschitzAt F x)
(h_nonsingular :
∀ ⦃V : Operator⦄, V ∈ (∂ F) x → V.IsInvertible) :
∃ r > 0, ∃ C : ℝ,
∀ ⦃y : Point⦄, y ∈ Metric.ball x r →
((∂ F) y).Nonempty ∧
∀ ⦃V : Operator⦄, V ∈ (∂ F) y →
V.IsInvertible ∧ ‖V.inverse‖ ≤ C
Theorem 14.8.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.8.3 (1): if xStar solves F x = 0, F is semismooth at xStar, and every V ∈ (∂ F) xStar = ∂F(xStar) is invertible, then the semismooth Newton method (14.8.18) is well-defined on some positive-radius closed-ball neighborhood of xStar.
open Filter
open scoped GeneralizedJacobian
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "JacobianMap" => Point →L[ℝ] Point
-- Domain sampling pass:
-- * canonical Chapter 14 owners reused here: `LocallyLipschitzAt` and `SemismoothAt` from
-- `Definition_14_8_extra_2`, `generalizedJacobian F` from `Definition_14_8_extra_1`, and
-- `NonsmoothNewtonMethod` from `Algorithm_14_8_extra_5` together with
-- `generalizedNewtonStep` from `Exercise_14_13`
-- * source-facing order bridge reused here: `OrderSemismoothAt`, `semismoothRemainderFilter`,
-- and `semismoothRemainder` from `Definition_14_8_extra_4`
-- * upstream directional-derivative owner reused through that file:
-- `HasOneSidedDirectionalDerivAt` and `oneSidedDirectionalDeriv`
-- * theorem-local layer here: Newton iteration well-definedness on closed balls, together with
-- the local convergence and source-facing error-estimate owners built on the canonical
-- Chapter 1 owner `HasQOrderConvergenceTo`
theorem semismoothNewton_exists_wellDefined_closedBall
(F : Point → Point) (xStar : Point)
(h_assumptions : HasSemismoothNewtonLocalConvergenceAssumptions F xStar) :
∃ r : ℝ, 0 < r ∧
SemismoothNewtonWellDefinedOnClosedBall F xStar r
Theorem 14.8.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Theorem 14.8.4: under the same assumptions, the semismooth Newton iterates of method converge to the unique solution x* ∈ S of method.map x* = 0. The closed-ball uniqueness conclusion reuses the canonical owner IsUniqueZeroOnClosedBall method.map method.initialPoint r xStar.
open Filter
open scoped GeneralizedJacobian
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "JacobianMap" => Point →L[ℝ] Point
-- Domain-style sampling:
-- * primary domain: semismooth generalized-Newton convergence on closed balls in Euclidean space
-- * core/canonical owner reused here for semismooth directional data:
-- `SemismoothAt` and its derived common-limit theorem
-- `SemismoothAt.existsCommonLimit` from `Definition_14_8_extra_2`
-- * core/canonical owner reused here for the closed-ball convergence data:
-- `HasGeneralizedNewtonClosedBallConvergenceAssumptions` from `Exercise_14_13`
-- * core/canonical owner reused here for closed-ball uniqueness:
-- `IsUniqueZeroOnClosedBall` from `Exercise_14_13`
-- * source-facing semismooth Newton method owner reused here:
-- `NonsmoothNewtonMethod` from `Algorithm_14_8_extra_5`
-- * layer used here:
-- source-facing closed-ball semismooth Newton assumptions on top of the canonical owners above
-- * primitive data kept here:
-- semismoothness on the closed ball and the chosen linearization-limit data for `semideriv`
-- * derived API kept here:
-- the semismooth difference-quotient limit and the closed-ball convergence consequences
variable (method : NonsmoothNewtonMethod n) (semideriv : Point → Point → Point)
variable (r β γ δ : ℝ)
variable (h_assumptions :
HasSemismoothNewtonGlobalConvergenceAssumptions
method.map semideriv method.initialPoint r β γ δ)
include semideriv β γ δ h_assumptions
theorem semismoothNewton_existsUniqueRoot_tendsto
:
∃ xStar : Point,
IsUniqueZeroOnClosedBall method.map method.initialPoint r xStar ∧
Tendsto method.iterate atTop (nhds xStar)
Definition 14.8.extra.1
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
Chapter14 Definition 14.8-extra-1: for a map F : X → Y, the generalized Jacobian ∂F(x) is the convex hull of all Jacobian-map limits obtained from sequences x_i → x through differentiability points, with the intrinsic Fréchet derivative fderiv ℝ F (x_i) as the primitive Jacobian object. The source Euclidean ℝ^n → ℝ^m case is recovered by specializing X and Y to finite-dimensional real Euclidean spaces; the matrix layer is a separate bridge below.
open Filter
universe u v
variable {X : Type u} {Y : Type v}
variable [NormedAddCommGroup X] [NormedSpace ℝ X]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
def generalizedJacobian (F : X → Y) (x : X) : Set (X →L[ℝ] Y) :=
convexHull ℝ
{V : X →L[ℝ] Y | ∃ xs : ℕ → X,
Tendsto xs atTop (nhds x) ∧
(∀ i : ℕ, DifferentiableAt ℝ F (xs i)) ∧
Tendsto (fun i : ℕ ↦ fderiv ℝ F (xs i)) atTop (nhds V)}Definition 14.8.extra.2
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The joint filter encoding V ∈ ∂ F (x + t • h'), h' → h, and t ↓ 0 for the chapter-level generalized Jacobian owner ∂ F.
open Filter
universe u v
variable {X : Type u} {Y : Type v}
variable [NormedAddCommGroup X] [NormedSpace ℝ X]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
local notation "JacobianMap" => X →L[ℝ] Y
-- Domain sampling pass:
-- * primary domain: semismoothness of locally Lipschitz maps `F : X → Y`
-- * core/canonical owner reused from the chapter: `generalizedJacobian F x : Set JacobianMap`
-- from `Definition_14_8_extra_1`
-- * primitive data in this file: the semismooth linearization limit/filter surface built from
-- that owner, together with the shared Chapter 14 owner `LocallyLipschitzAt`
-- * derived API in this file: `SemismoothAt`, its unfolding theorem, and the common-limit
-- consequence for difference quotients
open scoped GeneralizedJacobian
def semismoothSelectionFilter
(F : X → Y) (x h : X) : Filter (JacobianMap × X × ℝ) :=
principal {p | p.1 ∈ (∂ F) (x + p.2.2 • p.2.1)} ⊓
comap (fun p : JacobianMap × X × ℝ ↦ (p.2.1, p.2.2))
(nhds h ×ˢ nhdsWithin (0 : ℝ) (Set.Ioi 0))Definition 14.8.extra.3
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The book's "strong Fréchet derivative at x" is the canonical mathlib predicate HasStrictFDerivAt F A x, encoding (F z - F y - A (z - y)) / ‖z - y‖ → 0 as (y, z) → (x, x).
variable {n : ℕ}
open Filter
open scoped GeneralizedJacobian
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "JacobianMap" => Point →L[ℝ] Point
#check HasStrictFDerivAt
Definition 14.8.extra.4
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The pair filter encoding V ∈ (∂ F) (x + h) together with h → 0 from the source order-semismoothness condition.
open Asymptotics Filter
open scoped GeneralizedJacobian
universe u v
variable {X : Type u} {Y : Type v}
variable [NormedAddCommGroup X] [NormedSpace ℝ X]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
local notation "JacobianMap" => X →L[ℝ] Y
-- Domain sampling pass:
-- * primary domain: Chapter 14 semismoothness for maps `F : X → Y`
-- * core/canonical owners reused from earlier Chapter 14 files:
-- `generalizedJacobian F` from `Definition_14_8_extra_1`,
-- `LocallyLipschitzAt F x` and `SemismoothAt F x` from `Definition_14_8_extra_2`
-- * source-facing owner added in this file: `OrderSemismoothAt F x p`
-- * bridge/view layer added in this file: the order-semismooth remainder filter and remainder
-- estimate built from the canonical generalized-Jacobian owner `∂ F`
def semismoothRemainderFilter
(F : X → Y) (x : X) :
Filter (JacobianMap × X) :=
principal {q | q.1 ∈ (∂ F) (x + q.2)} ⊓
comap Prod.snd (nhds (0 : X))Algorithm 14.8.extra.5
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
The nonsmooth Newton update x - V⁻¹(F x) from (14.8.18) for a selected nonsingular matrix V.
variable {n : ℕ}
local notation "Point" => EuclideanSpace ℝ (Fin n)
local notation "JacobianMap" => Point →L[ℝ] Point
local notation "MatrixN" => Matrix (Fin n) (Fin n) ℝ
-- The generalized-Jacobian owner is `Definition_14_8_extra_1.generalizedJacobian`, with the
-- matrix coordinate surface `generalizedJacobianMatrix` used here for Newton steps that invert
-- selected matrices.
def nonsmoothNewtonStep (F : Point → Point) (x : Point) (V : MatrixN) : Point :=
x - Matrix.toEuclideanLin V⁻¹ (F x)Supporting modules
These source modules support the indexed items and are listed separately so the chapter inventory remains complete.
-
EuclideanSubgradient.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
LocallyLipschitzAt.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.
-
OneSidedDirectionalDeriv.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Wanli Ma, Zichen Wang.