How fast is fminsearch over brute force? or How fminsearch deal with a local/global min?

14 views (last 30 days)
How does fminsearch prevents getting stuck with the local min?
  2 Comments
Akbar
Akbar on 29 Jul 2020
There is no guarantee that a solution by fminsearch is a global minimum unless your problem is continuous and has only one minimum. To search for a global minimum, start the optimization from multiple starting points.

Sign in to comment.

Accepted Answer

John D'Errico
John D'Errico on 29 Jul 2020
Edited: John D'Errico on 29 Jul 2020
How fast is it? Since brute force is an extremely poor method to solve anything (unless your name happens to be the incredible Hulk) fminsearch does not have to be that good for it to be better than brute force.
However, it is almost impossible to give you some simplisitc answer like it will be 10 times as fast, etc. What is brute force anyway? How would you define that? Two different brute force searchs could be orders of magnitude different from each other anyway. And knowing what is the dimension of the problem is would be a huge factor. However ANY optimizer should generally be faster than brute force.
For example, suppose I want to search for the minimum of the function
fun = @(xy) (xy(:,1) - 1)^2 + (xy(:,2) - 2)^2;
So a simple parabolic function. The minimum is at [1,2].
How would brute force work? Would you evaluate the function at EVERY point in a grid? For example, we could evaluate the functino at every point in a grid from 0 to 3, with a grid spacing of 1e-6. THe would give us the minimum, to within a tolerance of 1e-6. This brute force search would reqiuire only 9e12 function evaluations. Rougly 10 trillion function evals, and that to give an accuracy of 1e-6, for only a 2-dimensional problem. Is this really a place you want to go?
It gets exponentially worse in higher dimensions. Suppose you wanted to search a similar domain, but now in 5 or 6 dimensions. Say a brute force search of the unit cube in 6 dimensions, down to a level of 1e-6 in each dimension.
That would require "only"
1e6^6
ans =
1e+36
function evaluations. No problem, since you happens to be using a super computer capable of 1e12 function evaluations per second. (I do mean a super computer there, since depending on the objective function, most normal computers today MIGHT be able to handle on the order of 1e9 function evaluations per second, even if the function is highly vectorized.)
At 30e6 second per year, that brute force search in 6 dimensions would take roughly
1e6^6/1e12/30e6
ans =
3.33333333333333e+16
YEARS. That is, around 3e16 years. to perform a brute force search in 6 dimensions. The universe has only existed for roughly 13 billions years so far, so by the time 3e16 years have passed, the entire universe may have fallen into one big black hole. Even simpler variations of a brute force search are nothing you want to touch with a 10 foot pole.
Compare that to fminsearch. Even if fminsearch uses some thousands of function evaluations, do you really want to compare a second at so of CPU time, even minutes, to the time before the entire universe goes into heat death?
What is a typical search time for fminsearch, again, depending on the number of iterations, and how nasty is the function?
[X,fval,exitflag,outp] = fminsearch(@(xy) peaks(xy(1),xy(2)),[0,-4])
X =
0.228270939813299 -1.62550520966348
fval =
-6.55113331854834
exitflag =
1
outp =
struct with fields:
iterations: 58
funcCount: 111
algorithm: 'Nelder-Mead simplex direct search'
message: 'Optimization terminated:↵ the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-04 ↵ and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-04 ↵'
So 58 iterations, with 111 function evaluations, with a tolerance of 1e-4. Harder problems in more dimensions can easily push the counts to some thousands of evals, even many thousands of function evaluations.
You also ask about convergence and global versus local mins. NO optimizer can insure convergence to a globally optimal solution. At least not unless you can put explicit finite limits on the derivatives of your objective function, assuming the function is continuous and differentiable. If you start it in a bad place, you can end up in a bad place.
This is something you need to understand about local minima. You need to provide intelligent starting values. If not, then expect strange results if your objective function has multiple local minima. Once an optimizer has found a point where any direction points upward, it will stop. Some optimizers are more robust, in the sense that they can sometimes escape such a local min. Tools like GA, simulated annealing, particle swarms, etc., can often be more robust, though even they are not perfect. And you can use multi-start methods, starting an optimizer like fminsearch with multiple random start points, then take the overall best solution found.
  3 Comments
Stephen23
Stephen23 on 29 Jul 2020
Edited: Stephen23 on 29 Jul 2020
You call a tolerance of 1e-6 brute force? Luxury! We used to have to start MATLAB at three o'clock in the morning, sort ten thousand unmarked punch cards in the dark, crank the computer by hand for 17 hours every day, and solved all tasks by incrementing the least-significant bit of 128bit floating point numbers that hadn't been invented yet to get a solution some time in the next 42 universe lifetimes if we were LUCKY!
But you try and tell the young people today that... and they won't believe ya'.
(apologies to Monty Python)

Sign in to comment.

More Answers (0)

Categories

Find more on Get Started with Optimization Toolbox in Help Center and File Exchange

Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!