Find zero of simple monotonic function where the independent variable can only be integer
1 visualizzazione (ultimi 30 giorni)
Mostra commenti meno recenti
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
0 Commenti
Risposte (2)
Torsten
il 20 Set 2024
Modificato: Torsten
il 20 Set 2024
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.
2 Commenti
Jeff Miller
il 22 Set 2024
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.
John D'Errico
il 21 Set 2024
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.
0 Commenti
Vedere anche
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!