# Algorithms to solve a non continuous global optimization problem

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.

-
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

## 1 Answer

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.

-
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