§6, p. 80 (display) — under (2.7), w(π^j) → w* = max w = w(π*)
ProvedHeldWolfeCrowder.CoreProblem.tendsto_maxconvergencep2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1piecewise-linearsubgradient-method
Let on be bounded above. Let be generated by the subgradient algorithm (2.6), , where attains the minimum in (2.2) at , from an arbitrary , with positive step sizes satisfying (2.7): and . Then attains its maximum at some point , and
The paper quotes this convergence theorem from Poljak [20, 21] and does not prove it. It is the analytic input of Section 6: Theorem 6.1 and Theorem 6.3 both rest on it. Boundedness of the iterates is not assumed here.
Formalization Note " bounded above" is the paper-wide standing assumption (p. 64). The choice of among minimizing indices is arbitrary.
Preamble
import Mathlib import Definitions.Def_HeldWolfeCrowder_CoreProblem_Setting
Formal statement
namespace HeldWolfeCrowder.CoreProblem
open scoped InnerProductSpace
open Filter Topology
/-- **Held, Wolfe & Crowder (1974), §6, p. 80 (display), citing Poljak [20, 21].** If `w` is
bounded above and `{π^j}` is generated by (2.6) with positive step sizes satisfying (2.7), then
`w` attains its maximum at some `π*` and `lim_{j→∞} w(π^j) = w* = max w = w(π*)`.
No boundedness of `{π^j}` is assumed. -/
theorem tendsto_max {n : ℕ} {ι : Type*} [Fintype ι] [Nonempty ι]
(c : ι → ℝ) (v : ι → EuclideanSpace ℝ (Fin n)) (hw : BddAbove (Set.range (w c v)))
(t : ℕ → ℝ) (π : ℕ → EuclideanSpace ℝ (Fin n)) (k : ℕ → ι)
(hrun : IsSubgradientRun c v t π k) (ht : StepSizeCond t) :
∃ πstar : EuclideanSpace ℝ (Fin n), (∀ π', w c v π' ≤ w c v πstar) ∧
Tendsto (fun j => w c v (π j)) atTop (𝓝 (w c v πstar)) := by sorry
end HeldWolfeCrowder.CoreProblem
Source
Held, Wolfe & Crowder, Validation of subgradient optimization, Math. Programming 6 (1974), p. 80, §6 (display), citing Poljak [20, 21]; p. 64 (existence of π*)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.