Optimisation of purely integer quantity with bound-constraints for a 1D expensive function whose analytical form is not available

Question

I have a computationally expensive objective function, whose analytical form is not available. The only input argument to the objective function is an integer variable. The goal is to compute the integer variable that minimizes the objective function.

$$x_{sol} = argmin_{x \epsilon [x_{min},x_{max}]} f(x)$$ where $x$ is integer. $f(x)$ returns a scalar value.

(The objective function is computed by solving a complicated system of non-linear coupled PDEs). The goal is to hopefully use some form of data-driven black-box optimisation which can solve over integer values for $x$ without resorting to a time-consuming/slow for-loop, since the bounds are very large. A MATLAB interface to a suitable solver is desired.

Answer 1

@Stellos already gave the correct answer, but let me try to back it up with a bit of intuition:

Think of your function $f(x)$ as a function that would actually make sense for any real-valued argument $x$. Then, if that function happened to be of the form $f(x)=\sin(1000x)$, you would have lots of maxima and minima between each integer point and, in essence, which integer value happens to minimize $f(x)$ comes down to chance: where the integers happen to line up with the minima of the high frequency sine function. In other words, just because you know $f(15)$ and $f(17)$ tells you nothing about $f(16)$, and consequently the only way to find which integer $x$ minimizes $f(x)$ is to try them all.

On the other hand, imagine that you knew that $f(x)$ only varies slowly, on lengthscales much larger than the distance between integers. Then if you know that $f'(16)\approx\frac{f(17)-f(16)}{1}$, and you can run a derivative based search to find the minimum of the function.

Likewise, if you knew that the function only changes slowly, you could use something like bisection search to find where $f'(x)\approx 0$, and the minimum is likely going to be one of the adjacent integers to all of these critical points.

Even better, if you knew that your function is, for example, convex or concave, then you would know that there is only one minimum or maximum, plus ones possibly located at the end points of your interval, and you can again find them through bisection.

In other words, it is often very valuable to establish such qualitative properties of your objective function because it allows you to choose more efficient algorithms than if you knew nothing at all about your $f(x)$.

Answer 2

Without any information/insights about $f(\cdot)$, your only option to find the maximum is by brute force, i.e., evaluate $f$ for all integers. Now, if this is is practically impossible to do, your only hope is to identify properties of $f$ and/or its maximum that will allow to obtain the maximum with fewer evaluations of $f$. For example, if it makes sense to define $f$ over $\mathbb{R}$ (set of reals) and $f$ is also continuous, you could perform an optimization over $\mathbb{R}\cap [x_\text{min}, x_\text{max}]$ (which is, in principle, much more efficient) in order to narrow the range of integers where you should look for the optimum.