(4.4), p. 10 (corrected) — Algorithm 4.1 starts at most (⌊3(f(x₀) − inf f)/(δε)⌋ + 1)·16L²/ε² line searches
ProvedNonconvexCost.Complexity.eq_4_4Let , let , let be bounded below on , let be an -bounded map (, ), and let satisfy
Let be a Goldstein subgradient. Then for every , the number of line searches started during the first steps of the run of Algorithm 4.1 from is at most
A line search starts at a step where the run is at the subgradient test with and the trial point fails the sufficient-decrease test.
This bounds the number of line searches by the number of phases between reductions times the number of shortening steps per phase.
Formalization Note Corrected. The paper prints , which is when ; but a run started with at a minimiser where the trial step fails starts a line search at once. The proof on p. 10 gives at most reductions, hence that many plus one phases; the statement uses this count. "" is the infimum over .
import Mathlib import Definitions.Def_NonconvexCost_Complexity_Setting import Definitions.Def_NonconvexCost_Complexity_Algorithm
namespace NonconvexCost.Complexity
open Classical in
theorem eq_4_4 {X : Type*} [NormedAddCommGroup X] [InnerProductSpace ℝ X]
(δ ε L : ℝ) (hδ : 0 < δ) (hε : 0 < ε) (C : Set X) (f : X → ℝ) (hbdd : BddBelow (f '' C))
(G : X → X → X) (hL : IsLBounded G L) (x0 : X) (hx0 : x0 ∈ C)
(hsub : ∀ x ∈ C, f x ≤ f x0 → ∀ y : X, ‖y‖ ≤ δ → x + y ∈ C)
(g0 : X) (hg0 : g0 ∈ goldstein G δ x0) (n : ℕ) :
(((Finset.range n).filter (fun j => StartsLineSearch f δ ε (run f G δ ε x0 g0 j))).card : ℝ) ≤
((⌊3 * (f x0 - sInf (f '' C)) / (δ * ε)⌋₊ : ℝ) + 1) * (16 * L ^ 2 / ε ^ 2) := by sorry
end NonconvexCost.Complexity
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.