Speeding up the Convergence of Optimization Problems: Part I

The use of genetic algorithms to solve optimization problems has a number of advantages. These include that they have the ability to solve essentially any problem, such as those which are non-linear, or those with multiple local optima but a single global optimum. Palisade’s Evolver can be used to deal with such situations in static Excel modelling, whereas RISKOptimizer can be applied to models containing uncertainties.

One main drawback to some approaches based on genetic algorithms is their slow convergence in some situations. In this blog, I mention a few heuristic methods to speed up the convergence of models when using Evolver (which also apply to RISKOptimizer), and in another posting deal with some items specific to RISKOptimizer.

Concerning Evolver, a few methods can sometimes helping, including:

  • In problems without constraints, recognising that the solution surface around an optimal point is often quite flat, so that for many practical purposes an approximate solution is essentially as useful as the true solution.
  • In problems with constraints, trial values very close to the optimum set of values are very likely to create situations in which constraints are not satisfied, even though they are very close to being the case. As well as therefore accepting approximate solutions as a sufficient solution, it can be more appropriate to replace hard constraints (that must be satisfied) with soft ones (in which a penalty function is applied when constraints are not satisfied).
  • Reformulating a continuous optimization problem (e.g. what weights to apply to each asset class in a portfolio situation) as a discrete one (e.g. in which trial weights are all multiples of 10%). Once an approximate solution has been found, the granularity can be increased.
  • Stopping the algorithm to adjust the Settings, and restarting can sometimes also help. A typical adjustment might include a large (but temporary) increase the mutation rate.
  • If all else fails, you may need a faster computer!

Dr. Michael Rees
Director of Training and Consulting

Leave a comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: