Optimizing cheap functions on mixed search space Assume we have a really cheap function $f$ that is defined on a mixed parameter space and we want to find a minimum.
For example

$\operatorname{arg\,min}\limits_{x_1,x_2,x_3} f(x_1,x_2,x_3)$

with 

$x_1 \in \mathbb{R}, \ x_2 \in \{1, \ldots, 10\}$ and $x_3 \in \{\text{'a'}, \text{'b'} \}$.

and we have no assumptions on monotony in any dimension or likely local optima.
How can I find the values that minimize the function without much computational overhead?
In general you can't. Optimization is a tricky business and proper solutions are only known if your $f$ and/or your search space belong to some restricted class.

You can try various heuristics. Things to google for include "genetic algorithms", "evolutionary algorithms", and "simulated annealing".