Long email ahead, but here is my implementation of BFGS and L-BFGS in Python from one of my research code, if anyone is interested in going down that route:
https://gist.github.com/1561144 but see my comment about why neither of these may be the right thing. - >>> Other important factors to test would be the trust radius (max step size) >>> and step >>> adjustment factors in the simple line-search -- I'm not sure where the >>> currently used parameters came from. >> >> I eyeballed them, although in the recent months, I've been tinkering to give >> both better time performance and better convergence. AFAICT, it's a black >> art to get a good trust radius and adjustment factor. If anyone knows of >> papers or methods to compute these, I'd be very interested. It may be useful to compare how geometry optimization is implemented in force field and quantum chemistry packages, which just about every package will support. Most of these use BFGS or L-BFGS with backtracking line search, and in particular with ab initio geometry packages they combine this a convergence acceleration technique such as DIIS. I've been told that the nature of geometry optimization lends itself better to linesearch strategies as opposed to trust radii because of the varying energy scales in the problem (or equivalently the stiffness of the Hessian). It is difficult to come up with a trust radius that handles a simultaneous optimization of a dihedral and a bond strength, for example. >> If you're going to do all that, I suggest someone consider writing a BFGS >> minimizer (which probably would require Eigen): >> http://en.wikipedia.org/wiki/BFGS_method >> http://en.wikipedia.org/wiki/Limited-memory_BFGS > There are also some existing opensource projects for other minimization > methods: > > LBFGS (MIT license): http://www.chokkan.org/software/liblbfgs/ > Levenberg-Marquardt non-linear lsq (GPL): > http://www.ics.forth.gr/~lourakis/levmar/ I use L-BFGS as my general purpose optimizer and it works extremely well. Is the MIT license compatible with GPLv2? > I've used them both directly in the past with some success, though > they will probably be more useful as reference implementations if we > add these to OB. Levenberg-Marquardt is not really designed for this type of problem. It is designed for least-squares minimizations, for which the algorithm can achieve quadratic convergence without building a Hessian or even an approximation thereof. One would expect the convergence rate to be similar to (an probably worse than) conjugate gradients for non-least-squares problems since it has no Hessian information and its assumptions about the nature of the Hessian may not be accurate. I've never tried it for geometry optimizations though. >> The BFGS minimizer would certainly converge faster and probably more >> tolerant of unusual energy surfaces than steepest descent or conjugate >> gradients. Does OB implement conjugate gradients or BiCGstab? If it is plain CG then one reason why it could be failing is simply that far away from ground state geometries the Hessian can develop negative eigenvalues (imaginary frequencies) which would mean the geometry is close to some kind of transition state or other saddle point. CG assumes the Hessian is SPD and so would try to go downhill in a direction it thinks is downhill, but could actually be uphill due to a component in an eigenvector corresponding to a negative eigenvalue. In such cases BFGS would also fail because it also assume an SPD Hessian and the approximate Hessian will simply diverge from the true Hessian; implementing BFGS would not help things much in this respect. In the presence of imaginary frequencies there be no choice but to use a different class of algorithms which are markedly less efficient than BFGS or CG (more or less the most efficient algorithms of their respective categorires). BiCGstab would be one of the simplest algorithms in this category, but it has well known precision issues which can be problematic for geometry optimizations. Most ab initio codes that handle transition state searches use GMRES, for which a robust public domain implementation in Fortran is available. http://www.cerfacs.fr/algor/Softs/GMRES/index.html An excellent resource on indefinite optimization is van der Vorst's book, although as the inventor of BiCGstab he is naturally biased in that direction. :) http://www.cambridge.org/gb/knowledge/isbn/item1170134/?site_locale=en_GB > Especially if we can get a good approximation / fast solution of the > Hessian (Possibly another good student project...) I presume you mean as a starting guess? What is the default in OB? Most codes I am familiar with start with the diagonal components of the exact Hessian as input into BFGS and this works very well in practice - it has the right balance of being a good approximation and sparse representability as a vector. Thanks, · Jiahao Chen · MIT Chemistry · ------------------------------------------------------------------------------ Ridiculously easy VDI. With Citrix VDI-in-a-Box, you don't need a complex infrastructure or vast IT resources to deliver seamless, secure access to virtual desktops. With this all-in-one solution, easily deploy virtual desktops for less than the cost of PCs and save 60% on VDI infrastructure costs. Try it free! http://p.sf.net/sfu/Citrix-VDIinabox _______________________________________________ OpenBabel-Devel mailing list OpenBabel-Devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/openbabel-devel
