Brute force search

Section 30.2 Brute force search

This is a very direct approach to minimization of \(f\colon [a, b]\to \mathbb R\text{:}\) choose some large number of points \(x_1, \dots, x_n\) on the interval, equally spaced, evaluate \(f\) at each point, take the minimum of \(f(x_k)\text{.}\) How close will this be to the actual global minimum? If \(f\) is differentiable and \(|f'|\le M\) on the interval, the mean value theorem implies

\begin{equation} |f(x)-f(y)| \le M|x-y| \tag{30.2.1} \end{equation}

for all \(x, y\text{.}\) Placing \(n\) points on the interval, we have intervals of size \(h = (b-a)/(n-1)\) between them. Hence, each point of the interval is within distance \(h/2\) of some grid point \(x_k\text{.}\) Therefore,

\begin{equation} \min_{k} f(x_k) - \frac{Mh}{2} \le \min_{a\le x\le b} f(x) \le \min_{k} f(x_k)\tag{30.2.2} \end{equation}

This may be good enough for a rough estimate of global minimum. One can also refine this estimate by applying a more advanced method on the interval \([x_{k-1}, x_{k+1}]\) around the point \(x_k\) where \(\min_{k} f(x_k)\) is attained.

🔗

In Matlab, the code for brute force search may look like

x = linspace(a, b, n);
y = f(x);
[fm, ind] = min(y);

Note the two-outputs form of min command: when used in this way, the first output is the value of minimum, and the second is the index at which it was found. So, y(ind) is the same as fm but more importantly, x(ind) is the corresponding \(x\)-value.

🔗

Example 30.2.1. Using brute force search on an interval.

Minimize \(f(x) = \sin (x) + \sin (\sqrt{2}x)\) on the interval \([0, 100]\) using \(n=100000\) points. Then use (30.2.2) to estimate the true global minimum of \(f\) on this interval.

🔗

Solution.

f = @(x) sin(x) + sin(sqrt(2)*x);
a = 0;
b = 100;
n = 100000;   % number of points
x = linspace(a, b, n);
y = f(x);
[fm, ind] = min(y);
fprintf('Minimum %g attained near %g \n', fm, x(ind));

The output is “Minimum -1.99306 attained near 29.9413”. To estimate the accurac, note that \(|f'(x)|\le 1+\sqrt{2}\approx 2.4\) everywhere, and that \(h = (100-0)/(10^6 - 1)\approx 10^{-4}\text{.}\) So \(Mh/2 \approx 0.00012\) and therefore, the true global minimum of \(f\) lies between \(-1.99306 - Mh/2 = -1.99218\) and \(-1.99306\text{.}\)

🔗

Brute force search requires many function evaluations, especially with several parameters. It is not practical as the primary search method, but may be useful in combination with other methods.

🔗

Prev Top Next