Can anyone comment on the most suitable approach for the following optimization problem:

We are given finite bounds for a set of $n$ real-valued parameters of an unknown deterministic function. The function is a black-box and we cannot assume convexity. It's execution cannot be parallelised, hence we obtain 1 output value at a time and can re-evaluate our strategy after each step. We are interested to find a global minimum of the function.

(so far this problem can be solved using one of the many optimization heuristics mentioned here)

I wonder if the choice of algorithms becomes more constrained if we specify upfront an upper bound on the number of steps $s$ we can perform (i.e. we limit the number of evaluations of our expensive black-box function).

Was any of the known global optimization heuristics shown to dominate the others for specific values of $n$ and $s$ (and perhaps also with regard to differing tightness of bounds on $n$)?

It seems that if we can incorporate priors on the search space, we can use a Gaussian process to model the minimization function as shown in this paper. I wonder if there are strong thoughts for, or against this approach by anyone who has successfully solved such problems?

  • $\begingroup$ What do you mean by "parameters" of a function? $\endgroup$
    – littleO
    Oct 7, 2015 at 0:43
  • $\begingroup$ Without further assumptions about the regularity of your unknown function, there is no algorithm that can solve this problem in any practical sense. $\endgroup$
    – littleO
    Oct 7, 2015 at 0:48
  • $\begingroup$ By "parameters" of the function I mean its inputs. Can you please elaborate on what you mean by any "practical sense"? Are you talking about the runtime complexity of the algorithm, or its convergence guarantees? Your comment seems to suggest that heuristics don't make practical sense - though this is not a discussion which I wanted to start. I was hoping to learn whether anyone is aware of an approach that uses the knowledge about the limited number of iteration steps to choose an optimization strategy or a bit clearer answer what are the challenges in this (my first and main question). $\endgroup$ Oct 7, 2015 at 11:01
  • $\begingroup$ General optimization problems, with no additional structure such as convexity or smoothness, tend to be completely intractable. So in order to pick a good algorithm for your problem, we should think about what extra structure your problem has, and which algorithms are available to exploit that structure. Can you tell us more about the optimization problem you want to solve? Is the objective function differentiable? Can you compute its gradient at a given point? Is $n$ a very small number? $\endgroup$
    – littleO
    Oct 10, 2015 at 19:57
  • $\begingroup$ The objective function is unknown (hence my description as black-box) so we can't assume anything about it - having said that, there is no reason why not to hypothesize characteristics and test them and pick an appropriate optimization strategy. My question is whether we can exploit the fact that n is known and fixed in advance. To me it seems that fixing the number of iteration steps is a natural setting for expensive optimization problems and I haven't found any useful information about this other than what I posted. $\endgroup$ Oct 12, 2015 at 17:40


You must log in to answer this question.