Hessian matrix optimization

Instead of a formal development of conditions that define a local optimum, we present a more intuitive kinematic illustration. Consider the contour plot of the objective function fix), given in Fig. 3-54, as a smooth valley in space of the variables X and x2. For the contour plot of this unconstrained problem Min/(x), consider a ball rolling in this valley to the lowest point offix), denoted by x. This point is at least a local minimum and is defined by a point with a zero gradient and at least nonnegative curvature in all (nonzero) directions p. We use the first-derivative (gradient) vector Vf(x) and second-derivative (Hessian) matrix V /(x) to state the necessary first- and second-order conditions for unconstrained optimality ... 

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. ... 

The Kuhn-Tucker necessary conditions are satisfied at any local minimum or maximum and at saddle points. If (x, A, u ) is a Kuhn-Tucker point for the problem (8.25)-(8.26), and the second-order sufficiency conditions are satisfied at that point, optimality is guaranteed. The second order optimality conditions involve the matrix of second partial derivatives with respect to x (the Hessian matrix of the... 

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... 

More variables are retained in this type of NLP problem formulation, but you can take advantage of sparse matrix routines that factor the linear (and linearized) equations efficiently. Figure 15.5 illustrates the sparsity of the Hessian matrix used in the QP subproblem that is part of the execution of an optimization of a plant involving five unit operations. 

Figure 15.4 shows the Hessian matrix for two different types of SQP algorithms for solving large-scale optimization problems. In the full-space SQP, all of... 

SHELXL (Sheldrick and Schneider, 1997) is often viewed as a refinement program for high-resolution data only. Although it undoubtedly offers features needed for that resolution regime (optimization of anisotropic temperature factors, occupancy refinement, full matrix least squares to obtain standard deviations from the inverse Hessian matrix, flexible definitions for NCS, easiness to describe partially... 

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. 

The computation of molecular vibrations is possible with all methods for structure refinement which compute the Hessian matrix (for MM this is the case for optimizers based on second derivatives such as the Newton-Raphson method18). The computed frequencies may then be used for comparison with experimental data90. Recent developments in this area are novel QM-based approaches for the efficient computation of specific vibrational frequencies in large molecules.177... 

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 BFGS (Broyden [42], Fletcher [124], Goldfarb [145], Shanno [379]) algorithm is an update procedure for the Hessian matrix that is widely used in iterative optimization [125]. The simpler Rm update takes the form... 

After the CASSCF calculation with the above choice of orbitals, in order to perform an efficient VB analysis, it is better in this case to resort to an overcomplete non-orthogonal hybrid set. The five active orbitals, in fact, can be split into ten hybrids, in term of which the VB transcription of the wavefunction turns out to be the simplest and the most compact. Such kinds of overcomplete basis sets are commonly used in constructing the so called non-paired spatial orbital structures (NPSO, see for example [35]), but it should be remarked that their use is restricted to gradient methods of wavefunction optimization, such as steepest descent, because other methods, which need to invert the hessian matrix (like Newton--Raphson) clearly have problems with singularities. 

The methods differ in the determination of the step length factor ak at the Ath iteration, since the direction of the steepest descent is, due to nonlinearities, not necessarily the optimal one, but only for quadratic dependencies. Some methods therefore use the second derivative matrix of the objective function with respect to the parameters, the Hessian matrix, to determine the parameter improvement step-length and its direction ... 

---