Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
@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

2 Answers 2

up vote 2 down vote accepted

At Jacques' cajoling, I'm turning the comments into an answer.

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.

share|improve this answer
    
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
    
@Willie Wong: Thanks in advance for your answers. –  Amit Mar 29 '10 at 13:10

I would use an optimization method based on interval methods to get guaranteed results. On problems such as this, they tend to converge much faster than traditional methods, and with the added bonus of being guaranteed correct, unlike methods based purely on point evaluations.

share|improve this answer
    
Thanks for your answer. I think I phrased my question slightly wrong. 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. –  Amit Mar 19 '10 at 16:32
    
The 2D Shubert function is just the product of two 1D ones. The global minima will be at (x,y) where either x is a global maximum of the 1D Shubert function and y is a global minimum, or vice versa. Here we use the fact that a maximum of the Shubert function is strictly positive, and a minimum is negative. (Three global min/max of the function exists in the interval under consideration, so this gives the 18 global minima.) The local ones can be found analogously by noting that there are 20 local minima and 19 local maxima in the region, which produces the 760 local minima. –  Willie Wong Mar 19 '10 at 17:16
    
To find the local extrema of the 1D function, note that its derivative can be written as a polynomial in sin(x) and cos(x). Then either the roots have nice closed-form, algebraic expressions, or they don't. –  Willie Wong Mar 19 '10 at 17:17
    
@Willie: Good points about the specifics of Shubert functions. My answer was about the general case. And, as so often happens, the structure present in special cases means that there is indeed a solution then. You should turn your comments into an answer! I would vote it up. –  Jacques Carette Mar 19 '10 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.