1
$\begingroup$

Let $[0,100]$ denote the interval of real numbers between $0$ and $100$. Given a function $f:[0,100]^n \rightarrow \mathbb{R}^+$, I want to implement the following simple algorithm to search for the point in $[0,100]^n$ maximizing $f$:

1.- Observe the value of $f$ at $k$ random points chosen uniformly in $[0,100]^n$. Let $A$ be the set of these points.

2.- Iterate many times:

  • (2.1) Calculate an interpolation function $g$ whose values coincide with those of $f$ for all points in $A$ (alternatively, $g$ could be a regression rather than an interpolation).
  • (2.2) Sample $k$ points in $[0,100]^n$ in such a way that the probability of choosing each point is proportional to the value of $g$ at them.
  • (2.3) Add these sample points to set $A$.

3.- Return the point of $A$ maximizing $f$.

I want to reach some tradeoff between the sophistication of the interpolation made in step (2.1) and the efficiency of the sampling method in step (2.2). What kind of interpolation or regression method should I use to compute function $g$ at each iteration?

On the one hand, the interpolation function $g$ could just return the weighted average of $f$ at all points in $A$, in such a way that the weight of each of these points in the calculation of $g$ at any point $p$ is e.g. inverse proportional with the distance of that point to $p$. In this case, the sampling step (2.2) could use the accept-reject sampling method. However, if $g$ gives extremely low values to many points, then the accept-reject method would have to be repeated a high number of times for each sample.

On the other hand, the interpolation function $g$ could be calculated as an interpolation n-dimension polynomial coinciding with $f$ for all points in $A$. In this case, the sampling step (2.2) would not need to use any try-and-fail method as before. Since polynomials can be integrated, we could do the sampling as follows: we uniformly sample a value $r\in[0,1]$ and then calculate the value $x_0$ of the first variable (i.e. dimension) such that the volume of $g$ for the interval $[0,x_0]$ of the first variable and the intervals $[0,100]$ for all other variables is an $r$-proportion of the whole volume for all points in $[0,100]^n$ (a trivial integral defines this volume). Then we do the same for the second variable (conditioned to the fact that the value of the first variable is $x_0$) and so on for all variables, removing a variable each time until we find out all the dimensions of our sampled point. However, I have not found any library letting me perform a multidimension polynomial interpolation for e.g. 30 dimensions or so. A very interesting interpolation library is Minterpy, but computing a high-degree 30-dimension polynomial from any unstructured sample set A is unfeasible. Is there any library letting me do this?

Is there any interpolation or regression library which is suitable for e.g. 30-dimension functions but, at the same time, the interpolated/regression function enables some direct sampling method not based on try-and-fail?

$\endgroup$

1 Answer 1

1
$\begingroup$

Good ideas! Unfortunately there is no single correct answer to your question. There is a "no free lunch" theorem that says every approach will work better on some functions $f$ and worse on others. So you will need to make a choice that is based on intuition, domain knowledge, or experiments. It might depend on what form you expect the true function to take and the number of dimensions. One approach is to use a neural network as $g$.

You might be interested to read about Bayesian optimization, which is an elaboration/extension of your idea, augmented with some predictions of where $g$ is more accurate and where it is likely less accurate, then using that information as well to help select more points to sample.

You might start by picking an existing Bayesian optimization toolkit/software package and try applying it to your problem setting.

Be prepared that black-box optimization can be extremely hard or extremely easy, depending on the nature of $f$, so you might be in a problem domain that is extremely difficult -- or you might not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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