Homotopy Newton Monotone — Monotone Roots with Lipschitz Second Derivatives
Descriptions may be stale. Consult the linked Lean sources.
Monotone Roots with Lipschitz Second Derivatives · Lean proof
Monotone Roots
with Lipschitz Second Derivatives
We consider finding a zero of a twice continuously differentiable
monotone map on a
finite-dimensional real inner product space . Its second derivative is -Lipschitz, where . A given point satisfies ,
where , and lies within
distance of a zero . Here primes denote Fréchet
derivatives and denotes the
induced operator norm. Two oracles return and , respectively. 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 The
norm is induced by the
inner product on . The derivative
is a linear map from
to , and is a bilinear map from
to ; their norms are the induced operator
norms. The algorithm receives ,
, , , , and .
Our assumptions:
Assumption 1 (Monotonicity). For every ,
Assumption 2 (Lipschitz second derivative). The map
is twice continuously Fréchet
differentiable on , and
Assumption 3 (Initial bounds). There exists such that
Both oracles are exact and may be queried at any point of . Calls to the value oracle and the
derivative oracle are counted separately. After the allotted calls, the
output must satisfy the residual criterion
Proved result
OracleTemplate.Convergence LongTails.Setups.UnconstrainedLipschitzSecondDerivativeMonotone.spec
LongTails.Theorems.HomotopyNewtonMonotone.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.