Algorithms to solve a non continuous global optimization problem

Question

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.

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.