Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.3 — lim⁡k→∞∥q(xk)∥=0\lim_{k\to\infty}\|q(x_k)\|=0limk→∞​∥q(xk​)∥=0 under the Strong Hypotheses

Proved
LewisTorczon.BoundPS.theorem_3_3

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

derivative-free-optimizationglobal-convergencep2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1pattern-search

Consider the bound constrained problem min⁡{f(x):ℓ≤x≤u}\min\{f(x):\ell\le x\le u\}min{f(x):ℓ≤x≤u} on Ω={ℓ≤x≤u}\Omega=\{\ell\le x\le u\}Ω={ℓ≤x≤u}, with ℓj<uj\ell_j<u_jℓj​<uj​ for every jjj (infinite bounds allowed), and let q(x)=P(x−∇f(x))−xq(x)=P(x-\nabla f(x))-xq(x)=P(x−∇f(x))−x, where PPP is the projection onto Ω\OmegaΩ. Let xk,Δk,sk,Ckx_k,\Delta_k,s_k,C_kxk​,Δk​,sk​,Ck​ be a run of the generalized pattern search method for bound constrained minimization (Algorithm 1 with Algorithm 2). Suppose that

  1. LΩ(x0)={x∈Ω:f(x)≤f(x0)}L_\Omega(x_0)=\{x\in\Omega:f(x)\le f(x_0)\}LΩ​(x0​)={x∈Ω:f(x)≤f(x0​)} is compact;
  2. fff is continuously differentiable on an open set containing Ω\OmegaΩ;
  3. the columns of the generating matrices CkC_kCk​ are uniformly bounded in norm;
  4. lim⁡k→∞Δk=0\lim_{k\to\infty}\Delta_k=0limk→∞​Δk​=0;
  5. the run enforces the Strong Hypotheses on Bound Constrained Exploratory Moves.

Then

lim⁡k→∞∥q(xk)∥=0.\lim_{k\to\infty}\|q(x_k)\|=0 .k→∞lim​∥q(xk​)∥=0.

Since q(x)=0q(x)=0q(x)=0 exactly at stationary points of the bound constrained problem, every limit point of the iterates is then a stationary point: the whole sequence, not just a subsequence, approaches first-order stationarity.

Formalization Note Two departures from the page, both disclosed in the mission description. (i) The page assumes fff continuously differentiable on LΩ(x0)L_\Omega(x_0)LΩ​(x0​); here it is assumed on an open set U⊇ΩU\supseteq\OmegaU⊇Ω, which the proof needs (it uses ∇f\nabla f∇f at trial points in Ω\OmegaΩ outside LΩ(x0)L_\Omega(x_0)LΩ​(x0​), and LΩ(x0)L_\Omega(x_0)LΩ​(x0​) may have empty interior). (ii) The third Strong Hypothesis is encoded with "≤\le≤" instead of the printed "<<<" (the printed strict form excludes the paper's own examples; "≤\le≤" is the weaker hypothesis). Norms are Euclidean.

Preamble
import Mathlib
import Definitions.Def_LewisTorczon_BoundPS_Box
import Definitions.Def_LewisTorczon_BoundPS_ProjQ
import Definitions.Def_LewisTorczon_BoundPS_GPS
Formal statement
namespace LewisTorczon.BoundPS

/-- **Theorem 3.3**, p. 7: if `L_Ω(x_0)` is compact, `f` is `C¹`, the columns of the generating
matrices are uniformly bounded in norm, `Δ_k → 0`, and the method enforces the Strong Hypotheses
on Bound Constrained Exploratory Moves, then `‖q(x_k)‖ → 0`. -/
theorem theorem_3_3 {n m : ℕ} (P : GPSParams n) (lo hi : Fin n → EReal)
    (hlohi : ∀ j, lo j < hi j) (f : EuclideanSpace ℝ (Fin n) → ℝ)
    (U : Set (EuclideanSpace ℝ (Fin n))) (hU : IsOpen U) (hΩU : box lo hi ⊆ U)
    (hf : ContDiffOn ℝ 1 f U) (R : GPSRun n m) (hR : IsGPSRun P lo hi f R)
    (hcpt : IsCompact (levelSet lo hi f (R.x 0))) (hbdd : BoundedCols R)
    (hΔ : Filter.Tendsto R.Δ Filter.atTop (nhds 0)) (hstrong : StrongHyp P lo hi f R) :
    Filter.Tendsto (fun k => ‖projQ lo hi f (R.x k)‖) Filter.atTop (nhds 0) := by sorry

end LewisTorczon.BoundPS
Source
Lewis & Torczon, Pattern Search Algorithms for Bound Constrained Minimization, ICASE Report No. 96-20 (NASA CR-198306), March 1996, p. 7, Theorem 3.3 (proof in §4.2, p. 11)
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me