Positive-definite Hessian matrix

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. 

In practice, of course, the surface is only quadratic to a first approximation and so a number of steps will be required, at each of which the Hessian matrix must be calculated and inverted. The Hessian matrix of second derivatives must be positive definite in a Newton-Raphson minimisation. A positive definite matrix is one for which all the eigenvalues are positive. When the Hessian matrix is not positive definite then the Newton-Raphson method moves to points (e.g. saddle points) where the energy increases. In addition, far from a mimmum the harmonic approximation is not appropriate and the minimisation can become unstable. One solution to this problem is to use a more robust method to get near to the minimum (i.e. where the Hessian is positive definite) before applying the Newton-Raphson method. 

If all the elements of the diagonal matrix D are positive and significantly large during factorization, the Hessian is positive definite and no problems... 

Through this criterion, Newton s method is automatically employed when the Hessian is positive definite otherwise, a positive definite matrix that will identify a direction of function decrease is used. 

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

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. 

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

This form is convenient in that the active inequality constraints can now be replaced in the QP by all of the inequalities, with the result that Sa is determined directly from the QP solution. Finally, since second derivatives may often be hard to calculate and a unique solution is desired for the QP problem, the Hessian matrix, is approximated by a positive definite matrix, B, which is constructed by a quasi-Newton formula and requires only first-derivative information. Thus, the Newton-type derivation for (2) leads to a nonlinear programming algorithm based on the successive solution of the following QP subproblem ... 

The direction given by —H(0s) lVU 0s) is a descent direction only when the Hessian matrix is positive definite. For this reason, the Newton-Raphson algorithm is less robust than the steepest descent method hence, it does not guarantee the convergence toward a local minimum. On the other hand, when the Hessian matrix is positive definite, and in particular in a neighborhood of the minimum, the algorithm converges much faster than the first-order methods. 

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

Most modern minimization methods are designed to find local minima in the function by search techniques characteristically they assume very little knowledge of the detailed analytic properties of the function to be minimized, other than the fact that a minimum exists and therefore that, close enough to the minimum, the matrix of the second derivatives of the function with respect to the minimizing variables (the hessian matrix) is positive definite. 

However, the Hessian or its approximation has to be inverted to determine the parameter step-change for the next iteration and, especially when far from the real minimum of the SSR, the matrix is not positive definite, a requirement for inversion. Levenbcrg [51] and Marquardt [52] therefore added a diagonal matrix to it and allowed this contribution to vary according to a parameter A, the Marquardt parameter. For the Ath iteration this yields... 

The Hessian matrix is a generalization in R of the concept of curvature of a function. The positive-definiteness of the Hessian is a generalized notion of positive curvature. Thus, the properties of H are very important in formulating minimum-seeking algorithms. 

Condition (2c) requires the Hessian matrix to be positive definite that is, the eigenvalues of G are all greater than... 

---