# Finding the local/global minima of Shubert function

Consider the 2D Shubert function. As given in that page, the function has 18 global minima and several local minima. How can I find the (x,y) of all these minima? Any help appreciated. If it was a summation (instead of a product), I would have done it by minimizing each individual term. However, I have 0 clue as to how to find the minima in this case.

UPDATE: Before applying any global optimizer, I want to know "theoretically" what are the (x,y) of all the minima. I want to be able to compare the expected and the obtained results

-
@Willie: retagged. –  Jacques Carette Mar 19 '10 at 16:09
You will need to re-edit, because I have no idea what you mean by knowing (x,y) "theoretically". You can't mean closed-form. –  Jacques Carette Mar 19 '10 at 17:14
Rereading your comment, I see what you are after: you want to be able to 'test' the results. But that (essentially) requires knowing the answer before computing it... which is usually exactly what people do when testing scientific software: they run many cases where the answer is already known from some other method, and verify that the new method agrees. The only alternative is to use a 'proven' method (like interval-based methods!) which have a proof of (partial) correctness, i.e. if they return a result, the result is correct. –  Jacques Carette Mar 19 '10 at 17:19

The two dimensional Shubert function is just the product of the one dimensional one by itself. $f(x,y) = g(x)g(y)$ where $g(x) = \sum_{j = 1}^5 j \cos( (j+1)x + j)$ is the 1 dimensional Shubert function. Observe that the local maxima are all positive, and the local minima all negative. So the minima for $f(x,y)$ occur at points $\{(x,y) : g'(x)= g'(y) = 0, f(x,y) < 0\}$. In other words, the minima of $f$ occurs at points where a maximum of $g$ is multiplied against a minimum.

Notice that there are 3 global max/min each of $g$ in the interval (-10,10), and 19 max and 20 min overall. This produces the 760 total local min of $f$ with 18 of them being global. (760 = 2 * 19 * 20, 18 = 2 * 3 * 3)

To find the extrema of the 1-d Shubert function, you evaluate its first derivative, and find that it can be simplified to a degree 6 polynomial in $\sin(x)$ and $\cos(x)$ by using the angle addition formulae. I have not evaluated the computations myself, so cannot tell you whether the expression has a closed-form algebraic solution.

-
Thanks a lot Willie Wong:) Just some clarifications: "Observe that the local maxima are all positive, and the local minima all negative"- How did you find that? Since each term is a summmation, so a minima will be obtained if ((j+1)x+j) = (2n+1)pi, that is cos(x) = -1, and hence the minima will be -ve and similarly for the positive maxima for which cos(x)=1 ? Pls. clarify. –  Amit Mar 20 '10 at 4:49
To be honest, I just plotted it with wxMaxima. –  Willie Wong Mar 20 '10 at 11:08
:) Yeah, I just could proceed with my problem because of your answers. I just noted the X-values for 1D from my plot using gnuplot (I had to use a huger number of samples to get an accurate estimation), but my work has progressed. Thanks a ton :) –  Amit Mar 20 '10 at 14:06
@Willie Wong: In 5D, a global minima will be obtained by the combination of 4 global maxima and global minima, right? If that is true, then we have (3^4 * 3 * 5) global minima. How do I get that? Considering the first four dimensions of a global minima has to come from the 5 global maxima, there are 3^4 possible ways of picking the first 4 dimensions. Now they can be combined with any of the 3 global minima, thus (3^4 * 3) global minima. Again the 4 sets of global maxima from the 5 can be chosen in 5 ways. Hence, a total of (3^4 *3 *5) global maxima. –  Amit Mar 29 '10 at 13:10