Lemma 4.2 — (4.1) and (4.2) give the model decrease σ_k‖s_k‖³/6
ProvedAdaptiveCubic.FirstOrder.lemma_4_2cubic-regularisationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let be the cubic model (1.2) at with symmetric approximation and weight . If the step satisfies
- (4.1) , and
- (4.2) ,
then
The decrease predicted by the model is thus controlled from below by the length of the step alone. Combined with a lower bound on (Lemma 5.2), this gives the model decrease used for the complexity bound.
Formalization Note The statement is about a single iteration: , , , and are arbitrary, no run is involved. No sign condition on or symmetry of is needed.
Preamble
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_model open scoped RealInnerProductSpace
Formal statement
namespace AdaptiveCubic.FirstOrder
/-- Lemma 4.2, p. 11 (Cartis, Gould & Toint, ARC Part II, preprint rev. 15 Sep 2009; = Part I,
Lemma 3.3). If `s_k` satisfies (4.1), `g_kᵀ s_k + s_kᵀ B_k s_k + σ_k‖s_k‖³ = 0`, and (4.2),
`s_kᵀ B_k s_k + σ_k‖s_k‖³ ≥ 0`, then `f(x_k) − m_k(s_k) ≥ (1/6) σ_k ‖s_k‖³` (4.4). -/
theorem lemma_4_2 {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(B : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
(σ : ℝ) (x sk : EuclideanSpace ℝ (Fin n))
(h41 : ⟪gradient f x, sk⟫ + ⟪sk, B sk⟫ + σ * ‖sk‖ ^ 3 = 0)
(h42 : 0 ≤ ⟪sk, B sk⟫ + σ * ‖sk‖ ^ 3) :
1 / 6 * σ * ‖sk‖ ^ 3 ≤ f x - AdaptiveCubic.Cauchy.model f B σ x sk := by sorry
end AdaptiveCubic.FirstOrder
Source
Cartis, Gould & Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II, preprint rev. 15 Sep 2009 (UNamur), p. 11, Lemma 4.2, (4.4) (= Part I, Lemma 3.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.