§5, (5.5)–(5.8), pp. 13–14 — the data (5.2)–(5.4) may be generated by ARC, every iteration very successful
ProvedSlowConvergence.ARC.arc_step_conditionscubic-regularizationlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let , and let and the cubic model be the data of the example. Then for every :
- (5.5) ;
- (5.6) ;
- (5.7) and ;
- , and hence (5.8) ;
- the cubic model is globally minimized exactly at :
- .
Items 4 and 5 say that the ratio of achieved to predicted decrease is and the predicted decrease is positive, so every iteration of ARC on a function with these values, gradients and Hessians at the iterates is very successful, whatever the algorithm's parameters.
Formalization Note The paper writes "for all "; the same computation holds at , which the goal needs, so the statement is for all . "Globally minimized exactly" (the paper's reading of (5.5)–(5.6) in one dimension) is stated directly as item 5. The model uses the prescribed values , , in place of , , , as condition (3.1) requires.
Preamble
import Mathlib import Definitions.Def_SlowConvergence_ARC_Data
Formal statement
namespace SlowConvergence.ARC
/-- Cartis, Gould & Toint, preprint 15 Oct 2009, §5, (5.5)–(5.8), pp. 13–14: the sequences (5.2)–(5.4)
may be generated by the ARC algorithm, every iteration being very successful. For `0 < τ < 1` and every
`k ≥ 0`, with `m_k` the cubic model (1.3) built from the prescribed data:
* (5.5) `g_k s_k + s_k H_k s_k + σ_k |s_k|³ = 0`;
* (5.6) `s_k H_k s_k + σ_k |s_k|³ ≥ 0`;
* (5.7) `σ_k > 0` and `σ_{k+1} ≤ σ_k`;
* p. 14: `m_k(x_k + s_k) = f_{4,k} − ⅔(1/(k+1))^{1+3η}`, and (5.8) `f_{4,k+1} = m_k(x_k + s_k)`;
* the cubic model is globally minimized exactly by `s_k`: `m_k(x_k + s_k) ≤ m_k(x_k + s)` for every `s`;
* `s_k = x_{k+1} − x_k ∈ (0, 1]`. -/
theorem arc_step_conditions (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (k : ℕ) :
gk τ k * sk τ k + sk τ k * Hk k * sk τ k + sigk k * |sk τ k| ^ 3 = 0 ∧
0 ≤ sk τ k * Hk k * sk τ k + sigk k * |sk τ k| ^ 3 ∧
0 < sigk k ∧ sigk (k + 1) ≤ sigk k ∧
dataModel τ k (sk τ k) = fk τ k - 2 / 3 * (1 / ((k : ℝ) + 1)) ^ (1 + 3 * eta τ) ∧
fk τ (k + 1) = dataModel τ k (sk τ k) ∧
(∀ s : ℝ, dataModel τ k (sk τ k) ≤ dataModel τ k s) ∧
sk τ k = xk τ (k + 1) - xk τ k ∧ 0 < sk τ k ∧ sk τ k ≤ 1 := by sorry
end SlowConvergence.ARC
Source
Cartis, Gould & Toint, On the complexity of steepest descent, Newton's and regularized Newton's methods, preprint 15 Oct 2009, pp. 13–14, §5, (5.5)–(5.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.