Chapter 04 — Second-Order Methods

Proofs omitted. Hover over highlighted terms to see their Lean types.

4.1 — Cubic Regularization of Newton’s Method

Algorithm 4.1.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.1.1 on the intrinsic operator layer: if the regularized Hessian operator G_k = hessian f xk + γ • 1 is nondegenerate, then the Levenberg--Marquardt update is obtained by applying its inverse to the gradient.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] def levenbergMarquardtRegularizedNewtonStep (f : E → ℝ) (xk : E) (γ : ℝ) (hG : (levenbergMarquardtRegularizedHessian f xk γ).det ≠ 0) : E := xk - (((levenbergMarquardtRegularizedHessian f xk γ).toContinuousLinearEquivOfDetNeZero hG).symm (∇ f xk))

Definition 4.1.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.1 reuses the imported pointwise and set-builder companion facts directly.

universe u v open scoped LevelSetNotation recall mem_levelSet_iff {E : Type u} {α : Type v} [Preorder α] {f : E → α} {a : α} {x : E} : x ∈ f ⁻¹' Set.Iic a ↔ f x ≤ a

Lemma 4.1.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.1 (1): if f has L-Lipschitz Hessian on 𝓕, then for x, y ∈ 𝓕 the first-order Taylor remainder in the gradient is bounded by (L / 2) * ‖y - x‖².

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L : NNReal} {𝓕 : Set E} {f : E → ℝ} namespace HessianLipschitzOn theorem gradient_deviation_le (hf : HessianLipschitzOn L 𝓕 f) (x y : E) (hx : x ∈ 𝓕) (hy : y ∈ 𝓕) : ‖∇ f y - ∇ f x - hessian f x (y - x)‖ ≤ ((L : ℝ) / 2) * ‖y - x‖ ^ (2 : ℕ)

Proposition 4.1.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.1: if f is C² at a local minimizer xStar : ℝⁿ, then the gradient vanishes and the Hessian is positive semidefinite at xStar.

open scoped Gradient variable {n : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem local_minimizer_gradient_eq_zero_and_hessian_posSemidef (f : E → ℝ) (xStar : E) (hf : ContDiffAt ℝ 2 f xStar) (hmin : IsLocalMin f xStar) : ∇ f xStar = 0 ∧ (∇² f xStar).PosSemidef

Theorem 4.1.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.1 (1): for a cubic-regularization method, the textbook decrease estimate is derived from the owner data, so a lower bound f* ≤ f suffices to conclude that ∑_{i=0}^∞ r_{Mᵢ}(xᵢ)^3 is summable and bounded by (12 / L₀) (f(x₀) - f*).

open Filter open scoped BigOperators Gradient open scoped CubicRegularizationResidual universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {stepMap : ℝ → E → E} {L0 L : ℝ} {x0 : E} {fStar : ℝ} variable (method : CubicRegularizationMethod f stepMap L0 L x0) local notation:max "r[" M "](" x ")" => r[stepMap M x] x theorem cubicRegularization_residual_cube_summable_and_tsum_le (hf_lower : ∀ z : E, fStar ≤ f z) : Summable (fun i ↦ r[method.regularization i](method i) ^ (3 : ℕ)) ∧ (∑' i, r[method.regularization i](method i) ^ (3 : ℕ)) ≤ (12 / L0) * (f (method 0) - fStar)

Algorithm 4.1.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.1.2 recalls the canonical damped Newton update from Chapter 1.

open scoped Gradient open NewtonSystem (AdmissiblePoint) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] recall DampedNewton.step (f : E → ℝ) (x : AdmissiblePoint (∇ f)) (h : ℝ) : E

Definition 4.1.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.2: on an open convex set 𝓕, a twice continuously differentiable real-valued function has L-Lipschitz Hessian when the Hessian map is L-Lipschitz with respect to the ambient norm and the induced operator norm. The source Euclidean case 𝓕 ⊆ ℝⁿ is recovered by specializing E to EuclideanSpace ℝ (Fin n).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] class HessianLipschitzOn (L : NNReal) (𝓕 : Set E) (f : E → ℝ) : Prop where /-- The domain `𝓕` is open. -/ isOpen : IsOpen 𝓕 /-- The domain `𝓕` is convex. -/ convex : Convex ℝ 𝓕 /-- The function is twice continuously differentiable on `𝓕`. -/ contDiffOn : ContDiffOn ℝ 2 f 𝓕 /-- The Hessian map `x ↦ ∇² f(x)` is `L`-Lipschitz on `𝓕`. -/ lipschitz : LipschitzOnWith L (hessian f) 𝓕

Lemma 4.1.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.2 on scalar quadratic forms: if M ≥ 0, f is C² at x, and T_M(x) globally minimizes the chapter cubic model centered at x, then the regularized Hessian quadratic form v ↦ ⟪(hessian f x + (M / 2) r_M(x) • 1) v, v⟫ is nonnegative on every direction v.

open scoped Gradient open scoped CubicRegularizationResidual universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] lemma regularized_hessian_quadratic_nonneg_of_cubic_model_global_min {f : E → ℝ} {M : ℝ} (hM : 0 ≤ M) {x trialPoint : E} (hf : ContDiffAt ℝ 2 f x) (hmin : IsMinOn (cubicRegularizationQuadraticApproximation f M x) Set.univ trialPoint) (v : E) : 0 ≤ inner ℝ ((hessian f x + ((M / 2) * r[trialPoint] x) • (1 : E →L[ℝ] E)) v) v

Proposition 4.1.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.2: if the iterates satisfy x_{k+1} = T_{M_k}(x_k), each accepted trial point satisfies f (T_{M_k}(x_k)) ≤ \tilde f_{M_k}(x_k), and the visited model values \tilde f_{M_k}(x_k) underestimate f(x_k) along the trajectory, then the objective values decrease stepwise: f(x_{k+1}) ≤ f(x_k) for every k.

universe u open RegularizedNewton variable {X : Type u} theorem objective_values_nonincreasing {f : X → ℝ} {stepMap : ℝ → X → X} {modelValue : ℝ → X → ℝ} {L : ℝ} (method : RelaxedRegularizedNewtonIteration stepMap L) (haccept : ∀ k : ℕ, method.regularization k ∈ acceptingParameters f stepMap modelValue (method k)) (modelValue_le_objective : ∀ k : ℕ, modelValue (method.regularization k) (method k) ≤ f (method k)) (k : ℕ) : f (method (k + 1)) ≤ f (method k)

Theorem 4.1.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.2 (1): if a cubic-regularization trajectory has a bounded feasible level set 𝓕 ∩ 𝓛[f]((f (x_{i₀}))), then the objective values f(x_i) converge to some limit f*. This uses only the proper-pseudometric owner layer behind the textbook ℝⁿ specialization.

open Filter open scoped CubicRegularizationModelNotation Gradient LevelSetNotation Topology open scoped CubicRegularizationResidual universe u variable {X : Type u} [NormedAddCommGroup X] [InnerProductSpace ℝ X] [CompleteSpace X] variable [ProperSpace X] variable {f : X → ℝ} variable {stepMap : ℝ → X → X} variable {L0 L : ℝ} {x0 : X} theorem cubicRegularization_objective_values_tendsto (method : CubicRegularizationMethod f stepMap L0 L x0) (hunder : ∀ i : ℕ, f̄[f; (method.regularization i)]((method i)) ≤ f (method i)) (hf_cont : Continuous f) {𝓕 : Set X} (hmem : ∀ i : ℕ, method i ∈ 𝓕) (i0 : ℕ) (hbounded : Bornology.IsBounded (𝓕 ∩ 𝓛[f]((f (method i0))))) : ∃ fStar : ℝ, Tendsto (fun i ↦ f (method i)) atTop (𝓝 fStar)

Algorithm 4.1.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.1.3: a chosen trust-region Newton step is feasible for the closed ball and minimizes the quadratic Taylor model on that trust region.

open scoped Gradient open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {xk : E} {ε : ℝ} namespace TrustRegionNewton theorem step_spec (step : {x : E // x ∈ argmin[Metric.closedBall xk ε] (secondOrderTaylorModelAt f xk)}) : (step : E) ∈ Metric.closedBall xk ε ∧ IsMinOn (secondOrderTaylorModelAt f xk) (Metric.closedBall xk ε) (step : E)

Definition 4.1.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.3: any point of argmin[Set.univ] (m[f; M](x)) realizes the displayed minimum value \bar f_M(x) through the canonical owner optimal value.

open scoped Gradient open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open SetConstrainedMinimizationProblem open scoped CubicRegularizationModelNotation theorem cubicRegularizationProblem_optimalValue_eq_of_mem_argmin {f : E → ℝ} {M : ℝ} {x y : E} (hy : y ∈ argmin[Set.univ] (m[f; M](x))) : Φ[f; M](x) = (m[f; M](x; y) : EReal)

Lemma 4.1.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.3 (1). Under the chapter's initial-sublevel containment context, for any x ∈ 𝓛[f]((f x₀)), the gradient at x has nonnegative pairing with the cubic-step displacement x - T_M(x). This is the displayed inequality (4.1.9) for the canonical whole-space cubic-step owner.

open scoped Gradient open scoped LevelSetNotation open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {𝓕 : Set E} {f : E → ℝ} {L : NNReal} {M : ℝ} {x trialPoint : E} theorem cubicStep_nonneg_inner [HessianLipschitzOn L 𝓕 f] (step : CubicRegularizationMapping f M) {x0 x : E} (hlevel0 : 𝓛[f]((f x0)) ⊆ 𝓕) (hx : x ∈ 𝓛[f]((f x0))) : 0 ≤ inner ℝ (∇ f x) (x - step x)

Proposition 4.1.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.3: if f is convex, xStar is a global minimizer of f, and f is differentiable at a point x lying in the closed ball of radius R around xStar, then the suboptimality gap above the optimal value sInf (Set.range f) is bounded by R * ‖∇ f x‖. Since xStar attains that infimum, this is equivalent to the textbook form f x - f xStar ≤ R * ‖∇ f x‖.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem convex_suboptimality_le_radius_mul_norm_gradient (f : E → ℝ) (hf_conv : ConvexOn ℝ Set.univ f) (xStar : E) (hxStar : IsMinOn f Set.univ xStar) {x : E} (hf_diff : DifferentiableAt ℝ f x) {R : ℝ} (hx : ‖x - xStar‖ ≤ R) : f x - sInf (Set.range f) ≤ R * ‖∇ f x‖

Theorem 4.1.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.3.1 (1): for a relaxed cubic-regularized Newton iteration satisfying the local step, Hessian, and gradient estimates from the cubic model, the least Hessian eigenvalue stays positive along the whole iterate sequence.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] open RelaxedRegularizedNewtonIteration variable (L : ℝ) (f : E → ℝ) {stepMap : ℝ → E → E} variable (method : RelaxedRegularizedNewtonIteration stepMap L) local notation "δ" => fun k : ℕ ↦ cubicRegularizationDelta f (method k) L theorem cubicRegularization_hessianLeastEigenvalue_pos (hmethod : method.HasCubicRegularizationRecurrenceHypotheses f) (k : ℕ) : 0 < λ_min(∇²f(method k))

Theorem 4.1.3.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.3.2: under the stronger theorem-family hypotheses method.HasCubicRegularizationHypotheses f extending the recurrence assumptions from Theorem 4.1.3.1, the least Hessian eigenvalue along the relaxed cubic-regularization iterates stays between e⁻¹ and e^(3/4) times its initial value.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] open RelaxedRegularizedNewtonIteration variable (L : ℝ) (f : E → ℝ) {stepMap : ℝ → E → E} variable (method : RelaxedRegularizedNewtonIteration stepMap L) local notation "δ" => fun k : ℕ ↦ cubicRegularizationDelta f (method k) L -- Proof sketch: combine `hmethod.lambda_succ` and `hmethod.lambda_succ_upper` with the step -- estimate to obtain -- `λ_min(∇² f (x_{i+1})) ∈ [(1 - δ_i) λ_min(∇² f (x_i)), (1 + δ_i) λ_min(∇² f (x_i))]`. -- The lower bound then comes from summing `log (1 - δ_i)`, while the upper bound comes from -- summing `log (1 + δ_i)`. In both directions the controlling series estimate is supplied by the -- theorem-family API from `Theorem_4_1_3_1`. theorem cubicRegularization_hessianLeastEigenvalue_bounds (hmethod : method.HasCubicRegularizationHypotheses f) (k : ℕ) : Real.exp (-1 : ℝ) * λ_min(∇² f (method 0)) ≤ λ_min(∇² f (method k)) ∧ λ_min(∇² f (method k)) ≤ Real.exp (3 / 4 : ℝ) * λ_min(∇² f (method 0))

Theorem 4.1.3.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.3.3 (1): under the assumptions of Theorem 4.1.3.1, the relaxed cubic-regularization Newton iterates form a Cauchy sequence.

open Filter open scoped Gradient Topology universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] open RelaxedRegularizedNewtonIteration variable (L : ℝ) (f : E → ℝ) {stepMap : ℝ → E → E} variable (method : RelaxedRegularizedNewtonIteration stepMap L) variable (hmethod : method.HasCubicRegularizationHypotheses f) local notation "δ" => fun k : ℕ ↦ cubicRegularizationDelta f (method k) L theorem cubicRegularizationNewton_iterates_cauchy (hmethod : method.HasCubicRegularizationRecurrenceHypotheses f) : CauchySeq method

Definition 4.1.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.4: the local optimality measure μ_M(x) for cubic regularization is the maximum of the square root of the scaled gradient norm term and the scaled negative least Hessian eigenvalue term.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] def cubicRegularizationLocalOptimalityMeasure (f : E → ℝ) (L M : ℝ) (x : E) : ℝ := max (Real.sqrt ((2 / (L + M)) * ‖∇ f x‖)) (-(2 / (2 * L + M)) * sInf (spectrum ℝ (hessian f x)))

Lemma 4.1.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.4: if f has L-Lipschitz Hessian on 𝓕, and y globally minimizes the cubic model centered at x with parameter M, then ‖∇ f y‖ ≤ ((L + M) / 2) ‖y - x‖².

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem gradient_norm_le_of_isMinOn_cubicRegularizationQuadraticApproximation {f : E → ℝ} {𝓕 : Set E} {L : NNReal} {M : ℝ} {x y : E} (hf : HessianLipschitzOn L 𝓕 f) (hM : 0 ≤ M) (hy : IsMinOn (cubicRegularizationQuadraticApproximation f M x) Set.univ y) (hx : x ∈ 𝓕) (hy𝓕 : y ∈ 𝓕) : ‖∇ f y‖ ≤ (((L : ℝ) + M) / 2) * ‖y - x‖ ^ (2 : ℕ)

Proposition 4.1.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.4: a positive strongly convex objective on a real Hilbert space is gradient dominated of degree 2.

open scoped Gradient StrongConvex open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] namespace StrongConvexOn theorem gradientDominatedOn_two {μ : ℝ} {f : E → ℝ} (hf : f ∈ 𝓛^1[μ]) (hf_diff : Differentiable ℝ f) : GradientDominatedOn 2 Set.univ f

Theorem 4.1.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.4 (1): if the initial objective gap is at least (3 / 2) L D^3, then one cubic segment-minimization step reduces it to at most (1 / 2) L D^3.

open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} {𝓕 : Set E} {xStar : E} {L D : ℝ} theorem starConvex_cubicSegment_first_gap_le_half_LD_cube {x0 x1 : E} (hF_bounded : Bornology.IsBounded 𝓕) (hdiam : Metric.diam 𝓕 ≤ D) (hxStar : xStar ∈ argmin[𝓕] f) (hstar : StarConvexWithRespectToOn f xStar 𝓕) (hx0 : x0 ∈ 𝓕) (hL : 0 < L) (hx1 : x1 ∈ argmin[segment ℝ x0 xStar] (cubicallyRegularizedObjective f ((3 / 2 : ℝ) * L) x0)) (hgap0 : f x0 - f xStar ≥ (3 / 2 : ℝ) * L * D ^ (3 : ℕ)) : f x1 - f xStar ≤ (1 / 2 : ℝ) * L * D ^ (3 : ℕ)

Algorithm 4.1.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.1.5: a cubic-regularization method for an objective f, a family of cubic trial maps T_M, constants L₀ ∈ (0, L] and L, and an initial point x₀ consists of an iterate sequence x_k, a regularization-parameter sequence M_k, and a chosen cubic-step owner step k : CubicRegularizationMapping f M_k such that step k agrees with T_{M_k}, x₀ = x0, each M_k lies in [L₀, 2L], the acceptance inequality f (T_{M_k}(x_k)) ≤ f̄[f; M_k](x_k) holds, and the next iterate is x_{k+1} = T_{M_k}(x_k).

open scoped ConstrainedArgmin CubicRegularizationModelNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure CubicRegularizationMethod (f : E → ℝ) (stepMap : ℝ → E → E) (L0 L : ℝ) (x0 : E) where /-- The iterate sequence `x₀, x₁, x₂, ...`. -/ x : ℕ → E /-- The chosen regularization parameters `M₀, M₁, M₂, ...`. -/ regularization : ℕ → ℝ /-- For each iteration `k`, `step k` is the chosen cubic-step owner with parameter `M_k`. -/ step (k : ℕ) : CubicRegularizationMapping f (regularization k) /-- The chosen owner `step k` agrees with the ambient family `T_{M_k}` used elsewhere in the chapter. -/ step_eq_stepMap (k : ℕ) (x : E) : step k x = stepMap (regularization k) x /-- The standing regularization lower bound satisfies `L₀ ∈ (0, L]`. -/ L0_mem_Ioc : L0 ∈ Set.Ioc (0 : ℝ) L /-- The zeroth iterate is the prescribed initial point `x₀`. -/ x_zero : x 0 = x0 /-- Every chosen parameter `M_k` belongs to the admissible interval `[L₀, 2L]`. -/ regularization_mem_Icc (k : ℕ) : regularization k ∈ Set.Icc L0 (2 * L) /-- The accepted trial point satisfies the model comparison `f (T_{M_k}(x_k)) ≤ f̄[f; M_k](x_k)` at every iteration. -/ objective_step_le_value (k : ℕ) : f ((step k) (x k)) ≤ EReal.toReal (SetConstrainedMinimizationProblem.optimalValue (cubicRegularizationProblem f (regularization k) (x k))) /-- The next iterate is obtained by applying `T_{M_k}` to the current iterate `x_k`. -/ x_succ (k : ℕ) : x (k + 1) = (step k) (x k)

Definition 4.1.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.5: a relaxed regularized Newton iteration for a trial map T_M and constant L consists of an iterate sequence x_k and regularization parameters M_k such that each M_k lies in (0, 2L] and the update x_{k+1} = T_{M_k}(x_k) holds for every k ≥ 0. These interval conditions force L > 0, recovered below as derived API.

universe u variable {X : Type u} structure RelaxedRegularizedNewtonIteration (stepMap : ℝ → X → X) (L : ℝ) where /-- The iterate sequence `x₀, x₁, x₂, ...`. -/ x : ℕ → X /-- The regularization parameters `M₀, M₁, M₂, ...`. -/ regularization : ℕ → ℝ /-- Every parameter `M_k` lies in the admissible interval `(0, 2L]`. -/ regularization_mem_Ioc (k : ℕ) : regularization k ∈ Set.Ioc 0 (2 * L) /-- The next iterate is obtained by applying `T_{M_k}` to the current iterate `x_k`. -/ x_succ (k : ℕ) : x (k + 1) = stepMap (regularization k) (x k)

Lemma 4.1.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.5 (1), pointwise form: for x ∈ 𝓕 and every feasible y, the cubic model value \bar f_M(x) is bounded above by the comparison quantity f(y) + ((L + M) / 6) ‖y - x‖³.

open scoped ConstrainedArgmin CubicRegularizationModelNotation Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped CubicRegularizationResidual variable {trialPoint : E} theorem cubicRegularizationValue_le_feasibleComparison_of_mem {𝓕 : Set E} {f : E → ℝ} {L : NNReal} {M : ℝ} {x y : E} (hf : HessianLipschitzOn L 𝓕 f) (hstep : IsMinOn (m[f; M](x)) Set.univ trialPoint) (hx : x ∈ 𝓕) (hy : y ∈ 𝓕) : f̄[f; M](x) ≤ f y + (((L : ℝ) + M) / 6 : ℝ) * ‖y - x‖ ^ (3 : ℕ)

Proposition 4.1.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.5: if g : E → F is differentiable on the uniquely differentiable feasible set 𝓕, xStar ∈ 𝓕 is a root of g, and σ > 0 is a uniform lower bound on the least eigenvalue of J(x) J(x)^*, recorded canonically as the inequality σ ≤ σ_min((fderivWithin ℝ g 𝓕 x)†)^2 for every x ∈ 𝓕, then the nonlinear least-squares objective x ↦ (1 / 2) ‖g x‖² is gradient dominated of degree 2 on 𝓕.

open scoped InnerProduct MinimalSingularValue open scoped ConstrainedArgmin universe u v variable {E : Type u} {F : Type v} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] [FiniteDimensional ℝ E] [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F] [FiniteDimensional ℝ F] variable (g : E → F) local notation "fLS" => fun x : E ↦ (1 / 2 : ℝ) * ‖g x‖ ^ (2 : ℕ) local notation "withinJacobianMinSq" => fun (𝓕 : Set E) (x : E) ↦ (σ_min((fderivWithin ℝ g 𝓕 x)†)) ^ (2 : ℕ) variable (𝓕 : Set E) (xStar : E) (σ : ℝ) variable (h𝓕_unique : UniqueDiffOn ℝ 𝓕) variable (hg : DifferentiableOn ℝ g 𝓕) (hxStar : xStar ∈ 𝓕) (hgstar : g xStar = 0) variable (hσ_pos : 0 < σ) variable (hσ : ∀ ⦃x : E⦄, x ∈ 𝓕 → σ ≤ withinJacobianMinSq 𝓕 x) theorem nonlinearLeastSquares_gradientDominatedOn_two (h𝓕_unique : UniqueDiffOn ℝ 𝓕) (hg : DifferentiableOn ℝ g 𝓕) (hxStar : xStar ∈ 𝓕) (hgstar : g xStar = 0) (hσ_pos : 0 < σ) (hσ : ∀ ⦃x : E⦄, x ∈ 𝓕 → σ ≤ withinJacobianMinSq 𝓕 x) : GradientDominatedOn 2 𝓕 fLS

Theorem 4.1.5.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.5.1: if f is star-convex, the canonical nondegeneracy witness HasGloballyNondegenerateOptimalSet.UsesConstant Set.univ f xStar μ packages the chosen optimal point xStar used in the gaps together with the matching quadratic error-bound constant μ, and [HessianLipschitzOn L Set.univ f] supplies the Hessian-Lipschitz regularity used in the cubic-model comparison, while the source initial gap assumption f (x₀) - f(x*) ≥ (4 / 9) * \barω holds, and the iterates are generated by the cubic-regularized Newton scheme (4.1.16), then every iterate that remains in the first phase satisfies the fourth-root decay bound with \barω = μ^3 / (8 L^2), and the first phase ends at some index k₀ where f (x_{k₀}) - f(x*) ≤ (4 / 9) \barω.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open HasGloballyNondegenerateOptimalSet (UsesConstant) open scoped ConstrainedArgmin namespace CubicRegularizationMethod variable (f : E → ℝ) {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal} {x0 : E} variable (xStar : E) (μ : ℝ) variable (method : CubicRegularizationMethod f stepMap L0 (L : ℝ) x0) local notation "ω̄" => starConvexNondegenerateBarOmega (L : ℝ) μ local notation "Δ" => fun k : ℕ ↦ f (method k) - f xStar theorem starConvex_cubicRegularization_firstPhase [HessianLipschitzOn L Set.univ f] (hstar : StarConvexFunction f) (hnondegenerate : UsesConstant Set.univ f xStar μ) (hgap0 : Δ 0 ≥ (4 / 9 : ℝ) * ω̄) : (∀ k : ℕ, Δ k ≥ (4 / 9 : ℝ) * ω̄ → Δ k ≤ (Real.rpow (Δ 0) (1 / 4 : ℝ) - ((k : ℝ) / 6 : ℝ) * Real.sqrt (2 / 3 : ℝ) * Real.rpow ω̄ (1 / 4 : ℝ)) ^ (4 : ℕ)) ∧ ∃ k0 : ℕ, Δ k0 ≤ (4 / 9 : ℝ) * ω̄

Theorem 4.1.5.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.5.2: if f is star-convex with respect to the chosen minimizer xStar, the canonical witness HasGloballyNondegenerateOptimalSet.UsesConstant Set.univ f xStar μ packages the arbitrary optimizer xStar used in the displayed gaps together with the quadratic-growth constant μ, the iterates are generated by the cubic-regularized Newton scheme (4.1.16), while [HessianLipschitzOn L Set.univ f] supplies the ambient smoothness constant used by the cubic comparison estimate, then once f (x_{k0}) - f(x*) ≤ (4 / 9) * \barω, every later iterate satisfies the superlinear estimate `f (x_{k+1}) - f(x*) ≤ (1 / 2) * (f (x_k) - f(x*)) * sqrt ((f (x_k) - f(x*)) / \barω), where \barω = μ^3 / (8 L^2)`.

open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] namespace CubicRegularizationMethod variable (f : E → ℝ) variable {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal} {x0 : E} variable (xStar : E) (μ : ℝ) variable (method : CubicRegularizationMethod f stepMap L0 (L : ℝ) x0) local notation "ω̄" => starConvexNondegenerateBarOmega (L : ℝ) μ local notation "Δ" => fun k : ℕ ↦ f (method k) - f xStar -- Proof sketch: apply the one-step cubic-regularization descent estimate from the first-phase -- analysis to the normalized gaps -- `Δ_k = (f (x_k) - f xStar) / starConvexNondegenerateBarOmega L μ`. Apply the one-step -- estimate directly at the chosen minimizer `xStar`, which is both the star center and the point -- used to normalize the displayed gaps, while -- `HasGloballyNondegenerateOptimalSet.UsesConstant Set.univ f xStar μ` supplies the matching -- quadratic-growth constant `μ`. Once -- `Δ_k ≤ 4 / 9`, -- the minimizer of the scalar upper bound on `[0, 1]` is attained at `α = 1`, yielding -- `Δ_{k+1} ≤ (1 / 2) Δ_k^(3/2)`. Rewriting this inequality gives the displayed superlinear -- estimate for every `k ≥ k0`. -- Semantic recall note: `lean_leansearch` only surfaced generic `IsMinOn` lemmas, so the local -- fixed-center owner `StarConvexWithRespectToOn` is the right API here. theorem starConvex_cubicRegularization_secondPhase_gap_le_superlinear [HessianLipschitzOn L Set.univ f] (hstar : StarConvexWithRespectToOn f xStar Set.univ) (hnondegenerate : HasGloballyNondegenerateOptimalSet.UsesConstant Set.univ f xStar μ) (k0 : ℕ) (hk0 : Δ k0 ≤ (4 / 9 : ℝ) * ω̄) (k : ℕ) (hk : k0 ≤ k) : Δ (k + 1) ≤ (1 / 2 : ℝ) * Δ k * Real.sqrt (Δ k / ω̄)

Definition 4.1.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.6: for the textbook cubic-regularization quantity attached to a twice continuously differentiable real objective f, a scalar L > 0, and an iterate x_k, the quantity δ_k is L * ‖∇ f(x_k)‖ / λ_min(∇²f(x_k))^2.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] notation:max "λ_min(" H:max ")" => Matrix.leastEigenvalue H notation:max "λ_max(" H:max ")" => Matrix.greatestEigenvalue H def cubicRegularizationDelta (f : E → ℝ) (xk : E) (L : ℝ) : ℝ := L * ‖∇ f xk‖ / (λ_min(∇² f xk)) ^ 2

Lemma 4.1.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.6: if x ∈ 𝓕, the Hessian of f is L-Lipschitz on 𝓕, y globally minimizes the cubic model centered at x with parameter M, y ∈ 𝓕, and the least eigenvalue of ∇² f(y) is bounded below by -((M / 2) + L) ‖y - x‖, then μ_M(y) ≤ ‖y - x‖.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] variable {f : E → ℝ} {L : NNReal} local notation:max "μ[" M "](" x ")" => cubicRegularizationLocalOptimalityMeasure f (L : ℝ) M x -- Proof sketch: apply -- `gradient_norm_le_of_isMinOn_cubicRegularizationQuadraticApproximation` to control the -- gradient term in `μ_M(y)`, use the `HessianLipschitzOn` owner from `Definition_4_1_2` for the -- on-set `C²` and Hessian-Lipschitz data, and control the spectral term by the assumed lower -- bound on the least eigenvalue of the Hessian at `y`. theorem cubicRegularizationLocalOptimalityMeasure_le_norm_sub_of_isMinOn {𝓕 : Set E} {M : ℝ} {x y : E} (hf : HessianLipschitzOn L 𝓕 f) (hM : 0 < M) (hy : IsMinOn (cubicRegularizationQuadraticApproximation f M x) Set.univ y) (hx : x ∈ 𝓕) (hy𝓕 : y ∈ 𝓕) (hlambdaMin : -(((M / 2) + (L : ℝ)) * ‖y - x‖) ≤ λ_min(∇²f y)) : μ[M](y) ≤ ‖y - x‖

Proposition 4.1.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.6 is modeled by a triangular transformation on ℝⁿ⁺¹. The correction at a higher coordinate depends only on the strictly earlier coordinates.

open Matrix namespace Nesterov.Chap04.Proposition_4_1_6 structure TriangularTransformation (n : ℕ) where /-- The correction term attached to the higher coordinate `i`. -/ correction (i : HigherCoord n) : EuclideanSpace ℝ (Fin i.1) → ℝ /-- Each correction term is differentiable on its natural Euclidean domain. -/ differentiable_correction (i : HigherCoord n) : Differentiable ℝ (correction i)

Theorem 4.1.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.6 (1): if the initial objective gap is at least hatω, then the normalized suboptimality logarithm along the cubic-regularized Newton iterates contracts by the factor (2 / 3)^k.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {stepMap : ℝ → E → E} {L0 L τf : ℝ} {x0 : E} variable (method : CubicRegularizationMethod f stepMap L0 L x0) variable (xStar : E) local notation "Δ" => fun k : ℕ ↦ f (method k) - f xStar local notation "κ" => (L0 / (3 * Real.sqrt 2 * Real.rpow (L + L0) (3 / 2 : ℝ)) : ℝ) local notation "ω̂" => gradientDominatedCubicHatOmega L L0 τf variable (hgradientDominated : GradientDominatedOn.UsesConstant 1 Set.univ f xStar τf) (hdescent : ∀ k : ℕ, f (method k) - f (method (k + 1)) ≥ κ * Real.rpow ‖∇ f (method (k + 1))‖ (3 / 2 : ℝ)) include hgradientDominated hdescent theorem gradientDominated_cubicRegularization_log_gap_le_geometric (hgap0 : ω̂ ≤ Δ 0) : ∀ k : ℕ, Real.log (Δ k / ω̂) ≤ (2 / 3 : ℝ) ^ k * Real.log (Δ 0 / ω̂)

Definition 4.1.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.7: a real-valued function is star-convex if it has a global minimizer x* such that, for every point x and every α ∈ [0,1], the value of f at α x* + (1 - α) x is bounded by the corresponding convex combination of f x* and f x.

open scoped ConstrainedArgmin variable {E : Type*} [AddCommMonoid E] [Module ℝ E] class StarConvexFunction (f : E → ℝ) : Prop where /-- The function has a global minimizer that is a valid star center on the whole ambient space. -/ exists_starCenter : ∃ xStar, xStar ∈ argmin[Set.univ] f ∧ StarConvexWithRespectToOn f xStar Set.univ

Lemma 4.1.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.7: near a critical point with strictly negative Hessian curvature, a cubic regularization method admits constants ε > 0 and δ > 0 such that, if xBar is an interior point of an open convex neighborhood 𝓕 on which the Hessian is L-Lipschitz, then any iterate in the local upper-level set Q = {x | ‖x - xBar‖ ≤ ε ∧ f xBar ≤ f x} has its next iterate strictly below the level f xBar - δ. Since HessianLipschitzOn L 𝓕 f already records that 𝓕 is open, this uses the same single local domain for both regularity and interior feasibility.

open scoped ConstrainedArgmin CubicRegularizationModelNotation open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] theorem exists_objective_drop_below_negative_curvature_level {f : E → ℝ} {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal} {x0 xBar : E} {𝓕 : Set E} (method : CubicRegularizationMethod f stepMap L0 (L : ℝ) x0) (hgrad : ∇ f xBar = 0) (hxBar : xBar ∈ 𝓕) (hreg : HessianLipschitzOn L 𝓕 f) (hneg : λ_min(∇²f xBar) < 0) : ∃ ε > 0, ∃ δ > 0, ∀ i : ℕ, method i ∈ Metric.closedBall xBar ε ∩ {x | f xBar ≤ f x} → f (method (i + 1)) ≤ f xBar - δ

Proposition 4.1.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.7 (1): for M > 0, fixing h and minimizing the slack-variable epigraph objective over the feasible fiber of cubicRegularizedQuadraticEpigraphProblem g H M recovers the original cubic-regularized quadratic value.

variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (H : Matrix (Fin n) (Fin n) ℝ) (M : ℝ)
local notation "P" => cubicRegularizedQuadraticEpigraphProblem g H M
local notation "F" => LagrangianProblem.feasibleSet P
theorem cubicRegularizedQuadraticObjective_isLeast_overSlackFiber
    (g : E) (H : Matrix (Fin n) (Fin n) ℝ) (M : ℝ)
    (hH : H.IsSymm) (hM : 0 < M) (h : E) :
    IsLeast
      ((fun τ : ℝ ↦ cubicRegularizedQuadraticEpigraphProblem g H M (h, τ)) ''
        {τ : ℝ |
          (h, τ) ∈
            LagrangianProblem.feasibleSet (cubicRegularizedQuadraticEpigraphProblem g H M)})
      (cubicRegularizedQuadraticObjective g H M h)

Theorem 4.1.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.7 (1): every iterate whose suboptimality gap is still at least \tilde ω satisfies the exponential bound f(x_k) - f(x^*) ≤ (f(x₀) - f(x^*)) e^{-kσ}, where σ = \tilde ω^{1/4} / (\tilde ω^{1/4} + (f(x₀) - f(x^*))^{1/4}).

open scoped CubicRegularizationResidual Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {stepMap : ℝ → E → E} {L0 L τf : ℝ} {x0 : E} variable (method : CubicRegularizationMethod f stepMap L0 L x0) variable (xStar : E) variable (hgradientDominated : GradientDominatedOn.UsesConstant 2 Set.univ f xStar τf) variable (hresidual_lower : ∀ k : ℕ, r[method.acceptedTrialPoint k] (method k) ≥ Real.sqrt (2 * ‖∇ f (method.acceptedTrialPoint k)‖ / (L + method.regularization k))) local notation "ω̃" => gradientDominatedCubicThreshold L L0 τf local notation "Δ" => fun k : ℕ ↦ f (method k) - f xStar local notation "σ" => Real.rpow ω̃ (1 / 4 : ℝ) / (Real.rpow ω̃ (1 / 4 : ℝ) + Real.rpow (Δ 0) (1 / 4 : ℝ)) local notation "δ" => fun k : ℕ ↦ Δ k / ω̃ include hgradientDominated hresidual_lower theorem gradientDominated_cubicRegularization_gap_le_exponential_until_threshold (k : ℕ) (hk : ω̃ ≤ Δ k) : Δ k ≤ Δ 0 * Real.exp (-(k : ℝ) * σ)

Definition 4.1.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.8: a real-valued function f on a feasible set F ⊆ X has a globally non-degenerate optimal set if argmin[F] f is nonempty and there exists a constant μ > 0 such that, for every feasible point x ∈ F, the objective gap above the constrained optimal value sInf (f '' F) is bounded below by (μ / 2) times the squared distance from x to argmin[F] f. The textbook ℝⁿ version is the specialization to X = EuclideanSpace ℝ (Fin n).

open scoped ConstrainedArgmin universe u variable {X : Type u} class HasGloballyNondegenerateOptimalSet [PseudoMetricSpace X] (F : Set X) (f : X → ℝ) : Prop where /-- The optimal set `argmin[F] f` is nonempty. -/ optimalSet_nonempty : (argmin[F] f).Nonempty /-- The objective gap dominates the squared distance to the optimal set with a positive error-bound constant. -/ exists_error_bound : ∃ μ : ℝ, 0 < μ ∧ ∀ ⦃x : X⦄, x ∈ F → f x - sInf (f '' F) ≥ (μ / 2) * (Metric.infDist x (argmin[F] f)) ^ (2 : ℕ)

Lemma 4.1.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.8: if a cubic-regularization method uses at step k a global minimizer of the cubic model, and if the residual at that step satisfies r_{M_k}(x_k) ≥ sqrt (2 ‖∇ f(x_{k+1})‖ / (L + M_k)), then the one-step objective drop obeys the gradient-3/2 lower bound f(x_k) - f(x_{k+1}) ≥ [L0 / (3 sqrt 2 (L + L0)^(3/2))] ‖∇ f(x_{k+1})‖^(3/2).

open scoped CubicRegularizationResidual Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {stepMap : ℝ → E → E} {L0 L : ℝ} {x0 : E} namespace CubicRegularizationMethod theorem objective_sub_succ_ge_gradient_norm_rpow_threeHalves (method : CubicRegularizationMethod f stepMap L0 L x0) (k : ℕ) (hresidual_lower : r[method.acceptedTrialPoint k] (method k) ≥ Real.sqrt (2 * ‖∇ f (method.acceptedTrialPoint k)‖ / (L + method.regularization k))) : f (method k) - f (method (k + 1)) ≥ (L0 / (3 * Real.sqrt 2 * Real.rpow (L + L0) (3 / 2 : ℝ)) : ℝ) * Real.rpow ‖∇ f (method (k + 1))‖ (3 / 2 : ℝ)

Proposition 4.1.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.8 (1): for M > 0, minimizing the epigraph Lagrangian with respect to τ at fixed h and λ is attained at τ(λ) = 4 λ |λ| / M², equivalently at the point satisfying (M / 4) |τ|^(1/2) sign(τ) = λ / 2.

open EuclideanSpace
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem cubicRegularizedQuadraticEpigraphLagrangian_tau_isMinOn
    (g : E) (Hmat : Matrix (Fin n) (Fin n) ℝ) {M : ℝ}
    (hM : 0 < M) (h : E) (lam : ℝ) :
    let τ := cubicRegularizedQuadraticTauMinimizer M lam
    (M / 4 : ℝ) * |τ| ^ (1 / 2 : ℝ) * Real.sign τ = (lam / 2 : ℝ) ∧
      IsMinOn
        (fun τ' : ℝ ↦ cubicRegularizedQuadraticScalarLagrangian g Hmat M h τ' lam)
        Set.univ
        τ

Theorem 4.1.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.8 (1): for a nonlinear transformation of a convex objective, if the Hessian of problem = problem.φ ∘ problem.u satisfies the canonical owner HessianLipschitzOn L 𝓕 problem on a comparison set 𝓕 containing the sublevel set f ⁻¹' Set.Iic (f x₀), and the iterates are generated by the chapter cubic-regularization method owner, then an initial gap of at least (3 / 2) L (σ D)^3 implies that the first-step gap is at most (1 / 2) L (σ D)^3.

open scoped Gradient LevelSetNotation CubicRegularizationModelNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (problem : NonlinearConvexTransformation E) variable (𝓕 : Set E) {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal} variable (method : CubicRegularizationMethod problem stepMap L0 (L : ℝ) problem.x0) local notation "f" => problem local notation "𝓛₀" => f ⁻¹' Set.Iic (f problem.x0) local notation "Δ" => fun k : ℕ ↦ f (method k) - f problem.xStar local notation "σD" => problem.sigma * problem.D variable (hlevel_subset : 𝓛₀ ⊆ 𝓕) [HessianLipschitzOn L 𝓕 problem] theorem nonlinearTransformation_cubicRegularization_first_gap_le_half_sigmaD_cube (hlevel_subset : 𝓛₀ ⊆ 𝓕) (hgap0 : Δ 0 ≥ (3 / 2 : ℝ) * (L : ℝ) * σD ^ (3 : ℕ)) : Δ 1 ≤ (1 / 2 : ℝ) * (L : ℝ) * σD ^ (3 : ℕ)

Theorem 4.1.8.MethodHelpers

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Along a cubic-regularization method for the transformed objective, the feasible comparison estimate from method (4.1.16) is derived from the method owner together with the local Hessian-Lipschitz comparison data on 𝓕; it is not extra primitive method data.

open scoped Gradient LevelSetNotation CubicRegularizationModelNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
namespace CubicRegularizationMethod
variable {problem : NonlinearConvexTransformation E} {𝓕 : Set E}
variable {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal}
variable [HessianLipschitzOn L 𝓕 problem]
local notation "f" => problem
local notation "𝓛₀" => f ⁻¹' Set.Iic (f problem.x0)
theorem objective_succ_le_feasibleComparison
    (method :
      CubicRegularizationMethod
        problem
        stepMap
        L0 (L : ℝ) problem.x0)
    (hlevel_subset : 𝓛₀ ⊆ 𝓕)
    (k : ℕ) {y : E} (hy : y ∈ 𝓕) :
    f (method (k + 1)) ≤
      f y + ((L : ℝ) / 2) * ‖(y - method k : E)‖ ^ (3 : ℕ)

Theorem 4.1.8.Recurrence

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Helper for Theorem 4.1.8: a nonnegative scalar sequence satisfying the normalized cubic one-step recurrence has the standard inverse-square decay.

lemma inverse_square_rate_of_normalized_cubic_recurrence
    {Δ : ℕ → ℝ} {c : ℝ}
    (hc : 0 < c)
    (hΔ_nonneg : ∀ k : ℕ, 0 ≤ Δ k)
    (hgap0 : Δ 0 ≤ c)
    (hstep_gap :
      ∀ k : ℕ, ∀ α : ℝ, α ∈ Set.Icc (0 : ℝ) 1 →
        Δ (k + 1) ≤ (1 - α) * Δ k + c * ((1 / 3 : ℝ) * α ^ (3 : ℕ))) :
    ∀ k : ℕ,
      Δ k ≤ c / (1 + (k : ℝ) / 3) ^ (2 : ℕ)

Definition 4.1.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.9: a differentiable function f on a uniquely differentiable feasible set 𝓕 ⊆ ℝⁿ is gradient dominated of degree p ∈ [1, 2] when it has a global minimizer xStar on 𝓕 and a positive constant τf such that f x - f xStar ≤ τf * ‖gradientWithin f 𝓕 x‖^p for every x ∈ 𝓕. On open feasible sets, and in particular for 𝓕 = Set.univ, this agrees with the textbook ambient-gradient form.

open scoped Gradient open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] class GradientDominatedOn (p : ℝ) (𝓕 : Set E) (f : E → ℝ) : Prop where /-- The function is differentiable on the feasible set. -/ differentiableOn : DifferentiableOn ℝ f 𝓕 /-- The degree of domination lies in the interval `[1, 2]`. -/ degree_mem_Icc : p ∈ Set.Icc (1 : ℝ) 2 /-- The canonical minimizer set `argmin[𝓕] f` is nonempty, and one minimizer carries the unique-differentiability and positive-constant data needed for the source-facing gradient-domination inequality. -/ exists_usesConstant : ∃ xStar τf, GradientDominatedOn.UsesConstant p 𝓕 f xStar τf

Lemma 4.1.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.1.9: if φ ∘ u is obtained from a nonlinear change of variables with convex φ, and ‖fderivWithin ℝ u.symm (𝓛[φ](φ (u x0))) z‖ ≤ σ on the image-side level set 𝓛[φ](φ (u x0)), then any two points of the transformed level set 𝓛[φ ∘ u]((φ ∘ u) x0) satisfy ‖x - y‖ ≤ σ ‖u x - u y‖.

universe u open scoped LevelSetNotation variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (u : E ≃ E) (φ : E → ℝ) (x0 : E) local notation "S" => (𝓛[φ]((φ (u x0))) : Set E) local notation "T" => (𝓛[(φ ∘ u)](((φ ∘ u) x0)) : Set E) -- Proof sketch: write `x = u.symm (u x)` and `y = u.symm (u y)` using the inverse identities. The -- image points `u x` and `u y` lie in the convex level set `𝓛[φ](φ (u x0))`, so the whole segment -- between them stays in that set. Apply the convex mean-value inequality to `u.symm` within this -- image-side sublevel set and use the uniform within-set derivative bound there. theorem norm_sub_le_sigma_mul_norm_image_sub (hφ_convex : ConvexOn ℝ Set.univ φ) (hdiff : DifferentiableOn ℝ u.symm S) (σ : ℝ) (hσ : ∀ ⦃z : E⦄, z ∈ S → ‖fderivWithin ℝ u.symm S z‖ ≤ σ) {x y : E} (hx : x ∈ T) (hy : y ∈ T) : ‖x - y‖ ≤ σ * ‖u x - u y‖

Proposition 4.1.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

If G² > 0, then the dual domain is exactly the open half-line (-H_min, ∞).

open scoped BigOperators
open scoped CubicRegularizedDiagonalInvariants
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : EuclideanSpace ℝ (Fin n)) (Hdiag : Fin n → ℝ) (M : ℝ)
local notation "H" => Matrix.diagonal Hdiag
local notation "Irest" => Finset.univ.filter fun i : Fin n ↦ i ∉ I*[Hdiag]
local notation "Ashift" => shiftedDiagonalMatrix (Hdiag := Hdiag)
local notation "qShift" => shiftedQuadraticObjective (g := g) (Hdiag := Hdiag)
local notation "ψ" => cubicRegularizedQuadraticDualFunction g H M
local notation "dom " "ψ" => cubicRegularizedQuadraticDualDomain g H M
local notation "resolventPoint" => diagonalResolventPoint (g := g) (Hdiag := Hdiag)
theorem cubicRegularizedQuadraticDualDomain_eq_Ioi_of_activeGradientSquare_pos
      (hM : 0 < M) (hGpos : 0 < G²[g;Hdiag]) :
    dom ψ = Set.Ioi (-H_min[Hdiag])

Theorem 4.1.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.9 (1): under the nonlinear-transformation assumptions from Theorem 4.1.8, if φ is μ-strongly convex and the initial gap is at least (4 / 9) * \tilde ω, then every iterate whose gap is still above that threshold satisfies the fourth-root decay bound.

open scoped Gradient LevelSetNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (problem : NonlinearConvexTransformation E) variable (𝓕 : Set E) (μ : ℝ) {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal} variable (method : CubicRegularizationMethod problem stepMap L0 (L : ℝ) problem.x0) local notation "f" => problem local notation "𝓛₀" => f ⁻¹' Set.Iic (f problem.x0) local notation "ω̃" => nonlinearTransformationStrongConvexCubicThreshold (L : ℝ) problem.sigma μ local notation "Δ" => fun k : ℕ ↦ f (method k) - f problem.xStar variable (hlevel_subset : 𝓛₀ ⊆ 𝓕) [HessianLipschitzOn L 𝓕 problem] (hμ : 0 < μ) (hphi_strong : StrongConvexOn Set.univ μ problem.φ) -- Semantic recall: `lean_leansearch` pointed to the `Analysis.Convex.Strong` module, while local -- symbol search found no ready-made `quadratic_growth` bridge under the current project names. theorem nonlinearTransformation_cubicRegularization_firstPhase_gap_bound (hlevel_subset : 𝓛₀ ⊆ 𝓕) (hμ : 0 < μ) (hphi_strong : StrongConvexOn Set.univ μ problem.φ) (hgap0 : Δ 0 ≥ (4 / 9 : ℝ) * ω̃) (k : ℕ) (hk : Δ k ≥ (4 / 9 : ℝ) * ω̃) : Δ k ≤ (Real.rpow (Δ 0) (1 / 4 : ℝ) - ((k : ℝ) / 6 : ℝ) * Real.sqrt (2 / 3 : ℝ) * Real.rpow ω̃ (1 / 4 : ℝ)) ^ (4 : ℕ)

Definition 4.1.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.10: a nonlinear transformation of a convex objective consists of an invertible map u : E → E, a convex function φ, a starting point x₀, differentiability of u⁻¹ on the controlling level set 𝓛[φ]((φ (u x₀))), a chosen minimizer u* of φ, and the corresponding constants σ and D. The transformed objective is f = φ ∘ u, the transported minimizer is x* = u⁻¹(u*), and the constants σ and D are the maxima of ‖(u⁻¹)'(z)‖ and ‖z - u*‖ on 𝓛[φ]((φ (u x₀))).

universe u open scoped LevelSetNotation variable (E : Type u) [NormedAddCommGroup E] [NormedSpace ℝ E] structure NonlinearConvexTransformation where /-- The nonlinear change of variables `u`. -/ u : E ≃ E /-- The convex potential `φ`. -/ φ : E → ℝ /-- The starting point `x₀`. -/ x0 : E /-- The potential `φ` is convex on the whole space. -/ φ_convex : ConvexOn ℝ Set.univ φ /-- The inverse map `u⁻¹` is differentiable at every point of the controlling level set `𝓛[φ]((φ (u x₀)))`. -/ u_symm_differentiableAt_controllingLevelSet {z : E} (hz : z ∈ (𝓛[φ]((φ (u x0))) : Set E)) : DifferentiableAt ℝ u.symm z /-- The chosen global minimizer `u*` of `φ`. -/ uStar : E /-- The chosen point `u*` minimizes `φ` globally. -/ isMinOn_uStar : IsMinOn φ Set.univ uStar /-- The constant `σ`, defined as the maximum of `‖fderiv ℝ u.symm z‖` on the controlling level set. -/ sigma : ℝ /-- The displayed value `σ` is the maximum of `‖fderiv ℝ u.symm z‖` on the controlling level set. -/ sigma_isGreatest : IsGreatest ((fun z : E ↦ ‖fderiv ℝ u.symm z‖) '' (𝓛[φ]((φ (u x0))) : Set E)) sigma /-- The constant `D`, defined as the maximum distance from `u*` on the controlling level set. -/ D : ℝ /-- The displayed value `D` is the maximum of `‖z - u*‖` on the controlling level set. -/ D_isGreatest : IsGreatest ((fun z : E ↦ ‖z - uStar‖) '' (𝓛[φ]((φ (u x0))) : Set E)) D

Proposition 4.1.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.10: if G² = 0 and λ > -H_min, then a vector h minimizes the shifted diagonal quadratic q_λ on ℝⁿ exactly when its coordinates satisfy h i = 0 on I* and h i = -g i / (H_i + λ) off I*.

open scoped CubicRegularizedDiagonalInvariants
variable {n : ℕ} [NeZero n]
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (Hdiag : Fin n → ℝ) (lam : ℝ)
local notation "A" => Matrix.diagonal fun i ↦ Hdiag i + lam
theorem cubicRegularizedDiagonal_isMinOn_iff
    (hG : G²[g;Hdiag] = 0)
    (hlam : -H_min[Hdiag] < lam)
    (h : E) :
    IsMinOn (quadraticObjective 0 g A) Set.univ h ↔
      ∀ i : Fin n,
        h i =
          if i ∈ I*[Hdiag] then
            0
          else
            -g i / (Hdiag i + lam)

Theorem 4.1.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.10: assume G²[g; Hdiag] > 0. Then cubicRegularizedQuadraticDualDomain g H M = Set.Ioi (-H_min[Hdiag]). Moreover, for every maximizer lamStar of ψ on cubicRegularizedQuadraticDualDomain g H M ∩ Set.Ici 0, strong duality holds, the explicit resolvent point -((H + lamStar I)⁻¹) g is a global minimizer of the primal objective, and `cubicRegularizedQuadraticTauMinimizer M lamStar = 4 lamStar |lamStar| / M²`.

open Filter
open scoped ConstrainedArgmin CubicRegularizedDiagonalInvariants EuclideanOrthant
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (Hdiag : Fin n → ℝ) (M : ℝ)
local notation "H" => Matrix.diagonal Hdiag
local notation "Dplus" => cubicRegularizedQuadraticDualDomain g H M ∩ Set.Ici (0 : ℝ)
local notation "v" => cubicRegularizedQuadraticObjective g H M
local notation "ψ" => cubicRegularizedQuadraticDualFunction g H M
local notation "P" => cubicRegularizedQuadraticEpigraphProblem g H M
local notation "Λ" => EuclideanSpace ℝ (Fin 1)
include Hdiag
theorem cubicRegularizedQuadraticDiagonal_dualMaximizer_consequences_of_minimalGradientSquare_pos
    (hM : 0 < M) (hGpos : 0 < G²[g;Hdiag]) {lamStar : ℝ}
    (hmax : IsMaxOn (cubicRegularizedQuadraticDualFunction g H M) Dplus lamStar) :
    cubicRegularizedQuadraticDualDomain g H M = Set.Ioi (-H_min[Hdiag]) ∧
      sInf (Set.range fun h : E ↦
        (cubicRegularizedQuadraticObjective g H M h : EReal)) =
          cubicRegularizedQuadraticDualFunction g H M lamStar ∧
      IsMinOn (cubicRegularizedQuadraticObjective g H M) Set.univ
        (-((H + lamStar • (1 : Matrix (Fin n) (Fin n) ℝ))⁻¹).mulVec g) ∧
      cubicRegularizedQuadraticTauMinimizer M lamStar =
        (4 : ℝ) * lamStar * |lamStar| / M ^ (2 : ℕ)

Definition 4.1.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.11: a triangular transformation of ℝⁿ⁺¹ is determined by differentiable coordinate-correction maps for the higher coordinates, where the correction at coordinate i depends only on the strictly earlier coordinates 0, …, i - 1. The associated map u : ℝⁿ⁺¹ → ℝⁿ⁺¹ is recovered by coercion to a function in the namespace below.

structure TriangularTransformation (n : ℕ) where /-- The correction term for the higher coordinate `i`, depending only on the earlier coordinates. -/ correction (i : HigherCoord n) : EuclideanSpace ℝ (Fin i.1) → ℝ /-- Each coordinate-correction map is differentiable on its natural Euclidean domain. -/ differentiable_correction (i : HigherCoord n) : Differentiable ℝ (correction i)

Proposition 4.1.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.11: in the degenerate case G² = 0, perturbing the objective by δ h^(k) for k ∈ I* and δ ≠ 0 forces every optimal dual maximizer λ_δ* on dom ψ_δ ∩ ℝ₊ to satisfy δ² / (H_min + λ_δ*)² + ∑_{i ∉ I*} (g^(i))² / (H_i + λ_δ*)² = 4 (λ_δ*)² / M².

open scoped BigOperators
open scoped ConstrainedArgmin CubicRegularizedDiagonalInvariants EuclideanOrthant
open Filter
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (Hdiag : Fin n → ℝ) (M : ℝ)
local notation "H" => Matrix.diagonal Hdiag
local notation "Dplus(" g' ")" =>
  cubicRegularizedQuadraticDualDomain g' H M ∩ Set.Ici (0 : ℝ)
variable {δ : ℝ} {k : Fin n}
local notation "gδ" => cubicRegularizedDiagonalPerturbedGradient g k δ
local notation "ψδ" => cubicRegularizedQuadraticDualFunction gδ H M
local notation "Dplusδ" => Dplus(gδ)
local notation "Λ" => EuclideanSpace ℝ (Fin 1)
theorem perturbedDiagonalDualMaximizer_satisfies_boundaryEquation
    {δ : ℝ} (hM : 0 < M) (hδ : δ ≠ 0) {k : Fin n}
    (hk : k ∈ I*[Hdiag])
    (hGzero : G²[g;Hdiag] = 0)
    {lamDelta : ℝ}
    (hopt_max :
      IsMaxOn
        (cubicRegularizedQuadraticDualFunction
          (cubicRegularizedDiagonalPerturbedGradient g k δ) H M)
        (cubicRegularizedQuadraticDualDomain
            (cubicRegularizedDiagonalPerturbedGradient g k δ) H M ∩
          Set.Ici (0 : ℝ))
        lamDelta) :
    δ ^ (2 : ℕ) / (H_min[Hdiag] + lamDelta) ^ (2 : ℕ) +
        Finset.sum
          (Finset.univ.filter fun i : Fin n ↦
            i ∉ I*[Hdiag])
          (fun i ↦ (g i) ^ (2 : ℕ) / (Hdiag i + lamDelta) ^ (2 : ℕ)) =
      (4 : ℝ) * lamDelta ^ (2 : ℕ) / M ^ (2 : ℕ)

Theorem 4.1.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.1.11 (1): for the diagonal cubic-regularized quadratic model with H = diag(Hdiag), if G² = 0 and the dual problem admits a maximizer λ* > -H_min, then strong duality holds at that maximizer: the minimum of the primal objective v(h) equals the dual value ψ(λ*).

open Filter
open scoped ConstrainedArgmin CubicRegularizedDiagonalInvariants EuclideanOrthant
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable [NeZero n]
variable (g : E) (Hdiag : Fin n → ℝ) (M : ℝ)
local notation "H" => Matrix.diagonal Hdiag
local notation "v" => cubicRegularizedQuadraticObjective g H M
local notation "ψ" => cubicRegularizedQuadraticDualFunction g H M
local notation "Dplus" => cubicRegularizedQuadraticDualDomain g H M ∩ Set.Ici (0 : ℝ)
local notation "Λ" => EuclideanSpace ℝ (Fin 1)
variable {lamStar : ℝ}
variable (hM : 0 < M)
variable (hGzero : G²[g;Hdiag] = 0)
variable (hmax : IsMaxOn ψ Dplus lamStar)
variable (hlam : -H_min[Hdiag] < lamStar)
theorem cubicRegularizedQuadraticDiagonal_strongDuality_of_zeroMinimalGradientSquare
    (hM : 0 < M)
    (hGzero : G²[g;Hdiag] = 0)
    (hmax : IsMaxOn ψ Dplus lamStar)
    (hlam : -H_min[Hdiag] < lamStar)
    :
    sInf (Set.range fun h : E ↦
      (v h : EReal)) =
      ψ lamStar

Definition 4.1.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.12: the cubic-regularized quadratic model v(h) = ⟪g, h⟫ + (1 / 2) ⟪H h, h⟫ + (M / 6) ‖h‖^3 is the existing owner cubicRegularizedQuadraticObjective.

variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (H : Matrix (Fin n) (Fin n) ℝ) (M : ℝ) (hStar : E)
recall cubicRegularizedQuadraticObjective

Proposition 4.1.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.12. In this formalization, the quoted textbook statement is not source-faithful without an extra boundary-feasibility hypothesis, so the main labeled result keeps only the corrected boundary branch. Under the additional sign and radicand hypotheses selecting that branch, the canonical perturbed resolvent branch -(H + lamDelta δ • I)⁻¹ (g + δ e_k) converges to the displayed boundary point, which is then a global minimizer of the original objective.

open scoped BigOperators Topology ConstrainedArgmin EuclideanOrthant
open scoped CubicRegularizedDiagonalInvariants
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (Hdiag : Fin n → ℝ) (M : ℝ) (k : Fin n)
local notation "H" => Matrix.diagonal Hdiag
local notation "Dplus(" g' ")" =>
  cubicRegularizedQuadraticDualDomain g' H M ∩ Set.Ici (0 : ℝ)
local notation "gδ(" δ ")" => (g + EuclideanSpace.single k δ : E)
local notation "Aδ(" lamDelta "," δ ")" => Matrix.diagonal fun i ↦ Hdiag i + lamDelta δ
local notation "hδ(" lamDelta "," δ ")" => -Matrix.mulVec ((Aδ(lamDelta, δ))⁻¹) (gδ(δ))
local notation "Λ" => EuclideanSpace ℝ (Fin 1)
local notation "dual_certificate_multiplier_eq_single" =>
  prop412DualCertificateMultiplier_eq_single
local notation "resolventCertificateVector" =>
  prop412ResolventCertificateVector
local notation "resolventTauCertificatePoint" =>
  prop412ResolventTauCertificatePoint
local notation "scalar_dual_maximizer_mem_Dplus_of_activeGradientSquare_pos" =>
  prop412ScalarDualMaximizer_mem_Dplus_of_activeGradientSquare_pos
local notation "resolvent_epigraph_dual_maximizer_of_scalar_dual_maximizer" =>
  prop412ResolventEpigraphDualMaximizer_of_scalarDualMaximizer
local notation "resolvent_multiplier_coord_gt_negDiagonalMinimum_of_mem_certificate_ball" =>
  prop412ResolventMultiplierCoord_gt_negDiagonalMinimum_of_mem_certificate_ball
local notation "resolvent_tau_certificate_continuousAt" =>
  prop412ResolventTauCertificate_continuousAt
local notation "resolvent_tau_certificate_mem_lagrangianMinimizers" =>
  prop412ResolventTauCertificate_mem_lagrangianMinimizers
theorem cubicRegularizedDiagonalPerturbedResolvent_tendsto_boundary_and_isMinimizer_of_boundaryFeasible
    (lamDelta : ℝ → ℝ)
    (hM : 0 < M)
    (hk : k ∈ I*[Hdiag])
    (hGzero : G²[g;Hdiag] = 0)
    (hHmin_nonpos : H_min[Hdiag] ≤ 0)
    (hboundary_feasible :
      0 ≤
        (4 : ℝ) * H_min[Hdiag] ^ (2 : ℕ) / M ^ (2 : ℕ) -
          Finset.sum
            (Finset.univ.filter fun j : Fin n ↦
              j ∉ I*[Hdiag])
            (fun j ↦
              (g j) ^ (2 : ℕ) /
                (Hdiag j - H_min[Hdiag]) ^ (2 : ℕ)))
    (hopt_max :
      ∀ {δ : ℝ}, 0 < δ →
        IsMaxOn
          (cubicRegularizedQuadraticDualFunction (gδ(δ)) H M)
          Dplus(gδ(δ))
          (lamDelta δ)) :
    Filter.Tendsto (fun δ : ℝ ↦ hδ(lamDelta, δ))
        (𝓝[>] (0 : ℝ))
        (𝓝 (cubicRegularizedDiagonalBoundaryMinimizer g Hdiag M k)) ∧
      IsMinOn
        (cubicRegularizedQuadraticObjective g H M)
        Set.univ
        (cubicRegularizedDiagonalBoundaryMinimizer g Hdiag M k)

Definition 4.1.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.13 is the existing source-facing owner cubicRegularizedQuadraticDualFunction.

open EuclideanSpace
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
recall cubicRegularizedQuadraticDualFunction

Proposition 4.1.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.13: if λ* maximizes the dual function ψ over dom ψ ∩ ℝ₊ and the shifted symmetric Hessian lies in the interior region λ* > -λ_min(H), then the scalar first-order optimality condition holds: ‖-(H + λ* I)⁻¹ g‖ = (2 / M) λ*.

open Filter
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (H : Matrix (Fin n) (Fin n) ℝ) (M : ℝ)
local notation "Dplus" => cubicRegularizedQuadraticDualDomain g H M ∩ Set.Ici (0 : ℝ)
local notation "A" lam => H + lam • (1 : Matrix (Fin n) (Fin n) ℝ)
local notation "resolvent" lam => -Matrix.mulVec ((A lam)⁻¹) g
local notation "penalty" =>
  fun lam : ℝ ↦ (2 / (3 * M ^ (2 : ℕ)) : ℝ) * |lam| ^ (3 : ℕ)
include g H M
variable {lamStar : ℝ}
variable (hM : 0 < M) (hH : H.IsSymm)
variable (hmax : IsMaxOn (cubicRegularizedQuadraticDualFunction g H M) Dplus lamStar)
variable (hlam : -λ_min(H) < lamStar)
theorem cubicRegularizedQuadratic_resolvent_norm_eq_of_dualMaximizer
    (hM : 0 < M) (hH : H.IsSymm)
    (hmax : IsMaxOn (cubicRegularizedQuadraticDualFunction g H M) Dplus lamStar)
    (hlam : -λ_min(H) < lamStar)
    : ‖resolvent lamStar‖ = (2 / M : ℝ) * lamStar

Definition 4.1.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.14: the auxiliary cubic subproblem is encoded by the equivalent one-constraint epigraph Lagrangian problem with objective `\tilde v(h, τ) = ⟪g, h⟫ + (1 / 2) ⟪H h, h⟫ + (M / 6) |τ|^{3/2}and constraint(1 / 2) ‖h‖² - (1 / 2) τ ≤ 0`; its generic Lagrangian and the downstream scalar dual function are derived from this owner.

open EuclideanSpace
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
def cubicRegularizedQuadraticEpigraphProblem
    (g : E) (H : Matrix (Fin n) (Fin n) ℝ) (M : ℝ) : LagrangianProblem (E × ℝ) 1 :=
  { objective := fun z ↦
      dotProduct g z.1 +
        (1 / 2 : ℝ) * dotProduct (H.mulVec z.1) z.1 +
          (M / 6 : ℝ) * |z.2| ^ (3 / 2 : ℝ)
    constraints := fun _ z ↦ (1 / 2 : ℝ) * ‖z.1‖ ^ (2 : ℕ) - (1 / 2 : ℝ) * z.2 }

-- Proof sketch: unfold `cubicRegularizedQuadraticEpigraphProblem`,
-- and reuse the canonical single-constraint expansion
-- `LagrangianProblem.lagrangian_single_eq`.

Proposition 4.1.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.14 (1): if the chosen point hStar is represented by hStar = -(H + λ* I)⁻¹ g and r := ‖hStar‖, then r = (2 / M) λ*.

variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
variable (g : E) (H : Matrix (Fin n) (Fin n) ℝ) (M : ℝ)
local notation "ψ" => cubicRegularizedQuadraticDualFunction g H M
local notation "Dplus" => cubicRegularizedQuadraticDualDomain g H M ∩ Set.Ici (0 : ℝ)
local notation "A" lam => H + lam • (1 : Matrix (Fin n) (Fin n) ℝ)
local notation "resolvent" lam => -Matrix.mulVec ((A lam)⁻¹) g
variable {lamStar : ℝ}
theorem cubicRegularizedQuadratic_stepLength_eq
    (hM : 0 < M) (hH : H.IsSymm)
    (hmax : IsMaxOn ψ Dplus lamStar)
    (hlam : -λ_min(H) < lamStar)
    (hStar : E) (hhStar : hStar = resolvent lamStar) :
    let r := ‖hStar‖
    r = (2 / M : ℝ) * lamStar

Definition 4.1.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.15's domain dom ψ is the existing owner cubicRegularizedQuadraticDualDomain; in the diagonal case, the bounded-below characterization of q_λ is the existing bridge theorem cubicRegularizedQuadraticScalarDualDomain_eq.

variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
open scoped CubicRegularizedDiagonalInvariants
recall cubicRegularizedQuadraticDualDomain

Proposition 4.1.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.15 (1): the two explicit minimizers in the counterexample are distinct.

open scoped CubicRegularizedDiagonalInvariants
namespace CubicRegularizedQuadraticCounterexample
local notation "E" => EuclideanSpace ℝ (Fin 2)
local notation "v" => cubicRegularizedQuadraticObjective g H 1
local notation "ψ" => cubicRegularizedQuadraticDualFunction g H 1
local notation "Dplus" => cubicRegularizedQuadraticDualDomain g H 1 ∩ Set.Ici (0 : ℝ)
theorem minimizerPos_ne_minimizerNeg :
    minimizerPos ≠ minimizerNeg

Definition 4.1.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.16: the accepted regularized-Newton parameters at x are the admissible parameters M ∈ [L₀, 2L] that satisfy the acceptance inequality f (T_M(x)) ≤ \tilde f_M(x).

universe u variable {X : Type u} namespace RegularizedNewton variable (f : X → ℝ) (stepMap : ℝ → X → X) (modelValue : ℝ → X → ℝ) variable (L0 L : ℝ) (x : X) def acceptedParameters : Set ℝ := Set.Icc L0 (2 * L) ∩ acceptingParameters f stepMap modelValue x

Proposition 4.1.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.16: for the conservative backtracking rule, if the acceptance inequality holds for every tested parameter M ≥ L and the initial regularization satisfies M₀ ∈ [L₀, 2L], then the total number of computed trial mappings T_M through iteration N is at most 2 (N + 1) + log₂ (2L / L₀).

open scoped BigOperators universe u variable {X : Type u} namespace CubicRegularizationBacktracking open RegularizedNewton variable {f : X → ℝ} {stepMap : ℝ → X → X} {modelValue : ℝ → X → ℝ} variable {x : ℕ → X} {regularization : ℕ → ℝ} {L0 L : ℝ} {N : ℕ} variable (htrajectory : ∀ i : Fin (N + 1), IsNextRegularization f stepMap modelValue (x i.1) (regularization i.1) L0 (regularization (i.1 + 1))) (hautomatic : ∀ k : ℕ, k ≤ N → ∀ ⦃M : ℝ⦄, M ∈ Set.Ici L → M ∈ acceptingParameters f stepMap modelValue (x k)) (hregularization_zero_mem_Icc : regularization 0 ∈ Set.Icc L0 (2 * L)) (hL0 : 0 < L0) include htrajectory hautomatic hregularization_zero_mem_Icc hL0 theorem totalComputedMappings_le_conservative_backtracking_cost_bound : (totalComputedMappings htrajectory hautomatic hregularization_zero_mem_Icc hL0 : ℝ) ≤ (2 : ℝ) * (N + 1 : ℝ) + Real.logb 2 ((2 * L) / L0)

Definition 4.1.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.1.17: i_k is the least backtracking exponent whose trial parameter 2^i M_k satisfies the acceptance inequality.

universe u variable {X : Type u} namespace CubicRegularizationBacktracking open RegularizedNewton variable (f : X → ℝ) (stepMap : ℝ → X → X) (modelValue : ℝ → X → ℝ) (xk : X) (Mk : ℝ) noncomputable def index (hAccepts : (acceptingExponents f stepMap modelValue xk Mk).Nonempty) : ℕ := let _ : DecidablePred (· ∈ acceptingExponents f stepMap modelValue xk Mk) := Classical.decPred _ Nat.find hAccepts

Proposition 4.1.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.1.18 (1): verified public theorem closing the dependency-closed plain bound coming from the same-file first/second-phase route.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped ConstrainedArgmin open HasGloballyNondegenerateOptimalSet (UsesConstant) variable {f : E → ℝ} {stepMap : ℝ → E → E} {L0 : ℝ} {L : NNReal} {x0 : E} variable {μ D ε : ℝ} {N : ℕ} local notation "χ" => ((L : ℝ) * D) / μ local notation "ω₀" => μ ^ (3 : ℕ) / (18 * (L : ℝ) ^ (2 : ℕ)) local notation "B" => (25 / 4 : ℝ) * Real.sqrt χ + Real.logb 3 (Real.logb 4 (1 / ε) + Real.logb 4 (2 * μ ^ (3 : ℕ) / (9 * (L : ℝ) ^ (2 : ℕ)))) namespace StrongConvexBound theorem le_globalIterationBound {n : ℕ} {f : EuclideanSpace ℝ (Fin n) → ℝ} {stepMap : ℝ → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n)} {L0 : ℝ} {L : NNReal} {x0 : EuclideanSpace ℝ (Fin n)} {μ D ε : ℝ} {N : ℕ} (method : CubicRegularizationMethod f stepMap L0 (L : ℝ) x0) (xStar : EuclideanSpace ℝ (Fin n)) (hμ : 0 < μ) (hL : 0 < (L : ℝ)) (hf_hessian : f ∈ C22[L]) (hf_strong : StrongConvexOn Set.univ μ f) (hxStar : IsMinOn f Set.univ xStar) (hD : IsGreatest ((fun x : EuclideanSpace ℝ (Fin n) ↦ ‖x - xStar‖) '' {x : EuclideanSpace ℝ (Fin n) | f x ≤ f x0}) D) (hε : ε ∈ Set.Ioc 0 (μ ^ (3 : ℕ) / (18 * (L : ℝ) ^ (2 : ℕ)))) (hN : IsLeast {k : ℕ | f (method k) - f xStar ≤ ε} N) : (N : ℝ) ≤ 2 + 3 * Real.sqrt (((L : ℝ) * D) / μ) + 6 * Real.rpow (((3 / 2 : ℝ) * μ * D ^ (2 : ℕ)) / (μ ^ (3 : ℕ) / (18 * (L : ℝ) ^ (2 : ℕ)))) (1 / 4 : ℝ) + (1 + Real.logb (3 / 2) (Real.logb 4 (1 / ε) + Real.logb 4 (2 * μ ^ (3 : ℕ) / (9 * (L : ℝ) ^ (2 : ℕ)))))

4.2 — Accelerated Cubic Newton

Algorithm 4.2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.2.1: a cubic Newton method for an objective f, an initial point x₀, and a Lipschitz-Hessian constant L₃ consists of a chosen cubic-model minimizer map T_{L₃} and the standing owner hypothesis f ∈ C22[L3]; the iterate sequence x₀, x₁, x₂, ... is the canonical recursive orbit x_k = T_{L₃}^[k](x₀).

open scoped Gradient
open scoped CubicRegularizationModelNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
structure CubicNewtonMethod
    (f : E → ℝ) (L3 : NNReal) (x0 : E) where
  /-- The chosen cubic-model minimizer map `T_{L₃}`. -/
  step : CubicRegularizationMapping f (L3 : ℝ)
  /-- The objective belongs to the canonical whole-space Hessian-Lipschitz owner `C_M^{2,2}`. -/
  objective_mem : f ∈ C22[L3]

Definition 4.2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.1: for an R-module E, the dual space E* is the canonical owner Dual R E, i.e. the space (E →ₗ[R] R) of linear functionals on E. The textbook real-vector- space case is the specialization R = ℝ.

open Module universe u v variable {R : Type u} {E : Type v} [Semiring R] [AddCommMonoid E] [Module R E] recall Module.Dual

Lemma 4.2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.2.1: in the chapter regime p ≥ 2, if d is differentiable on a convex set Q and its gradient satisfies the monotonicity bound ⟪∇ d(x) - ∇ d(y), x - y⟫ ≥ σp ‖x - y‖^p, then d is uniformly convex on Q with modulus r ↦ (1 / p) * σp * r^p.

open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable {Q : Set E} {d : E → ℝ} {σp p : ℝ}
local notation "gradQ" => gradientWithin d Q
theorem uniformConvexOn_of_gradient_monotone
    (hp : 2 ≤ p)
    (hQ : Convex ℝ Q)
    (hd : DifferentiableOn ℝ d Q)
    (hmono :
      ∀ ⦃x y : E⦄, x ∈ Q → y ∈ Q →
        σp * Real.rpow ‖x - y‖ p ≤ inner ℝ (gradQ x - gradQ y) (x - y)) :
    UniformConvexOn Q (uniformConvexPowerModulus σp p) d

Text 4.2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.1 lies in the real inner-product-space gradient/Fréchet-derivative domain. Relevant owner-style declarations sampled before refinement: - DifferentiableAt.hasGradientAt - HasGradientAt.fderiv_apply - inner_gradient_left - HasGradientAt.hasFDerivAt Best owner abstraction: - DifferentiableAt.hasGradientAt Primitive data: - a function f : E → ℝ - a base point x : E Derived API: - the canonical gradient witness DifferentiableAt.hasGradientAt - the owner-side derivative evaluation formula HasGradientAt.fderiv_apply - its differentiability-point specialization inner_gradient_left Source/core/bridge triage: - source-facing: the textbook statement that, at differentiability points, the gradient represents the derivative - core/canonical: DifferentiableAt.hasGradientAt - bridge/view: HasGradientAt.fderiv_apply and inner_gradient_left The first sentence of Text 4.2.1 is already exactly the mathlib owner theorem, so this file recalls the canonical owner surface directly instead of keeping parallel wrapper lemmas. The ambient model is generalized from EuclideanSpace ℝ (Fin n) to an arbitrary complete real inner product space, since the canonical owner API and the source mathematics use only that structure.

variable {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall DifferentiableAt.hasGradientAt

Theorem 4.2.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.2.1: if xStar ∈ argmin[Q] d and d is uniformly convex on Q with modulus r ↦ (1 / p) * σp * r^p, then d x ≥ d xStar + (σp / p) * ‖x - xStar‖^p for all x ∈ Q.

open scoped ConstrainedArgmin universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] theorem lower_bound_at_minimizer_of_uniformConvexOn {σp p : ℝ} {Q : Set E} {d : E → ℝ} (huniform : UniformConvexOn Q (uniformConvexPowerModulus σp p) d) {xStar : E} (hxStar : xStar ∈ argmin[Q] d) (x : E) (hx : x ∈ Q) : d x ≥ d xStar + uniformConvexPowerModulus σp p ‖x - xStar‖

Algorithm 4.2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.2.2: an accelerated cubic regularization method for Newton's method with the chosen cubic-step owners T_{L₃} and T_{2L₃}, Hessian-Lipschitz constant L₃, and initial point x₀ consists of the iterate sequence x_k, affine parts ℓ_k of the estimating functions, estimating-function minimizers v_k, and scaling parameters A_k such that x₁ = T_{L₃}(x₀), ψ_k(x) = ℓ_k(x) + L₃ ‖x - x₀‖^3, ℓ₁(x) = f(x₁), A₁ = 1, each v_k minimizes ψ_k, each successor iterate satisfies x_{k+1} = T_{2L₃}(y_k) with y_k = (k / (k + 3)) x_k + (3 / (k + 3)) v_k, the affine parts satisfy ℓ_{k+1} = ℓ_k + a_k [f(x_{k+1}) + ⟪∇ f(x_{k+1}), · - x_{k+1}⟫], and the updates A_{k+1} = A_k + a_k hold for a_k = ((k + 1) (k + 2)) / 2.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure AcceleratedCubicNewtonMethod (f : E → ℝ) (L3 : NNReal) (x0 : E) where /-- The canonical cubic-step owner `T_{L₃}` used for the first iterate. -/ step : CubicRegularizationMapping f (L3 : ℝ) /-- The canonical cubic-step owner `T_{2L₃}` used in the recursive updates. -/ doubleStep : CubicRegularizationMapping f (2 * (L3 : ℝ)) /-- The objective belongs to the chapter smoothness owner `C_M^{2,2}`. -/ objective_mem : f ∈ C22[L3] /-- The main iterate sequence `x₀, x₁, x₂, ...`. -/ x : ℕ → E /-- The affine parts `ℓ_k` of the estimating functions `ψ_k`. -/ affinePart : ℕ → E →ᵃ[ℝ] ℝ /-- The minimizers `v_k` of the estimating functions `ψ_k`. -/ v : ℕ → E /-- The scaling parameters `A_k`. -/ A : ℕ → ℝ /-- The initialization fixes the starting point `x₀`. -/ x_zero : x 0 = x0 /-- The first accelerated iterate is the cubic step `x₁ = T_{L₃}(x₀)`. -/ x_one : x 1 = step x0 /-- The first affine part is the constant affine map with value `f(x₁)`. -/ affinePart_one : affinePart 1 = AffineMap.const ℝ E (f (x 1)) /-- The initial scaling parameter equals `A₁ = 1`. -/ A_one : A 1 = 1 /-- Each `v_k` is a global minimizer of the estimating function `ψ_k`. -/ v_isMin (k : ℕ) (hk : 1 ≤ k) : IsMinOn (cubicNewtonEstimatingFunction affinePart (6 * (L3 : ℝ)) x0 k) Set.univ (v k) /-- Each successor iterate is obtained by the cubic regularization step `x_{k+1} = T_{2L₃}(y_k)` with `y_k = (k / (k + 3)) x_k + (3 / (k + 3)) v_k`. -/ x_succ (k : ℕ) (hk : 1 ≤ k) : x (k + 1) = doubleStep (acceleratedCubicNewtonInterpolationPoint x v k) /-- The affine parts satisfy the affine-gradient recursion from the algorithm. -/ affinePart_succ (k : ℕ) (hk : 1 ≤ k) : affinePart (k + 1) = affinePart k + acceleratedCubicNewtonWeight k • sampledAffineMinorant (x (k + 1)) (∇ f (x (k + 1))) (f (x (k + 1))) /-- The scaling parameters satisfy `A_{k+1} = A_k + a_k`. -/ A_succ (k : ℕ) (hk : 1 ≤ k) : A (k + 1) = A k + acceleratedCubicNewtonWeight k

Definition 4.2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.2: for a differentiable real-valued function on a complete real inner-product space, the gradient at xBar, denoted ∇ f xBar, is the canonical gradient vector.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) (xBar : E) #check (∇ f xBar : E)

Lemma 4.2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.2.2 in source-facing form: for a degree-p uniformly convex function, the Bregman gap between two feasible points is controlled by the dual power of the difference of their canonical within-gradients.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {Q : Set E} {d : E → ℝ} {p σp : ℝ} local notation "gradQ" => gradientWithin d Q namespace UniformConvexOn theorem tangent_gap_le_gradient_sub_rpow (huc : UniformConvexOn Q (uniformConvexPowerModulus σp p) d) (hp : 1 < p) (hσp : 0 < σp) {x y : E} (hx : x ∈ Q) (hy : y ∈ Q) (hdx : DifferentiableWithinAt ℝ d Q x) (hdy : DifferentiableWithinAt ℝ d Q y) : d y - d x - inner ℝ (gradQ x) (y - x) ≤ ((p - 1) / p) * Real.rpow (1 / σp) (1 / (p - 1)) * Real.rpow ‖gradQ y - gradQ x‖ (p / (p - 1))

Text 4.2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.2: the duality pairing equals the Euclidean inner product of the coordinate vectors B* s and B⁻¹ x.

open Module universe u v variable {E : Type u} [AddCommGroup E] [Module ℝ E] -- Proof sketch: expand `x` in the basis `B` and `s` in the dual basis `B*`; evaluation of `s` -- on the resulting linear combination reduces to the sum of coordinatewise products, which is the -- Euclidean dot product of the two coordinate vectors. theorem dualityPairing_eq_inner_coordinateVectors {n : ℕ} (B : Basis (Fin n) ℝ E) (s : Dual ℝ E) (x : E) : Module.dualPairing ℝ E s x = inner ℝ ((EuclideanSpace.equiv (Fin n) ℝ).symm (B.dualBasis.equivFun s)) ((EuclideanSpace.equiv (Fin n) ℝ).symm (B.equivFun x))

Theorem 4.2.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

In basis/dual-basis coordinates, the duality pairing is the standard dot product.

open Module universe u v variable {R : Type v} {ι : Type*} {E : Type u} variable [CommSemiring R] [Fintype ι] [AddCommMonoid E] [Module R E] theorem dualityPairing_eq_coordinateDotProduct (B : Basis ι R E) (s : Dual R E) (x : E) : Module.dualPairing R E s x = (fun i ↦ s (B i)) ⬝ᵥ B.equivFun x

Algorithm 4.2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.2.3: if innerMethod x denotes the chapter accelerated cubic-Newton method started from x, then the restarted accelerated cubic-Newton method with starting point x₀ is the canonical outer orbit of the restart map x ↦ 𝓐_m(x), where m = ⌈((24 e) / (σ₃ / L₃))^{1/3}⌉₊ and 𝓐_m(x) is written canonically as innerMethod x (acceleratedCubicNewtonRestartPeriod σ₃ L₃).

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] variable {f : E → ℝ} {sigma3 : ℝ} {L3 : NNReal} variable [CompleteSpace E] def restartedAcceleratedCubicNewtonMethod (innerMethod : (x : E) → AcceleratedCubicNewtonMethod f L3 x) (sigma3 : ℝ) (x0 : E) : ℕ → E := fun k ↦ (acceleratedCubicNewtonRestartMap innerMethod sigma3)^[k] x0

Definition 4.2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.3: for a linear operator A : E₁ → E₂*, the adjoint operator is exactly the canonical transpose A.flip : E₂ → E₁*.

open Module universe u v w variable {R : Type u} {E₁ : Type v} {E₂ : Type w} variable [CommSemiring R] variable [AddCommMonoid E₁] [Module R E₁] variable [AddCommMonoid E₂] [Module R E₂] #check (LinearMap.flip : (E₁ →ₗ[R] Dual R E₂) → E₂ →ₗ[R] Dual R E₁)

Lemma 4.2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.2.3 in owner form: on the intrinsic B-weighted space, the degree-p power regularizer is uniformly convex with the textbook modulus (1 / p) * (1 / 2)^(p - 2) * r^p.

universe u open LinearMap (BilinForm) open scoped BInducedNorm variable {E : Type u} [AddCommGroup E] [Module ℝ E] variable (B : BilinForm ℝ E) (hSymm : B.IsSymm) (hPos : B.toQuadraticMap.PosDef) variable (p : ℝ) variable (x0 x y : LinearMap.BilinForm.PrimalSpace B) theorem powerFunction_uniformConvexOn (hp : 2 ≤ p) : by let _ := hp letI : Fact B.IsSymm := ⟨hSymm⟩ letI : Fact B.toQuadraticMap.PosDef := ⟨hPos⟩ exact UniformConvexOn Set.univ (uniformConvexPowerModulus (Real.rpow (1 / 2 : ℝ) (p - 2)) p) (powerFunction B p x0)

Text 4.2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.3: if f is twice differentiable at x, then the Hessian at x is the continuous linear operator from the primal space E to the continuous dual E⋆ obtained by differentiating the gradient and composing with the Riesz identification E ≃ E⋆.

open InnerProductSpace open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem hessian_toDualMap_hasFDerivAt (f : E → ℝ) (x : E) (hf : DifferentiableAt ℝ (∇ f) x) : HasFDerivAt ((toDualMap ℝ E) ∘ ∇ f) ((toDualMap ℝ E).toContinuousLinearMap.comp (hessian f x)) x

Theorem 4.2.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.3: let method be the accelerated cubic Newton method. If f ∈ C22[L3] is convex, then every iterate with index k ≥ 1 satisfies f(x_k) - f(x^*) ≤ 8 L₃ ‖x₀ - x^*‖^3 / (k (k + 1) (k + 2)).

open scoped Gradient CubicRegularizationModelNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem acceleratedCubicRegularization_gap_le_inverse_cubic_rate {f : E → ℝ} {L3 : NNReal} {x0 xStar : E} (method : AcceleratedCubicNewtonMethod f L3 x0) (hf_conv : ConvexOn ℝ Set.univ f) (hxStar : IsMinOn f Set.univ xStar) (k : ℕ) (hk : 1 ≤ k) : f (method k) - f xStar ≤ (8 * (L3 : ℝ) * ‖x0 - xStar‖ ^ (3 : ℕ)) / ((k : ℝ) * ((k : ℝ) + 1) * ((k : ℝ) + 2))

Algorithm 4.2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.2.4: the strong-convex accelerated cubic-Newton method is the outer sequence obtained by applying at stage k the restart map with the stage-dependent length ⌈m_k⌉₊ = stageSteps σ₂ L₃ R k, where the source stage schedule is m_k = stageLength σ₂ L₃ R k.

universe u namespace StrongConvexAcceleratedCubicNewton variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {L3 : NNReal} def method (innerMethod : (x : E) → AcceleratedCubicNewtonMethod f L3 x) (σ2 R : ℝ) (y0 : E) : ℕ → E := Nat.rec y0 (fun k yk ↦ stageMap innerMethod σ2 R k yk)

Definition 4.2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.4 uses the canonical basis coordinate equivalence B.equivFun, whose inverse is the basis operator from coordinates to vectors.

open Module open scoped BigOperators universe u v #check Basis.equivFun

Lemma 4.2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.2.4, pointwise form: for any x, y ∈ E, the Hessian of the centered cubic power function satisfies ‖∇² d₃(x) - ∇² d₃(y)‖ ≤ 2 * ‖x - y‖.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem powerDistance_three_zero_hessian_norm_sub_le (x y : E) : ‖hessian (powerDistance (3 : ℝ) (0 : E)) x - hessian (powerDistance (3 : ℝ) (0 : E)) y‖ ≤ (2 : ℝ) * ‖x - y‖

Text 4.2.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.4: the support-function formula for the B-dual norm agrees with the coordinate-free expression ⟨s, B⁻¹ s⟩^(1/2), where B⁻¹ s is the preimage of s under the finite-dimensional equivalence B.toDual induced by the symmetric positive-definite bilinear form B.

open Module LinearMap universe u namespace LinearMap.BilinForm open scoped BInducedNorm variable {E : Type u} [AddCommGroup E] [Module ℝ E] [FiniteDimensional ℝ E] theorem dualNorm_eq_sqrt_dualPairing_preimage (B : LinearMap.BilinForm ℝ E) (hSymm : B.IsSymm) (hPos : B.toQuadraticMap.PosDef) (s : Dual ℝ E) : sSup ((fun x : E ↦ s x) '' {x | B.primalSeminorm hPos x ≤ 1}) = Real.sqrt (s (B.dualPreimage hPos s))

Algorithm 4.2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

open scoped ConstrainedArgmin Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable (f : E → ℝ) {M : ℝ} (step : CubicRegularizationMapping f M) (xk yk : E) #check ({xHat : E // xHat ∈ argmin[{xk, step yk}] f} : Type u)

Definition 4.2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.5: for a linear operator B : E → E⋆ on a real vector space, the textbook self-adjointness condition is the canonical symmetry predicate on the associated bilinear form, equivalently (B x) y = (B y) x for all x and y.

universe u v variable {R : Type u} {M : Type v} [CommSemiring R] [AddCommMonoid M] [Module R M] open LinearMap (BilinForm) recall LinearMap.BilinForm.IsSymm (B : BilinForm R M) : Prop

Lemma 4.2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.2.5: if f ∈ C22[L₃], if T belongs to the canonical cubic-regularization step set argmin[Set.univ] (m[f; M](x)), and if 2 L₃ ≤ M, then ⟪∇ f(T), x - T⟫ ≥ √(2 / (L₃ + M)) ‖∇ f(T)‖^(3 / 2).

open scoped Gradient open scoped ConstrainedArgmin open scoped CubicRegularizationModelNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem cubicRegularization_gradientPairing_ge_sqrt_mul_gradientNorm_rpow_threeHalves {f : E → ℝ} {L3 : NNReal} (hf : f ∈ C22[L3]) {x T : E} {M : ℝ} (hM : 2 * (L3 : ℝ) ≤ M) (hT : T ∈ argmin[Set.univ] (m[f; M](x))) : inner ℝ (∇ f T) (x - T) ≥ Real.sqrt (2 / ((L3 : ℝ) + M)) * Real.rpow ‖∇ f T‖ (3 / 2 : ℝ)

Text 4.2.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.5 lies in the second-order smooth optimization domain on real Hilbert spaces. Sampled owner-style declarations: - HasLipschitzContinuousHessian - HasLipschitzContinuousHessian.norm_sub_le - HasLipschitzContinuousHessian.gradient_deviation_le - HasLipschitzContinuousHessian.secondOrderTaylorModel_error_le Best owner abstraction: - the Chapter 1 owner HasLipschitzContinuousHessian M f, written on theorem surfaces as f ∈ C22[M] Primitive data: - a function f : E → ℝ - a Hessian-Lipschitz constant M : NNReal - base and target points x y : E Derived API: - HasLipschitzContinuousHessian.gradient_deviation_le - HasLipschitzContinuousHessian.secondOrderTaylorModel_error_le Source/core/bridge triage: - source-facing: the gradient and second-order Taylor remainder bounds stated in Text 4.2.5 - core/canonical: the Chapter 1 owner HasLipschitzContinuousHessian - bridge/view: evaluation of the owner theorems at the points x and y Text 4.2.5 adds no new mathematics beyond the Chapter 1 owner theorems, so this file is a pure recall item. Keeping local wrappers here would duplicate the owner API and weaken the chapter's canonical vocabulary.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall HasLipschitzContinuousHessian.gradient_deviation_le

Definition 4.2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.6: for a positive-definite self-adjoint operator, the primal norm on E is recalled through the canonical bilinear-form owner LinearMap.BilinForm.primalSeminorm, whose value at h is ⟪Bh, h⟫^(1/2) and whose owner surface depends only on B.toQuadraticMap.

universe u open Module LinearMap namespace LinearMap.BilinForm variable {E : Type u} [AddCommGroup E] [Module ℝ E] recall LinearMap.BilinForm.primalSeminorm (B : LinearMap.BilinForm ℝ E) (hPos : B.toQuadraticMap.PosDef) : Seminorm ℝ E

Lemma 4.2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.2.6 (1): if f lies in the strong-convex smooth class 𝓢^{1,1}_{σ₂,L}, then relative to any chosen global minimizer xStar there exists a uniform first-order nondegeneracy lower bound τ whose size is at least the explicit threshold 2 * sqrt q[σ₂, L] / (1 + q[σ₂, L]).

open scoped Gradient StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {σ2 L τ : ℝ} {f : E → ℝ} {xStar : E} theorem exists_firstOrderNondegeneracyLowerBound_of_mem_S11 (hf : f ∈ 𝓢[σ2, L]¹¹) (hxStar : IsMinOn f Set.univ xStar) : ∃ τ : ℝ, 2 * Real.sqrt q[σ2, L] / (1 + q[σ2, L]) ≤ τ ∧ IsFirstOrderNondegeneracyLowerBound f xStar τ

Text 4.2.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.6: for p ≥ 2, the power-distance x ↦ (1 / p) * ‖x - x₀‖^p on a real inner-product space has gradient ‖x - x₀‖^(p - 2) • (x - x₀) at every point. In particular, this applies to the finite-dimensional setting of the text.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem hasGradientAt_powerDistance {p : ℝ} (hp : 2 ≤ p) (x0 x : E) : HasGradientAt (powerDistance p x0) (‖x - x0‖ ^ (p - 2) • (x - x0)) x

Definition 4.2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.7: a real-valued function has Lipschitz-continuous Hessian with constant L₃ when it is twice continuously differentiable and its second Fréchet derivative x ↦ fderiv ℝ (fderiv ℝ f) x is globally L₃-Lipschitz in operator norm. On real Hilbert spaces, the usual Hessian-operator surface is recovered by the derived theorem HasLipschitzContinuousHessian.lipschitz.

universe u open scoped Gradient variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] class HasLipschitzContinuousHessian (L3 : NNReal) (f : E → ℝ) : Prop where /-- The function is twice continuously differentiable. -/ contDiff : ContDiff ℝ 2 f /-- The second Fréchet derivative is globally `L₃`-Lipschitz in operator norm. -/ sndFDeriv_lipschitz : LipschitzWith L3 (fun x ↦ fderiv ℝ (fderiv ℝ f) x)

Lemma 4.2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

universe u
open scoped DegreeConditioning
open LinearMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (x0 : E)
instance :
    HasIteratedFDerivLipschitzConstantOfDegree 2 (powerDistance (2 : ℝ) x0)

Text 4.2.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

universe u
open scoped DegreeConditioning
open LinearMap
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable (x0 : E)
instance :
    HasIteratedFDerivLipschitzConstantOfDegree 2 (powerDistance (2 : ℝ) x0)

Definition 4.2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.8: d is uniformly convex on Q of degree p if p ≥ 2 and there exists a positive parameter σp such that, for all x, y ∈ Q, d y ≥ d x + ⟪∇ d(x), y - x⟫ + (1 / p) * σp * ‖y - x‖^p.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {Q : Set E} {p : ℝ} {d : E → ℝ} class ExistsPosUniformConvexOn (Q : Set E) (p : ℝ) (d : E → ℝ) : Prop where hp : 2 ≤ p isClosed : IsClosed Q convex : Convex ℝ Q differentiableOn : DifferentiableOn ℝ d Q lower_tangent_power : ∃ σp > 0, ∀ ⦃x y : E⦄, x ∈ Q → y ∈ Q → d y ≥ d x + inner ℝ (gradientWithin d Q x) (y - x) + uniformConvexPowerModulus σp p ‖y - x‖

Text 4.2.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.8 (1) is the direct Chapter 4 recall of the owner theorem from Lemma_4_1_4; this file keeps no parallel local theorem shell.

open scoped Gradient CubicRegularizationModelNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {L3 : NNReal} {f : E → ℝ} {M : ℝ} {x T : E} recall gradient_norm_le_of_isMinOn_cubicRegularizationQuadraticApproximation -- Proof sketch: compare `f T` with `m[f; M](x; T)` using the -- Chapter 4 objective-versus-model upper bound from `Lemma_4_1_5`, use the minimizing property -- against the competitor `x`, and then rewrite the resulting cubic-model gap using the -- first-order optimality relation of the minimizer. Convexity keeps the Hessian quadratic term -- nonnegative, leaving the factor `(M / 3) ‖x - T‖³`.

Definition 4.2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.9: for a fixed center x₀ and a positive-definite self-adjoint bilinear form B, the degree-p power function is x ↦ (1 / p) * ‖x - x₀‖[B]^p.

universe u open LinearMap (BilinForm) open scoped BInducedNorm variable {E : Type u} [AddCommGroup E] [Module ℝ E] def powerFunction (B : BilinForm ℝ E) [Fact B.toQuadraticMap.PosDef] (p : ℝ) (x0 : LinearMap.BilinForm.PrimalSpace B) : LinearMap.BilinForm.PrimalSpace B → ℝ := powerDistance p x0

Text 4.2.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.9 ("Complexity of Non-degenerate Problems"): the subsection's canonical complexity surface is the cubic-Newton iteration bound stated in Text 4.2.10.

recall cubic_newton_gap_le_of_iteration_count_bound

Definition 4.2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.10: a nonnegative constant L is a Lipschitz constant for the (p - 1)-st derivative of f on s exactly when f belongs to the Chapter 1 owner 𝒞^{p - 1,p - 1}_{L}(s). The iteratedFDerivWithin presentation is a bridge view recovered under UniqueDiffOn ℝ s, not the primitive owner.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable (p : ℕ) (f : E → ℝ) (s : Set E) (L : NNReal) local notation "TaylorSeries" => E → FormalMultilinearSeries ℝ E ℝ #check (f ∈ 𝒞^{p - 1,p - 1}_{L}(s))

