Lemma 3.1 i) (3.3) — Cauchy decrease of the cubic model
ProvedAdaptiveCubic.Cauchy.lemma_3_1_icauchy-pointcubic-regularisationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , with gradient , a symmetric matrix and , and let be the cubic model at with these data. If the step satisfies the Cauchy condition (2.2), i.e. for every , then
where is the operator norm induced by the Euclidean norm.
This is the basic model decrease guaranteed by the Cauchy point; in particular whenever , which is (2.7). The result is quoted from Part I of the paper (Lemma 2.1 there).
Formalization Note The statement concerns one iteration, so the index is dropped. At the left-hand side is and the inequality reads ; it is not excluded. is a continuous linear operator on EuclideanSpace ℝ (Fin n).
Preamble
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_IsARCRun open scoped RealInnerProductSpace
Formal statement
namespace AdaptiveCubic.Cauchy
/-- Lemma 3.1 i), (3.3), p. 7 (Cartis, Gould & Toint, ARC Part II, preprint rev. 15 Sep 2009;
quoted from Part I, Lemma 2.1). For one iteration with iterate `x`, symmetric `B`, weight `σ > 0`
and a step `s` satisfying the Cauchy condition (2.2) (`m(s) ≤ m(−α g)` for all `α ≥ 0`):
`f(x) − m(s) ≥ (‖g‖ / (6√2)) · min(‖g‖ / (1 + ‖B‖), ½ √(‖g‖/σ))`, with `g = ∇f(x)`. -/
theorem lemma_3_1_i {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(B : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hB : IsSelfAdjoint B)
(σ : ℝ) (hσ : 0 < σ) (x s : EuclideanSpace ℝ (Fin n))
(hcauchy : ∀ α : ℝ, 0 ≤ α → model f B σ x s ≤ model f B σ x (-(α • gradient f x))) :
‖gradient f x‖ / (6 * √2) *
min (‖gradient f x‖ / (1 + ‖B‖)) (1 / 2 * √(‖gradient f x‖ / σ)) ≤
f x - model f B σ x s := by sorry
end AdaptiveCubic.Cauchy
Source
Cartis, Gould & Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II, preprint rev. 15 Sep 2009 (UNamur), p. 7, Lemma 3.1 i), (3.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.