5
$\begingroup$

I am wondering what methods exist out there for optimization on problems where your contour has lots of small sharp kinks. For example, suppose we have a contour where there are lots of lots of spiky, but sufficiently smooth maxima. In this case, if we were to use an optimization procedure such as gradient descent, we must set our gradient descent step size to be very small, in case we "leap" over a maxima that is too small for our step size to detect. Is there any existing literature for controlling this? Thanks!

$\endgroup$
2
  • 2
    $\begingroup$ Have you heard of simulated annealing? en.wikipedia.org/wiki/Simulated_annealing $\endgroup$ Feb 17 '16 at 1:44
  • $\begingroup$ There are many global optimizers. I've found that the literature is a bit dated, so I created a colab notebook to make recommendations. It helps you choose a Python global optimizer package, and strategy therein, from Ax-Platform, bayesian-optimization, DLib, HyperOpt, NeverGrad, Optuna, Platypus, PyMoo, PySOT, Scipy classic and shgo, Skopt, nlopt, Py-Bobyaq, UltraOpt and maybe others by the time you read this. Please say what your objective function is and I can provide a precise answer, or read medium.com/geekculture/… $\endgroup$ Jul 27 '21 at 2:24
7
$\begingroup$

The state-of-the-art for non-convex optimization in a complex, ill-conditioned and multi-modal landscape is Covariance Matrix Adaptation - Evolution Strategies, aka CMA-ES, which in various versions (such as BIPOP-CMA-ES) has scored first in several global optimization contests (see e.g. the Black-Box Optimization Benchmarking, BBOB 2009).

You can find a lot of information, code for several languages (C, C++, Java, Matlab, Octave, Python, Scilab), research papers and tutorials about CMA-ES on Nikolaus Hansen's website.

The relevant paper is:

Hansen, Nikolaus, Sibylle D. Müller, and Petros Koumoutsakos. "Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)." Evolutionary computation 11.1 (2003): 1-18;

which you can find on the first author's website linked above. I also recommend his tutorial paper, which you can also find on his webpage.

The disadvantage is that CMA-ES requires a lot of functions evaluations to be effective (e.g., usually not less than $10^3$-$10^4$, and even more); however, it is able to solve problems that are just impossible for other solvers.

A possible alternative, if your target function is costly to evaluate, is to use Bayesian Optimization (BO) assuming noise in the target function; this would smooth away kinks in the target distribution. See also this question and my reply there to get some references about BO or other optimizers.

$\endgroup$
2
  • 2
    $\begingroup$ +1. Thanks for joining our community. I hope that you continue to make these kinds of high-quality contributions. $\endgroup$
    – Sycorax
    Feb 17 '16 at 4:26
  • 2
    $\begingroup$ (+1) I initially read the first line as "The state-of-the-art for non-convex optimization is a complex, ill-conditioned and multi-modal landscape", which also seemed accurate. $\endgroup$
    – Cliff AB
    Mar 5 '19 at 18:06

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