Text 4.2.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.10 (1): if 3 √σ₃ (f x - f xStar) ≤ 2 ‖∇ f x‖^(3/2) for every x, and if the sequence x satisfies ‖∇ f(x_{k+1})‖^(3/2) ≤ 3 √L₃ (f(x_k) - f(x_{k+1})), then each one-step decrease controls the next gap by √σ₃ (f(x_{k+1}) - f(xStar)) ≤ 2 √L₃ (f(x_k) - f(x_{k+1})), equivalently by the textbook factor (1 / 2) * sqrt (σ₃ / L₃).

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {x : ℕ → E} {xStar : E} {σ₃ L₃ : NNRealˣ} local notation "Δ" => fun k : ℕ ↦ f (x k) - f xStar local notation "ρ" => ((2 : ℝ) * Real.sqrt (L₃ : ℝ)) / ((2 : ℝ) * Real.sqrt (L₃ : ℝ) + Real.sqrt (σ₃ : ℝ)) -- Proof sketch: apply the global gap estimate at `x_{k+1}` to bound -- `Real.rpow ‖∇ f (x (k + 1))‖ (3 / 2)` from below, then substitute that lower bound into the -- assumed one-step descent inequality. Writing the source bounds in multiplication form yields -- `√σ₃ * Δ_{k+1} ≤ 2 √L₃ * (f(x_k) - f(x_{k+1}))`, which is equivalent to the textbook factor -- `(1 / 2) * sqrt (σ₃ / L₃)` because `σ₃, L₃ > 0` are owned by `NNRealˣ`. theorem cubic_newton_objective_drop_ge_half_sqrt_conditionNumber_mul_next_gap (hgap : ∀ z : E, (3 : ℝ) * Real.sqrt (σ₃ : ℝ) * (f z - f xStar) ≤ (2 : ℝ) * Real.rpow ‖∇ f z‖ (3 / 2 : ℝ)) (hdescent : ∀ k : ℕ, Real.rpow ‖∇ f (x (k + 1))‖ (3 / 2 : ℝ) ≤ (3 : ℝ) * Real.sqrt (L₃ : ℝ) * (f (x k) - f (x (k + 1)))) (k : ℕ) : Real.sqrt (σ₃ : ℝ) * Δ (k + 1) ≤ (2 : ℝ) * Real.sqrt (L₃ : ℝ) * (f (x k) - f (x (k + 1)))

Definition 4.2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.11: for a function f and degree p, the degree-p condition number γ_p(f) is the ratio σ_p(f) / L_p(f) of its degree-p uniform-convexity parameter and its degree-p Lipschitz constant for the (p - 1)st derivative. This is defined only when σ_p(f) is a genuine real parameter and the canonical denominator L_p(f) is strictly positive.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] def conditionNumberOfDegree (f : E → ℝ) (p : ℕ) [HasUniformConvexityParameterOfDegree p f] [HasIteratedFDerivLipschitzConstantOfDegree p f] [HasPositiveIteratedFDerivLipschitzConstantOfDegree p f] : ℝ := uniformConvexityParameterOfDegree f p / iteratedFDerivLipschitzConstantOfDegree f p

Text 4.2.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.11 uses the existing Chapter 4 cubic-model owner and its expansion directly; this file keeps no parallel local copy.

open scoped Gradient CubicRegularizationModelNotation ConstrainedArgmin StrongConvex universe u variable {E : Type u} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] recall cubicRegularizationQuadraticApproximation

Definition 4.2.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.12: if f is C² at x, then the cubic-regularization point T x satisfies the textbook stationarity equation for the cubic model centered at x.

open scoped Gradient open scoped ConstrainedArgmin open scoped CubicRegularizationResidual open scoped CubicRegularizationModelNotation universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] namespace CubicRegularizationMapping -- Proof sketch: combine `T.isMinOn_apply x` with the `C²` stationarity theorem -- `cubicRegularization_firstOrderOptimalityCondition_of_isMinOn`. theorem firstOrderOptimalityCondition (T : CubicRegularizationMapping f M) (x : E) (hf : ContDiffAt ℝ 2 f x) : ∇ f x + hessian f x (T x - x) + ((M / 2 : ℝ) * ‖T x - x‖) • (T x - x) = 0

Text 4.2.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The gradient-based threshold region 𝒬_g from Text 4.2.12, written in multiplication form so that the degenerate case L₃ = 0 still gives the intended whole-space threshold.

open scoped Gradient open NewtonSystem (AdmissiblePoint step) universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] def quadraticGradientRegion (f : E → ℝ) (σ2 : ℝ) (L3 : NNReal) : Set E := {x | 4 * (L3 : ℝ) * ‖∇ f x‖ ≤ σ2 ^ (2 : ℕ)} -- Proof sketch: unfold `quadraticGradientRegion`.

Definition 4.2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.13: the cubic-regularized proximal problem at x is the source-facing owner cubicRegularizationProblem f M x, and Φ_M(x) is its canonical optimal value.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped CubicRegularizationModelNotation variable (f : E → ℝ) (M : ℝ) (x T : E) recall cubicRegularizationProblem

Text 4.2.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The quadratic-entry region for Text 4 2 13, written in multiplication form so that the degenerate case L₃ = 0 still gives the intended whole-space threshold region.

open scoped BigOperators Gradient open StrongConvexAcceleratedCubicNewton universe u variable {E : Type u} def strongConvexAcceleratedCubicNewtonQuadraticRegion (f : E → ℝ) (xStar : E) (σ2 : ℝ) (L3 : NNReal) : Set E := {x | (8 : ℝ) * (L3 : ℝ) ^ (2 : ℕ) * (f x - f xStar) ≤ σ2 ^ (3 : ℕ)} -- Proof sketch: unfold `strongConvexAcceleratedCubicNewtonQuadraticRegion`.

Definition 4.2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.14: a cubic-Newton estimating sequence for f, centered at x0 with cubic parameter C and Hessian-Lipschitz constant L3, consists of affine parts ℓ_k, points x_k, scales A_k, and increments a_k such that ψ_k(x) = ℓ_k(x) + (C / 6) ‖x - x0‖^3, each x_k minimizes ψ_k, the scales satisfy A_{k+1} = A_k + a_k, and the recursive relations 𝓡_k^1 and 𝓡_k^2 hold.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] structure CubicNewtonEstimatingSequence (f : E → ℝ) (x0 : E) (L3 C : ℝ) where /-- The affine parts `ℓ_k` of the estimating functions `ψ_k`. -/ affinePart : ℕ → E →ᵃ[ℝ] ℝ /-- The minimizing points `x_k`. -/ x : ℕ → E /-- The scaling parameters `A_k`. -/ A : ℕ → ℝ /-- The increments `a_k` in the recursion `A_{k+1} = A_k + a_k`. -/ a : ℕ → ℝ /-- The scaling parameters satisfy `A_{k+1} = A_k + a_k`. -/ A_succ (k : ℕ) : A (k + 1) = A k + a k /-- Each point `x_k` globally minimizes the estimating function `ψ_k`. -/ x_isMin (k : ℕ) : IsMinOn (cubicNewtonEstimatingFunction affinePart C x0 k) Set.univ (x k) /-- The recursive relation `𝓡_k^1`, written at the minimizing point `x_k` so that `ψ_k(x_k) = ψ_k^*`. -/ value_lower (k : ℕ) : A k * f (x k) ≤ cubicNewtonEstimatingFunction affinePart C x0 k (x k) /-- The recursive relation `𝓡_k^2`: every estimating function is bounded above by `A_k f(x) + ((2 L₃ + C) / 6) ‖x - x0‖^3`. -/ upper_bound (k : ℕ) (y : E) : cubicNewtonEstimatingFunction affinePart C x0 k y ≤ A k * f y + ((2 * L3 + C) / 6) * ‖y - x0‖ ^ (3 : ℕ)

Text 4.2.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The accepted-point owner from Algorithm 4.2.5 immediately gives the comparison f x_k - f x_{k+1} ≥ f xHat - f x_{k+1}. This is the bridge/view part of Text 4.2.14.

universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped ConstrainedArgmin open ModifiedAcceleratedCubicNewton theorem modified_accelerated_cubic_drop_ge_hat_drop (f : E → ℝ) (L3 : NNReal) {xk yk : E} (step : CubicRegularizationMapping f (2 * (L3 : ℝ))) (xHat : argmin[{xk, step yk}] f) : f xk - f (xNext xHat) ≥ f xHat - f (xNext xHat)

Definition 4.2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.15: an unconstrained objective is first-order non-degenerate relative to a chosen optimal solution xStar if xStar globally minimizes f and the coefficient α(x) = ⟪∇ f(x), x - xStar⟫ / (‖∇ f(x)‖ * ‖x - xStar‖) admits a uniform positive lower bound for every x ≠ xStar. The first-order interpretation of ∇ f(x) is part of the owner data: away from xStar, f is differentiable so the canonical gradient ∇ f x is the actual gradient.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] class IsFirstOrderNondegenerate (f : E → ℝ) (xStar : E) : Prop where /-- The reference point `xStar` is a global minimizer of `f`. -/ isMinOn : IsMinOn f Set.univ xStar /-- Away from the optimizer, `f` is differentiable, hence its canonical gradient is well-defined in the first-order sense. -/ differentiableAt {x : E} (_hx : x ≠ xStar) : DifferentiableAt ℝ f x /-- The cosine coefficient has a uniform positive lower bound away from the optimizer. -/ lowerBound : ∃ τ : ℝ, IsFirstOrderNondegeneracyLowerBound f xStar τ

Text 4.2.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.15 lies in the chapter's false-acceleration objective-gap transfer domain. Sampled neighboring declarations: * acceleratedCubicRegularization_gap_le_inverse_cubic_rate in Theorem_4_2_3, the chapter's owner inverse-cubic objective-gap estimate for accelerated cubic Newton iterates; * false_acceleration_gap_ge_gap_to_next_iterate_of_isMinOn in Text_4_2_16, the next scalar bridge statement in the same false-acceleration discussion; * false_acceleration_gap_le_inverse_eighth_rate in Text_4_2_17, the downstream scalar consequence that reuses the chapter-standard nonnegative constants L3 and R. Best owner abstraction: * source-facing: the displayed two-thirds-index objective-gap estimate f (x hatK) - f xStar ≤ 3^3 L3 R^3 / N^3; * core/canonical: the scalar inverse-cubic gap profile gap k ≤ (L3 * R^3) / k^3; * bridge/view: the companion specialization from the scalar profile to the objective-gap sequence gap k = f (x k) - f xStar. Primitive data: * the displayed indices N and hatK; * the chapter-standard nonnegative constants L3 and R. * the objective f, iterate sequence x, and comparison point xStar. Derived API: * the scalar companion theorem obtained by abstracting the objective gaps to a sequence gap; * positivity of the scalar prefactor, inherited from L3 R : NNReal. The previous version made the scalar bridge theorem the main public entry and left the textbook identification gap k = f (x k) - f xStar only in commentary. This refinement restores the source-facing objective-gap statement as the main theorem and keeps the scalar inverse-cubic algebra as a reusable companion.

universe u theorem inverse_cubic_gap_at_two_thirds_index_le_three_cubed_bound (gap : ℕ → ℝ) (N hatK : ℕ) (L3 R : NNReal) (hN : 0 < N) (hhatK : (hatK : ℝ) = (2 / 3 : ℝ) * (N : ℝ)) (hgap : ∀ ⦃k : ℕ⦄, 1 ≤ k → gap k ≤ ((L3 : ℝ) * (R : ℝ) ^ (3 : ℕ)) / (k : ℝ) ^ (3 : ℕ)) : gap hatK ≤ ((3 : ℝ) ^ (3 : ℕ) * ((L3 : ℝ) * (R : ℝ) ^ (3 : ℕ))) / (N : ℝ) ^ (3 : ℕ)

Definition 4.2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.16: the cubically regularized objective associated to f, the reference point x₀, and the parameter δ is the function x ↦ f x + (δ / 3) ‖x - x₀‖^3.

universe u open scoped LevelSetNotation variable {E : Type u} [NormedAddCommGroup E] def cubicallyRegularizedObjective (f : E → ℝ) (δ : ℝ) (x0 : E) : E → ℝ := fun x ↦ f x + (δ / 3) * ‖x - x0‖ ^ (3 : ℕ)

Text 4.2.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.16: if xStar is a global minimizer of f, then the objective gap at any iterate x_hatK dominates the gap from the same iterate to the later point x_{N+1}. In the textbook application, hatK is the two-thirds index from the preceding step.

universe u theorem false_acceleration_gap_ge_gap_to_next_iterate_of_isMinOn {E : Type u} (f : E → ℝ) (x : ℕ → E) (xStar : E) (N hatK : ℕ) (hxStar : IsMinOn f Set.univ xStar) : f (x hatK) - f xStar ≥ f (x hatK) - f (x (N + 1))

Definition 4.2.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.17: a function belongs to the class 𝓕_{2,3} when σ[2](f) and σ[3](f) are positive and L[3](f) is finite. The finiteness clause is carried by the canonical owner HasIteratedFDerivLipschitzConstantOfDegree 3 f, while the well-definedness of σ[2](f) and σ[3](f) is carried by the canonical finite-parameter owners HasUniformConvexityParameterOfDegree 2 f and HasUniformConvexityParameterOfDegree 3 f.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] open scoped DegreeConditioning class IsInFunctionClassF23 (f : E → ℝ) : Prop where /-- The degree-two uniform-convexity parameter of `f` is a genuine finite real parameter. -/ degreeTwo_uniform : HasUniformConvexityParameterOfDegree 2 f /-- The degree-three uniform-convexity parameter of `f` is a genuine finite real parameter. -/ degreeThree_uniform : HasUniformConvexityParameterOfDegree 3 f /-- The degree-three Lipschitz constant of `f` is finite. -/ degreeThree_lipschitz : HasIteratedFDerivLipschitzConstantOfDegree 3 f

Text 4.2.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.17 at the source-facing scalar consequence level: once the earlier convexity, smoothness, and false-acceleration hypotheses have been condensed into the local gap estimate at x_{N+1} and the inverse-linear distance decay ‖x_{N+1} - xStar‖ ≤ 3 R / N, substituting the distance bound into the eighth-power estimate yields the inverse-eighth decay of the objective gap for every positive index N.

universe u variable {E : Type u} [NormedAddCommGroup E] theorem false_acceleration_gap_le_inverse_eighth_rate (f : E → ℝ) (x : ℕ → E) (xStar : E) (σ₂ : ℝ) (L3 R : NNReal) (N : ℕ) (hσ₂ : 0 < σ₂) (hN : 0 < N) (hgap_upper : f (x (N + 1)) - f xStar ≤ (((3 : ℝ) ^ (9 : ℕ)) * (L3 : ℝ) ^ (4 : ℕ) / (2 * σ₂ ^ (3 : ℕ))) * ‖x (N + 1) - xStar‖ ^ (8 : ℕ)) (hdistance_decay : ‖x (N + 1) - xStar‖ ≤ 3 * (R : ℝ) / (N : ℝ)) : f (x (N + 1)) - f xStar ≤ (((3 : ℝ) ^ (17 : ℕ)) * (L3 : ℝ) ^ (4 : ℕ) * (R : ℝ) ^ (8 : ℕ)) / (2 * σ₂ ^ (3 : ℕ) * (N : ℝ) ^ (8 : ℕ))

Definition 4.2.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.2.18: a function belongs to the class 𝓕₂^{Lip} when its degree-two uniform-convexity parameter is positive and the degree-two and degree-three derivative Lipschitz constants are finite. The finiteness clauses are carried by the canonical owner classes HasUniformConvexityParameterOfDegree 2 f, HasIteratedFDerivLipschitzConstantOfDegree 2 f and HasIteratedFDerivLipschitzConstantOfDegree 3 f.

universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] open scoped DegreeConditioning class IsInFunctionClassF2Lip (f : E → ℝ) : Prop where /-- The degree-two uniform-convexity parameter of `f` is a genuine finite real parameter. -/ degreeTwo_uniform : HasUniformConvexityParameterOfDegree 2 f /-- The gradient of `f` admits a global Lipschitz constant. -/ degreeTwo_lipschitz : HasIteratedFDerivLipschitzConstantOfDegree 2 f /-- The Hessian of `f` admits a global Lipschitz constant. -/ degreeThree_lipschitz : HasIteratedFDerivLipschitzConstantOfDegree 3 f

Text 4.2.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The two displayed estimates preceding Text 4.2.18 imply the intermediate bound g_T^* ≤ ((27 L₃^(3/2) D^3) / (4 (m + 2)^3))^(2/3) for the fixed-start sampled minimum g_T^* = g⋆[T] = min_{1 ≤ k ≤ T} ‖∇ f (x k)‖, where D is recorded as a nonnegative radius constant.

open scoped Gradient MinGradientNormAlongIterates universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {x : ℕ → E} {xStar : E} variable {m T : ℕ} variable {L3 : NNReal} {D : NNReal} variable (h1T : 1 ≤ T) local notation "g⋆[" T "]" => g[f; x; 1, T | h1T] theorem accelerated_cubic_newton_min_gradient_norm_le_intermediate_bound (hL3 : 0 < (L3 : ℝ)) (hxStarT : f xStar ≤ f (x T)) (heven_gap : f (x (2 * m)) - f xStar ≤ (9 * (L3 : ℝ) * (D : ℝ) ^ (3 : ℕ)) / (4 * (m + 2 : ℝ) ^ (2 : ℕ))) (hterminal_drop : f (x (2 * m)) - f (x T) ≥ ((m + 2 : ℝ) / (3 * Real.sqrt (L3 : ℝ))) * Real.rpow g⋆[T] (3 / 2 : ℝ)) : g⋆[T] ≤ Real.rpow (((27 : ℝ) * Real.rpow (L3 : ℝ) (3 / 2 : ℝ) * (D : ℝ) ^ (3 : ℕ)) / (4 * (m + 2 : ℝ) ^ (3 : ℕ))) (2 / 3 : ℝ)

Text 4.2.19

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Under 0 < (L3 : ℝ), the comparison f xStar ≤ f (x (4 * m)), the gap bound at x_{3m}, and the descent lower bound from x_{3m} to x_{4m}, Text 4.2.19 first yields the intermediate estimate on the sampled minimum g⋆[m] = min_{1 ≤ k ≤ 4m} ‖∇ f (x k)‖, namely `g⋆[m] ≤ (8 L₃^(3/2) R₀^3 / (m² (3m + 1) (3m + 2)))^(2/3), where R₀ = ‖x₀ - xStar‖`.

open scoped Gradient MinGradientNormAlongIterates universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {f : E → ℝ} {L3 : NNReal} {x : ℕ → E} {x0 xStar : E} variable {m : ℕ} (hm : 1 ≤ m) local notation "g⋆[" m "]" => g[f; x; 1, 4 * m | by omega] theorem acceleratedCubicNewton_minGradientNorm_le_intermediate_bound (hL3 : 0 < (L3 : ℝ)) (hxStar4m : f xStar ≤ f (x (4 * m))) (hgap : f (x (3 * m)) - f xStar ≤ (8 * (L3 : ℝ) * ‖x0 - xStar‖ ^ (3 : ℕ)) / ((3 * m : ℝ) * ((3 * m : ℝ) + 1) * ((3 * m : ℝ) + 2))) (hdrop : f (x (3 * m)) - f (x (4 * m)) ≥ ((m : ℝ) / (3 * Real.sqrt (L3 : ℝ))) * Real.rpow g⋆[m] (3 / 2 : ℝ)) : g⋆[m] ≤ Real.rpow ((8 * Real.rpow (L3 : ℝ) (3 / 2 : ℝ) * ‖x0 - xStar‖ ^ (3 : ℕ)) / ((m : ℝ) ^ (2 : ℕ) * ((3 * m : ℝ) + 1) * ((3 * m : ℝ) + 2))) (2 / 3 : ℝ)

Text 4.2.20

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.20: for a nonnegative cubic regularization parameter, if the cubically regularized objective at x is at most f x₀, then x belongs to the initial sublevel set {y | f y ≤ f x₀}, hence ‖x - x₀‖ is bounded by any textbook radius D that is an attained maximum of the distances to x₀ on that sublevel set.

universe u variable {E : Type u} [NormedAddCommGroup E] theorem norm_sub_le_of_cubicallyRegularizedObjective_le_of_initialSublevelDistanceSet_isGreatest (f : E → ℝ) (x0 x : E) {δ : ℝ} (hδ : 0 ≤ δ) {D : ℝ} (hD : IsGreatest (initialSublevelDistanceSet f x0) D) (hx : cubicallyRegularizedObjective f δ x0 x ≤ f x0) : ‖x - x0‖ ≤ D

Text 4.2.21

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Text 4.2.21: if the auxiliary points of a restarting scheme satisfy ‖∇ f (y_k^*)‖ ≤ e^(-2k/3) L₃ D² √(1 + ε / (L₃ D²)) + ε / 2 for every k, then every index k above the logarithmic threshold (3 / 2) log (2 √(x² + x)), with x = L₃ D² / ε, satisfies ‖∇ f (y_k^*)‖ ≤ ε.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] theorem gradient_norm_le_target_of_restarting_auxiliary_bound (f : E → ℝ) (L3 : NNReal) (D ε : ℝ) (yAux : ℕ → E) (hε : 0 < ε) (hbound : ∀ k : ℕ, ‖∇ f (yAux k)‖ ≤ Real.exp (-(2 * (k : ℝ) / 3)) * (L3 : ℝ) * D ^ 2 * Real.sqrt (1 + ε / ((L3 : ℝ) * D ^ 2)) + ε / 2) (k : ℕ) (hk : (3 / 2 : ℝ) * Real.log (2 * Real.sqrt ((((L3 : ℝ) * D ^ 2 / ε) ^ 2) + (L3 : ℝ) * D ^ 2 / ε)) ≤ (k : ℝ)) : ‖∇ f (yAux k)‖ ≤ ε

Text 4.2.22

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The local quadratic-convergence region from Text 4.2.22, written in multiplication form so that the degenerate case L₃(f) = 0 does not force a division-based surface.

open scoped ConstrainedArgmin Gradient DegreeConditioning FunctionClasses universe u variable {E : Type u} variable [NormedAddCommGroup E] [NormedSpace ℝ E] def acceleratedCubicNewtonQuadraticConvergenceRegion (f : E → ℝ) [HasIteratedFDerivLipschitzConstantOfDegree 3 f] [HasUniformConvexityParameterOfDegree 3 f] (xStar : E) : Set E := {x | L[3](f) * ‖x - xStar‖ ≤ σ[3](f)} -- Proof sketch: unfold `acceleratedCubicNewtonQuadraticConvergenceRegion`.

Text 4.2.23

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The source-facing example ξ_{α,β} = α d₂ + β d₃, with d₂ and d₃ realized by the chapter owner powerDistance at the origin. The positive coefficients are carried by the project-standard owner NNRealˣ.

universe u
open scoped DegreeConditioning FunctionClasses
variable (E : Type u) [NormedAddCommGroup E]
def xi_alpha_beta (α β : NNRealˣ) : E → ℝ :=
  (α : ℝ) • powerDistance (2 : ℝ) (0 : E) + (β : ℝ) • powerDistance (3 : ℝ) (0 : E)

Text 4.2.24

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The entry-time bound from Text 4.2.24 is nonnegative by construction.

open scoped Gradient DegreeConditioning FunctionClasses StrongConvexSmooth universe u variable {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] variable {f : E → ℝ} [f ∈ 𝓕₂Lip] -- Semantic recall note: `lean_leansearch` did not surface a reusable owner for this natural-index -- bridge, so this file follows a larger additive-offset pattern from `Theorem_5_3_11` rather than -- the -- least-entry `max 0` pattern used in `Text_4_2_13`. theorem newtonQuadraticConvergenceEntryBound_nonneg (f : E → ℝ) [f ∈ 𝓕₂Lip] (x0 xStar : E) (C : ℝ) : 0 ≤ newtonQuadraticConvergenceEntryBound f x0 xStar C

4.3 — Optimal Second-Order Methods

Algorithm 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.3.1: the conceptual optimal cubic Newton method for an objective f, initialization point x₀, and parameter σ ∈ (0, 1) consists of a cubic Newton step map T_M with M = M_f / σ, a positive auxiliary sequence ρ_k, and the stagewise minimizing points v_k of the recursively generated quadratic estimating functions. The displayed sequences x_k, ℓ_k, A_k, a_{k+1}, y_k, and ψ_k are then derived recursively from these data, with a_{k+1} defined by the positive quadratic root solving a_{k+1}² = 2 (A_k + a_{k+1}) / (M ρ_k).

