How do you search a high dimensional for the global maxima using as few samples as possible? Suppose the value at any point in the space is defined by Y = f(x1, x2 .. xk). For simplicity, we can assume that x takes only binary values. Which means that we have a total of 2^k possible values. I want to find the point in this k-dimensional space such that Y at this point is the highest.

The constraint lies in the cost of calculating Y. Because it is very 'expensive' to calculate Y, I want to do it as infrequently as possible. That being said, I have the ability to measure Y for any point in this k-dimensional space. I'm looking for a way to use only a small subset of values n, where n &lt;&lt; 2^k and use it build a prediction model that extrapolates to the entire space

I've been able to do this by starting off with a set of randomly selected n points and using them to construct a regression tree. The prediction error is acceptable. But the size of n is still quite high.

Is there a more intelligent way to choose my n samples? What are some alternative approaches to extrapolate n measurements into the entire feature space?

If I'm willing to settle for the local maxima, how can I find it? Seems like a straight forward problem in linear algebra. But it's been ages and I could really use some help. TIA!
I think you probably should use some randomized optimization algorithm such as randomized hill climbing or genetic algorithm. These are probably more suited for such a problem