Proposition 1 — critical points and descent along the projected arc
ProvedProjNewton.Superlinear.proposition1bound-constraintsnonlinear-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1projected-newton
Let , let be continuously differentiable, let , and let be symmetric positive definite and diagonal with respect to . Define for . Then:
If is not critical, some satisfies for every . This links the orthant first-order condition to the projected arc and supplies local descent.
Formalization Note Feasibility, the paper's standing assumption and are explicit. The matrix condition zeroes rows indexed by ; symmetry supplies the matching columns.
Preamble
import Mathlib import Definitions.Def_ProjNewton_Superlinear_Algorithm
Formal statement
namespace ProjNewton.Superlinear
open Matrix Filter Topology
/-- Bertsekas (1982), Proposition 1, p. 226. -/
theorem proposition1 {n : ℕ} (hn : 0 < n) (f : Vec n → ℝ)
(hf : ContDiff ℝ 1 f) (x : Vec n) (hx : x ∈ orthant n)
(D : Matrix (Fin n) (Fin n) ℝ) (hD : D.PosDef)
(hdiag : DiagonalWrt D (Iplus f x)) :
(IsCritical f x ↔ ∀ a : ℝ, 0 ≤ a → arc f D x a = x) ∧
(¬ IsCritical f x → ∃ abar : ℝ, 0 < abar ∧
∀ a ∈ Set.Ioc (0 : ℝ) abar, f (arc f D x a) < f x) := by sorry
end ProjNewton.Superlinear
Source
Bertsekas, Projected Newton Methods for Optimization Problems with Simple Constraints, SIAM J. Control Optim. 20(2) (1982), p. 226, Proposition 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.