Cohypomonotone Newton Acceleration — Cohypomonotone Root Finding
Descriptions may be stale. Consult the linked Lean sources.
Cohypomonotone Root Finding · Lean proof
Cohypomonotone
Root Finding
We consider finding a zero of a differentiable map on a finite-dimensional real
inner product space . The map is
-cohypomonotone, where , and its derivative is -Lipschitz in operator norm, where . A given starting point lies within distance of a zero of . The oracle returns at . For a tolerance , the goal is an output
satisfying almost
surely under , the law of the
algorithm’s randomness.
The root-finding problem is to find such that Write
for the
inner product and for its
induced norm; denotes the
induced operator norm for linear maps from to . The algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Lipschitz derivative). The map is Fréchet differentiable everywhere on
, with derivative , and
Assumption 2 (Cohypomonotonicity). For every ,
Assumption 3 (Initial distance to a zero). There
exists such that
Queries may be made at any point of , and both components of the oracle
reply are exact. After the allotted oracle calls, the output must
satisfy the residual criterion
Proved result
OracleTemplate.Convergence LongTails.Setups.CohypomonotoneNewton.spec
LongTails.Theorems.CohypomonotoneNewtonAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.