Lemma 4.2 — (4.1) and (4.2) give the model decrease σ_k‖s_k‖³/6
ProvedAdaptiveCubic.SecondOrder.lemma_4_2cubic-regularisationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Suppose the step satisfies (4.1), , and (4.2), . Then
This is the decrease of the model that every ARC(S) step achieves, and it is the link between the step length and the decrease of in all complexity bounds for ARC(S).
Preamble
import Mathlib import Definitions.Def_AdaptiveCubic_Cauchy_model open scoped RealInnerProductSpace
Formal statement
namespace AdaptiveCubic.SecondOrder
/-- 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.SecondOrder
Source
Cartis, Gould & Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II, preprint rev. 15 Sep 2009 (UNamur), p. 11, Lemma 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.