§3, (3.9)–(3.10), pp. 7–8 — the knot values and the pieces p_k, q_k are nonnegative, so is bounded below by zero
ProvedSlowConvergence.Newton.bounded_belowp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1worst-case-complexity
Let and . Define the knot values of the two coordinate functions by (3.9) and (3.10):
Then for every :
- and ;
- , where is the prescribed value (3.3);
- consequently ;
- the Hermite pieces are nonnegative on their intervals: for and for , where is the quintic (2.11) with coefficients (2.14) at and the quintic of pp. 7–8.
Since on the cell , items 1 and 4 give on the whole nonnegative quadrant where the page builds .
Each knot value is a tail of a convergent zeta series, which is why the decreasing sequence of function values stays above zero; this is the step " is bounded below by zero" of the example.
Preamble
import Mathlib import Definitions.Def_SlowConvergence_Newton_Data import Definitions.Def_SlowConvergence_Newton_Pieces open scoped RealInnerProductSpace
Formal statement
namespace SlowConvergence.Newton
/-- Cartis, Gould & Toint, preprint 15 Oct 2009, §3, (3.9)–(3.10), p. 7 and p. 8: "The fact that f_2 is
bounded below by zero results from (3.10) and the fact that ζ(2) = π²/6." For `0 < τ < 1` and every
`k ≥ 0`, the knot values `f_{2,1}([x_k]_1)` of (3.9) and `f_{2,2}([x_k]_2)` of (3.10) are nonnegative,
they add up to the prescribed value `f_k` of (3.3), and hence `f_k ≥ 0`. Moreover the pieces are
nonnegative on their intervals, `p_k ≥ 0` on `[0, µ_k]` and `q_k ≥ 0` on `[0, 1]`, so that
`f_2([x]_1, [x]_2) = p_k([x]_1 − [x_k]_1) + f_{2,1}([x_{k+1}]_1) + q_j([x]_2 − j) + f_{2,2}(j + 1) ≥ 0`
everywhere on the nonnegative quadrant where the page builds `f_2`. -/
theorem bounded_below (τ : ℝ) (hτ0 : 0 < τ) (hτ1 : τ < 1) (k : ℕ) :
0 ≤ f21knot τ k ∧ 0 ≤ f22knot k ∧ fk τ k = f21knot τ k + f22knot k ∧ 0 ≤ fk τ k ∧
(∀ t ∈ Set.Icc (0 : ℝ) (mu τ k), 0 ≤ p τ k t) ∧
(∀ t ∈ Set.Icc (0 : ℝ) 1, 0 ≤ q k t) := by sorry
end SlowConvergence.Newton
Source
Cartis, Gould & Toint, On the complexity of steepest descent, Newton's and regularized Newton's methods, preprint 15 Oct 2009, p. 7, §3, (3.9)–(3.10); p. 8, §3; (3.3), p. 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.