Lemma 3.1 ii) (3.4) —
ProvedAdaptiveCubic.Cauchy.lemma_3_1_iicauchy-pointcubic-regularisationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , with gradient , a symmetric matrix with for some (assumption AM.1), and . If the step satisfies the Cauchy condition (2.2), then
The bound says that the cubic term keeps the step of order once dominates the curvature bound. It is quoted from Part I of the paper (Lemma 2.2 there) and is used to bound the Taylor remainder in Lemma 3.2.
Formalization Note One iteration, index dropped; is the operator norm.
Preamble
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_IsARCRun open scoped RealInnerProductSpace
Formal statement
namespace AdaptiveCubic.Cauchy
/-- Lemma 3.1 ii), (3.4), p. 7 (Cartis, Gould & Toint, ARC Part II, preprint rev. 15 Sep 2009;
quoted from Part I, Lemma 2.2). For one iteration with iterate `x`, symmetric `B` with
`‖B‖ ≤ κ_B` (AM.1, `κ_B ≥ 0`), weight `σ > 0` and a step `s` satisfying the Cauchy condition (2.2):
`‖s‖ ≤ (3/σ) max(κ_B, √(σ ‖g‖))`, with `g = ∇f(x)`. -/
theorem lemma_3_1_ii {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(B : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n)) (hB : IsSelfAdjoint B)
(κB : ℝ) (hκB : 0 ≤ κB) (hAM1 : ‖B‖ ≤ κB)
(σ : ℝ) (hσ : 0 < σ) (x s : EuclideanSpace ℝ (Fin n))
(hcauchy : ∀ α : ℝ, 0 ≤ α → model f B σ x s ≤ model f B σ x (-(α • gradient f x))) :
‖s‖ ≤ 3 / σ * max κB (√(σ * ‖gradient f x‖)) := 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 ii), (3.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.