Find zero of simple monotonic function where the independent variable can only be integer

This is a super simple problem, and I'm sure there is a simple answer. However, all my searching takes me to much more complicated descriptions of mixed-integer optimization, etc., and I don't understand what I am supposed to do. I suspect making an optimization variable may have something to do with the answer, but I can't figure it out.

I have a simple monotonic function in a single variable, call it x, that returns a real number, call it y, and the function passes through y = 0. It doesn't matter what it is. Call it y = x - 5 (but, obviously, mine isn't expressible in closed form and doesn't have such a simple answer) I want to find x such that y is as close to zero as possible. (Think any of the variations of Newton's method. The function is very well behaved and there aren't many complications.) Here is the problem. X can only take on integer values. In fact the function doesn't make sense with real x. I could round the input and turn the function into something discontinuous on the real numbers, but, of course, solvers hate that. I know a million ways to do this for real x, but I can't figure out how to do it for integer x. In my case the possible values of x are bounded (1:1E9 or something). What is the simplest way to get MatLab to find a zero or a minimum bound or similar forcing the domain to be integer?

Thanks,

Mike

Answer 1

[Torsten]

If you know a lower integer value xl and an upper integer value xu with y(xl)*y(xu) < 0, you could do a binary search starting from the interval [xl,xu]. This should work since you claim that your function is monotonic.

Maybe your idea of rounding together with the secant method will be even faster.

[Michael Albert]

Torsten, thank you for your suggestion. That could certainly work. However, perhaps I should have been more clear. I can certainly solve the problem manually in a variety of ways. But, I need to do this process many times over large data sets, and I would like to find an efficient method. For example, if I had a continuous function, writing my own Levenberg-Marquardt algorithm in MatLab script with for loops could never come close to the speed of fzero or fminbnd. MatLab and the Optimization toolbox have a huge array of fast compiled functions that do this sort of thing. Is there a smartest speediest most computationally efficient way to use MatLab's optimization tools to do this type of problem?

For example, one approach I thought of: the function is called with a real number R. I evaluate the function at the floor(R) and floor(R) +1. Then I return a linearly interpolated value between the two answers. This makes my discrete function appear to be continuous and all optimization routines (fzero, fminbnd, etc.) might work. I don't love this for two reasons. First, while this function is continuous, the derivatives are not, which isn't great for optimization. Also, this seems terribly inefficient, and I just know there is some obvious MatLab function or approach that is built for this type of problem.

[Jeff Miller]

FWIW, I have used exactly your "one approach I thought of" method several times (even in 2 dimensions) and always found that it works well.

Answer 2

[John D'Errico]

@Michael Albert

No. You just THINK there is some obscure MATLAB function to solve your problem. You do not know that to be the case, because there is not. You just want there to be an existing code to solve your problem.

Can you write some version of Levenberg-Marquardt? Of course not, since it would require computing a derivative.

My suggestion would be to use a guarded method, where you start with two points that bracket the solution. (Much like fzero.)

Now try to use a secant method, where simple linear interpolation is employed between those points, rounding the new identified point at each step. If the new point chosen is too close to either endpoint, then you want to resort to ideas like modified regula falsi, or even bisection. Again, at each step, you will need to round the result. But the idea of a guarded scheme is important, since it will be able to converge well in regions where the function allows it, but it has the ability to handle the bad cases robustly.

Essentially, you almost want a version of fzero that worries about an integer independent variable. That is because fzero is the code you would want to use, except fzero is not designed to work with integers.