After (37) — finite line search, descent and critical-point termination
ProvedProjNewton.Superlinear.well_definedbound-constraintsnonlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projected-newton
For the algorithm of (32)–(37) with , each feasible noncritical point has a sufficiently small trial step accepted by the Armijo inequality: some makes every acceptable. At a critical point, is accepted and the projected unit step fixes the point. Consequently every run with admissible matrices stays feasible, strictly decreases at a noncritical iterate, and remains fixed at a critical iterate.
This records the well-definedness and descent conclusion stated after (37).
Formalization Note The run predicate chooses the first acceptable nonnegative exponent, as on p. 229. The fixed-point sentence on p. 230 says “for all ,” matching Proposition 1(a).
Preamble
import Mathlib import Definitions.Def_ProjNewton_Superlinear_Algorithm
Formal statement
namespace ProjNewton.Superlinear
open Matrix Filter Topology
/-- Bertsekas (1982), discussion following (37), pp. 229–230. -/
theorem well_defined {n : ℕ} (hn : 0 < n) (f : Vec n → ℝ)
(hf : ContDiff ℝ 1 f) (μ : Fin n → ℝ) (ε β σ : ℝ)
(hpar : Params μ ε β σ) :
(∀ (x : Vec n), x ∈ orthant n →
∀ (D : Matrix (Fin n) (Fin n) ℝ), D.PosDef →
DiagonalWrt D (Ik f μ ε x) →
(¬ IsCritical f x → ∃ m₀ : ℕ, ∀ m ≥ m₀, Armijo f μ ε β σ D x m) ∧
(IsCritical f x → Armijo f μ ε β σ D x 0 ∧ arc f D x 1 = x)) ∧
(∀ (D : ℕ → Matrix (Fin n) (Fin n) ℝ) (x : ℕ → Vec n),
IsRun f μ ε β σ D x → AdmissibleScaling f μ ε D x →
∀ k, x k ∈ orthant n ∧
(¬ IsCritical f (x k) → f (x (k + 1)) < f (x k)) ∧
(IsCritical f (x k) → x (k + 1) = x k)) := by sorry
end ProjNewton.Superlinear
Source
Bertsekas, Projected Newton Methods for Optimization Problems with Simple Constraints, SIAM J. Control Optim. 20(2) (1982), pp. 229–230, §2 discussion after (37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.