4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Is $f(-1,y)\leq 0\leq f(1,y)$ supposed to be $f(-1,y)_1 \leq 0\leq f(1,y)_1$? $\endgroup$ Apr 16 at 15:34
  • $\begingroup$ Shouldn't the running time also depend on the Lipschitz constant? $\endgroup$
    – Chao Xu
    Apr 16 at 17:05
  • $\begingroup$ This probably answers the question: link.springer.com/chapter/10.1007/11561071_78 $\endgroup$
    – Chao Xu
    Apr 16 at 21:19
  • $\begingroup$ @mathworker21 yes, fixed. $\endgroup$ Apr 17 at 9:24
  • $\begingroup$ @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. $\endgroup$ Apr 17 at 11:54

1 Answer 1

3
+50
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Apr 23 at 17:20
  • $\begingroup$ @ErelSegal-Halevi Wow, thank you, I am honored. My name is Chester Lawrence (I have no affiliations nor grants to thank). $\endgroup$ Apr 27 at 6:41
  • $\begingroup$ I sent you a draft - did you get it? $\endgroup$ May 24 at 20:32
  • $\begingroup$ @ErelSegal-Halevi I just checked my spam and it was there. I'll look now. $\endgroup$ May 24 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.