3
$\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$
5
$\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$
  • 1
    $\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
  • 1
    $\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 at 18:06

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.