Quadratic convergence method

If we consider the limiting case where p=0 and q O, i.e., the case where there are no unknown parameters and only some of the initial states are to be estimated, the previously outlined procedure represents a quadratically convergent method for the solution of two-point boundary value problems. Obviously in this case, we need to compute only the sensitivity matrix P(t). It can be shown that under these conditions the Gauss-Newton method is a typical quadratically convergent "shooting method." As such it can be used to solve optimal control problems using the Boundary Condition Iteration approach (Kalogerakis, 1983). 

Such a full investigation is virtually impossible except in some very simple cases, and is even then usually very difficult. In particular for quadratically convergent methods, the convergence region is usually bounded by a fractal instead of a regular curve. Out of necessity, the convergence properties studied are usually some necessary criterion on f and c near the desired solution, and the influence of that criterion on the asymptotic error. 

MC-SCF calculations on polyatomic molecules are still rather rare, although there have been many such calculations on triatomic and diatomic molecules. Levy45 has described the results of such calculations using a minimal STO basis set for CH4, C2H4, and CjjHa. A quadratically convergent method was described and the results of localizing the orbitals were investigated. 

Murtagh B A and Sargent R W 1970 Computational experience with quadratically convergent minimisation methods Comput. J. 13 185... 

Bacskay G B 1981 A quadratically convergent Hartree-Fock (QC-SCF) method. Applications to the closed-shell case Chem. Phys. 61 385... 

Werner H-J and Meyer W 1981 A quadratically convergent MCSCF method for the simultaneous optimization of several states J. Chem. Phys 74 5794... 

The Gauss-Newton method is directly related to Newton s method. The main difference between the two is that Newton s method requires the computation of second order derivatives as they arise from the direct differentiation of the objective function with respect to k. These second order terms are avoided when the Gauss-Newton method is used since the model equations are first linearized and then substituted into the objective function. The latter constitutes a key advantage of the Gauss-Newton method compared to Newton s method, which also exhibits quadratic convergence. 

Minimization of S(k) can be accomplished by using almost any technique available from optimization theory, however since each objective function evaluation requires the integration of the state equations, the use of quadratically convergent algorithms is highly recommended. The Gauss-Newton method is the most appropriate one for ODE models (Bard, 1970) and it presented in detail below. 

The above method is the well-known Gauss-Newton method for differential equation systems and it exhibits quadratic convergence to the optimum. Computational modifications to the above algorithm for the incorporation of prior knowledge about the parameters (Bayessian estimation) are discussed in detail in Chapter 8. 

The quadratic convergence of the Gauss-Newton method is shown in Table 17.2 where the reduction of the LS objective function is shown for an initial guess of k =l00 andk2=0.1. 

The chief merit of this method is its rapid rate of convergence starting with a set of good initial guesses. Since the discussion of its quadratic convergence... 

EXAMPLE 6.4 APPLICATION OF NEWTON S METHOD AND QUADRATIC CONVERGENCE... 

All the basis functions were given independently variable orbital exponents (CH4, 9 NH3,8 H20,7) and all exponents were optimised by the quadratically convergent direct search method of Fletcher (19). For comparison, the calculations were repeated with the GHOs constrained to have the symmetry of the molecule three independent variables for CH4 (1 sc, sp3, 1 sH) four for NH3 (1 sN, sp3, sp3, 1 sH) and four for H20 (1 sQ, sp3, sp3,1 sH). The most striking qualitative result is the confirmation of the results quoted earlier for H2 when the orbital exponents are all optimised, the GHO basis has the symmetry of the molecule there is no spatial symmetry dilemma.9)... 

Observe that for a converging Newton s process (3.3.66a,b) hold. Indeed, due to quadratic convergence of Newton s method, we have... 

Finally, let us stress that the obtained asymptotic feature is entirely due to quadratic convergence characteristic of Newton s method. Thus no process with a linear convergence, e.g., Picard s method, would generate an asymptotic sequence. 

In the method of steepest descents one calculates the gradient at a point. The method of attack depends on whether this gradient may be calculated analytically or numerically (which requires calculations at N + 1 points for an TV dimensional surface) and one moves along this direction until the lowest point is reached when a new gradient is calculated. When one is close to the minimum and the gradient is small it is necessary to have a method which is quadratically convergent, and to calculate the general quadratic function for N dimensions numerically requires N -t 1)(A+ 2)/2 function evaluations. 

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. 

---