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 on a finite-dimensional real
inner product space . The map and
its derivative are Lipschitz. A root satisfies the weak Minty
inequality for every , where , and a given starting point
lies within distance of this root. The oracle returns
either or its derivative at
the queried point . For , the goal is an output
with almost
surely under , the law of the
algorithm’s randomness.
The root-finding problem is to find such that Write
for the Fréchet
derivative of at . The norm is induced by the inner product
on , and denotes the
induced operator norm. The parameters satisfy The algorithm receives , , , , , and ; the radius may enter only the oracle-call
budget.
Our assumptions:
Assumption 1 (Lipschitz map and derivative). The map
is Fréchet differentiable
everywhere on , and, for all ,
Assumption 2 (Weak Minty root and initial distance).
There exists such that
At any point , the
algorithm may request either the exact value or the exact linear operator . 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
Proved result
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.