Adding Fibonacci Search Method for Univariate optimization without derivatives

[Ayush-iitkgp]

Apart from Golden Section search and the Brent's method, Fibonacci search method is also used for univariate optimization and in general is faster than the Golden section search.

I wanted to know if previous attempts have been made to add Fibonacci Search Method.I am willing to implement it and provide package users with more options.

[timholy]

I don't know of any previous attempt, and a search didn't reveal one either. (You can search old issues & PRs using the tab above.)

Under what situations is it faster than golden section search? I thought Fibonacci was basically the "rounded-to-integers" version of golden section?

[Ayush-iitkgp]

@timholy after doing a bit more of research, I have found that Fibonacci method with N function evaluation reduces the interval containing the minimum of function f by a factor of 1/fib(N+1) and golden section reduces this by 1/(golden ratio)^N-1. Thus for small epsilon golden section ratio yields a final interval that is 17% longer than the Fibonacci method.

But at the same time, the Fibonacci is slower(I was wrong above when I mentioned Fibonacci is faster) than Golden because at each step we have to calculate fib(N) whose best time complexity is O(log(N)) where as in Golden section we don't have such overhead.

[pkofod]

Is this a dead end, or something you want to have a go at @Ayush-iitkgp ?

[Ayush-iitkgp]

@pkofod I have been working on my GSoc'16 proposal lately. I do wish to implement Fibonacci search sometime very soon.

[pkofod]

Okay! Good luck on the GSoC proposal.

[pkofod]

@Ayush-iitkgp is this dead? I mean, there are many solvers out there, so if this issue has no plan or anything to act on, we should probably close it.

[pkofod]

Closing this "feature request". PRs are welcome still.