Theorem A.10 — global minimization with a known term
OpenHOTrap.Supplement.theorem_A_10approximation-theoryglobal-optimizationinterpolationoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let with and . Let , , , , let on a neighborhood of , and let be a known continuous function on .
For every , a nonadaptively chosen set exists with
There are explicit coefficient functions , smooth near , with finite positive stability constant
If supplied values satisfy , then the model satisfies . Every -approximate minimizer of satisfies
Constructing and optimizing the model and evaluating use no further query to .
Differences from the source:
- encoding: sup-norm and attained-minimum notation → pointwise inequalities for every ; reason: equivalent because the nondegenerate rectangle is nonempty compact and all functions involved are continuous
- encoding: “explicit coefficient functions” → existential coefficient functions quantified before the unknown , known term , and supplied data; reason: a Lean witness supplies the construction while the quantifier order enforces nonadaptive independence
- encoding: together with the displayed division by → is recorded explicitly; reason: the constructed Lagrange family has , and positivity excludes the undefined zero-denominator reading
- encoding: with coordinates →
EuclideanSpace ℝ (Fin k)with zero-based coordinates; reason: this is the same finite-dimensional Euclidean space and product rectangle
Preamble
import Mathlib import Definitions.Def_HOTrap_HolderNear import Definitions.Def_HOTrap_Supplement_hyperrectangle
Formal statement
namespace HOTrap.Supplement
/-- **Theorem A.10 (global minimization with a known term).** Zhou--Sugiyama--Suzuki,
*Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order
Lower Bounds*, arXiv:2610.02791, Theorem A.10, p.64 (PDF p.67), Eq. (71).
The node set and coefficient functions occur before `f,q` and the supplied values, expressing the
paper's nonadaptive sampling. The reconstructed model is the displayed finite sum, and every
`δ/2`-approximate minimizer of it plus the known term is `δ`-optimal for `f+q`.
**Formalization Note.** The universal constant is before the rectangle, `D,L_p,δ,f,q`, so it
depends only on `k,p,β`. Uniform errors and approximate minima are written pointwise over `Y`,
which is equivalent to the paper's sup norm and attained minimum on this nonempty compact
rectangle. Positivity of `Λ₀` is included as an existential property of the constructed stable
basis, making `δ/(8Λ₀)` nondegenerate. The model uses only supplied values after the one batch. -/
theorem theorem_A_10 (k p : ℕ) (hk : 1 ≤ k) (hp : 1 ≤ p) (β : ℝ)
(hβ0 : 0 < β) (hβ1 : β ≤ 1) :
∃ C : ℝ, 0 < C ∧
∀ (a b : Fin k → ℝ), (∀ i, a i < b i) →
∀ D L δ ν : ℝ, 0 ≤ L → 0 < δ → ν = (p : ℝ) + β →
Metric.diam (hyperrectangle a b) ≤ D →
∃ (V : Finset (EuclideanSpace ℝ (Fin k)))
(Lv : EuclideanSpace ℝ (Fin k) → EuclideanSpace ℝ (Fin k) → ℝ) (Λ₀ : ℝ),
(∀ v ∈ V, v ∈ hyperrectangle a b) ∧
(V.card : ℝ) ≤ C * max 1
(D ^ k * Real.rpow (L / δ) ((k : ℝ) / ν)) ∧
(∀ v ∈ V, ∃ U : Set (EuclideanSpace ℝ (Fin k)),
hyperrectangle a b ⊆ U ∧ IsOpen U ∧ ContDiffOn ℝ ⊤ (Lv v) U) ∧
0 < Λ₀ ∧
Λ₀ = sSup (Set.range (fun y : {y // y ∈ hyperrectangle a b} =>
∑ v ∈ V, |Lv v y|)) ∧
∀ (f q : EuclideanSpace ℝ (Fin k) → ℝ),
HOTrap.HolderNear (hyperrectangle a b) p β L f →
ContinuousOn q (hyperrectangle a b) →
∀ τ : ℝ, 0 ≤ τ → τ ≤ δ / (8 * Λ₀) →
∀ vals : EuclideanSpace ℝ (Fin k) → ℝ,
(∀ v ∈ V, |vals v - f v| ≤ τ) →
(∀ y ∈ hyperrectangle a b,
|(∑ v ∈ V, vals v * Lv v y) - f y| ≤ δ / 4) ∧
∀ yhat ∈ hyperrectangle a b,
(∀ y ∈ hyperrectangle a b,
(∑ v ∈ V, vals v * Lv v yhat) + q yhat ≤
(∑ v ∈ V, vals v * Lv v y) + q y + δ / 2) →
∀ y ∈ hyperrectangle a b, f yhat + q yhat - (f y + q y) ≤ δ := by sorry
end HOTrap.Supplement
Source
Zhou–Sugiyama–Suzuki, Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds, arXiv:2610.02791, Theorem A.10, p.64, Eq. (71)