open scoped Gradient ConstrainedArgmin open LinearMap (BilinForm) open LinearMap.BilinForm open scoped BInducedNorm universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure OptimalCubicNewtonMethod (B : BilinForm ℝ E) (Mf : NNRealˣ) (f : PrimalSpace B → ℝ) [Fact B.toQuadraticMap.PosDef] (x0 : PrimalSpace B) (sigma : ℝ) where /-- The algorithmic parameter satisfies `σ ∈ (0, 1)`. -/ sigma_mem : sigma ∈ Set.Ioo (0 : ℝ) 1 /-- The cubic Newton step map `T_M` for `M = M_f / σ`. -/ step : CubicNewtonStep B f ((Mf : ℝ) / sigma) /-- The positive auxiliary parameters `ρ_k`. -/ rho : ℕ → ℝ /-- Each auxiliary parameter `ρ_k` is positive. -/ rho_pos (k : ℕ) : 0 < rho k /-- The stagewise minimizing points `v_k` of the recursively generated estimating functions. -/ v : ℕ → PrimalSpace B /-- Each `v_k` globally minimizes the corresponding recursively generated quadratic estimating function. -/ v_isMinOn (k : ℕ) : IsMinOn (optimalCubicNewtonEstimatingFunction f x0 ((Mf : ℝ) / sigma) step rho v k) Set.univ (v k)

Assumption 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Assumption 4.3.1: a sequence of test points generated by an iterative second-order scheme satisfies x_k ∈ x₀ + Lin{𝒢_f(x₀), …, 𝒢_f(x_{k-1})} for every k ≥ 0, where the case k = 0 is tautological and the usual textbook form is recovered by replacing k with k + 1. The set 𝒢_f(x) is the textbook second-order oracle-direction set at x, and the sequence is required to query points where the displayed gradient and Hessian are genuine second-order oracle data; on a C² objective this is exactly the textbook affine-span restriction.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] open scoped SecondOrderOracleDirections def IsSecondOrderSpanSequence (f : E → ℝ) (testPoints : ℕ → E) : Prop := HasSecondOrderOracleSequence f testPoints ∧ ∀ k : ℕ, testPoints k ∈ secondOrderOracleSpanSearchSpace f testPoints k

Corollary 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Corollary 4.3.1: if the iterates x_i, i = 0, ..., k, lie in the coordinate subspaces ℝ^{i,n} and the full sequence satisfies Assumption 4.3.1 for the hard-instance objective f_t, with k + 1 ≤ t ≤ n, then the next iterate x_{k+1} belongs to ℝ^{k+1,n}.

open scoped CoordinateSubspace SecondOrderOracleDirections
open scoped Gradient
variable {n k t : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem fk_spanSequence_next_iterate_mem_coordinateSubspace
    (hkt : k + 1 ≤ t) (htn : t ≤ n)
    {testPoints : ℕ → E}
    (hspan : IsSecondOrderSpanSequence (fk htn) testPoints)
    (htestPoints : ∀ i : Fin (k + 1), testPoints i ∈ ℝ^{i,n}) :
    testPoints (k + 1) ∈ ℝ^{k + 1,n}

Definition 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The textbook positive-witness form is equivalent to the canonical existential C22 surface, since any Hessian-Lipschitz witness can be enlarged to a positive one.

universe u
open scoped ConstrainedArgmin
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
namespace SetConstrainedMinimizationProblem
variable (problem : SetConstrainedMinimizationProblem E)
theorem exists_pos_mem_C22_iff :
    (∃ L3 : NNReal, 0 < L3 ∧ problem.objective ∈ C22[L3]) ↔
      ∃ L3 : NNReal, problem.objective ∈ C22[L3]

Lemma 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.3.1: if x ∈ ℝ^{i,n} with i < t, then for the hard-instance function f_t formalized by fk, the pair formed by the gradient and Hessian matrix at x belongs to ℝ^{i+1,n} × 𝕊^{i+1,n}.

open scoped BigOperators Gradient CoordinateSubspace CoordinateSymmetricMatrixSubspace
variable {n t i : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
local notation "e" => EuclideanSpace.basisFun (Fin n) ℝ
theorem fk_first_second_order_mem_next_coordinate_subspaces
    (htn : t ≤ n) {x : E} (hx : x ∈ ℝ^{i,n}) (hit : i < t) :
    (∇ (fk htn) x, ∇² (fk htn) x) ∈
      (ℝ^{i + 1,n}).prod 𝕊^{i + 1,n}

Proposition 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

The explicit vector x_* with coordinates x_*^(i) = (k - i + 1)_+.

open scoped BigOperators ConstrainedArgmin variable {n k : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def cubicLowerBoundMinimizer (n k : ℕ) : EuclideanSpace ℝ (Fin n) := (EuclideanSpace.equiv (Fin n) ℝ).symm fun i : Fin n ↦ ((k - (i : ℕ) : ℕ) : ℝ) -- Proof sketch: unfold `cubicLowerBoundMinimizer`; on the `i`-th zero-based coordinate the value -- is the truncated natural difference `k - i`, which is exactly `(k - i + 1)_+` in textbook -- one-based indexing.

Theorem 4.3.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.3.1: let the Hessian of the objective be Lipschitz continuous with constant L_f, and let a second-order method satisfy the textbook second-order information restriction and the guarantee min_{0 ≤ i ≤ k} f(x_i) - f(x^*) ≤ L_f ρ₀^3 / C_𝓜(k) for every starting point x₀ with ‖x₀ - x^*‖ ≤ ρ₀. Then, whenever k = 3m + 2 with m + 1 ≤ n / 4 (equivalently 4 * (m + 1) ≤ n), the strictly positive complexity quantity satisfies C_𝓜(k) ≤ 36 (k + 1)^{3.5}.

open scoped Gradient
open scoped CoordinateSubspace
open scoped ConstrainedArgmin
variable {n : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
theorem secondOrderMethod_complexityConstant_le_cubicHardInstance_bound
    (testPoints : (E → ℝ) → E → ℕ → E)
    (complexityConstant : ℕ → NNRealˣ)
    (htestPoints_zero :
      ∀ (f : E → ℝ) (x0 : E), testPoints f x0 0 = x0)
    (hspan :
      ∀ (f : E → ℝ) (_ : ContDiff ℝ 2 f) (x0 : E),
        IsSecondOrderSpanSequence f (testPoints f x0))
    (hguarantee :
      ∀ (f : E → ℝ) (Lf : NNReal) (_ : f ∈ C22[Lf])
        (xStar x0 : E) (rho0 : ℝ) (k : ℕ),
        IsMinOn f Set.univ xStar →
          ‖x0 - xStar‖ ≤ rho0 →
            bestFunctionValueUpTo (fun i ↦ f (testPoints f x0 i)) k - f xStar ≤
              (Lf : ℝ) * rho0 ^ 3 / (complexityConstant k : ℝ))
    {k m : ℕ} (hk : k = 3 * m + 2) (hm : m + 1 ≤ n / 4) :
    (complexityConstant k : ℝ) ≤
      36 * ((k + 1 : ℝ) ^ 3 * Real.sqrt (k + 1))

Definition 4.3.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.3.2: for k ≤ n, fk hkn extends the textbook hard-instance objective f_k : ℝ^n → ℝ; when 0 < k, it is given by the cubic sum of adjacent-coordinate differences over the first k - 1 coordinates, the cubic tail sum from coordinate k onward, and the linear term -x^{(1)}, while the degenerate case k = 0 keeps only the cubic tail term so the owner is defined for all k ≤ n.

open scoped BigOperators variable {n k : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) def fk (hkn : k ≤ n) : E → ℝ := fun x ↦ if hk : 0 < k then (1 / 3 : ℝ) * ((∑ i : Fin (k - 1), |fkPrefixCoords hk hkn x (Fin.castSucc i) - fkPrefixCoords hk hkn x i.succ| ^ (3 : ℕ)) + |fkPrefixCoords hk hkn x (Fin.last (k - 1))| ^ (3 : ℕ)) - fkPrefixCoords hk hkn x 0 + (1 / 3 : ℝ) * ∑ i : Fin (n - k), |fkTailCoords x i| ^ (3 : ℕ) else (1 / 3 : ℝ) * ∑ i : Fin n, |x i| ^ (3 : ℕ)

Lemma 4.3.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.3.2: if x lies in the coordinate subspace ℝ^{k,n}, then enlarging the hard-instance index from k to k + p does not change the value of the textbook function f_k.

variable {n k p : ℕ}
local notation "E" => EuclideanSpace ℝ (Fin n)
open scoped CoordinateSubspace

-- Proof sketch: unfold `fk` on both sides. If `x ∈ coordinateSubspace k n`,
-- then `mem_coordinateSubspace_iff` says that every coordinate with index at least `k` vanishes,
-- so the extra adjacent-difference terms and tail terms introduced when passing from `f_k` to
-- `f_{k+p}` are all zero, while the shared terms and the linear term `-x^{(1)}` are unchanged.
theorem fk_add_eq_of_mem_coordinateSubspace
    (hkpn : k + p ≤ n) {x : E}
    (hx : x ∈ ℝ^{k,n}) :
    fk hkpn x =
      fk (le_trans (Nat.le_add_right k p) hkpn) x

Proposition 4.3.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.3.2: for k ≤ n, the hard-instance objective fk hkn has globally (8 * √2)-Lipschitz Hessian, recorded on the chapter's canonical C22[...] surface. The degenerate cases k = 0, 1 are included because the same owner bound still applies there.

open scoped Gradient open scoped BigOperators variable {n k : ℕ} local notation "E" => EuclideanSpace ℝ (Fin n) theorem fk_mem_C22 (hkn : k ≤ n) : fk hkn ∈ C22[⟨8 * Real.sqrt 2, by positivity⟩]

Theorem 4.3.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.3.2: if f is convex, the auxiliary parameters of Algorithm 4.3.1 satisfy the residual sandwich r_M(y_k) ≤ ρ_k ≤ γ r_M(y_k) from Lemma 4.3.5, and the estimating functions are majorized at a comparison point xStar by A_k f(xStar) + (1 / 2) ‖x₀ - xStar‖^2, then Algorithm 4.3.1 with M = M_f / σ satisfies, for every k ≥ 1, f(x_k) - f(xStar) ≤ (2 γ^(3/2) M_f ‖x₀ - xStar‖^3 / (σ * √(1 - σ^2))) * (3 / (2k + 1))^(7/2), where the norm is the primal norm induced by B.

open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped BInducedNorm CubicNewtonStepNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable {B : BilinForm ℝ E} {Mf : NNRealˣ} {f : PrimalSpace B → ℝ}
  [Fact B.toQuadraticMap.PosDef]
  {x0 xStar : PrimalSpace B} {sigma γ : ℝ}
  (method : OptimalCubicNewtonMethod B Mf f x0 sigma)
namespace OptimalCubicNewtonMethod
theorem gap_le_inverse_seven_halves_rate
    (hf_conv : ConvexOn ℝ Set.univ f)
    (hpsi_upper : ∀ k : ℕ,
      let Δ := x0 - xStar
      method.psi k xStar ≤
        method.A k * f xStar + (1 / 2 : ℝ) * ‖Δ‖[B] ^ (2 : ℕ))
    (hresidual_lower : ∀ k : ℕ, r[(method.step)] (method.y k) ≤ method.rho k)
    (hresidual_upper : ∀ k : ℕ, method.rho k ≤ γ * r[(method.step)] (method.y k))
    {k : ℕ} (hk : 1 ≤ k) :
    let Δ := x0 - xStar
    f (method k) - f xStar ≤
      (((2 : ℝ) * Real.rpow γ (3 / 2 : ℝ) * (Mf : ℝ)) *
          ‖Δ‖[B] ^ (3 : ℕ) /
        (sigma * Real.sqrt (1 - sigma ^ (2 : ℕ)))) *
        Real.rpow ((3 : ℝ) / (2 * k + 1 : ℝ)) (7 / 2 : ℝ)

Definition 4.3.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.3.3 lies in the finite-dimensional linear-algebra / symmetric-matrix subspace domain. Sampled owner-style declarations in this domain: * coordinateSubspace and mem_coordinateSubspace_iff in Text_2_13, the Chapter 2 owner/view for coordinatewise vanishing subspaces in ℝⁿ; * mathlib selfAdjointMatricesSubmodule, the canonical submodule owner for symmetric real matrices via the identity bilinear form; * mathlib Submodule.pi and Submodule.comap, the canonical owners for coordinatewise support conditions on function spaces; * mathlib Matrix.ofLinearEquiv, the canonical bridge between matrices and curried entrywise functions. Best owner abstractions: * source-facing: coordinateSymmetricMatrixSubspace k n, the textbook subspace 𝕊^{k,n}; * core/canonical: the intersection of the symmetric-matrix owner selfAdjointMatricesSubmodule (1 : Matrix (Fin n) (Fin n) ℝ) with the coordinate-support submodule defined via Submodule.comap/Submodule.pi; * bridge/view: mem_coordinateSymmetricMatrixSubspace_iff. Primitive data: * symmetry of the matrix; * the allowed support pattern: diagonal entries are free, and off-diagonal entries are free only inside the leading k × k block. Derived API: * the source-facing owner coordinateSymmetricMatrixSubspace; * its notation 𝕊^{k,n}; * the textbook membership criterion mem_coordinateSymmetricMatrixSubspace_iff. This file therefore keeps the textbook owner 𝕊^{k,n} but deletes the hand-written additive closure proofs in favor of the canonical symmetric-matrix owner and a private support submodule.

variable {n : ℕ}
local notation "Mat" => Matrix (Fin n) (Fin n) ℝ
#check coordinateSubspace

Lemma 4.3.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.3.3 (1): the pairing of the gradient at the cubic Newton point with the displacement x - T_M(x) is bounded below by the reciprocal-residual dual-gradient term plus the cubic correction ((M² - M_f²) / (4M)) r_M(x)^3.

open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped BInducedNorm CubicNewtonStepNotation Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable {B : BilinForm ℝ E} {Mf : NNReal} {f : PrimalSpace B → ℝ}
variable [Fact B.toQuadraticMap.PosDef]
lemma cubicNewtonStep_dualPairing_lower_bound
    (hf :
      letI : NormedAddCommGroup (PrimalSpace B) :=
        LinearMap.BilinForm.instNormedAddCommGroupPrimalSpaceOfFactPosDefRealToQuadraticMap B
      letI : NormedSpace ℝ (PrimalSpace B) :=
        LinearMap.BilinForm.instNormedSpaceRealPrimalSpace B
      (f : PrimalSpace B → ℝ) ∈ C22[(Mf : NNReal)])
    {M : ℝ} (step : CubicNewtonStep B f M)
    (hM : 0 < M)
    (x : PrimalSpace B) :
    let g := fderiv ℝ f (step x)
    g (x - step x) ≥
      (1 / (M * r[step](x))) *
          ‖g‖[B,*] ^ (2 : ℕ) +
        ((M ^ (2 : ℕ) - (Mf : ℝ) ^ (2 : ℕ)) / (4 * M)) *
          (r[step](x)) ^ (3 : ℕ)

Proposition 4.3.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.3.3: if f is C² at x and B is symmetric, then the cubic Newton point T_M(x) satisfies the source first-order optimality condition (4.3.12). This is the Chapter 4.3 C² bridge obtained from firstOrderOptimalityCondition_toDual_of_isSelfAdjoint via hessian_isSelfAdjoint_of_contDiffAt.

open LinearMap (BilinForm) open LinearMap.BilinForm open scoped Gradient CubicNewtonStepNotation LinearMap.BilinForm.BInducedNorm universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E] [CompleteSpace E] namespace CubicNewtonStep variable {B : BilinForm ℝ E} [Fact B.toQuadraticMap.PosDef] {f : E → ℝ} {M : ℝ} theorem firstOrderOptimalityCondition_toDual (step : CubicNewtonStep B f M) (x : E) (hSymm : B.IsSymm) (hf : ContDiffAt ℝ 2 f x) : InnerProductSpace.toDual ℝ E (∇ f x + hessian f x (step x - x)) + ((M / 2 : ℝ) * r[step](x)) • LinearMap.toContinuousLinearMap (B (step x - x)) = 0

Definition 4.3.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.3.4 in owner form: the positive-definite quadratic data of B induce the canonical seminorm x ↦ ⟪Bx, x⟫^(1/2).

open Module LinearMap universe u namespace LinearMap.BilinForm variable {E : Type u} [AddCommGroup E] [Module ℝ E] def primalSeminorm (B : LinearMap.BilinForm ℝ E) (hPos : B.toQuadraticMap.PosDef) : Seminorm ℝ E

Lemma 4.3.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.3.4: if f ∈ C22[Mf] is convex and the algorithmic parameters satisfy r_M(y_k) ≤ ρ_k for every k, then A_k f(x_k) + B_k is bounded above by ψ_k(v_k) = ψ_k^* = min_x ψ_k(x), where B_k is the accumulated cubic correction term ((1 - σ^2) / 4) M * ∑_{i=0}^{k-1} A_{i+1} r_M(y_i)^3.

open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped BInducedNorm CubicNewtonStepNotation Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable {B : BilinForm ℝ E} {Mf : NNRealˣ} {f : PrimalSpace B → ℝ}
  [Fact B.toQuadraticMap.PosDef]
  {x0 : PrimalSpace B} {sigma : ℝ}
  (method : OptimalCubicNewtonMethod B Mf f x0 sigma)
lemma optimalCubicNewtonMethod_accumulated_value_le_estimating_minimum
    (hf : primalSpaceMemC22 (B := B) (Mf := (Mf : NNReal)) f)
    (hf_conv : ConvexOn ℝ Set.univ f)
    (hresidual : ∀ k : ℕ, r[(method.step)] (method.y k) ≤ method.rho k)
    (k : ℕ) :
    method.A k * f (method k) +
        method.estimatingLowerBoundCorrection k ≤
      method.psi k (method.v k)

Proposition 4.3.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.3.4, scalar part: the prefactor in Theorem 4.3.2 is minimized on (0, 1) at σ = 1 / √2.

open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped BInducedNorm CubicNewtonStepNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
theorem inverse_seven_halves_prefactor_isMinOn :
    IsMinOn
      (fun σ : ℝ ↦
        (2 : ℝ) / (σ * Real.sqrt (1 - σ ^ (2 : ℕ))))
      (Set.Ioo (0 : ℝ) 1)
      ((1 : ℝ) / Real.sqrt 2)

Definition 4.3.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.3.5: on the intrinsic carrier PrimalSpace B, the textbook condition that the Hessian of f is globally M_f-Lipschitz in the B-induced norm is exactly the chapter owner HasLipschitzContinuousHessian Mf f, written on theorem surfaces as f ∈ C22[Mf].

universe u open LinearMap (BilinForm) open LinearMap.BilinForm open scoped BInducedNorm variable {E : Type u} [AddCommGroup E] [Module ℝ E] variable {B : BilinForm ℝ E} [Fact B.toQuadraticMap.PosDef] variable {Mf : NNReal} {f : PrimalSpace B → ℝ} recall HasLipschitzContinuousHessian

Lemma 4.3.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.3.5: if f ∈ C22[Mf] is convex, xStar globally minimizes f, γ ≥ 1, the auxiliary parameters of Algorithm 4.3.1 satisfy r_M(y_k) ≤ ρ_k ≤ γ r_M(y_k) for every k, the estimating functions are majorized at the solution point xStar by A_k f(xStar) + (1 / 2) ‖x₀ - xStar‖², and the initial B-distance to the solution is positive, then every index k ≥ 1 satisfies the denominator-free form of the textbook accumulated-weight lower bound (1 / 4) (1 / γ)^(3/2) * sqrt (1 - σ^2) * ((2k + 1) / 3)^(7/2) ≤ M ‖x₀ - xStar‖ A_k, with M = M_f / σ and the norm induced by B. Under 0 < ‖x₀ - xStar‖[B], this is equivalent to the source bound obtained by dividing through by ‖x₀ - xStar‖[B].

open LinearMap (BilinForm)
open LinearMap.BilinForm
open scoped BInducedNorm CubicNewtonStepNotation
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
variable {B : BilinForm ℝ E} {Mf : NNRealˣ} {f : PrimalSpace B → ℝ}
  [Fact B.toQuadraticMap.PosDef]
  {x0 : PrimalSpace B} {sigma γ : ℝ}
  (method : OptimalCubicNewtonMethod B Mf f x0 sigma) {xStar : PrimalSpace B}
namespace OptimalCubicNewtonMethod
variable [CompleteSpace E]
theorem accumulated_weight_lower_bound
    (hγ : 1 ≤ γ)
    (hf : (f : PrimalSpace B → ℝ) ∈ C22[(Mf : NNReal)])
    (hf_conv : ConvexOn ℝ Set.univ f)
    (hxStar : IsMinOn f Set.univ xStar)
    (hΔ : 0 < ‖x0 - xStar‖[B])
    (hpsi_upper : ∀ k : ℕ,
      let Δ := x0 - xStar
      method.psi k xStar ≤
        method.A k * f xStar + (1 / 2 : ℝ) * ‖Δ‖[B] ^ (2 : ℕ))
    (hresidual_lower : ∀ k : ℕ, r[(method.step)] (method.y k) ≤ method.rho k)
    (hresidual_upper : ∀ k : ℕ, method.rho k ≤ γ * r[(method.step)] (method.y k))
    {k : ℕ} (hk : 1 ≤ k) :
    let Δ := x0 - xStar
    let M : ℝ := (Mf : ℝ) / sigma
    ((1 / 4 : ℝ) * Real.rpow (1 / γ) (3 / 2 : ℝ) * Real.sqrt (1 - sigma ^ (2 : ℕ))) *
        Real.rpow ((2 * k + 1 : ℝ) / 3) (7 / 2 : ℝ) ≤
      M * ‖Δ‖[B] * method.A k

Definition 4.3.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.3.6: a cubic Newton step for the B-induced geometry is a map T_M : E → E such that, for every base point x, the value T_M x globally minimizes the B-dependent cubic Newton model centered at x.

open LinearMap (BilinForm) open LinearMap.BilinForm open scoped Gradient ConstrainedArgmin BInducedNorm universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] structure CubicNewtonStep (B : BilinForm ℝ E) [Fact B.toQuadraticMap.PosDef] (f : E → ℝ) (M : ℝ) where /-- The chosen cubic Newton step map `T_M`. -/ toFun : E → E /-- For each base point `x`, the step `T_M x` globally minimizes the `B`-dependent cubic Newton model centered at `x`. -/ isMinOn (x : E) : IsMinOn (cubicNewtonModel B f M x) Set.univ (toFun x)

4.4 — The Modified Gauss–Newton Method

Algorithm 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Algorithm 4.4.1: a modified Gauss--Newton method for a smooth nonlinear equation problem problem : ℝⁿ → ℝᵐ, a sharp merit function φ, constants L₀ ∈ (0, L] and L, and an initial point x₀ consists of a parameter sequence M_k ∈ [L₀, 2L] and a chosen modified Gauss--Newton step V_{M_k} at each iteration such that f (V_{M_k}(x_k)) ≤ f[V_{M_k}](x_k), where the iterate sequence is the canonical recursion x_{k+1} = V_{M_k}(x_k) with x₀ = x0 and f = meritFunctionReformulation problem φ.

open scoped Manifold
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
structure ModifiedGaussNewtonMethod
    (problem : SmoothMap)
    (φ : E₂ → ℝ) [IsSharpMeritFunction φ]
    (L0 L : ℝ) (x0 : E₁) where
  /-- The chosen regularization parameters `M₀, M₁, M₂, ...`. -/
  regularization : ℕ → ℝ
  /-- For each iteration `k`, `step k` is the chosen modified Gauss--Newton step with
  regularization parameter `M_k`. -/
  step
      (k : ℕ) :
      ModifiedGaussNewtonStep
        (ψ[problem; φ; fun x ↦ fderiv ℝ problem x])
        Set.univ (regularization k)
  /-- The parameter `L₀` lies in the interval `(0, L]`. -/
  L0_mem_Ioc : L0 ∈ Set.Ioc (0 : ℝ) L
  /-- Every chosen regularization parameter `M_k` belongs to the admissible interval
  `[L₀, 2L]`. -/
  regularization_mem_Icc (k : ℕ) : regularization k ∈ Set.Icc L0 (2 * L)
  /-- The accepted modified Gauss--Newton trial point satisfies
  `f (V_{M_k}(x_k)) ≤ f[V_{M_k}](x_k)` at every iteration. -/
  step_value_le_modelValue (k : ℕ) :
    meritFunctionReformulation problem φ
        ((step k).point (modifiedGaussNewtonIterates x0 regularization step k)) ≤
      (f[(step k)]) (modifiedGaussNewtonIterates x0 regularization step k)

Assumption 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Assumption 4.4.1: a real-valued function on a subset 𝓕 of a real normed space has a Lipschitz-continuous derivative with constant L when it is differentiable on the uniquely differentiable feasible set 𝓕 and its canonical within-derivative map x ↦ fderivWithin ℝ f 𝓕 x is L-Lipschitz on 𝓕. On open feasible sets this agrees with the ambient derivative formulation.

universe u class HasLipschitzDerivativeOnWith (L : NNReal) {E : Type u} [NormedAddCommGroup E] [NormedSpace ℝ E] (𝓕 : Set E) (f : E → ℝ) : Prop where /-- The function is differentiable on the feasible set. -/ differentiableOn : DifferentiableOn ℝ f 𝓕 /-- The feasible set is uniquely differentiable, so the within derivative is intrinsic. -/ uniqueDiffOn : UniqueDiffOn ℝ 𝓕 /-- The derivative map is `L`-Lipschitz on the feasible set. -/ lipschitz : LipschitzOnWith L (fun x ↦ fderivWithin ℝ f 𝓕 x) 𝓕

Corollary 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Corollary 4.4.1: if xStar globally minimizes f, if the sublevel set 𝓛[f]((f x)) = {y | f y ≤ f x} is contained in 𝓕, and if step is a whole-space modified Gauss--Newton minimizer at regularization M, then the textbook value f[step](x) satisfies f[step](x) ≤ f^* + ((L + M) / 2) ‖x - xStar‖², where f^* = f(xStar). In the intended application, f is the merit-function reformulation from Definition 4.4.10 and xStar is an exact solution.

open SetConstrainedMinimizationProblem open scoped LevelSetNotation open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation universe u variable {E : Type u} [NormedAddCommGroup E] variable {f : E → ℝ} {ψ : E → E → ℝ} variable {𝓕 : Set E} {L M : ℝ} theorem modifiedGaussNewton_modelValue_le_solutionValue_add_quadratic_error (step : ModifiedGaussNewtonStep ψ Set.univ M) (x xStar : E) (hxStar : IsMinOn f Set.univ xStar) (hupper : ∀ ⦃y : E⦄, y ∈ 𝓕 → ψ x y ≤ f y + (L / 2 : ℝ) * ‖y - x‖ ^ (2 : ℕ)) (hlevel : 𝓛[f]((f x)) ⊆ 𝓕) : f[step](x) ≤ f xStar + ((L + M) / 2 : ℝ) * ‖x - xStar‖ ^ (2 : ℕ)

Definition 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.1: a merit function on a residual type with distinguished origin 0 is a nonnegative scalarization that vanishes exactly at the origin, so it can be used in merit reformulations x ↦ φ (F x).

universe u
variable {R : Type u} [Zero R]
variable {m : ℕ}
class IsMeritFunction (φ : R → ℝ) : Prop where
  /-- A merit function is everywhere nonnegative. -/
  nonneg (u : R) : 0 ≤ φ u
  /-- A merit function vanishes exactly at the origin. -/
  eq_zero_iff (u : R) : φ u = 0 ↔ u = 0

Lemma 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.1: if 𝓕 is convex and x and y belong to 𝓕, then the difference between the merit reformulation f(y) = φ(F y) and the modified Gauss--Newton local model ψ(x; y) = φ(F(x) + F'(x)(y - x)) is bounded by ((L : ℝ) / 2) * ‖y - x‖².

open scoped Manifold open scoped ModifiedGaussNewtonLocalModelNotation universe u v variable {E : Type u} {F : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup F] [NormedSpace ℝ F] theorem abs_meritFunctionReformulation_sub_modifiedGaussNewtonLocalModel_le (problem : C^⊤⟮𝓘(ℝ, E), E; 𝓘(ℝ, F), F⟯) (φ : F → ℝ) (hφ : LipschitzWith 1 φ) {𝓕 : Set E} {L : NNReal} (h𝓕 : Convex ℝ 𝓕) (h_jacobian_lipschitz : LipschitzOnWith L (fderiv ℝ problem) 𝓕) {x y : E} (hx : x ∈ 𝓕) (hy : y ∈ 𝓕) :

Proposition 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.1: the minimal singular value of a continuous linear map gives the lower bound σ_min(A) * ‖x‖ ≤ ‖A x‖ for every vector x, equivalently ‖A x‖ ≥ σ_min(A) * ‖x‖.

open scoped MinimalSingularValue universe u v w variable {𝕜 : Type w} {E₁ : Type u} {E₂ : Type v} [NormedField 𝕜] [NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁] [NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂] namespace ContinuousLinearMap theorem minimalSingularValue_mul_norm_le (A : E₁ →L[𝕜] E₂) (x : E₁) : σ_min(A) * ‖x‖ ≤ ‖A x‖

Theorem 4.4.1

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.4.1 (1): the residual-square tail starting at x_k is summable, and the merit gap at iterate x_k dominates its weighted sum (L₀ / 2) ∑_{i=k}^∞ r_{Mᵢ}(xᵢ)^2.

open scoped BigOperators LocalModelNotation Manifold
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonLocalDecreaseNotation
open scoped ModifiedGaussNewtonQuadraticChiNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable
    (problem : SmoothMap)
    (φ : E₂ → ℝ) [IsSharpMeritFunction φ]
    (L0 L : ℝ) (x0 : E₁)
local notation "f" => meritFunctionReformulation problem φ
local notation "ψ" => ψ[problem; φ; (fderiv ℝ problem)]
namespace ModifiedGaussNewtonMethod

-- Proof sketch: sum the one-step decrease inequalities
-- `f(x_i) - f(x_{i+1}) ≥ (M_i / 2) r_{M_i}(x_i)^2`, first derived once from
-- `method.step_value_le_modelValue`, `method.step_modelValue_le_merit`, and Lemma 4.4.2, along
-- the tail starting at
-- `k`, telescope the partial sums, and bound the remaining iterate values below by `fStar` via
-- `hf_lower`. Since the residual-square terms are nonnegative, the bounded partial sums give both
-- summability of the tail and the asserted `tsum` bound.
theorem gap_ge_residualSqTail
    (method : ModifiedGaussNewtonMethod problem φ L0 L x0)
    {fStar : ℝ}
    (hf_lower : ∀ z : E₁, fStar ≤ f z)
    (k : ℕ) :
    Summable (fun i ↦ (r[(method.step (k + i))] (method (k + i))) ^ (2 : ℕ)) ∧
      f (method k) - fStar ≥
        (L0 / 2 : ℝ) *
          ∑' i, (r[(method.step (k + i))] (method (k + i))) ^ (2 : ℕ)

Assumption 4.4.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Assumption 4.4.2: a feasible set 𝓕 is sufficiently large with respect to x₀ for the objective f when x₀ ∈ interior 𝓕 and the canonical sublevel set 𝓛[f]((f x₀)) is contained in 𝓕.

universe u v open Set open scoped LevelSetNotation def IsSufficientlyLargeFeasibleSetAt {E : Type u} [TopologicalSpace E] {α : Type v} [Preorder α] (f : E → α) (𝓕 : Set E) (x0 : E) : Prop := x0 ∈ interior 𝓕 ∧ 𝓛[f]((f x0)) ⊆ 𝓕

Corollary 4.4.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Corollary 4.4.2 (1): along a modified Gauss--Newton method, the consecutive differences ‖x_k - x_{k+1}‖ converge to 0.

open Filter
open scoped LevelSetNotation Manifold ModifiedGaussNewtonLocalDecreaseNotation Topology
open scoped ModifiedGaussNewtonQuadraticChiNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable {problem : SmoothMap}
variable {φ : E₂ → ℝ} [IsSharpMeritFunction φ]
variable {L0 L : ℝ} {x0 : E₁}
local notation "f" => meritFunctionReformulation problem φ
local notation "𝓛0" => (𝓛[f]((f x0)) : Set E₁)
namespace ModifiedGaussNewtonMethod
theorem stepDifferences_tendsto_zero
    (method : ModifiedGaussNewtonMethod problem φ L0 L x0) :
    Tendsto (fun k ↦ ‖method k - method (k + 1)‖) atTop (𝓝 0)

Definition 4.4.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.2: a Gauss--Newton search direction at x is a feasible step h with x + h ∈ D x whose step-space local-model value ψ[F; φ; J](x; x + h) is minimal among all feasible steps for the auxiliary Gauss--Newton subproblem.

open scoped ConstrainedArgmin Gradient ModifiedGaussNewtonLocalModelNotation open ContinuousLinearMap PiLp universe u v variable {E₁ : Type u} {E₂ : Type v} variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂] def IsGaussNewtonSearchDirectionAt (φ : E₂ → ℝ) (F : E₁ → E₂) (J : E₁ → E₁ →L[ℝ] E₂) (D : E₁ → Set E₁) (x h : E₁) : Prop := h ∈ argmin[gaussNewtonFeasibleDirections D x] (fun h' ↦ ψ[F; φ; J](x; (x + h')))

