Theorem 2.8 — level surfaces with ratio give with
ProvedShorNonsmooth.LinearRate.linear_rate_of_level_set_ratioLet be a convex function on with a unique minimum point , and let be any subgradient of at . For a starting point choose numbers and with
Let and assume that every pair of points with satisfies
Then the sequence generated by
converges to at a linear rate:
The theorem replaces the angle condition of Theorem 2.7 by a condition on the shape of the level surfaces of near the minimum: if they are not too oblong, the subgradient method with geometrically decreasing steps converges geometrically with ratio .
Formalization Note The book writes the stepsize rule for "", which would define from an undefined although is chosen; the rule is required for . The book's exception " for some , i.e. " is the stop of the method: the sequence then stays at , where (2.21) holds, so the bound is asserted for all .
import Mathlib import Definitions.Def_ShorNonsmooth_LinearRate_SubgradientMethod
namespace ShorNonsmooth.LinearRate
/-- Shor (1985), p. 32, **Theorem 2.8**. Let `f` be convex on `E_n` with unique minimum point
`x*`. For a starting point `x₀` let `σ ≥ √2` and `h₁ ≥ ‖x₀ - x*‖/σ`, let
`Y = {y : ‖y - x*‖ ≤ σ h₁}`, and assume (2.20): `‖x - x*‖ ≤ σ ‖z - x*‖` for every pair
`x, z ∈ Y` with `f(x) = f(z) ≠ f(x*)`. Then the normalized subgradient iterates with stepsizes
`h_{k+1} = h_k √(σ² - 1)/σ` (`k ≥ 1`) satisfy (2.21): `‖x_k - x*‖ ≤ h_{k+1} σ` for all `k`.
The book's exception "`g_f(x_k̄) = 0`, i.e. `x_k̄ = x*`" is the stop of the method; the stopped
sequence stays at `x*`, where the bound holds trivially. -/
theorem linear_rate_of_level_set_ratio {n : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(hf : ConvexOn ℝ Set.univ f) (xs : EuclideanSpace ℝ (Fin n)) (hxs : ShorNonsmooth.SubgradMethod.MinSet f = {xs})
(x₀ : EuclideanSpace ℝ (Fin n)) (σ : ℝ) (h : ℕ → ℝ)
(hσ : Real.sqrt 2 ≤ σ) (hh₁ : ‖x₀ - xs‖ / σ ≤ h 1)
(hY : ∀ x ∈ Metric.closedBall xs (σ * h 1), ∀ z ∈ Metric.closedBall xs (σ * h 1),
f x = f z → f x ≠ f xs → ‖x - xs‖ ≤ σ * ‖z - xs‖)
(hrec : ∀ k, 1 ≤ k → h (k + 1) = h k * (Real.sqrt (σ ^ 2 - 1) / σ))
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hg : ∀ x, ShorNonsmooth.AlmostDiff.IsSubgradient f x (g x)) :
∀ k, ‖ShorNonsmooth.SubgradMethod.normalizedIter g h x₀ k - xs‖ ≤ h (k + 1) * σ := by sorry
end ShorNonsmooth.LinearRate
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.