Optimization method that considers varying time cost of objective function for different parameters

Question

I am working on improving the optimization process of some demographic modeling software so it can better fit demographic models to data. We'd like to decrease optimization time.

The time it takes to evaluate our objective function varies a lot, depending on the input values. The relationship between time to evaluate the objective function and the input is known. I am wondering if there are any optimization methods that consider the relative time cost of the objective function when choosing which points to evaluate.

Thanks!

Update:

As Paul requested, here are some salient features of this particular objective function:

1. The number of parameters is moderate (~12ish)
2. Our problem is non-convex, or at least there are narrow and flat "ridges" in the objective function surface. Right now we're dealing with this using multiple optimizations from different points, but we'd love to do better.
3. The objective function is pretty smooth, although we can only calculate finite-difference approximations to derivatives.
4. The evaluation cost is also a smooth function of the parameter values, and it's quite predictable. roughly speaking, for each parameter the cost to evaluate is high at one end of the range and low at the other end. So we have large regions of expensive-to-evaluate parameter sets, but we know where they are.

Answer 1

One common approach to dealing with expensive objective functions is to build (by e.g. regression modeling) a "response surface model" that approximates the original objective function, and then optimize over that response surface rather than working with the original function. In practice the response surfaces are typically just quadratic models fitting by regression, so finding a minimum of the response surface becomes a very easy optimization problem.

You haven't said anything about the smoothness or convexity of your objective function. If the function is nonsmooth or nonconvex, then this obviously becomes much, much harder.

You also haven't said anything about where the expensive points are in your parameter space. If they're randomly distributed throughout the parameter space, then you could use design of experiments techniques to build your response surface model while avoiding the expensive points. If there are larger regions of the parameter space where evaluations are expensive, then you could try to minimize the number of points in those areas that you use in constructing the response surface model. Of course, if your optimum is located in the middle of such a region, you're going to be doomed to evaluating functions in the expensive region.

Answer 2

I don't know of methods that specifically weigh the relative costs of evaluating the objective at different trial points but if you are able to predict relatively reliably whether a candidate will be expensive to evaluate or not, then I could suggest giving a try to a direct method. Direct methods fit in the family of derivative-free methods. It's not necessarily a bad thing to use them even if you suspect that your problem is quite smooth because they can provide some level of flexibility that methods for smooth optimization can't.

The idea is that direct methods define a (iteration-dependent) mesh about the current iterate and a (iteration-dependent) mesh "step". Based on this mesh step, the method determines the trial points on the mesh that are neighbors of the current iterate (they lie on the mesh and are at a distance defined by the mesh step). It will then proceed to evaluating the objective at the neighbors. As soon as a better candidate is found, it becomes the new current iterate. At your option, you can also evaluate all the neighbors and choose the best.

In your case, it could be a good idea to order the neighbors based on your estimate of the cost of evaluating the objective there. Evaluate them in this order and pick the first success as next iterate. Intuitively, you're favoring cheap candidates. In direct methods, such orderings fit it the category of surrogate models, a concept that generalizes that of a response surface model mentioned by Brian.

Here's an excellent implementation of a direct method (in C++): http://www.gerad.ca/nomad/Project/Home.html

If that seems to be giving promising results, please feel free to get back to me and I may be able to suggest other improvements.

I believe NOMAD also has features for global optimization (such as the multi-start you're currently applying) based on the concept of variable neighborhood search.