Lemma 4.4.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.2: if the local model slice ψ(x; ·) is convex on the whole space, then for a modified Gauss--Newton step on the whole space the model improvement δ_M(x) attached to the diagonal objective f(x) = ψ(x; x) satisfies δ_M(x) ≥ (M / 2) r_M(x)^2.

universe u variable {E₁ : Type u} [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation open ModifiedGaussNewtonStep -- Proof sketch: use convexity of `ψ x` to make the quadratic-regularized local model -- `quadraticallyRegularizedObjective (ψ x) M x` smaller at its minimizer `step x` than at every -- segment point `x + t (step x - x)` with `0 ≤ t < 1`. Convexity of `ψ x` bounds the local model -- at those segment points by a convex combination of `ψ x x` and `ψ x (step x)`, which yields -- `δ_M(x) ≥ t (M / 2) r_M(x)^2` for every `t < 1`; then let `t` approach `1`. theorem modifiedGaussNewton_modelGap_ge_half_mul_residual_sq {ψ : E₁ → E₁ → ℝ} {M : ℝ} (step : ModifiedGaussNewtonStep ψ Set.univ M) (x : E₁) (hconv : ConvexOn ℝ Set.univ (ψ x)) : δ[step; fun z ↦ ψ z z](x) ≥ (M / 2 : ℝ) * (r[step](x)) ^ (2 : ℕ)

Proposition 4.4.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.2: for an invertible continuous linear operator, the minimal singular value equals the reciprocal operator norm of the inverse.

open scoped MinimalSingularValue universe u v w variable {𝕜 : Type w} {E₁ : Type u} {E₂ : Type v} [NontriviallyNormedField 𝕜] [NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁] [NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂] namespace ContinuousLinearEquiv theorem minimalSingularValue_eq_inv_norm_symm (A : E₁ ≃L[𝕜] E₂) : σ_min(A) = 1 / ‖A.symm‖

Theorem 4.4.2

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.4.2: let x* be a nondegenerate exact solution with x* ∈ 𝓛[f]((f x₀)) and x* ∈ solutionSet problem, let γφ be a sharpness witness from Definition 4.4.9, assume the current iterate x_k lies in 𝓛[f]((f x₀)), and assume the same displayed constant L is a Jacobian-Lipschitz constant for problem on a convex feasible set 𝓕 satisfying Assumption 4.4.2 for the initial merit sublevel set 𝓛[f]((f x₀)). If ‖x_k - x*‖ ≤ (2 / L) * (σ γφ / (3 + 5 γφ)), then the next iterate stays in 𝓛[f]((f x₀)) and satisfies the explicit quadratic estimate in (4.4.20). The final comparison of that bound with ‖x_k - x*‖ is recorded separately below.

open SmoothNonlinearEquationProblem
open scoped InnerProduct LevelSetNotation Manifold MinimalSingularValue
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁]
variable [CompleteSpace E₁]
variable [NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂]
variable [CompleteSpace E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable {problem : SmoothMap}
variable {φ : E₂ → ℝ} [IsSharpMeritFunction φ]
variable {L0 : ℝ} {L : NNReal} {γφ : ℝ} {x0 xStar : E₁}
local notation "f" => meritFunctionReformulation problem φ
local notation "𝓛0" => (𝓛[f]((f x0)) : Set E₁)
theorem local_contraction_near_nondegenerate_solution
    (method : ModifiedGaussNewtonMethod problem φ L0 (L : ℝ) x0)
    {𝓕 : Set E₁}
    {k : ℕ}
    (h𝓕 : Convex ℝ 𝓕)
    (hxStar_level : xStar ∈ 𝓛0)
    (hxStar : xStar ∈ solutionSet problem)
    (hk_level : method k ∈ 𝓛0)
    (hlarge : IsSufficientlyLargeFeasibleSetAt f 𝓕 x0)
    (hJacobianLipschitz : LipschitzOnWith L (fderiv ℝ problem) 𝓕)
    (hσ_pos : 0 < σ_min(fderiv ℝ problem xStar))
    (hγφ_mem : γφ ∈ Set.Ioc (0 : ℝ) 1)
    (hγφ_lower : ∀ u : E₂, γφ * ‖u‖ ≤ φ u)
    (hclose :
      ‖method k - xStar‖ ≤
        (2 / (L : ℝ)) * (σ_min(fderiv ℝ problem xStar) * γφ / (3 + 5 * γφ))) :
    method (k + 1) ∈ 𝓛0 ∧
      ‖method (k + 1) - xStar‖ ≤
        (3 * (1 + γφ) * (L : ℝ) * ‖method k - xStar‖ ^ (2 : ℕ)) /
          (2 * γφ * (σ_min(fderiv ℝ problem xStar) - (L : ℝ) * ‖method k - xStar‖))

Assumption 4.4.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Assumption 4.4.3: for a smooth nonlinear equation problem problem, the Jacobian operators problem'(x) have a uniform dual nondegeneracy on the initial merit sublevel set 𝓛[meritFunctionReformulation problem φ]((meritFunctionReformulation problem φ x₀)), meaning that a single constant σ > 0 satisfies σ ≤ σ_min(problem'(x)*) for every x in that set.

universe u v open scoped InnerProduct LevelSetNotation Manifold MinimalSingularValue variable {E : Type u} {F : Type v} variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F] local notation "SmoothMap" => C^⊤⟮𝓘(ℝ, E), E; 𝓘(ℝ, F), F⟯ def HasUniformDualNondegeneracyOnInitialSublevelSet (problem : SmoothMap) (φ : F → ℝ) (x0 : E) (σ : ℝ) : Prop := let f := meritFunctionReformulation problem φ 0 < σ ∧ ∀ ⦃x : E⦄, x ∈ (𝓛[f]((f x0)) : Set E) → σ ≤ σ_min((fderiv ℝ problem x)†)

Definition 4.4.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.3: for a linear operator A : E₁ → E₂, the adjoint operator on dual spaces is exactly the canonical dual map A.dualMap : E₂⋆ → E₁⋆.

open Module universe u v w variable {R : Type u} {E₁ : Type v} {E₂ : Type w} variable [CommSemiring R] [AddCommMonoid E₁] [Module R E₁] variable [AddCommMonoid E₂] [Module R E₂] recall LinearMap.dualMap (A : E₁ →ₗ[R] E₂) : Dual R E₂ →ₗ[R] Dual R E₁

Lemma 4.4.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.3: for a smooth nonlinear equation problem problem, a sharp merit function φ, and a modified Gauss--Newton step with positive regularization parameter M, the model gap δ_M(x) is bounded below by M r² χ(Δ_r(x) / (M r²)) for every x and every radius r.

open scoped LocalModelNotation Manifold
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
open ModifiedGaussNewtonStep
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable (problem : SmoothMap) (φ : E₂ → ℝ) [IsSharpMeritFunction φ]
local notation "f" => meritFunctionReformulation problem φ
local notation "ψ" => ψ[problem; φ; (fderiv ℝ problem)]
open scoped ModifiedGaussNewtonQuadraticChiNotation

-- Proof sketch: unfold `modifiedGaussNewtonQuadraticChi` and use the branch condition `t < 1`
-- to select the quadratic branch of the `if`.
open scoped ModifiedGaussNewtonLocalDecreaseNotation
theorem modifiedGaussNewton_modelGap_ge_localModelDecrease_chi
    (M : ℝ)
    (hM : 0 < M)
    (step :
      ModifiedGaussNewtonStep
        ψ
        Set.univ M)
    (x : E₁) (r : NNReal) :
    δ[step; f](x) ≥
      M * (r : ℝ) ^ (2 : ℕ) *
        χ (Δ[problem; φ; r](x) /
          (M * (r : ℝ) ^ (2 : ℕ)))

Proposition 4.4.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.3: the minimal singular value is supermultiplicative under composition, so σ_min(A₁.comp A₂) is at least σ_min(A₁) * σ_min(A₂).

open scoped MinimalSingularValue universe u₀ u₁ u₂ u₃ variable {𝕜 : Type u₃} {E₀ : Type u₀} {E₁ : Type u₁} {E₂ : Type u₂} [NormedField 𝕜] [NormedAddCommGroup E₀] [NormedSpace 𝕜 E₀] [NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁] [NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂] -- Proof sketch: apply Proposition 4.4.1 first to `A₂ x`, obtaining -- `‖A₁ (A₂ x)‖ ≥ σ_min(A₁) * ‖A₂ x‖`, and then again to `A₂` to bound -- `‖A₂ x‖` from below by `σ_min(A₂) * ‖x‖`. Dividing by `‖x‖` for each nonzero `x` gives the -- lower bound for `σ_min(A₁.comp A₂)`. namespace ContinuousLinearMap theorem minimalSingularValue_comp_ge_mul (A₁ : E₁ →L[𝕜] E₂) (A₂ : E₀ →L[𝕜] E₁) : σ_min(A₁.comp A₂) ≥ σ_min(A₁) * σ_min(A₂)

Theorem 4.4.3

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.4.3 (1): under Assumptions 4.4.1, 4.4.2, and 4.4.3, if a modified Gauss--Newton iterate satisfies f(x_k) ≥ (σ² / (2L)) γ_φ², then the next merit value decreases by at least (σ² / (4L)) γ_φ². On the theorem surface, the only part of Assumption 4.4.2 used here is the sublevel containment 𝓛[f]((f x₀)) ⊆ 𝓕.

open ModifiedGaussNewtonStep
open scoped InnerProduct Manifold MinimalSingularValue
open scoped LevelSetNotation
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
variable [NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable {problem : SmoothMap}
variable {φ : E₂ → ℝ} [IsSharpMeritFunction φ]
variable {𝓕 : Set E₁}
variable {L0 : ℝ} {L : NNReal} {σ γφ : ℝ} {x0 : E₁}
local notation "f" => meritFunctionReformulation problem φ
local notation "𝓛0" => (𝓛[f]((f x0)) : Set E₁)
theorem modifiedGaussNewton_large_value_oneStep_decrease
    (method : ModifiedGaussNewtonMethod problem φ L0 (L : ℝ) x0)
    (h𝓕 : Convex ℝ 𝓕)
    (h_jacobian_lipschitz : LipschitzOnWith L (fderiv ℝ problem) 𝓕)
    (h𝓛0_subset : 𝓛0 ⊆ 𝓕)
    (hσ : HasUniformDualNondegeneracyOnInitialSublevelSet problem φ x0 σ)
    (hγφ_pos : 0 < γφ)
    (hγφ_lower : ∀ u : E₂, γφ * ‖u‖ ≤ φ u)
    (k : ℕ)
    (hk :
      modifiedGaussNewtonQuadraticMeritThreshold σ γφ L ≤
        f (method k)) :
    f (method (k + 1)) ≤
      f (method k) - ((σ ^ (2 : ℕ)) / (4 * (L : ℝ))) * γφ ^ (2 : ℕ)

Definition 4.4.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.4: the dual norm on E₁⋆ is exactly the existing norm on the continuous dual StrongDual ℝ E₁.

open Metric universe u variable {E₁ : Type u} [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] #check (‖·‖ : StrongDual ℝ E₁ → ℝ) -- Proof sketch: start from the operator-norm formula -- `ContinuousLinearMap.sSup_unitClosedBall_eq_norm`, then use the symmetry of the closed unit -- ball to replace `|s x|` by `s x`; in finite dimensions the resulting supremum is a maximum.

Lemma 4.4.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.4: if the local-model slice ψ[F; φ; J](x; ·) is convex, the textbook level set 𝓛(f(x)) of the continuous merit reformulation is contained in interior 𝓕, and M ≥ L ≥ 0, then the modified Gauss--Newton iterate V_M(x) belongs to the same level set.

open Set open scoped LevelSetNotation open scoped ModifiedGaussNewtonLocalModelNotation universe u v variable {E₁ : Type u} {E₂ : Type v} variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂] variable {F : E₁ → E₂} {φ : E₂ → ℝ} {J : E₁ → E₁ →L[ℝ] E₂} local notation "f" => meritFunctionReformulation F φ -- Proof sketch: argue by contradiction. If `step x` left the level set, then because the whole -- level set `𝓛(f(x))` lies in `interior 𝓕`, the segment from `x` to `step x` would meet the -- boundary of `𝓕`. At that boundary point, use the quadratic upper-model estimate together with -- convexity of the local-model slice `ψ[F; φ; J](x; ·)` to compare the true objective with the -- modified Gauss--Newton model. The inequality `L ≤ M` and the basic model-gap estimate from -- Lemma 4.4.2 then force a contradiction. theorem modifiedGaussNewton_step_mem_levelSet_of_levelSet_subset_interior {𝓕 : Set E₁} {L : NNReal} {M : ℝ} (step : ModifiedGaussNewtonStep (ψ[F; φ; J]) 𝓕 M) (x : 𝓕) (hcont : Continuous f) (hconv : ConvexOn ℝ Set.univ (ψ[F; φ; J] x)) (hupper : ∀ ⦃y : E₁⦄, y ∈ 𝓕 → f y ≤ quadraticallyRegularizedObjective (ψ[F; φ; J] x) (L : ℝ) x y) (hlevel : (𝓛[f]((f x)) : Set E₁) ⊆ interior 𝓕) (hLM : (L : ℝ) ≤ M) : step x ∈ 𝓛[f]((f x))

Proposition 4.4.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.4: if xStar realizes the minimum value f* of the merit reformulation meritFunctionReformulation F φ, and φ is nonnegative and vanishes only at the zero residual, then that minimum value is 0 if and only if the nonlinear equation F x = 0 is solvable.

universe u v
variable {E₁ : Type u} {E₂ : Type v} [Zero E₂]
namespace IsMinOn
theorem meritFunctionReformulation_eq_zero_iff_exists_zero_residual
    {F : E₁ → E₂} {φ : E₂ → ℝ} [IsMeritFunction φ] {xStar : E₁}
    (hxStar : IsMinOn (meritFunctionReformulation F φ) Set.univ xStar) :
    meritFunctionReformulation F φ xStar = 0 ↔ ∃ x : E₁, F x = 0

Theorem 4.4.4

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.4.4: if the residual map problem has L-Lipschitz Jacobian on Set.univ and Assumption 4.4.3 holds on the initial sublevel set of the norm-merit reformulation x ↦ ‖problem x‖, then there exists an exact solution x* ∈ solutionSet problem whose distance from the initial point is bounded by (2 / σ) * ‖problem x₀‖.

open Filter
open SmoothNonlinearEquationProblem
open scoped ConstrainedArgmin InnerProduct LevelSetNotation Manifold MinimalSingularValue
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonLocalDecreaseNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
open scoped Topology
universe u v
variable {E : Type u} {F : Type v}
variable [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E]
variable [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E), E; 𝓘(ℝ, F), F⟯
variable {problem : SmoothMap}
variable {x0 : E} {σ : ℝ}
local notation "f" => meritFunctionReformulation problem norm
theorem exists_exact_solution_dist_le_two_div_sigma_mul_initialResidual
    (L : NNReal)
    (hJacobianLipschitz : LipschitzOnWith L (fderiv ℝ problem) Set.univ)
    (hσ : HasUniformDualNondegeneracyOnInitialSublevelSet problem norm x0 σ) :
    ∃ xStar : E,
      xStar ∈ solutionSet problem ∧
        ‖xStar - x0‖ ≤ (2 / σ) * ‖problem x0‖

Definition 4.4.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.5: the least singular value of A is the infimum of the quotients ‖A x‖ / ‖x‖ over nonzero vectors x.

