1
$\begingroup$

When I want to solve $$\text{minimize}\quad f(x)$$ over $x\in\mathbb{R}^n$, where $n$ is quite a large value, e.g. $n$ is around thirty, which metaheuristic algorithm is good?


If $f(x)$ is continuous and convex, we can easily utilize many methods to find a minimizer like gradient-based algorithm, etc.

However, $f(x)$ that I am examining is not a convex function. So, I cannot adjust gradient method, and then, I tried to adjust simulaetd annealing and accelerated particle swarm optimization algorithms. The result is quite not bad, but not so good I think.

I consider that the reason why these algorithms may not produce enough good result is the fact that $f(x)$ is a noncontinuous function.


I saw from some material that PSO is one of the best optimizing algorihtms for finding minimizer for continuous objective function.


Is there any well-known algorithm for high-dimensional, non-continuous, and non-convex function?


ps) The function $f$ could be whatever. I am dealing with a general form.

For example, $x_1,x_2,x_3$ could be coordinates of $x$-, $y$-, and $z$-axies, $x_4,…,x_10$ could be result values from the other layer, and $x_11,…,x_20$ could be any random variables for guaranteeing uncertainty of the system, and so forth.

That is, even if $f(x)$ is just $∥x∥$, the design variable vector $x$ would be discrete and very fluctuating according to the system. I would like to consider this system.

$\endgroup$
1
$\begingroup$

Many of the algorithms you are thinking of tend to fall into the "evolutionary optimization" framework, including particle swarm optimization.

One method that I have used with some success is differential evolution. Basically, it is a continuous (i.e. non-discrete) genetic algorithm in a vector space. I am not sure if you have a need for boundary conditions or constraints, but they are easy to build into the algorithm.

Adding stochasticity to gradient descent (e.g. simulated annealing) can work fine, but if the derivative is changing very rapidly, there are gradient-flat parts of space, or there are too many local extrema, it may not be very useful. (Although, some methods have been invented to overcome the lattermost short-coming.)

Another interesting method I've found useful is cross-entropy optimization. It costs a little more due to redundant computations, but also can also give a notion of probability distributions on the space, where the extrema are more likely to be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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