# Computing an approximate root of a two-dimensional monotone function

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.

1. 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.

2. 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)$$.

• Is $f(-1,y)\leq 0\leq f(1,y)$ supposed to be $f(-1,y)_1 \leq 0\leq f(1,y)_1$? Apr 16 at 15:34
• Shouldn't the running time also depend on the Lipschitz constant? Apr 16 at 17:05
• @mathworker21 yes, fixed. Apr 17 at 9:24
• @ChaoXu yes, the runtime also depends on the Lipschitz constant. For simplicity, I assumed that it is a fixed constant. The paper you linked to is very interesting, but it considers functions from a 2-dimensional array to $\mathbb{R}$, not to to $\mathbb{R}^2$. Also, the property of monotonicity is defined differently. Apr 17 at 11:54

Yes, it's possible with $$O\left(\log^2(1/\epsilon)\right)$$ function evaluations.

We write $$f = (f_1,f_2)$$, so in your notation, e.g. $$f_1(x,y) := f(x,y)_1$$. By replacing $$f_1$$ with $$(x,y) \mapsto f_1(x,y)+\epsilon x$$ and $$f_2$$ with $$(x,y) \mapsto f_2(x,y)+\epsilon y$$ (at the unimportant cost of changing $$\epsilon$$ to, say, $$4\epsilon$$), we may assume that $$f_1$$ and $$f_2$$ are strictly increasing.

The key is that the monotonicity assumptions imply that the function $$g : [-1,1] \to [-1,1]$$ given by $$g(y) := f_2(x_y,y)$$ is continuous, where $$x_y$$ is the unique solution to $$f_1(x_y,y) = 0$$ (which exists since $$f_1$$ is strictly increasing and has $$f_1(-1,y) \le 0 \le f_1(1,y)$$).

Indeed, it suffices to show that $$x_{y_n} \to x_y$$ whenever $$y_n \to y$$ (since $$f_2$$ is continuous). If, for contradiction, there were some $$\delta > 0$$ and some subsequence $$(y_{n_k})_k$$ of $$(y_n)_n$$ with $$x_{y_{n_k}} > x_y+\delta$$ for all $$k$$, then $$0 = f_1(x_{y_{n_k}},y_{n_k}) \ge f_1(x_y+\delta,y_{n_k}) \to f_1(x_y+\delta,y) > f_1(x_y,y) = 0,$$ where the limit is taken as $$k \to \infty$$. The similar argument works for the case of some $$\delta > 0$$ and some subsequence $$(y_{n_k})_k$$ with $$x_{y_{n_k}} < x_y-\delta$$ for all $$k$$.

Now that we know $$g(y)$$ is continuous, the bound $$O\left(\log^2(1/\epsilon)\right)$$ follows relatively straightforwardly from the bisection method. Indeed, for any fixed value of $$y$$, the bisection method allows us to approximate $$x_y$$ up to an additive error of $$\pm \epsilon$$, with $$O\left(\log(1/\epsilon)\right)$$ function evaluations. Because $$f_2$$ is Lipschitz, this allows us to calculate $$g(y)$$ up to an additive error of $$\pm O(\epsilon)$$, which is sufficient to make the bisection method applied to the one-dimensional function $$g$$ work as needed, with $$O\left(\log(1/\epsilon)\right)$$ function evaluations of $$g(y)$$.

• Thanks! I am working on a paper that proves a slightly more generalized result (without the continuity condition), and some applications. I will be happy to add you as a co-author. By what name can I add you? Apr 23 at 17:20
• @ErelSegal-Halevi Wow, thank you, I am honored. My name is Chester Lawrence (I have no affiliations nor grants to thank). Apr 27 at 6:41
• I sent you a draft - did you get it? May 24 at 20:32
• @ErelSegal-Halevi I just checked my spam and it was there. I'll look now. May 24 at 22:42