Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This Image:

http://img821.imageshack.us/i/nonconopt.png/

Shows the non continuous target function I'm talking about. That's just to illustrate the problem. I'm looking for an algorithm that searches for the minimum/minima of this function or similar functions.

As you can see, it consists of rectangular areas with constant function value (represented by color). That's a problem, as all the algorithms I know expect the objective function to be continuous.

Algorithms like PSO or GA do actually some kind of optimization if I apply them, but I guess that's not really the most effective way to do this, they converge way to early. No surprise there.

Any suggestions on what algorithms could be applicable? Maybe even some key words for searching would be of help.

share|improve this question
    
Downhill simplex ("amoeba") method? –  mjqxxxx Feb 11 '11 at 2:17
    
Ok, that would be a local approach to a global problem. But I'd be fine with that. However it also seems to be unable to deal with the discontinuities or rather with the partial flatness of the function. Ran a small test with Nelder Mead, but it performed worse than PSO and GAs I used before. Thanks for the suggestion anyways. :) –  dOOb Feb 11 '11 at 11:06
    
By the way, when I said "key words" I meant that I'd be happy to have some good words to describe my problem. Searching on google didnt really give me any good results. How can I describe the problem better? –  dOOb Feb 12 '11 at 14:58
add comment

1 Answer 1

I don't pretend this is an answer but I could not put it as a comment. Perhaps this may help.

Your objective function is non-convex, it has local minimas. You want to find the global minima, there exist no algorithm that can find it with efficiency in both time and space. Your regions could be represented by points, so you have a distribution of points and you want to find the maximum by searching in this distribution using the objective function. However, you know almost nothing about these points? (can the difference between neighbors be bounded?)

If you know almost nothing about these points, stochastic optimization algorithms (such as PSO or GA) should be useful, perhaps try with other parameters? if they get stuck on a local minima , perhaps try simulated annealing and start with a high temperature?

Perhaps you could also try regularization, for example by approximating each region with a center point and assume continuity between center-points, this would allow you to use gradient-descent techniques.

share|improve this answer
    
Thanks man, that's at least some things to think about. (and yes, the function is a black box, I know virtually nothing about it). Maybe you are right and parametrization of the stochastic algorithms is one of my problems. –  dOOb Feb 21 '11 at 18:57
add comment

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.