0

I am looking for local minimum search algorithms free of derivative. More specifically, given a continuous and multi-modal $h:[0,1]\longrightarrow \mathbb{R}$ (note that we do not assume $h$ is smooth or Lipschitz), What free derivative algorithm can you recommend me to find a local minimum of $h$?

I know some stochastic adaptive algorithms, such as "HitAndRun", "Improved Hit and Run" and others, but these algorithms need, in general, a lot of functions evaluations to reach a local minimum.

Many thanks in advance for your comments.

user123043
  • 154

1 Answers1

1

There are quite a few possibilities in terms of algorithms that you can use, and it’s difficult to give a recommendation without knowing anything about the specifics of you problem. How many variables does your objective function have? Do you have bounds on those parameters? Linear/nonlinear constraints? Is your function expensive to evaluate or very fast?

That said, depending on which programming language you are targeting, I would try (not necessarily in this order):

  1. NLOpt: widely used optimization framework, has binding for multiple languages. In particular, I found the Subplex algorithm in NLOpt quite effective in many instances - but nothing stops you from trying others such as COBYLA, BOBYQA and Nelder-Mead Simplex (https://nlopt.readthedocs.io/en/latest/NLopt_Algorithms/)

  2. Mystic: Python-based, I found the Powell algorithm to give good results in specific problems I had (https://mystic.readthedocs.io/en/latest/mystic.html)

  3. A few more algorithms, some of those with less stellar performances- language and problem dependent, so your mileage may vary: https://www.gerad.ca/Sebastien.Le.Digabel/MTH8418/

Infinity77
  • 257
  • Many thanks. The objective function $h$ is only assumed to be continuous and the search domain is [0,1]. In general, h will have hundreds (or even thousands) of local minima. – user123043 Jan 02 '21 at 09:53
  • 1
    Yes, I had somehow missed the [0, 1] bounds in your question, sorry. In any case, all algorithms I linked to support simple bounds on the parameters. Depending on how jagged/badly non-differentiable your objective function is, approaches like Nelder-Mead or Subplex may be faster/more appropriate for your problem. That of course is also a function of how many parameters your function has. – Infinity77 Jan 02 '21 at 10:55