Positive definite Hessian

For transition state searches, none of the above updates is particularly appropriate as a positive definite Hessian is not desired. A more usefiil update in this case is the Powell update [16] ... 

Solving a QP with a positive-definite Hessian is fairly easy. Several good algorithms all converge in a finite number of iterations see Section 8.3. However, the Hessian of the QP presented in (8.69), (8.70), and (8.73) is V2L (x,X), and this matrix need not be positive-definite, even if (x, X) is an optimal point. In addition, to compute V2L, one must compute second derivatives of all problem functions. 

The iteration counter k and the argument x(l) refers to the macroiterations made in the Newton-Raphson procedure, and they are obviously constant within the context of this section. Let us drop them for convenience. Also, let us explicitly assume that the Jacobian is in fact a positive definite Hessian, and that f(x< >) is a gradient The equation to be solved is thus rewritten in the form... 

The algorithm also ensures that a regular quadratic programme with a positive definite Hessian matrix is obtained at each step, provided that this is so for the initial point. Thus, although a "first-phase" procedure may sometimes be required to locate such a point, no rescue procedure is needed subsequently. 

The first iteration in a CG method is the same as in SD, with a step along the current negative gradient vector. Successive directions are constructed differently so that they form a set of mutually conjugate vectors with respect to the (positive-definite) Hessian A of a general convex quadratic function. 

For modified Newton methods, it is sufficient to have a positive definite Hessian. 

BzzPrint (" nNon positive definite Hessian") gamma.BzzPrint("gamma") ... 

The required condition for a minimum is a positive definite Hessian in the space of constraints. 

Nonlinear CG methods form another popular type of optimization scheme for large-scale problems where memory and computational performance are important considerations. These methods were first developed in the 1960s by combining the linear CG method (an iterative technique for solving linear systems Ax = b where A is an /i x /i matrix ) with line-search techniques. The basic idea is that if / were a convex quadratic function, the resulting nonlinear CG method would reduce to solving the Newton equations (equation 27) for the constant and positive-definite Hessian H. 

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. 

It can be shown from a Taylor series expansion that if/(x) has continuous second partial derivatives, /(x) is concave if and only if its Hessian matrix is negative-semidefinite. For/(x) to be strictly concave, H must be negative-definite. For /(x) to be convex H(x) must be positive-semidefinite and for/(x) to be strictly convex, H(x) must be positive-definite. 

As indicated in Table 4.2, the eigenvalues of the Hessian matrix of fix) indicate the shape of a function. For a positive-definite symmetric matrix, the eigenvectors (refer to Appendix A) form an orthonormal set. For example, in two dimensions, if the eigenvectors are Vj and v2, v[v2 =0 (the eigenvectors are perpendicular to each other). The eigenvectors also correspond to the directions of the principal axes of the contours of fix). 

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

Marquardt (1963), Levenberg (1944), and others have suggested that the Hessian matrix of fix) be modified on each stage of the search as needed to ensure that the modified H(x),H(x), is positive-definite and well conditioned. The procedure adds elements to the diagonal elements of H(x)... 

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

Show how to make the Hessian matrix of the following objective function positive-definite at x = [1 l]r by using Marquardt s method ... 

If no active constraints occur (so x is an unconstrained stationary point), then (8.32a) must hold for all vectors y, and the multipliers A and u are zero, so V L = V /. Hence (8.32a) and (8.32b) reduce to the condition discussed in Section 4.5 that if the Hessian matrix of the objective function, evaluated at x, is positive-definite and x is a stationary point, then x is a local unconstrained minimum of/. 

The penalty term of an augmented Lagrangian method is designed to add positive curvature so that the Hessian of the augmented function is positive-definite. 

To check the sufficiency conditions, we examine the Hessian matrix of W (after substituting p and / ) to see if it is positive-definite. 

---