Proposition 4 — superlinear convergence of the projected Newton method
ProvedProjNewton.Superlinear.proposition4Let be convex and twice continuously differentiable. Suppose problem (1) has a unique optimal solution in the nonnegative orthant satisfying Assumption (C). Suppose also that some bound the Hessian quadratic form at every point in the unrestricted initial level set and in every direction :
Run (32)–(37) with , where zeros only off-diagonal Hessian entries touching . Then and the error converges superlinearly: for every , eventually . If the Hessian is Lipschitz on a neighborhood of , the error is at least quadratic: for some , eventually .
This is the paper's main rate claim for its partly diagonal projected Newton method.
Formalization Note The printed bound misbinds in the level set while leaving its Hessian point free; it is read as the stated quantification. The level set has no feasibility restriction, as printed. The hypothesis includes the standing convention; is feasible and uniquely optimal among feasible points. The run starts feasible and chooses the first acceptable exponent. No convergence, matrix invertibility, active-set identification or admissibility is assumed. Superlinearity uses a uniform eventual inequality, so finite termination is covered.
import Mathlib import Definitions.Def_ProjNewton_Superlinear_Algorithm
namespace ProjNewton.Superlinear
open Matrix Filter Topology
/-- Bertsekas (1982), Proposition 4, p. 236. -/
theorem proposition4 {n : ℕ} (hn : 0 < n) (f : Vec n → ℝ)
(hf2 : ContDiff ℝ 2 f) (hconv : ConvexOn ℝ Set.univ f)
(xs : Vec n) (hopt : xs ∈ orthant n ∧ ∀ y ∈ orthant n, f xs ≤ f y)
(huniq : ∀ y ∈ orthant n, (∀ z ∈ orthant n, f y ≤ f z) → y = xs)
(hC : AssumptionC f xs) (μ : Fin n → ℝ) (ε β σ : ℝ)
(hpar : Params μ ε β σ) (x : ℕ → Vec n)
(hm : ∃ m₁ m₂ : ℝ, 0 < m₁ ∧ 0 < m₂ ∧
∀ y : Vec n, f y ≤ f (x 0) → ∀ z : Fin n → ℝ,
m₁ * (z ⬝ᵥ z) ≤ hessForm f y z ∧ hessForm f y z ≤ m₂ * (z ⬝ᵥ z))
(hrun : IsRun f μ ε β σ (fun k => (Hmat f μ ε (x k))⁻¹) x) :
Tendsto x atTop (𝓝 xs) ∧
(∀ c : ℝ, 0 < c → ∀ᶠ k in atTop,
‖x (k + 1) - xs‖ ≤ c * ‖x k - xs‖) ∧
((∃ δ : ℝ, 0 < δ ∧ ∃ L : NNReal,
LipschitzOnWith L (fderiv ℝ (gradient f)) (Metric.ball xs δ)) →
∃ C : ℝ, 0 < C ∧ ∀ᶠ k in atTop,
‖x (k + 1) - xs‖ ≤ C * ‖x k - xs‖ ^ 2) := by sorry
end ProjNewton.Superlinear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.