Hessians minimization

Global strategies for minimization are needed whenever the current estimate of the minimizer is so far from x that the local model is not a good approximation to fix) in the neighborhood of x. Three methods are considered in this section the quadratic model with line search, trust region (restricted second-order) minimization and rational function (augmented Hessian) minimization. 

The EF algoritlnn [ ] is based on the work of Cerjan and Miller [ ] and, in particular, Simons and coworkers [70,1Y. It is closely related to the augmented Hessian (rational fiinction) approach[25]. We have seen in section B3.5.2.5 that this is equivalent to addmg a constant level shift (damping factor) to the diagonal elements of the approximate Hessian H. An appropriate level shift effectively makes the Hessian positive definite, suitable for minimization. 

Although it was originally developed for locating transition states, the EF algoritlnn is also efficient for minimization and usually perfonns as well as or better than the standard quasi-Newton algorithm. In this case, a single shift parameter is used, and the method is essentially identical to the augmented Hessian method. 

Order 2 minimization algorithms, which use the second derivative (curvamre) as well as the first derivative (slope) of the potential function, exhibit in many cases improved rate of convergence. For a molecule of N atoms these methods require calculating the 3N X 3N Hessian matrix of second derivatives (for the coordinate set at step k)... 

There are several reasons that Newton-Raphson minimization is rarely used in mac-romolecular studies. First, the highly nonquadratic macromolecular energy surface, which is characterized by a multitude of local minima, is unsuitable for the Newton-Raphson method. In such cases it is inefficient, at times even pathological, in behavior. It is, however, sometimes used to complete the minimization of a structure that was already minimized by another method. In such cases it is assumed that the starting point is close enough to the real minimum to justify the quadratic approximation. Second, the need to recalculate the Hessian matrix at every iteration makes this algorithm computationally expensive. Third, it is necessary to invert the second derivative matrix at every step, a difficult task for large systems. 

Given that one does not need to perform an energy minimization and that the Hessian is very sparse, it is not surprising that the computation time is reported to be at least one order of magnitude less than for a conventional normal mode analysis. 

The simple-minded approach for minimizing a function is to step one variable at a time until the function has reached a minimum, and then switch to another variable. This requires only the ability to calculate the function value for a given set of variables. However, as tlie variables are not independent, several cycles through tlie whole set are necessary for finding a minimum. This is impractical for more than 5-10 variables, and may not work anyway. Essentially all optimization metliods used in computational chemistry tlius assume that at least the first derivative of the function with respect to all variables, the gradient g, can be calculated analytically (i.e. directly, and not as a numerical differentiation by stepping the variables). Some metliods also assume that tlie second derivative matrix, the Hessian H, can be calculated. 

Near a first-order saddle point the NR step maximizes the energy in one direction (along the Hessian TS eigenvector) and minimizes the energy along all other directions. Such a step may be enforced by choosing suitable shift parameters in the augmented... 

Hessian method, i.e. the step is parameterized as in eq. (14.6). The minimization step is similar to that described in Section 14.3.1 for locating minima, the only difference is for the unique TS mode. 

Minimization of this quantity gives a set of new coefficients and the improved instanton trajecotry. The second and third terms in the above equation require the gradient and Hessian of the potential function V(q)- For a given approximate instanton path, we choose Nr values of the parameter zn =i 2 and determine the corresponding set of Nr reference configurations qo(2n) -The values of the potential, first and second derivatives of the potential at any intermediate z, can be obtained easily by piecewise smooth cubic interpolation procedure. 

The ratio of the largest to the smallest eigenvalue of the Hessian matrix at the minimum is defined as the condition number. For most algorithms the larger the condition number, the larger the limit in Equation 5.5 and the more difficult it is for the minimization to converge (Scales, 1985). 

In optimization the matrix Q is the Hessian matrix of the objective function, H. For a quadratic function /(x) of n variables, in which H is a constant matrix, you are guaranteed to reach the minimum of/(x) in n stages if you minimize exactly on each stage (Dennis and Schnabel, 1996). In n dimensions, many different sets of conjugate directions exist for a given matrix Q. In two dimensions, however, if you choose an initial direction s1 and Q, s2 is fully specified as illustrated in Example 6.1. 

Steepest descent can terminate at any type of stationary point, that is, at any point where the elements of the gradient of /(x) are zero. Thus you must ascertain if the presumed minimum is indeed a local minimum (i.e., a solution) or a saddle point. If it is a saddle point, it is necessary to employ a nongradient method to move away from the point, after which the minimization may continue as before. The stationary point may be tested by examining the Hessian matrix of the objective function as described in Chapter 4. If the Hessian matrix is not positive-definite, the stationary point is a saddle point. Perturbation from the stationary point followed by optimization should lead to a local minimum x. ... 

Difficulty 3 can be ameliorated by using (properly) finite difference approximation as substitutes for derivatives. To overcome difficulty 4, two classes of methods exist to modify the pure Newton s method so that it is guaranteed to converge to a local minimum from an arbitrary starting point. The first of these, called trust region methods, minimize the quadratic approximation, Equation (6.10), within an elliptical region, whose size is adjusted so that the objective improves at each iteration see Section 6.3.2. The second class, line search methods, modifies the pure Newton s method in two ways (1) instead of taking a step size of one, a line search is used and (2) if the Hessian matrix H(x ) is not positive-definite, it is replaced by a positive-definite matrix that is close to H(x ). This is motivated by the easily verified fact that, if H(x ) is positive-definite, the Newton direction... 

Is it necessary that the Hessian matrix of the objective function always be positive-definite in an unconstrained minimization problem ... 

The condition number of the Hessian matrix of the objective function is an important measure of difficulty in unconstrained optimization. By definition, the smallest a condition number can be is 1.0. A condition number of 105 is moderately large, 109 is large, and 1014 is extremely large. Recall that, if Newton s method is used to minimize a function/, the Newton search direction s is found by solving the linear equations... 

Now, since the Hessian is the second derivative matrix, it is real and symmetric, and therefore hermitian. Thus, all its eigenvalues are real, and it is positive definite if all its eigenvalues are positive. We find that minimization amounts to finding a solution to g(x)=0 in a region where the Hessian is positive definite. Convergence properties of iterative methods to solve this equation have earlier been studied in terms of the Jacobian. We now find that for this type of problems the Jacobian is in fact a Hessian matrix. 

To summarize, in the RF approach we make the quadratic model bounded by adding higher-order terms. This introduces n+1 stationary points, which are obtained by diagonalizing the augmented Hessian Eq. (3.22). The figure below shows three RF models with S equal to unity, using the same function and expansion points as for the linear and quadratic models above. Each RF model has one maximum and one minimum in contrast to the SO models that have one stationary point only. The minima lie in the direction of the true minimizer. 

---