However, constructing and sampling the Bayesian posterior using MCMC methods has several advantages. Sometimes you can have a local minimum which is essentially flat, so the optimal hyperparameter is unstable. You'll see this in the posterior distribution. Or you could have two parameters which are correlated so it's their sum that's constrained not their individual values. All this information provides important context when understanding your model's uncertainty.
Big nearly-flat areas aren't really a new feature of hyperparameter problems... I guess the exact choice of algorithm would depend on how common they are, and maybe Nelder-Mead would be a poor choice. (And I'm not sure how easy it is to parallelise.)
[0]: https://devblogs.nvidia.com/sigopt-deep-learning-hyperparame...