How do you search a high dimensional for the global maxima using as few samples as possible?
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