Quasi-Newton Method with a Transformed Hessian

Question

I've recently came across an implementation of the BFGS algorithm but it has an additional step where the Hessian is transformed after the each update. This transformation is done so that certain constraints to the search directions are made. In this case it is optimising a molecules geometry but removes search directions that will lead to translations or rotations.

Has anyone come across anything like this before or anything similar, is there an name for this method and where can I find more information?

Answer 1

It might help us give a better answer if you give more details of your problem. But I think what's going on is effectively elimination of equality constraints. I'll take just translation as an example. You want the centroid of the system to not change at each step, i.e.

$$\frac{1}{n}\sum_i\mathbf v_i = 0$$

where $\mathbf v_i$ is the perturbation to atom $i$ of the molecule in the current optimization step. You can write that as solving a linearly-constrained optimization problem

$$\text{argmin}_v f(x + v)\; \text{s.t. } Av = 0.$$

Now ordinarily you might introduce a Lagrange multiplier $\lambda$ to enforce this constraint. But the null space of $A$ is easy to characterize, so it's more cost-effective to just project onto the null space directly.

The fact that you're using BFGS or some other quasi-Newton scheme is a red herring. This trick would work even if you were using the full Newton method.

If you want to read more, have a look at section 10.1.2 in Convex Optimization by Boyd and Vandenberghe or section 15.3 in Numerical Optimization by Nocedal and Wright.