← All setups

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 F:E→E on a finite-dimensional real inner product space E. Its second derivative is L-Lipschitz, where L>0. A given point x0∈E satisfies ∥F′(x0)∥op≤H0, where H0≥0, and lies within distance D>0 of a zero x⋆. Here primes denote Fréchet derivatives and ∥⋅∥op denotes the induced operator norm. Two oracles return F(x) and F′(x), respectively. 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. The norm ∥⋅∥ is induced by the inner product on E. The derivative F′(x) is a linear map from E to E, and F″(x) is a bilinear map from E×E to E; their norms are the induced operator norms. The algorithm receives E, x0, L, D, H0, and ε.

Our assumptions:

Assumption 1 (Monotonicity). For every x,y∈E, ⟨F(x)−F(y),x−y⟩≥0.

Assumption 2 (Lipschitz second derivative). The map F is twice continuously Fréchet differentiable on E, and ∥F″(x)−F″(y)∥op≤L∥x−y∥,x,y∈E.

Assumption 3 (Initial bounds). There exists x⋆∈E such that F(x⋆)=0,∥x0−x⋆∥≤D,∥F′(x0)∥op≤H0.

Both oracles are exact and may be queried at any point of E. Calls to the value oracle and the derivative oracle are counted separately. After the allotted calls, the output must satisfy the residual criterion ∥F(x¯)∥≤εP-a.s.

Proved result

Oracle 0:⌈221⋅(1+(L⋅D3ε)14)⋅(log⁡(2+H0⋅Dε+L⋅D3ε))2⌉+ Oracle 1:⌈221⋅(1+(L⋅D3ε)14)⋅(log⁡(2+H0⋅Dε+L⋅D3ε))2⌉+

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.