Finding roots without knowing much about the function

Question

Consider solving numerically for roots:

$( x_0, y_0): f(x_0, y_0) = 0, g(x_0, y_0) = 0$

where you only know that

f, g continuously differentiable but the theoretical differentiation is not a possible. So for this rather take it as continuous only.

$ f_x(x,y) \leq 0$

$ g_y(x,y) \leq 0$.

$f_y $ and $g_x $are per se not known, they can be locally both weakly increasing or decreasing. f,g are interpolations on discretized Bellman iterations.

It is impossible to fall back on actual values of the derivatives or cross derivatives, but I suppose, locally, with bad accuracy, these could be computed.

I'm looking for any input w.r.t. how to attack this problem. As usual, performance is key. I'll be using Python, if someone wants to even point me at useful packages.

Answer 1

Since $f$ and $g$ are both differentiable, your problem sounds like a prime candidate for an inexact newton method. Particularly, you can formulate the jacobian matrix by way of finite differences. Check out Nocedal and Wright's book on Numerical Optimization, particularly chapter 7 on practical approaches to calculating derivatives.

If necessary, you may also want to implement a globally convergent strategy, like line-searching or trust-region methods.