Newton inversion method

Another systematic way to construct CG models from detailed atomistic simulations is the Newton inversion method [97]. In this method, the structural information extracted from atomistic simulations is used to determine effective potentials for a CG model of the system. Suppose the effective potentials in the CG model are determined by a set of parameters A, where i runs from 1 to the number of parameters in the potential. The set of target properties that are known from atomistic simulations is represented by Aj], where j changes fi om 1 to the number of target properties. By means of the Newton inversion method, a set of nonlinear multidimensional equation between /I, and computed average properties Aj) is solved iteratively. At each iteration of the Newton inversion, the effect of different potential parameters on different averages can be calculated by the following formula [97] ... 

Lyubartsev A, Mirzoev A, Chen LJ, Laaksonen A (2010) Systematic coarse-graining of molecular models by the Newton inversion method. Faraday Discnss 144 43-56... 

Xk) is the inverse Hessian matrix of second derivatives, which, in the Newton-Raphson method, must therefore be inverted. This cem be computationally demanding for systems u ith many atoms and can also require a significant amount of storage. The Newton-Uaphson method is thus more suited to small molecules (usually less than 100 atoms or so). For a purely quadratic function the Newton-Raphson method finds the rniriimum in one step from any point on the surface, as we will now show for our function f x,y) =x + 2/. 

Furthermore, the implementation of the Gauss-Newton method also incorporated the use of the pseudo-inverse method to avoid instabilities caused by the ill-conditioning of matrix A as discussed in Chapter 8. In reservoir simulation this may occur for example when a parameter zone is outside the drainage radius of a well and is therefore not observable from the well data. Most importantly, in order to realize substantial savings in computation time, the sequential computation of the sensitivity coefficients discussed in detail in Section 10.3.1 was implemented. Finally, the numerical integration procedure that was used was a fully implicit one to ensure stability and convergence over a wide range of parameter estimates. 

There are a few points with respect to this procedure that merit discussion. First, there is the Hessian matrix. With elements, where n is the number of coordinates in the molecular geometry vector, it can grow somewhat expensive to construct this matrix at every step even for functions, like those used in most force fields, that have fairly simple analytical expressions for their second derivatives. Moreover, the matrix must be inverted at every step, and matrix inversion formally scales as where n is the dimensionality of the matrix. Thus, for purposes of efficiency (or in cases where analytic second derivatives are simply not available) approximate Hessian matrices are often used in the optimization process - after aU, the truncation of the Taylor expansion renders the Newton-Raphson method intrinsically approximate. As an optimization progresses, second derivatives can be estimated reasonably well from finite differences in the analytic first derivatives over the last few steps. For the first step, however, this is not an option, and one typically either accepts the cost of computing an initial Hessian analytically for the level of theory in use, or one employs a Hessian obtained at a less expensive level of theory, when such levels are available (which is typically not the case for force fields). To speed up slowly convergent optimizations, it is often helpful to compute an analytic Hessian every few steps and replace the approximate one in use up to that point. For really tricky cases (e.g., where the PES is fairly flat in many directions) one is occasionally forced to compute an analytic Hessian for every step. 

Newton s method and quasi-Newton techniques make use of second-order derivative information. Newton s method is computationally expensive because it requires analytical first-and second-order derivative information, as well as matrix inversion. Quasi-Newton methods rely on approximate second-order derivative information (Hessian) or an approximate Hessian inverse. There are a number of variants of these techniques from various researchers most quasi-Newton techniques attempt to find a Hessian matrix that is positive definite and well-conditioned at each iteration. Quasi-Newton methods are recognized as the most powerful unconstrained optimization methods currently available. 

The quasi-Newton methods. In the Newton-Raphson method, the Jacobian is filled and then solved to get a new set of independent variables in eveiy trial. The computer time consumed in doing this can be very high and increases dramatically with the number of stages and components. In quasi-Newton methods, recalculation of the Jacobian and its inverse or LU factors is avoided. Instead, these are updated using a formula based on the current values of the independent functions and variables. Broyden s (119) method for updating the Jacobian and its inverse is most commonly used. For LU factorization, Bennett s (120) method can be used to update the LU factors. The Bennett formula is... 

