Golden-section Search

[@moontiger6393]

Can't believe how few views this has for just have fantastic it is, needed to find a simple and fast method for computing minima today, and this video explained exactly what was needed in a mere few minutes. Otherwise it would have taken much longer for me to be sure of what I was doing, thank you so much!

[@cangizer352]

Thank you Oscar, those videos really helped me to understand and visualize what's going on. You're a life saver in terms of math for sure :)

[@filip8985]

wow you explained this sooo much better than my lecturer

[@blaise2561]

very useful, thanks! my CS101 teacher referred me here and it did not dissapoint! :)

[@tetamusha]

Hey, thanks to you, I was able to implement these methods in a scientific package I work on and I got significant speedups and more stability in my results, compared to the janky solutions I used before. Thanks for the videos.

[@vasantk6663]

These videos are very informative. Thank you!

[@alexandrevachon541]

Overall, my favorites are golden section search and successive parabolic interpolation.

[@niravtank8546]

Video is very informative and thank you for that. Can you please explain derivation of golden section ratio more? I mean to say..I cannot correlate that how you managed to keep same ratio by for every iteration.. It seems you took ratio of current lengths only..

[@OscarVeliz]

The current lengths are shown in the video at 6:25 giving the golden ration. The next interval ratio at 6:39 is also shown to be the golden ratio. Repeat this and you keep the same ratio every iteration.

[@orktv4673]

If we are looking for an inflection point rather than an extremum, it appears we need to draw two auxiliary lines before we can rule out one of the outermost subintervals. We can re-use two of the lines and need to draw a third one to repeat the process. Is it still possible to choose the proportionate positioning of the lines in an efficient way like here? And if so, can we generalize this to n lines (to find the root of the n-1th derivative)?

[@OscarVeliz]

Consider dividing an interval over a function into n intervals (say 5 if you want to visualize). Then remove the function and keep only the points where they met the sub-intervals. I bet you it is possible to draw a function that goes through those points but also has an inflection point between each interval. Let's say for argument sake that you assume there was only one inflection point. It would still be possible to draw n different functions that each have an inflection point somewhere at each sub-interval. The only good way to find inflection points (I think) is to use derivatives or something more sophisticated than just intervals.

[@orktv4673]

​@@OscarVeliz Thanks for looking into this with me! "I bet you it is possible to draw a function that goes through those points but also has an inflection point between each interval." Assume there is just one inflection point and the function is monotonic (it's probably possible to generalize this), then I (poorly) draw this: imgur.com/a/RGDXUxP. Depending on the three sampled values, we can rule out that the inflection point is in either interval IV or I. (Consider we find the green value in the middle sample: to go through the first three points the function must have been decelerating, but to go through the fourth one the function must already have switched to accelerating; therefore the inflection point can in no circumstance be in interval IV.) Once that interval is ruled out, we can proceed with what's left, pick a new value to sample and repeat the process, thus converging to the inflection point; the only question is how to do so in the most efficient way. "The only good way to find inflection points (I think) is to use derivatives or something more sophisticated than just intervals." Numerically taking derivitives requires taking a lot of samples of the function, so this is just a cumbersome way of solving the problem that we are seeking to optimize.

[@OscarVeliz]

What about this scenario imgur.com/a/uI0eqx4

[@orktv4673]

@@OscarVeliz You're showing a bit of a special case, since all those points lie on a line. The curves you draw have straight segments, which technically aren't inflection _points_ but trajectories. Let's be precise and say the function we are looking for has just a single inflection point. I tried drawing another set of points to see what kind of curves can be drawn through here: imgur URL bNmsWG9 Is it possible to draw a decelerating line through the first four points, and then accelerate so the inflection point is in interval IV. It is also possible to place the inflection point in interval III. You can also go through the first two points while decelerating, and then touch the other three points while speeding up, thus placing the inflection point in interval II. It is not possible to have the inflection point in interval I: to go through points 2 through 4, the slope of the path needs to decrease, but then to reach point 5 it must increase, thus warranting an inflection point somewhere in those intervals. Since we assumed there to be one inflection point, it cannot possibly be in interval I. (Had point 3 lain below the imaginary line connecting points 2 and 4, we would have ruled out interval IV by the same argument.) Closing in on a zero requires one sample value in an interval. Closing in on a maximum requires two sample values. We now see that finding an inflection point requires three samples. My conjecture is that finding the zero of the nth derivative requires n+1 points, and it may be possible to generalize binary search and golden mean search to an algorithm for the zero of the nth derivative. If I am mistaken in this I'd love to hear it.

[@OscarVeliz]

Using your example imgur.com/a/NdsmfSK to show it could be in interval 1. With a set of intervals it is possible to put the inflection (where the derivative reaches zero) at any of them. Unlike Bisection where you use the intermediate value theorem to guarentee the root lies in some interval or the unimodal property of ternary/dichotomous/fibonacci/golden that says if a minimum exists it will find it, I can't think of any way to do the same for inflection using just intervals.

[@esakkiappanthevar3320]

Could you please tell, what is the real-life application of the golden section search?

[@OscarVeliz]

I think you are asking the wrong question. GSS is one of many minimization algorithms that I have covered on this channel (more if you count root finding of the derivative). I would recommend looking into real-life applications of minimization.

[@lizzyzhou4954]

Another thing that bothers me: Why the iteration times for Finonacci is one less than for golden-section? Is that always true? Then how can we prove that?

[@OscarVeliz]

This is due to the terminal condition for Fibonacci Search. It ends when the interval size is 2ε, which can be fixed by taking n+1 terms of Fibonacci instead of n. Then the two will reach the same size final condition and I suspect the same number of iterations.