5 ms·
Hobest question, why not just use a binary/ternary search? It's because there's no known a priori how many local maximum and/or minimums? Because that's just a
by frankreyes 3y ago
Hobest question, why not just use a binary/ternary search? It's because there's no known a priori how many local maximum and/or minimums?
Because that's just an iterative/recursive version of binary/ternary search.
- alfla 3y agoHow would you do a binary search on a continuous space without discretizing?
- frankreyes 3y agoReplace A[x] with f(x) and done. A modified binary search called ternary search is well known used to find when derivative = 0, numerically. https://en.m.wikipedia.org/wiki/Ternary_search https://en.m.wikipedia.org/wiki/Ternary_search
- n2d4 3y agoWhat would you search for, the zero/root in the derivative? Imagine the derivative is a function like y=x^2-eps with some small eps, say 0.000001. For binary search like that to work, you need to start with two values x1 and x2 such that sign(y1) != sign(y2). But with the derivative above those values are hard to find with random initialization. More generally, for binary search to find a value x such that f(x)=0, we need to have f(any value less than x)<0 and f(any value greater than x)>0. We can't guarantee these properties for general derivatives.
- jdthedisciple 3y ago> What would you search for I imagine you could search until the incremental change between your current and last result is below some threshold epsilon, as a kind of stopping criterion.
- frankreyes 3y agoIEEE 754 is by default limited by 64 bits, so yes.
- BazookaMusic 3y agoThis is probably what you're thinking of: https://en.m.wikipedia.org/wiki/Bisection_method https://en.m.wikipedia.org/wiki/Bisection_method
- rg111 3y agoBecause the search space is tremendously huge.
- AbrahamParangi 3y agoTry doing binary search on a space of nontrivial dimensionality (ie, not 1, 2, or 3) and you will have your answer.
- amelius 3y agoBecause of the dimensionality of the problem. Bracketing is easy to do in 1D space, not so in N-dimensional space, with large N.
- eterevsky 3y agoBinary search only works on sorted data.
- whatever1 3y agoWe do, it’s called global optimization. It works for small problems with ~ 1000 variables or so. Check BARON and the branch & reduce algorithm
- frankreyes 3y agoThanks!
- geysersam 3y agoBinary search only works in 1D parameter space