# 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?

• You cannot. A simple adversarial argument shows that in the worst case you have to query $f$ across its entire domain. – Yuval Filmus Jan 26 '17 at 16:29

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.