Quasi-Newton convergence

The development of an SC procedure involves a number of important decisions (1) What variables should be used (2) What equations should be used (3) How should variables be ordered (4) How should equations be ordered (5) How should flexibility in specifications be provided (6) Which derivatives of physical properties should be retained (7) How should equations be linearized (8) If Newton or quasi-Newton hnearization techniques are employed, how should the Jacobian be updated (9) Should corrections to unknowns that are computed at each iteration be modified to dampen or accelerate the solution or be kept within certain bounds (10) What convergence criterion should be applied ... 

Quasi-Newton methods may seem crude, but they work well in practice. The order of convergence is (1 + /5)/2 1.6 for a single variable. Their convergence is slightly slower than a properly chosen finite difference Newton method, but they are usually more efficient in terms of total function evaluations to achieve a specified accuracy (see Dennis and Schnabel, 1983, Chapter 2). 

Determine the relative rates of convergence for (1) Newton s method, (2) a finite difference Newton method, (3) quasi-Newton method, (4) quadratic interpolation, and (5) cubic interpolation, in minimizing the following functions ... 

At this point it may seem as though we can conclude our discussion of optimization methods since we have defined an approach (Newton s method) that will rapidly converge to optimal solutions of multidimensional problems. Unfortunately, Newton s method simply cannot be applied to the DFT problem we set ourselves at the beginning of this section To apply Newton s method to minimize the total energy of a set of atoms in a supercell, E(x), requires calculating the matrix of second derivatives of the form SP E/dxi dxj. Unfortunately, it is very difficult to directly evaluate second derivatives of energy within plane-wave DFT, and most codes do not attempt to perform these calculations. The problem here is not just that Newton s method is numerically inefficient—it just is not practically feasible to evaluate the functions we need to use this method. As a result, we have to look for other approaches to minimize E(x). We will briefly discuss the two numerical methods that are most commonly used for this problem quasi-Newton and... 

We have referred to quasi-Newton methods rather than the quasi-Newton method because there are multiple definitions that can be used for the function F in this expression. The details of the function F are not central to our discussion, but you should note that this updating procedure now uses information from the current and the previous iterations of the method. This is different from all the methods we have introduced above, which only used information from the current iteration to generate a new iterate. If you think about this a little you will realize that the equations listed above only tell us how to proceed once several iterations of the method have already been made. Describing how to overcome this complication is beyond our scope here, but it does mean than when using a quasi-Newton method, the convergence of the method to a solution should really only be examined after performing a minimum of four or five iterations. 

The Broyden method is one of the simplest quasi-Newton method. The aim of quasi Newton methods is to achieve convergence properties comparable to those... 

The quasi-Newton methods estimate the matrix = H-1 by updating a previous guess of C in each iteration using only the gradient vector. These methods are very close to the quasi-Newton methods of solving a system of nonlinear equations. The order of convergence is between 1 and 2, and the minimum of a positive definite quadratic function is found in a finite number of steps. 

Table 1. Convergence in a CASSCF calculation on water, with a DTP basis. The approximate super-CI method was used with and without quasi-Newton update. The active space comprised 8 orbitals (4a12b1, 2b2 in C2v symmetry), yielding 492 CSF s. The Is orbital was inactive.

Quadratic convergence means that eventually the number of correct figures in Xc doubles at each step, clearly a desirable property. Close to x Newton s method Eq. (3.9) shows quadratic convergence while quasi-Newton methods Eq. (3.8) show superlinear convergence. The RF step Eq. (3.20) converges quadratically when the exact Hessian is used. Steepest descent with exact line search converges linearly for minimization. 

Quasi-Newton methods may be used instead of our full Newton iteration. We have used the fast (quadratic) convergence rate of our Newton algorithm as a numerical check to discriminate between periodic and very slowly changing quasi-periodic trajectories the accurate computed elements of the Jacobian in a Newton iteration can be used in stability computations for the located periodic trajectories. There are deficiencies in the use of a full Newton algorithm, such as its sometimes small radius of convergence (Schwartz, 1983). Several other possibilities for continuation methods also exist (Doedel, 1986 Seydel and Hlavacek, 1986). The pseudo-arc length continuation was sufficient for our calculations. 

Broyden, C.G. (1970). The convergence of single-rank quasi-Newton methods, Math. Comput. 24, 365-382. 

In addition, convergence calculations may be combined simultaneously with design specifications. The usual methods would be to embed the design in a convergence loop and meet the design specification in each recycle calculation. A quasi-Newton method convergence calculation in ASPEN will allow a simultaneous, more efficient solution for the more difficult problems. 

Two specific classes are emerging as the most powerful techniques for large-scale applications limited-memory quasi-Newton (LMQN) and truncated Newton methods. LMQN methods attempt to combine the modest storage and computational requirements of CG methods with the superlinear convergence properties of standard (i.e., full memory) QN methods. Similarly, TN... 

Quasi-Newton methods can be viewed as extensions of nonlinear CG methods, in which additional curvature information is used to accelerate convergence. Thus, the required analytic Hessian information, memory, and computational requirements are kept as low as possible, and the main strength of Newton methods—employing curvature information to detect and move away from saddle points efficiently—is retained. 

R. H. Byrd, J. Nocedal, and Y. Yuan, SIAM ]. Numer. Anal., 24, 1171 (1987). Global Convergence of a Class of Quasi-Newton Methods on Convex Problems. 

A. R. Conn, N. I. M. Gould, and Ph. L. Toint, Math. Prog., 2, 177 (1991). Convergence of Quasi-Newton Matrices Generated by the Symmetric Rank One Update. 

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. 

In this paragraph, a Lesaint-Raviart method is presented. A Newton algorithm allowing fixed values of the viscoelastic extra-stress components outside the finite elements is used. A fixed-point algorithm on those exter extra-stress components is also involved. Tffis quasi-Newton method needs a storage requirement of the same size as that related to a classical decoupled method, but allows improved convergence [39]. 

Care is needed in setting the step size, h, and the tolerance for convergence, s. The Quasi-Newton method generally gives fast convergence unless f" x) is close to zero, in which case convergence is poor. 

Newton and quasi-Newton methods are used for more difficult convergence problems, for example, when there are many recycle streams, or many recycles that include operations that must be converged at each iteration, such as distillation columns. The Newton and quasi-Newton methods are also often used when there are many recycles and control blocks (see Section 4.8.1). The Newton method should not normally be used unless the other methods have failed, as it is more computationally intensive and can be slower to converge for simple problems. 

---