Genetic algorithm vs conjugate gradient method

Question

I am trying to optimize some force-field parameters in a molecular framework so that the result of simulation comes as close as it can to the experimental structure.

In the past, I have written a genetic algorithm where I essentially randomly sample the parameter space, select the combination that works best, create sets of mutated parameters, and repeat the process until I get the best parameters for some objective function. I also perform some optimization of the algorithm itself, where the distribution of the mutated values is optimized to favor faster convergence.

My advisor has not heard of genetic algorithms, and I have never heard of the methods he recommended: conjugate gradient method and the simplex algorithm.

In my situation, the objective function is a function of every atom's deviation from its experimental location (so its a structural optimization). The system is 4-10K atoms. Is it worth it to invest some time into learning CGM or the simplex algorithm? Out of all three, which is the best for this situation?

Answer 1

The conjugate gradient method is good for finding the minimum of a strictly convex functional. This is typical when you reformulate a nonlinear elliptic PDE as an optimization problem. If you want to learn about it, I recommend you read about the CG method for linear systems first, for which An Introduction to the Conjugate Gradient Method Without the Agonizing Pain is a good reference. Unfortunately, many books treat it by pulling the algorithm out of a hat without the least concern for whether you understand it at an intuitive level, hence the title. From there, it's not a great leap to seeing how one could devise a nonlinear conjugate gradient method.

From what I know about genetic algorithms, they would be better suited for finding the global minimum of an objective functional which has many local minima, which can be the case for molecular systems that have lots of meta-stable equilibria. In that case, the objective function isn't convex everywhere, which precludes the use of CG. The cost is the slower convergence of randomized algorithms.

Whether it's worth it for you to learn about CG depends on:

• whether or not CG is even applicable
• how fast your approach is already
• how much faster CG might be (my guess: a lot, if you can use it)
• how much time you will spend learning/coding CG
• how badly you want to not appear ignorant to your adviser
• how big you expect your problem to get later.

My two cents: it's a pretty neat tool, but I use it all the time so I'm biased.

Answer 2

You can also look at CMAES. It essentially boils down to CG for convex functions, yet represents global and robust optimizer for other types of functions (including non-convex functions with multiple minima). I have not seen, however, its application to anything larger than a couple of hundreds unknowns.

Note also that CG can be applied in combination with Tikhonov regularization which, in a way, makes your function more convex and easier to minimize, although at the cost of some bias in the solution, which is often acceptable trade off.