← All setups

Multi Step Anchored Cohypomonotone — Cohypomonotone Operator Inclusions

Descriptions may be stale. Consult the linked Lean sources.

Cohypomonotone Operator Inclusions · Lean proof

Cohypomonotone Operator Inclusions

We seek a zero of F+A on a real inner product space E, where F:E→E is L-Lipschitz and A:E⇉E is monotone. The sum is ρ-cohypomonotone, with L>0, ρ≥0, and ρL<1. A given point x0∈E is within distance R≥0 of a zero. The oracle returns exact values of F and resolvent evaluations of A. For ε>0, the goal is an output x¯∈E admitting ξ∈A(x¯) with ∥F(x¯)+ξ∥≤ε, almost surely under the law of the algorithm’s randomness.

The inclusion problem is to find x∈E such that 0∈F(x)+A(x), where F(x)+A(x)={F(x)+a:a∈A(x)}. Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The algorithm receives only E, L, ρ, and x0; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Lipschitz continuity and monotonicity). For every x,y∈E, ∥F(x)−F(y)∥≤L∥x−y∥. For every x,y∈E, a∈A(x), and b∈A(y), ⟨a−b,x−y⟩≥0.

Assumption 2 (Cohypomonotonicity). For every x,y∈E, a∈A(x), and b∈A(y), setting u=F(x)+a and v=F(y)+b, we have ⟨u−v,x−y⟩≥−ρ∥u−v∥2.

Assumption 3 (Resolvent access). There is a map J:R×E→E, written Jγ(z), such that, for every γ>0 and z∈E, z−Jγ(z)γ∈A(Jγ(z)). The oracle returns F(x) for a query x∈E, or Jγ(z) for a query (γ,z)∈R×E. These replies are exact. For γ≤0, the map Jγ is unrestricted. Both query types count toward the same oracle-call budget.

Assumption 4 (Initial distance). There exists x⋆∈E satisfying −F(x⋆)∈A(x⋆),∥x0−x⋆∥≤R.

After the allotted oracle calls, the output must satisfy ∃ξ∈A(x¯)∥F(x¯)+ξ∥≤εP-a.s., where P is the law of the algorithm’s randomness. The required output is x¯; the residual witness ξ need not be returned.

Proved result

2+(2⋅⌈21−ρ⋅L⋅log⁡(161−ρ⋅L)⌉++3)⋅⌈16⋅L⋅R(1−ρ⋅L)⋅ε⌉+

OracleTemplate.Convergence LongTails.Setups.CohypomonotoneInclusion.spec OracleTemplate.CohypomonotoneInclusion.budget

Relevant previous results