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.
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.
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 ≤ aLemma 4.1.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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).PosSemidefTheorem 4.1.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 : ℝ) : EDefinition 4.1.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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)
vProposition 4.1.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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.
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.
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 methodDefinition 4.1.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 fTheorem 4.1.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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 𝓕 fLSTheorem 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.
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.
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.
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)) ^ 2Lemma 4.1.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.univLemma 4.1.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 τfLemma 4.1.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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))
DProposition 4.1.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 xProposition 4.1.16
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 hAcceptsProposition 4.1.18
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.DualLemma 4.2.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.hasGradientAtTheorem 4.2.1
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 kDefinition 4.2.2
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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 xAlgorithm 4.2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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] x0Definition 4.2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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)) xTheorem 4.2.3
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.equivFunLemma 4.2.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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) : PropLemma 4.2.5
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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_leDefinition 4.2.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 ℝ ELemma 4.2.6
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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)) xDefinition 4.2.7
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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 x0Text 4.2.9
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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_boundDefinition 4.2.10
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 pText 4.2.11
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 cubicRegularizationQuadraticApproximationDefinition 4.2.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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) = 0Text 4.2.12
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 cubicRegularizationProblemText 4.2.13
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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.
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.
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.
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 fText 4.2.17
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 fText 4.2.18
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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‖ ≤ DText 4.2.21
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 C4.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.
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.
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 kCorollary 4.3.1
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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)) = 0Definition 4.3.4
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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 ℝ ELemma 4.3.4
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 HasLipschitzContinuousHessianLemma 4.3.5
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
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.
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 fderivLemma 4.4.7
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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 → ℝ :=
φ ∘ FProposition 4.4.10
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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 ψ)) xDefinition 4.4.14
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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
— source only (outside the published documentation root) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
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.
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.
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.
-
ModifiedGaussNewtonSecantBounds.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.
-
ModifiedGaussNewtonValueFunction.lean(Documentation) (Lean source)
Lean contributors (project-level attribution): Chenyi Li, Siyuan Shao, Yijie Wang, Feiming Wang, Weiran Shi, Yuhao Jiang, Zebo Liu, Wentao Long.