← All setups

Full Range Second Order Weak Minty — Second-Order Weak Minty Root Finding

Descriptions may be stale. Consult the linked Lean sources.

Second-Order Weak Minty Root Finding · Lean proof

Second-Order Weak Minty Root Finding

We seek a zero of a differentiable map F:E→E on a finite-dimensional real inner product space E. The map and its derivative are Lipschitz. A root x⋆ satisfies the weak Minty inequality ⟨F(x),x−x⋆⟩≥−(ρ/2)∥F(x)∥2 for every x∈E, where ρ≥0, and a given starting point x0 lies within distance R≥0 of this root. The oracle returns either F(x) or its derivative at the queried point x. For ε>0, the goal is an output x¯∈E with ∥F(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The root-finding problem is to find x∈E such that F(x)=0. Write J(x):E→E for the Fréchet derivative of F at x. The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The parameters satisfy L1>0,L2>0,ρL1<2. The algorithm receives E, L1, L2, ρ, ε, and x0; the radius R may enter only the oracle-call budget.

Our assumptions:

Assumption 1 (Lipschitz map and derivative). The map F is Fréchet differentiable everywhere on E, and, for all x,y∈E, ∥F(x)−F(y)∥≤L1∥x−y∥,∥J(x)−J(y)∥op≤L2∥x−y∥.

Assumption 2 (Weak Minty root and initial distance). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤R,⟨F(x),x−x⋆⟩≥−ρ2∥F(x)∥2for every x∈E.

At any point x∈E, the algorithm may request either the exact value F(x) or the exact linear operator J(x). Each request counts as one call toward a shared oracle-call budget; obtaining both at a point requires two calls. After the allotted calls, the output must satisfy ∥F(x¯)∥≤εP-a.s.

Proved result

⌈1048576⋅(1+L2⋅R2ε)⋅log⁡(21−ρ⋅L12)(1−ρ⋅L12)5⌉+

OracleTemplate.Convergence LongTails.Setups.WeakMintySecondOrder.spec
  OracleTemplate.WeakMintyHybrid.FullRangeSecondOrderWeakMinty.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.