Let’s say I have a continuous (even smooth) function f(x) which is defined on the whole real line. Now, I want to know whether f(x) has a zero in [0, ∞).
I can say for sure that if it has a zero on this ray, this zero must lie in [0,a) for an a > 0 that I know. But how can I check that there is at least one ? When I do not care about the exact location of the zero.
So far, I tried doing this with the Roots.jl package. But if I use Brent’s algorithm with a bracketing interval [c,d], this requires that I know f(c) * f(d) < 0. So that I already know that such a zero exists. Using find_zero with an initial guess could fail, or give me a root in (- ∞, 0).
Later, I would like to incorporate this into my optimization routine, where I use autodifferentiation. So try and catch statements with find_zero will not work.
I can also relatively easily compute uniform bounds on f(x) and its derivatives by constants on [0,a).
Unfortunately, I cannot supply a closed form of f(x), as it will vary based on the run.
It can be a polynomial, or a polynomial + a neural network.
Thanks in advance for any help !
In general it is impossible to assure that a function has a zero, or a minimum, in any interval. The function can, for instance, be constant everywhere except in a very, very, narrow interval where it assumes a shape that provides it with a zero or a minimum, like so:
The function must have some provable property that allows to demonstrate it has the minimum or the zero in the interval. Being smooth is not enough.
Maybe I edited this too late, Sorry about that. But I can also compute explicit bounds on the derivative on [0,a). So that in your example, if I can say |f(x_0)| = 1 at some point x_0, and |f'(x)| <= M for a constant M, then there cannot be a zero in the interval [x_0, x_0 + 1/M). So that ridge in your example could not be arbitrarily small. And I guess that based on the structure f(x) = polynomial(x) or polynomial(x) + NN(x), the derivative should be only zero at a limited number of points (based on degree of the polynomial and size of the NN). That’s why I think this should be computable.
As the math tea kettle joke goes (see internet for details), you can look for a minimum and a maximum of f(x) in [0,a) and if they are of different signs, use Brent’s algorithm you mentioned.
The benefit may be that packages are much more oriented towards this optimization goal (?).
Another idea in this vein, minimize the square of f(x) and if strictly positive, no zero (if accepting soundness of minimization given constraints).
Those are pretty good ideas. But my algorithm gives wrong results when a zero is not detected. And optimizers could always get stuck in local optima. I implemented another function that is maybe much slower, but should be hopefully more reliable.
function has_zero(f::Function, a_limit::Float64, b_limit::Float64, M::Float64)
# First, extract the possible intervals which contain all the roots
Interval_vec = roots(f, a_limit, b_limit)
if length(Interval_vec) == 0
return false
end
for interval in Interval_vec
x_start = interval.interval.lo
x_end = interval.interval.hi
while x_start <= x_end
if abs(f(x_start)) < 10^(-10)
return true
end
current_deriv = Zygote.gradient(f,x_start)[1]
# Check if there is a sign change nearby
if f(x_start)*f(x_start + abs(f(x_start)/current_deriv)) < 0
return true
end
x_start += floor(abs(f(x_start))/M)
end
end
return false
end
using also the idea from @juliohm. But if it turns out that this conflicts with Zygote, I think I will use your ideas @Dan :). Here M should be an upper bound on |f'(x)| on the whole interval. And a_limit and b_limit the interval boundaries.
