Solved – Optimization vs Brute-force. What is the difference

algorithmsoptimizationr

Question

I've recently discovered that a brute-force algorithm is much faster at solving an optimal solution than the optimization routine for a particular problem I've been working on. This is mainly because the number of possible solutions is rather small ($2^{12}=4096$), but it has made me question whether computing power is no longer a limitation in optimization routines.

If the problem can be reduced to a minimization of all possible solutions then what is the difference between optimization routines and brute-force algorithms? From a theoretical standpoint, is it best to optimize the functional form? Or from a practical standpoint, and under limited constraints of solutions, is it best to solve for all solutions and minimize?

Problem

For simplicity, let's assume the functional form for an optimization problem is:

$$f(x, a) = (x – a)^2$$

We can then solve this by minimizing the function over all possible solutions where $x \in \{0,1\}$ and $a = 1/3$. Solving for $x$ shows that,

$$\frac{df(x,a)}{dx} = 2(x- \frac{1}{3}) = 0$$

The solution for this problem after optimizing is: $x=0.33$ and $f(x,a) =1.111111e-05 $

Example

In R this is rather simple to produce.

Optimization

f <- function (x, a) (x - a)^2
xmin <- optimize(f, c(0, 1), tol = 0.01, a = 1/3)
xmin

> $minimum
[1] 0.3333333

$objective
[1] 0

Brute-force algorithm

dat <- data.frame(x = rang, f = rep(0, length(rang)))
rang <- seq(0,1,0.01)
a <- 1/3

for (i in 1:length(rang)){
  dat$f[i] <- f(rang[i], a)
}
opt <- min(dat$f)
loc <- which(dat$f == opt)
print(paste("minimum: ", dat$x[loc]))

[1] "minimum:  0.33"

Best Answer

Brute force only works on certain special cases and optimization is a general technique to solve "more realistic" problems.

Here is a small demo: if we add one small change in your problem, the brute force will "fail". Suppose the tuning parameter $x$ is a vector that has $10$ dimensions. Then, the brute force will have huge search space (if using fixed grid the search space grows exponentially with respect to the length of $x$), but the gradient in optimization will provide the "direction" to go.

The intuition is that:

  • Brute force will check everything and choose the best place to go.
  • Gradient will make sure every step is effective, i.e., will reduce the loss and have a better solution after the iteration.
Related Question