universe u v w variable {𝕜 : Type w} {E₁ : Type u} {E₂ : Type v} namespace ContinuousLinearMap variable [NormedField 𝕜] [NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁] [NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂] def minimalSingularValue (A : E₁ →L[𝕜] E₂) : ℝ := sInf (Set.range fun x : {x : E₁ // x ≠ 0} ↦ ‖A x.1‖ / ‖x.1‖)

Lemma 4.4.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.5: f_M(x) is bounded above by inf_{y ∈ 𝓕} [f(y) + ((L + M) / 2) ‖y - x‖²], written as the infimum over the feasible subtype.

open SetConstrainedMinimizationProblem open scoped Manifold open scoped ModifiedGaussNewtonLocalModelNotation universe u v variable {E₁ : Type u} {E₂ : Type v} variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂] theorem modifiedGaussNewton_modelValue_le_sInf_feasible_merit_plus_quadratic (problem : C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯) (φ : E₂ → ℝ) (hφ : LipschitzWith 1 φ) {𝓕 : Set E₁} {L : NNReal} {M : ℝ} (h𝓕 : Convex ℝ 𝓕) (h_jacobian_lipschitz : LipschitzOnWith L (fderiv ℝ problem) 𝓕) (step : ModifiedGaussNewtonStep (ψ[problem; φ; (fderiv ℝ problem)]) 𝓕 M) (x : 𝓕) : step.modelValue x ≤ sInf (Set.range fun y : 𝓕 ↦ meritFunctionReformulation problem φ (y : E₁) + (((L : ℝ) + M) / 2 : ℝ) * ‖(y : E₁) - x‖ ^ (2 : ℕ))

Proposition 4.4.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.5: if the Jacobian of a smooth nonlinear equation problem is L-Lipschitz on a convex feasible set 𝓕, then for all x, y ∈ 𝓕 the first-order Taylor remainder of the residual map satisfies ‖F(y) - F(x) - F'(x)(y - x)‖ ≤ (L / 2) * ‖y - x‖².

universe u v open scoped Manifold variable {E : Type u} {F : Type v} variable [NormedAddCommGroup E] [NormedSpace ℝ E] variable [NormedAddCommGroup F] [NormedSpace ℝ F] local notation "SmoothMap" => C^⊤⟮𝓘(ℝ, E), E; 𝓘(ℝ, F), F⟯ namespace ContMDiffMap open AffineMap -- Restrict the smooth map to the segment from `x` to `y`, subtract its affine approximation at -- `x`, and differentiate the resulting one-variable remainder explicitly. theorem jacobian_lipschitz_taylor_remainder_le (problem : SmoothMap) {𝓕 : Set E} {L : NNReal} (h𝓕 : Convex ℝ 𝓕) (h_jacobian_lipschitz : LipschitzOnWith L (fderiv ℝ problem) 𝓕) (x y : E) (hx : x ∈ 𝓕) (hy : y ∈ 𝓕) : ‖problem y - problem x - fderiv ℝ problem x (y - x)‖ ≤ ((L : ℝ) / 2) * ‖y - x‖ ^ (2 : ℕ)

Theorem 4.4.5

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Theorem 4.4.5: in the whole-space setting, where Assumption 4.4.2 is automatic, any modified Gauss--Newton sequence generated by Algorithm 4.4.1 for the merit reformulation f(x) = φ(F(x)) converges to a unique limit point x* in the exact-solution set of F under Assumptions 4.4.1 and 4.4.3.

open Filter
open ModifiedGaussNewtonStep
open SmoothNonlinearEquationProblem
open scoped InnerProduct LevelSetNotation Manifold MinimalSingularValue
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonLocalDecreaseNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
open scoped Topology
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
variable [NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable {problem : SmoothMap}
variable {φ : E₂ → ℝ} [IsSharpMeritFunction φ]
variable {L0 : ℝ} {L : NNReal} {x0 : E₁} {σ : ℝ}
local notation "f" => meritFunctionReformulation problem φ
local notation "𝓢" => solutionSet problem
local notation "𝓛0" => (𝓛[f]((f x0)) : Set E₁)
theorem modifiedGaussNewtonMethod_tendsto_unique_solution
    (method : ModifiedGaussNewtonMethod problem φ L0 (L : ℝ) x0)
    (hLipschitz : HasLipschitzDerivativeOnWith L Set.univ f)
    (hσ : HasUniformDualNondegeneracyOnInitialSublevelSet problem φ x0 σ) :
    ∃! xStar : E₁, xStar ∈ 𝓢 ∧ Tendsto method atTop (𝓝 xStar)

Definition 4.4.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.6: primal nondegeneracy is the canonical positivity proposition 0 < σ_min(A).

open scoped InnerProduct MinimalSingularValue universe u v w variable {𝕜 : Type w} {E₁ : Type u} {E₂ : Type v} variable [NormedField 𝕜] [NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁] [NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂] variable (A : E₁ →L[𝕜] E₂) #check (0 < σ_min(A))

Lemma 4.4.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.6: if the adjoint of a linear operator has positive minimal singular value, then every right-hand side b admits a preimage whose norm is bounded by ‖b‖ / σ_min(A†).

open scoped InnerProduct MinimalSingularValue universe u v w variable {𝕜 : Type w} {E₁ : Type u} {E₂ : Type v} [RCLike 𝕜] [NormedAddCommGroup E₁] [InnerProductSpace 𝕜 E₁] [CompleteSpace E₁] [FiniteDimensional 𝕜 E₁] [NormedAddCommGroup E₂] [InnerProductSpace 𝕜 E₂] [CompleteSpace E₂] [FiniteDimensional 𝕜 E₂] namespace ContinuousLinearMap theorem exists_preimage_norm_le_of_adjoint_minimalSingularValue_pos (A : E₁ →L[𝕜] E₂) (hA : 0 < σ_min(A†)) (b : E₂) : ∃ x : E₁, A x = b ∧ ‖x‖ ≤ ‖b‖ / σ_min(A†)

Proposition 4.4.6

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.6: if a whole-space modified Gauss--Newton minimizer is chosen for each positive regularization parameter, then the source-facing residual quantity (1 / 2) r_M(x)^2 is decreasing in M on (0, ∞). The proof uses the source-faithful minimum-of-affine comparison at two parameters rather than exposing any extra derivative bridge as public API.

open Set open scoped ConvexAnalysis open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation universe u variable {E₁ : Type u} [NormedAddCommGroup E₁] theorem antitone_modifiedGaussNewtonResidualSqHalf {ψ : E₁ → E₁ → ℝ} {x : E₁} (step : (M : Ioi (0 : ℝ)) → ModifiedGaussNewtonStep ψ Set.univ M.1) : Antitone (fun M : Ioi (0 : ℝ) ↦ (1 / 2 : ℝ) * (r[(step M)](x)) ^ (2 : ℕ))

Definition 4.4.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.7: for a Fréchet differentiable map F : E₁ → E₂, the Jacobian at x is the canonical Fréchet derivative fderiv; in the real Euclidean setting of the text, this is the linear operator fderiv ℝ F x : E₁ →L[ℝ] E₂ characterized by the usual directional quotient limit.

recall fderiv

Lemma 4.4.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.7: if the Jacobian F'(x) is dual nondegenerate, then the modified Gauss--Newton residual r_M(x) is bounded by ‖F(x)‖ / σ_min(F'(x)^*).

open ModifiedGaussNewtonStep
open scoped InnerProduct MinimalSingularValue
open scoped ModifiedGaussNewtonLocalModelNotation
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁]
variable [FiniteDimensional ℝ E₁]
variable [NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂]
variable [FiniteDimensional ℝ E₂]
variable (problem : E₁ → E₂) (φ : E₂ → ℝ) [IsMeritFunction φ]
local notation "ψ" => ψ[problem; φ; (fderiv ℝ problem)]

-- Proof sketch: apply the owner theorem
-- `ContinuousLinearMap.exists_preimage_norm_le_of_adjoint_minimalSingularValue_pos`, and the
-- Jacobian `fderiv ℝ problem x` to the right-hand side `-problem x` to obtain a correction `h*`
-- with
-- `problem x + fderiv ℝ problem x h* = 0` and
-- `‖h*‖ ≤ ‖problem x‖ / σ_min((fderiv ℝ problem x)†)`. Use `x + h*` as a competitor in the
-- global minimization property of `step`. Since merit functions are nonnegative and vanish at the
-- zero residual, the local-model term at `x + h*` is `0`, so positivity of `M` lets the
-- quadratic term control `r[step](x)`.
theorem modifiedGaussNewton_residual_le_nonlinearResidual_div_minimalSingularValue_adjoint
    {M : ℝ} (hM : 0 < M)
    (step : ModifiedGaussNewtonStep ψ Set.univ M)
    (x : E₁)
    (hdual : 0 < σ_min((fderiv ℝ problem x)†)) :
    r[step](x) ≤ ‖problem x‖ / σ_min((fderiv ℝ problem x)†)

Proposition 4.4.7

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.7: the modified Gauss--Newton iterates produced by Algorithm 4.4.1 have nonincreasing merit-function values, so f(x_{k+1}) ≤ f(x_k) for every iteration index k.

open scoped Manifold
open scoped ModifiedGaussNewtonStep.ModifiedGaussNewtonStepWholeSpaceNotation
universe u v
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
namespace ModifiedGaussNewtonMethod
variable {problem : SmoothMap}
variable {φ : E₂ → ℝ} [IsSharpMeritFunction φ]
variable {L0 L : ℝ} {x0 : E₁}
local notation "f" => meritFunctionReformulation problem φ

-- Proof sketch: compose the owner-side acceptance inequality
-- `method.step_value_le_modelValue k` with the owner-side comparison
-- `method.step_modelValue_le_merit k`.
theorem meritFunction_succ_le
    (method : ModifiedGaussNewtonMethod problem φ L0 L x0) (k : ℕ) :
    f (method (k + 1)) ≤ f (method k)

Definition 4.4.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

universe u v w open scoped Manifold variable (𝕜 : Type w) [NontriviallyNormedField 𝕜] variable (E₁ : Type u) (E₂ : Type v) variable [NormedAddCommGroup E₁] [NormedSpace 𝕜 E₁] variable [NormedAddCommGroup E₂] [NormedSpace 𝕜 E₂] #check C^⊤⟮𝓘(𝕜, E₁), E₁; 𝓘(𝕜, E₂), E₂⟯

Lemma 4.4.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lemma 4.4.8: for positive regularization, the canonical weighted optimal-value owner equals the infimum of the reduced positive-τ objective written in the explicit B-induced norms.

open LinearMap (BilinForm) open LinearMap.BilinForm open Set open scoped ConvexAnalysis open scoped BInducedNorm open scoped ModifiedGaussNewtonLocalModelNotation universe u v variable {E₁ : Type u} {E₂ : Type v} variable [AddCommGroup E₁] [Module ℝ E₁] variable [AddCommGroup E₂] [Module ℝ E₂] variable (B₁ : BilinForm ℝ E₁) [Fact B₁.toQuadraticMap.PosDef] variable (B₂ : BilinForm ℝ E₂) [Fact B₂.toQuadraticMap.PosDef] variable (F : PrimalSpace B₁ → PrimalSpace B₂) variable (J : PrimalSpace B₁ → PrimalSpace B₁ →L[ℝ] PrimalSpace B₂) variable (x : PrimalSpace B₁) theorem modifiedGaussNewtonWeightedAuxiliaryValue_eq_sInf_weightedTauObjective (M : NNRealˣ) : modifiedGaussNewtonOptimalValue (ψ[F; norm; J]) x M = sInf (range fun τ : NNRealˣ ↦ ((τ : ℝ) / 2 : ℝ) + sInf (range fun h : PrimalSpace B₁ ↦ (1 / (2 * (τ : ℝ)) : ℝ) * ‖F x + J x h‖[B₂] ^ (2 : ℕ) + (((M : ℝ) / 2 : ℝ) * ‖h‖[B₁] ^ (2 : ℕ))))

Proposition 4.4.8

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.8: if D is the attained minimum distance from x₀ to the exact solution sublevel-distance set solutionSublevelDistanceSet problem f x₀ from Definition 4.4.15, equivalently the direct distance image of 𝓢 = solutionSet problem for the merit reformulation f = meritFunctionReformulation problem φ, and the first modified Gauss--Newton local model at x₀ satisfies the exact-solution quadratic upper estimate on 𝓢, then the first iterate of Algorithm 4.4.1 obeys f(x₁) ≤ (3 / 2) L D².

universe u v
open SmoothNonlinearEquationProblem
open scoped Manifold
open scoped ModifiedGaussNewtonLocalModelNotation
variable {E₁ : Type u} {E₂ : Type v}
variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁]
variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂]
local notation "SmoothMap" =>
  C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯
variable {problem : SmoothMap}
variable {φ : E₂ → ℝ} [IsSharpMeritFunction φ]
variable {x0 : E₁}
local notation "f" => meritFunctionReformulation problem φ
local notation "localModel" => ψ[problem; φ; fun x ↦ fderiv ℝ problem x]
local notation "𝓢" => solutionSet problem
namespace ModifiedGaussNewtonMethod
theorem first_merit_le_three_halves_mul_L_mul_sq_of_isLeastSolutionDistance
    {L0 L D : ℝ}
    (method : ModifiedGaussNewtonMethod problem φ L0 L x0)
    (hD : IsLeast (solutionSublevelDistanceSet problem f x0) D)
    (hupper :
      ∀ ⦃y : E₁⦄, y ∈ 𝓢 →
        localModel x0 y ≤ (L / 2 : ℝ) * ‖y - x0‖ ^ (2 : ℕ)) :
    f (method 1) ≤ (3 / 2 : ℝ) * L * D ^ (2 : ℕ)

Definition 4.4.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.9: a sharp merit function on a real normed residual space is a merit function that is convex, 1-Lipschitz, and has a sharp minimum at the origin with some constant in (0, 1].

variable {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
class IsSharpMeritFunction (φ : E → ℝ) : Prop extends IsMeritFunction φ where
  /-- A sharp merit function is convex on the whole residual space. -/
  convex : ConvexOn ℝ Set.univ φ
  /-- A sharp merit function is `1`-Lipschitz. -/
  lipschitz_one : LipschitzWith 1 φ
  /-- A sharp merit function dominates the ambient norm by some factor in `(0, 1]`. -/
  sharp_origin : ∃ γ : ℝ, γ ∈ Set.Ioc (0 : ℝ) 1 ∧ ∀ u : E, γ * ‖u‖ ≤ φ u

Proposition 4.4.9

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.9 (1): if N is the first iterate index satisfying the threshold inequality f(x_N) < (σ² / (2L)) γ_φ², then N ≤ 1 + (4L / (σ² γ_φ²)) f(x₁), where x₁ = method 1 and f = meritFunctionReformulation problem φ.

universe u v
open SmoothNonlinearEquationProblem
open scoped Manifold MinimalSingularValue
variable {E₁ : Type u} {E₂ : Type v}
open scoped ModifiedGaussNewtonLocalModelNotation
variable [NormedAddCommGroup E₁] [InnerProductSpace ℝ E₁] [CompleteSpace E₁]
variable [NormedAddCommGroup E₂] [InnerProductSpace ℝ E₂] [CompleteSpace E₂]
variable
    (problem : C^⊤⟮𝓘(ℝ, E₁), E₁; 𝓘(ℝ, E₂), E₂⟯)
    (φ : E₂ → ℝ) [IsSharpMeritFunction φ]
    {L0 : ℝ} (L : NNReal) (x0 : E₁)
    (method : ModifiedGaussNewtonMethod problem φ L0 (L : ℝ) x0)
local notation "f" => meritFunctionReformulation problem φ
local notation "localModel" => ψ[problem; φ; fun x ↦ fderiv ℝ problem x]
local notation "𝓢" => solutionSet problem
theorem modifiedGaussNewton_firstQuadraticMeritRegionIndex_le_one_add_scaled_firstMerit
    {σ γφ : ℝ}
    (hJacobianLipschitz : LipschitzOnWith L (fderiv ℝ problem) Set.univ)
    (hσ :
      HasUniformDualNondegeneracyOnInitialSublevelSet problem φ x0 σ)
    (hγφ_pos : 0 < γφ)
    (hγφ_lower : ∀ u : E₂, γφ * ‖u‖ ≤ φ u)
    {N : ℕ}
    (hN :
      IsLeast
        {k : ℕ | f (method k) < modifiedGaussNewtonQuadraticMeritThreshold σ γφ L}
        N) :
    (N : ℝ) ≤
      1 + (4 * (L : ℝ) / (σ ^ (2 : ℕ) * γφ ^ (2 : ℕ))) * f (method 1)

Definition 4.4.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.10: the merit-function reformulation of the nonlinear system F(x) = 0 attached to a residual map F : X → Y and a scalar merit function φ : Y → ℝ is the scalar objective f(x) = φ(F(x)) to be minimized over the whole domain.

universe u v open SetConstrainedMinimizationProblem variable {X : Type u} {Y : Type v} def meritFunctionReformulation (F : X → Y) (φ : Y → ℝ) : X → ℝ := φ ∘ F

Proposition 4.4.10

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.10: with characteristic quantity ξ = L ‖x₀ - x*‖ / σ, if φ is σ-strongly convex on Set.univ, belongs to C22[L], x* minimizes φ on Set.univ, method is the associated modified Newton iteration started at x₀, and N₁ is the first iterate index for which the orbit enters the modified-Newton region of quadratic convergence, then the assumption 1 ≤ ξ implies N₁ ≤ 6.25 * sqrt ξ.

open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E]
variable [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]
theorem modifiedNewton_firstQuadraticRegionEntryIndex_le_sqrt_characteristicQuantity
    {φ : E → ℝ} {σ : ℝ} {L : NNReal} {x0 xStar : E}
    (hσ : 0 < σ)
    (hφ_strong : StrongConvexOn Set.univ σ φ)
    (hφ_hessian : φ ∈ C22[L])
    (hxStar : IsMinOn φ Set.univ xStar)
    (method : ModifiedNewtonMethod φ x0)
    (hxi : 1 ≤ modifiedNewtonCharacteristicQuantity σ L x0 xStar)
    {N1 : ℕ}
    (hN1 :
      IsLeast {k : ℕ | InModifiedNewtonQuadraticConvergenceRegion method σ L xStar k} N1) :
    (N1 : ℝ) ≤
      (25 / 4 : ℝ) * Real.sqrt (modifiedNewtonCharacteristicQuantity σ L x0 xStar)

Definition 4.4.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.11: given a residual map F, a Jacobian family J, and a merit function φ, the modified Gauss--Newton local model is the two-variable function ψ(x; y) = φ (F(x) + J(x)(y - x)). When J x = F'(x), this is the textbook affine first-order residual model at the base point x.

open scoped ConstrainedArgmin universe u v variable {E₁ : Type u} [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] variable {E₂ : Type v} [NormedAddCommGroup E₂] [NormedSpace ℝ E₂] def modifiedGaussNewtonLocalModel (F : E₁ → E₂) (φ : E₂ → ℝ) (J : E₁ → E₁ →L[ℝ] E₂) : E₁ → E₁ → ℝ := fun x ↦ meritFunctionReformulation (fun y ↦ F x + J x (y - x)) φ

Proposition 4.4.11

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Proposition 4.4.11: if problem is a modified Gauss--Newton problem, method is the associated modified Newton orbit started at problem.x0, and N₂ is the first quadratic-convergence index of method toward problem.xStar, then (N₂ : ℝ) is bounded by 1 + 6 * problem.characteristicQuantity ^ (2 : ℕ).

open scoped Gradient
universe u
variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E]
variable [FiniteDimensional ℝ E]
theorem modifiedGaussNewton_scheme_firstQuadraticConvergenceIndex_le_one_add_six_mul_characteristicQuantity_sq
    (problem : ModifiedGaussNewtonProblem E)
    (method : NewtonSystem.Method (∇ problem) problem.x0)
    {N2 : ℕ}
    (hN2 : IsLeast {k : ℕ | HasQuadraticConvergenceFrom method problem.xStar k} N2) :
    (N2 : ℝ) ≤ 1 + 6 * problem.characteristicQuantity ^ (2 : ℕ)

Definition 4.4.12

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.12: on a feasible set 𝓕, a modified Gauss--Newton step with parameter M chooses, for each base point x ∈ 𝓕, a global minimizer V_M(x) of the quadratic-regularized local model y ↦ ψ(x; y) + (M / 2) ‖y - x‖². The associated quantities r_M, f_M, and δ_M are defined from this chosen step in the namespace below; later results may impose 0 < M when that positivity is mathematically needed.

open scoped ConstrainedArgmin universe u variable {E₁ : Type u} [NormedAddCommGroup E₁] structure ModifiedGaussNewtonStep (ψ : E₁ → E₁ → ℝ) (𝓕 : Set E₁) (M : ℝ) where /-- The chosen modified Gauss--Newton iterate `V_M(x)` as a point of the canonical whole-space argmin set of the quadratic-regularized local model centered at `x`. -/ minimizer (x : 𝓕) : argmin[Set.univ] (quadraticallyRegularizedObjective (ψ x) M x)

Definition 4.4.13

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.13: for a radius r, localModelDecrease f ψ r is the textbook decrease quantity Δ_r on the natural finite-value locus of the closed-ball local-model partial infimum. At a point x together with a proof that the Chapter 3 partial infimum is finite there, the companion bridge theorem localModelDecreaseAt_eq_sub_sInf recovers the textbook formula Δ_r(x) = f x - inf_{y ∈ B̄(x,r)} ψ(x;y).

universe u open scoped ConvexAnalysis variable {E₁ : Type u} [PseudoMetricSpace E₁] def localModelDecrease (f : E₁ → ℝ) (ψ : E₁ → E₁ → ℝ) (r : NNReal) : localModelFiniteDomain ψ r → ℝ := fun x ↦ f x - extendedRealRealPart (partialInfProjection (localModelClosedBallRelation r) (Real.toEReal ∘ Function.uncurry ψ)) x

Definition 4.4.14

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.14: the level set 𝓛[f](τ) is the recalled owner surface for the canonical sublevel set of f at level τ.

universe u v open scoped LevelSetNotation variable {E : Type u} {α : Type v} [Preorder α] variable (f : E → α) (τ : α) #check (𝓛[f](τ) : Set E)

Definition 4.4.15

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

For a merit reformulation, the source-facing attained-distance owner from Definition 4.4.15 agrees with the direct distance image of the exact solution set.

universe u v
open SmoothNonlinearEquationProblem
open scoped LevelSetNotation
variable {E₁ : Type u} {E₂ : Type v} [Zero E₂]
variable [NormedAddCommGroup E₁]
theorem solutionSublevelDistanceSet_eq_image_solutionSet_of_meritFunctionReformulation
    (problem : E₁ → E₂)
    (φ : E₂ → ℝ) [IsMeritFunction φ]
    (x0 : E₁) :
    solutionSublevelDistanceSet problem (meritFunctionReformulation problem φ) x0 =
      (fun y : E₁ ↦ ‖y - x0‖) '' solutionSet problem

Definition 4.4.16

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.16: a modified Gauss--Newton problem consists of a whole-space objective f on a real normed space, a positive strong-convexity modulus σ, a global second-derivative Lipschitz constant L, the canonical owner hypotheses StrongConvexOn Set.univ σ f and f ∈ C22[L], a chosen global minimizer xStar, and an initial point x0. The ambient whole-space minimization problem is recovered by the bridge problem.toSetConstrainedMinimizationProblem, while convexity, C² regularity, and uniqueness of the minimizer are derived from the owner fields rather than stored as extra primitive data.

open scoped Gradient
universe u
variable (E : Type u) [NormedAddCommGroup E] [NormedSpace ℝ E]
structure ModifiedGaussNewtonProblem where
  objective : E → ℝ
  σ : ℝ
  L : NNReal
  xStar : E
  x0 : E
  sigma_pos : 0 < σ
  objective_strongConvex : StrongConvexOn Set.univ σ objective
  objective_mem : objective ∈ C22[L]
  xStar_isMin : IsMinOn objective Set.univ xStar

Definition 4.4.17

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.17: the stationarity map for unconstrained minimization is the canonical gradient map.

open scoped Gradient universe u variable {E : Type u} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [CompleteSpace E] variable {φ : E → ℝ} {x : E} #check (∇ φ)

Definition 4.4.18

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Definition 4.4.18: for positive M, the canonical norm-specialized auxiliary value equals the supremum of the intrinsic strong-dual objective over the closed unit ball of the residual strong dual.

open Metric open scoped InnerProduct open scoped ModifiedGaussNewtonLocalModelNotation universe u v variable {E₁ : Type u} {E₂ : Type v} variable [NormedAddCommGroup E₁] [NormedSpace ℝ E₁] variable [NormedAddCommGroup E₂] [NormedSpace ℝ E₂] theorem modifiedGaussNewtonOptimalValueAt_norm_eq_sSup_dualObjective (F : E₁ → E₂) (J : E₁ → E₁ →L[ℝ] E₂) (x : E₁) (M : NNRealˣ) : modifiedGaussNewtonOptimalValueAt (ψ[F; norm; J]) x (M : ℝ) = sSup ((((↑) : ℝ → EReal) ∘ modifiedGaussNewtonNormDualObjective F J M x) '' closedBall (0 : StrongDual ℝ E₂) 1)

Supporting modules

These source modules support the indexed items and are listed separately so the chapter inventory remains complete.

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source

Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.

Source header · Attribution source