I'm familiar with a wide variety of local and global nonlinear optimization algorithms and the numerical libraries that implement them (such as NLopt https://nlopt.readthedocs.io/en/latest/).
In my particular application, the cost of evaluating the objective function varies dramatically but systematically across the parameter space. In other words, some regions of parameter space are much more expensive to explore than others, and we can predict the expense of each function evaluation pretty well. I expect that it would be most efficient if we could explore the cheap regions of parameter space before we explore the expensive regions. But I'm not aware of any algorithms that take the cost of function evaluation into account.
Has there been work on optimization algorithms that factor in the expense of evaluating the objective function in different regions of parameter space?
Or are there ways we could manipulate existing algorithms to steer them toward cheap regions first?
"Bayesian optimization" refers to optimization methods that use Bayesian reasoning to reduce the amount objective evaluations. The link I provided has an excellent write-up, but the brief is that a simple model of the objective function is proposed and then sequentially updated by Bayes rule every time the true objective function is sampled during your optimization, and this increasingly accurate model can advise where your optimizer goes next. In essence, the model keeps track of where you already evaluated and how that one evaluation is correlated to nearby regions so that you avoid objective calls that don't give you much information or that are likely far from the optimum. It sounds like this methodology can be applied to your problem with some minor tweaks.