Quasi-Newton search directions

Quasi-Newton search directions provide an attractive alternative in that they do not... 

This formula is exact for a quadratic function, but for real problems a line search may be desirable. This line search is performed along the vector — x. . It may not be necessary to locate the minimum in the direction of the line search very accurately, at the expense of a few more steps of the quasi-Newton algorithm. For quantum mechanics calculations the additional energy evaluations required by the line search may prove more expensive than using the more approximate approach. An effective compromise is to fit a function to the energy and gradient at the current point x/t and at the point X/ +i and determine the minimum in the fitted function. 

The steepest descent method is quite old and utilizes the intuitive concept of moving in the direction where the objective function changes the most. However, it is clearly not as efficient as the other three. Conjugate gradient utilizes only first-derivative information, as does steepest descent, but generates improved search directions. Newton s method requires second derivative information but is veiy efficient, while quasi-Newton retains most of the benefits of Newton s method but utilizes only first derivative information. All of these techniques are also used with constrained optimization. 

Procedures that compute a search direction using only first derivatives of/provide an attractive alternative to Newton s method. The most popular of these are the quasi-Newton methods that replace H(x ) in Equation (6.11) by a positive-definite approximation W ... 

In the global region the Newton or quasi-Newton step may not be satisfactory. It may, for example, increase rather than decrease the function to be minimized. Although the step must then be rejected we may still use it to provide a direction for a one-dimensional minimization of the function. We then carry out a search along the Newton step until an acceptable reduction in the function is obtained and the result of this line search becomes our next step. 

Another technique for handling the mass balances was introduced by Castillo and Grossmann (1). Rather than convert the objective function into an unconstrained form, they implemented the Variable Metric Projection method of Sargent and Murtagh (32) to minimize Gibbs s free energy. This is a quasi-Newton method which uses a rank-one update to the approximation of H l, with the search direction "projected" onto the intersection of hyperplanes defined by linear mass balances. 

Although line searches are typically easier to program, trust region methods may be effective when the procedure for determining the search direction p is not necessarily one of descent. This may be the case for methods that use finite-difference approximations to the Hessian in the procedure for specifying p (discussed in later sections). As we shall see later, in BFGS quasi-Newton or truncated Newton methods line searches may be preferable because descent directions are guaranteed. 

While the steepest descent search direction s can be shown to converge to the minimum with a proper line search, in practice the method has slow and often oscillatory behavior. Most Quasi-Newton procedures, however, make this choice for the initial Step, for there is no information yet on G. 

Early in the quasi-Newton procedure, when one is not very close to a minimum, the procedure may well predict large coordinate changes for which the quadratic approximation to the PES may be quite inaccurate and the predicted quasi-Newton step might make things worse, rather than better. To avoid this problem, one imposes a trust radius. When the length of a predicted step exceeds the trust radius, the coordinate changes are reduced by a scale factor also, the direction of the step may be varied from the quasi-Newton prediction using some other search procedure. 

The conjugate gradient (CG) algorithm is one of the older methods and, strictly speaking, is not a quasi-Newton method. However, it is the method of choice for very large problems where the storage of the Hessian is not practicable. In the Fletcher-Reeves approach the search direction is given by... 

Descent methods are specific (quasi-)Newton methods which look for minimizers only. They differ from the general (quasi-)Newton methods in the line search step which is added to ensure that the procedure makes a sufficient progress in the direction to a minimizer, particularly in the case when the initial guess is far away from a solution. Line search means that at a point x the energy functional E is minimized along the (quasi-)Newton vector p, i.e. a positive value is determined such that... 

---