1
$\begingroup$

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"
$\endgroup$
  • 2
    $\begingroup$ The brute force solution you present, even in this coarse grid, is slower than than the optimise solution you calculate by orders of magnitude (comparing milliseconds to microseconds). Having said that, if you can enumerate all solutions and (relatively fast) get the results, go for it! No reason to depend on any computational routines to solve a trivial problem. $\endgroup$ – usεr11852 Dec 4 '16 at 11:25
1
$\begingroup$

As @usεr11852 has pointed out, the difference in speed can be the determination in the decision. In the case of my modeling strategy, a nonlinear model was extremely difficult to calculate the maximum value due to discontinuity in the function form. As a result, I simply calculated all possible values through a brute force algorithm and arrived at the optimal value. This was the quickest way to verify my results. I agree, there is no reason to depend on any computational routines to solve a trivial problem.

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

When evaluating algorithms, one usually uses the worst-case scenario (O(f(n)) when n reaches infinity (i.e., asymptotic efficiency)

However, in practice, n is not sufficiently large as in your case. As optimization requires a certain amount of computation, it could be said that it has some fixed costs. For instance, if you use gradient descent algorithm, it entails the costs of computing derivatives. On the contrary, brute force algorithm does not have a high level of fixed costs, but can incur great variable costs if the number of cases is tremendous.

Hence, it depends on your objective function and search space. It cannot be said without loss of generality which algorithm is superior to another.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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