Theorem 6.4 — a convergence criterion for nonmonotone sequences
ProvedNumStochOpt.Nonstationary.theorem_6_4_nonmonotone_convergence_criterionLet be closed and let be a sequence in such that:
- for all , with compact;
- for every subsequence with :
- (a) if , then as ;
- (b) if , then for every sufficiently small and every the exit time
is finite; 3. there is a continuous function taking at most countably many values on such that, in the situation of (2)(b),
Then the sequence converges, and every accumulation point of belongs to .
The criterion replaces monotone decrease of a Lyapunov function by the requirement that the sequence leave any neighbourhood of a non-solution with a lower value of ; it applies to essentially nonmonotone procedures such as the nonstationary method (6.41), where Zangwill-type conditions are hard to verify. The book cites the proof to Ermoliev's 1976 monograph [5, p. 181].
Formalization Note The page prints (2)(b) as "", which no sequence satisfies. The proof of Theorem 6.3 (pp. 155–156) shows what is intended: is the first index from on with , and (2)(b) asserts ; that is the reading formalized. "For sufficiently small and for any " is read as: there is such that for all and all ; condition (3) is required for the same . The left-hand limit of (3) is read as a (the proof of Theorem 6.3 prints ); the right-hand limit exists and equals by continuity of , and is written so. The real is well defined because is bounded on the compact set . Subsequences are strictly increasing index maps with ; accumulation points are cluster points of the sequence along atTop.
import Mathlib import Definitions.Def_NumStochOpt_Nonstationary_ExitTime open Filter Topology
namespace NumStochOpt.Nonstationary
/-- Theorem 6.4 (Ermoliev, Ch. 6 of Ermoliev & Wets (1988), p. 155, citing [5, p. 181]): a
convergence criterion for nonmonotone sequences. Let `X* ⊆ ℝⁿ` be closed and `(x^s)` a sequence
in `ℝⁿ` such that
(1) all `x^s` lie in a compact set `K`;
(2) for every subsequence `x^{s_k} → x'`:
(a) if `x' ∈ X*` then `‖x^{s_k+1} - x^{s_k}‖ → 0`;
(b) if `x' ∉ X*` then for all sufficiently small `ε > 0` and every `k` the exit time
`τ_k = min {s ≥ s_k | ‖x^s - x^{s_k}‖ > ε}` is finite, and
(3) for a continuous `V` taking at most countably many values on `X*`,
`limsup_k V(x^{τ_k}) < lim_k V(x^{s_k}) = V(x')`.
Then `V(x^s)` converges and every accumulation point of `(x^s)` lies in `X*`.
The page prints `τ_k = min{s | s ≥ s_k, ‖x^{s_k} - x^s‖ < ε} > ∞`; the reading used is the
one the proof of Theorem 6.3 (pp. 155–156) verifies. -/
theorem theorem_6_4_nonmonotone_convergence_criterion {n : ℕ}
(Xstar K : Set (EuclideanSpace ℝ (Fin n))) (x : ℕ → EuclideanSpace ℝ (Fin n))
(V : EuclideanSpace ℝ (Fin n) → ℝ)
(hXstar : IsClosed Xstar)
(hK : IsCompact K) (hxK : ∀ s, x s ∈ K)
(h2a : ∀ (φ : ℕ → ℕ) (x' : EuclideanSpace ℝ (Fin n)), StrictMono φ →
Tendsto (x ∘ φ) atTop (𝓝 x') → x' ∈ Xstar →
Tendsto (fun k => ‖x (φ k + 1) - x (φ k)‖) atTop (𝓝 0))
(hV : Continuous V) (hVcount : (V '' Xstar).Countable)
(h2b3 : ∀ (φ : ℕ → ℕ) (x' : EuclideanSpace ℝ (Fin n)), StrictMono φ →
Tendsto (x ∘ φ) atTop (𝓝 x') → x' ∉ Xstar →
∃ ε₀ : ℝ, 0 < ε₀ ∧ ∀ ε : ℝ, 0 < ε → ε < ε₀ →
(∀ k, ∃ s, φ k ≤ s ∧ ε < ‖x s - x (φ k)‖) ∧
limsup (fun k => V (x (exitTime x (φ k) ε))) atTop < V x') :
(∃ L : ℝ, Tendsto (fun s => V (x s)) atTop (𝓝 L)) ∧
∀ x' : EuclideanSpace ℝ (Fin n), MapClusterPt x' atTop x → x' ∈ Xstar := by sorry
end NumStochOpt.Nonstationary
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.