Linear convergence

Bertz, S.H. (2003) Complexity of Synthetic Routes Linear, Convergent and Reflexive Syntheses. New Journal of Chemistry, 27, 870-879. 

In the above equation, the norm is usually the Euclidean norm. We have a linear convergence rate when 0 is equal to 1. Superlinear convergence rate refers to the case where 0=1 and the limit is equal to zero. When 0=2 the convergence rate is called quadratic. In general, the value of 0 depends on the algorithm while the value of the limit depends upon the function that is being minimized. 

Table 8.3 shows output generated by this PSLP algorithm when it is applied to the test problem of Section 8.5 using the objective x + 2y. This version of the problem has a nonvertex optimum with one degree of freedom. We mentioned the slow linear convergence of PSLP in this problem previously. Consider the ratio and max step bound columns of Table 8.2. Note that very small positive or negative ratios occur at every other iteration, with each such occurrence forcing a reduction...

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. 

It must be taken into account that second order MCSCF procedures, as the AH and other exact or approximate second order methods, converge quadratically when close to the final solution, but with a very small radius of convergence. More than this, when the MO-CI coupling is not included one finds linear convergence even with second order methods. For example, see Table II of Werner s paper /14/. 

The first seven iterations in Table I show slow linear convergence. The correction-halving procedure outlined previously was used at least once in iterations 2-6. The other runs in Table II behaved similarly. All took more than nine iterations, and for each case the norms would decrease slowly (even occasionally rising for one iteration) until the last two or three iterations when they would dramatically decrease. Two of the runs did not converge. 

Yield of each step Overall yield linear convergent ... 

The use of approximate Hessians within the NR method is known as pseudo-Newton-Raphson or variable metric methods. It is clear that they do not converge as fast as true NR methods, where the exact Hessian is calculated in each step, but if for example five steps can be taken for the same computational cost as one true NR step, the overall computational effort may be less. True NR methods converge quadratically near a stationary point, while pseudo-NR methods display a linear convergence. Far from a stationary point, however, the true NR method will typically also only display linear convergence. 

A rather slow convergence rate (linear convergence) persists. 

Any sequence that is linear convergent can be accelerated by a method called the Aitken method. 

Let a be a linearly convergent sequence with a limit a. By definition, we... 

By applying Aitken s method to a linearly convergent sequence obtained from fixed point (successive substitution) iteration, we can accelerate the convergence to quadratie order. This procedure is known as the Steffenson s method, which leads to Steffenson s algorithm as follows. 

Given a linearly convergent series of t , the Aitken formula generates a new and more efHcient series z ... 

Heuristic methods linearly converge to the solution in the neighborhood of the minimum. 

They (in theory in classical analysis without round-off errors) linearly converge to the minimum. The gradient tends to zero close to the minimum. Methods that exploit the gradient can, therefore, encounter problems in the neighborhood of the minimum since the search direction is numerically inaccurate. 

In the specific case of an accurate one-dimensional search along the gradient direction, it is possible to join the linear convergence ratio (Nocedal and Wright, 2000) to the maximum and minimum eigenvalues A ax and A m of the Hessian. 

Bertz, S.H. Complexity of synthetic routes Linear, convergent and reflexive syntheses, 2003b,... 

---