Proposition 10.1 -- iteration bound under a unique minimizer
ProvedDiscreteConvex.Algorithms.steepest_descent_unique_minimizer_boundalgorithmsdiscrete-convex-analysisoperations-research
Proposition 10.1 (p.282). If has a unique minimizer , the number of iterations in the steepest descent algorithm is bounded by , where is the initial vector found in step S0 — formalized as for any run of iterations, avoiding a division that need not land on an integer a priori (the book separately notes is always even, but this item does not need that fact to state the bound faithfully).
(Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.282, Proposition 10.1.)
Preamble
import Mathlib import Definitions.Def_DiscreteConvex_MConvexFunctions_MExchangeAxiom import Definitions.Def_DiscreteConvex_MConvexFunctions_ArgMin import Definitions.Def_DiscreteConvex_MConvexFunctions_DomZ import Definitions.Def_DiscreteConvex_Algorithms_IsSteepestDescentRun import Definitions.Def_DiscreteConvex_Algorithms_L1Dist
Formal statement
open DiscreteConvex.MConvexFunctions
namespace DiscreteConvex.Algorithms
/-- Proposition 10.1 (Murota, *Discrete Convex Analysis*, SIAM 2003, p.282). If `f` has a
unique minimizer `x*`, the number of iterations in the steepest descent algorithm is bounded
by `‖x⁰ - x*‖₁ / 2`, where `x⁰` is the initial vector found in step S0. -/
theorem steepest_descent_unique_minimizer_bound {V : Type*} [Fintype V] [DecidableEq V]
(f : (V → ℤ) → WithTop ℝ) (hf : MExchangeAxiom f) (xstar : V → ℤ)
(hxstar : ArgMin f = {xstar}) (x0 : V → ℤ) (hx0 : x0 ∈ DomZ f) (x : ℕ → V → ℤ) (N : ℕ)
(hrun : IsSteepestDescentRun f x0 x N) :
2 * N ≤ L1Dist x0 xstar := by sorry
end DiscreteConvex.Algorithms
Source
Murota, Discrete Convex Analysis, SIAM 2003, DOI 10.1137/1.9780898718508, p.282, Proposition 10.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.