However, in a quantum chemical context there is often one overwhelming difficulty that is common to both Newton-like and variable-metric methods, and that is the difficulty of storing the hessian or an approximation to its inverse. This problem is not so acute if one is using such a method in optimizing orbital exponents or internuclear distances, but in optimizing linear coefficients in LCAO type calculations it can soon become impossible. In modern calculations a basis of say fifty AOs to construct ten occupied molecular spin-orbitals would be considered a modest size, and that would, even in a closed-shell case, give one a hessian of side 500. In a Newton-like method the problem of inverting a matrix of such a size is a considerable... 

The number of line searches, energy and gradient evaluations are given in Table VI for both the Newton and Quasi-Newton methods. Table VI clearly indicates that the use of an exact inverse Hessian requires less points to arrive at the optimum geometry. However in Table VI we have not included the relative computer times required to form the second derivative matrix. If this is taken into account, then the Newton s method with its requirement for an exact Hessian matrix is considerably slower than the quasi-Newton procedures. 

The Newton-Raphson approach is another minimization method.f It is assumed that the energy surface near the minimum can be described by a quadratic function. In the Newton-Raphson procedure the second derivative or F matrix needs to be inverted and is then usedto determine the new atomic coordinates. F matrix inversion makes the Newton-Raphson method computationally demanding. Simplifying approximations for the F matrix inversion have been helpful. In the MM2 program, a modified block diagonal Newton-Raphson procedure is incorporated, whereas a full Newton-Raphson method is available in MM3 and MM4. The use of the full Newton-Raphson method is necessary for the calculation of vibrational spectra. Many commercially available packages offer a variety of methods for geometry optimization. 

Usually, p is chosen to be a number between 4 and 10. In this way the system moves in the best direction in a restricted subspace. For this subspace the second-derivative matrix is constructed by finite differences from the stored displacement and first-derivative vectors and the new positions are determined as in the Newton-Raphson method. This method is quite efficient in terms of the required computer time, and the matrix inversion is a very small fraction of the entire calculation. The adopted basis Newton-Raphson method is a combination of the best aspects of the first derivative methods, in terms of speed and storage requirements, and the more costly full Newton-Raphson technique, in terms of introducing the most important second-de-... 

Included in the methods discussed below are Newton-based methods (Section 10.3.1), the geometry optimization by direct inversion of the iterative subspace, or GDIIS, method (Section 10.3.2), QM/MM optimization techniques (Section 10.3.3), and algorithms designed to find surface intersections and points of closest approach (Section... 

Quasi-Newton methods attempt to achieve the very fast convergence of Newton s method without having to calculate the Hessian matrix explicitly. The idea is to use gradients to successively build up an approximation to the inverse Hessian. For Newton s method, new directions are taken as... 

There are a number of variations on the Newton-Raphson method, many of which aim to eliminate the need to calculate the full matrix of second derivatives. In addition, a family of methods called the quasi-Newton methods require only first derivatives and gradually construct the inverse Hessian matrix as the calculation proceeds. One simple way in which it may be possible to speed up the Newton-Raphson method is to use the same Hessian matrix for several successive steps of the Newton-Raphson algorithm with only the gradients being recalculated at each iteration. 

Solution of the system of equations The system of Eq. (3), whose equations combine numerical values, theoretical expressions, and covariances, can be solved for the adjusted variables Z best estimates of their values can thus be calculated. The method used in [2,3] consists in using a sequence of linear approximations to system (3), around a numerical vector Z that converges toward the solution of the full, non-linear system (this is akin to Newton s method—see, e.g. [23]). Each of the successive linear approximations to system (3) is solved through the Moore-Penrose pseudo-inverse [20] (see, also. Ref. [2, App. E]). The numerical solution for Z as found in CODATA 2002 can be found on the web . These values are such that the equations in system (3) are satisfied, as a whole, as best as possible [3, App. E]). 

Newton s Method The classical Newton s method is a technique that instead of specifying a step length at each iteration uses the inverse of the Hessian matrix, H(x)" to deflect the direction of steepest descent. The method assumes that /(x) may be approximated locally by a second order Taylor approximation and is derived quite easily by determining the minimum point of this quadratic approximation. Assuming that H(x ) is nonsingular, then the algorithmic process is defined by... 

Newton-Raphson methods can be combined with extrapolation procedures, and the best known of these is perhaps the Geometry Direct Inversion in the Iterative Subspace (GDIIS), which is directly analogous to the DIIS for electronic wave functions described in Section 3.8.1. In the GDIIS method, the NR step is not taken from the last geometry but from an interpolated point with a corresponding interpolated gradient based on the previously calculated points on the surface. 

---