Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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.
share|improve this question
2  
Hi Kate, and welcome to Scicomp! Could you share some of the characteristics of your objective function? That may help pinpoint a specific method for your case. –  Paul Jan 25 '13 at 1:36
    
I've never heard of any algorithm that considers the cost of evaluating the objective function (or any constraints) explicitly when choosing points to evaluate. However, there exist derivative-free optimization algorithms that attempt to choose cleverly the next point to be evaluated by the optimizer. The premise is that the number of function evaluations should be minimized if function evaluations are expensive. However, I'm not sure that using derivative-free algorithms will help with your use case. –  Geoff Oxberry Jan 25 '13 at 5:41
    
Hi @Paul, thanks for the welcome! I'm excited to have found this community. I've added characteristics. Let me know if there are other features that are more important. –  Kate Jan 25 '13 at 22:39
    
Am I right to infer from your #2 that you are interested in a global minimizer? Or are you satisfied with "sufficient" decrease? Global optimization is a field of its own and the question of attaining a global solution (if there exists one) may be entirely separate from avoiding expensive trial points. –  Dominique Jan 26 '13 at 0:32
    
Dominique, we had assumed that a global optimizer would be too slow for our problem, so we were satisfied with local optimizers. Global optimizers are something we plan to look into in the future. –  Kate Jan 28 '13 at 21:44
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.