After Proposition 4 — eventual acceptance of the unit step
ProvedProjNewton.Superlinear.unit_stepbound-constraintsnonlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projected-newton
Use the convex problem, unique feasible optimum, Assumption (C), level-set Hessian bounds and matrix choice of Proposition 4. For the resulting first-acceptable-step run, the initial trial satisfies (37) for all sufficiently large :
Hence the Armijo search eventually accepts the unity stepsize at its first trial.
Formalization Note The printed Hessian-bound quantifier in Proposition 4 is read as “every point in the unrestricted initial level set and every direction .” The first-trial exponent is ; is constructed from , with no invertibility or matrix admissibility premise.
Preamble
import Mathlib import Definitions.Def_ProjNewton_Superlinear_Algorithm
Formal statement
namespace ProjNewton.Superlinear
open Matrix Filter Topology
/-- Bertsekas (1982), after Proposition 4, p. 236. -/
theorem unit_step {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) :
∀ᶠ k in atTop, Armijo f μ ε β σ ((Hmat f μ ε (x k))⁻¹) (x k) 0 := by sorry
end ProjNewton.Superlinear
Source
Bertsekas, Projected Newton Methods for Optimization Problems with Simple Constraints, SIAM J. Control Optim. 20(2) (1982), p. 236, §2 after Proposition 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.