For a industrial application (layout-planning) I am currently trying to globally optimize a discontinuous function f. The objective function is defined on some bounded parameter space in R^N where the dimension N of this space depends on some initiation parameter. The N lies typically between 30-100.
The goal is to run this optimization a number of times (each time for a slightly different layout) and afterwards choose the best one.
Currently I use the MLSL-algorithm provided by the NLOPT-library to compute the global minimum of the objective. Especially when N goes up the time needed for each run to obtain a good result increases a lot. This is why I am looking for a way to speed up my computations.
From the structure of the objective function I know that it is oscillating which slows down the convergence of typical global optimization-algorithms. On the other hand the function f is the sum of a differentiable function and a upper-semi-continuous step-function, so in particular f is upper-semi-continuous and almost everywhere differentiable. The objective function is bounded as well and as it is defined on a bounded set it is integrable.
My question now is: Does anyone here have experiences with optimization of such functions (or more generally noisy or black-box functions) and has experiences which algorithms work best?
Especially as I have more details about my function is it maybe possible to use a subgradient-method or first smooth out my function by let's say a smoothing kernel phi, i.e. g = f * phi, and then optimize g to obtain a result for f?
I have tried out all global algorithms provided by https://nlopt.readthedocs.io/en/latest/NLopt_Algorithms/.
In particular I have tried out ESCH, ISRES and CRS as well which are evolutionary or "particle-based" algorithms. These algorithms did often not find the global minimum or were very slow compared to direct-search algorithms like DIRECT and MLSL.
Do you have suggestions which particular algorithm I should try out as well?
Maybe something which can make use of the known structure of the objective function?
I will definitely give those a try. Thanks for the help.
Do you have suggestion which libraries I can use therefore? My current implementation of the objective function is written in C++, so a library in C/C++ would be great.
What can be done is to create a representation of the objective space, by determining several (very many!!) points on the function surface, and from that create an explicit function that interpolates the points you have found. That function can hopefully be optimised by global optimisation software, and by evaluating new points in regions that may be interesting, you can refine the search towards the global optimum - at least if the function is not too weird. :-)
You need of course be aware that it may take some time, as the interpolated function needs to be re-optimized many times, perhaps, at several vectors.
Thanks for the answer Michael Patriksson . This actually sounds very interesting! So as I understand it, this would be like a stepwise convolution of the function or more generally it would be (stepwise) smoothing out of the noisy function by interpolation.
Are there maybe theoretical convergence results for this kind of procedure? Like how do I know that the interpolation actually finds the correct "attractive regions" and therefore refines in the correct manner. I can imagine some l.s.c and maybe even Sobolev-regularity would help/is needed to ensure actual convergence?
And are there software-packages implementing this? :)
That will depend on smoothness and perhaps some guess-work on a possible Lipschitz constant. Wendland has a book that describes the workings of how to deal with surfaces, and finding maxima or minima - right now I do not remember the name of the book ...
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling