Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions:
- For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is monotonically-increasing with $x$.
- For all $x\in [-1,1]$: $~~~~f(x,-1)_2\leq 0\leq f(x,1)_2$, and $f(x,y)_2$ is monotonically-increasing with $y$.
The Poincare-Miranda theorem guarantees that $f$ has a root -- a point $(x,y)$ for which $|f(x,y)|=0$.
I am interested in computing an $\epsilon$-root of $f$ -- point $(x,y)$ for which $|f(x,y)|\leq \epsilon$. The number of function evaluations should be polynomial in $\log_2(1/\epsilon)$ --- the binary representation of $\epsilon$ (where the Lipschitz constant is considered a fixed parameter). Is it possible?
To motivate the question, here are some related results.
If the function is one-dimensional (from $[-1,1]$ to itself), then the bisection method can be used to find $\epsilon$-root of $f$ using $O(\log(1/\epsilon))$ evaluations. This is true even without the monotonicity conditions.
Without the monotonicity conditions, finding an $\epsilon$-root is computationally equivalent to finding an $\epsilon$-fixed-point. It is known that finding an $\epsilon$-fixed-point in two dimensions might require $\Omega(1/\epsilon)$ evaluations, that is, the number of evaluations is exponential in the binary representation of $\epsilon$. (I asked about it in this cs.SE post.)
Can the monotonicity condition make the two-dimensional problem polynomial in $\log(1/\epsilon)$?
I am also interested in references to other conditions, similar to monotonicity, that make the two-dimensional problem polynomial in $\log(1/\epsilon)$.