Gradient method convergence

Heuristic and gradient methods converge linearly in the neighborhood of the minimum, hence, although applied to quadratic functions, they require a large number of iterations to achieve the solution (theoretically infinite iterations to get the exact solution). 

Note Because of its neglect of off-diagonal blocks, this optimizer can sometimes oscillate and fail to converge. In this case, use a conjugate gradient method. 

The Polak-Ribiere prescription is usually preferred in practice. Conjugate gradient methods have much better convergence characteristics than the steepest descent, but they are again only able to locate minima. They do require slightly more storage than the steepest descent, since the previous gradient also must be saved. 

This algorithm shares with the gradient methods the ability to converge from an initial guess that may be... 

There are different variants of the conjugate gradient method each of which corresponds to a different choice of the update parameter C - Some of these different methods and their convergence properties are discussed in Appendix D. The time has been discretized into N time steps (f, = / x 8f where i = 0,1, , N — 1) and the parameter space that is being searched in order to maximize the value of the objective functional is composed of the values of the electric field strength in each of the time intervals. 

Direct search methods use only function evaluations. They search for the minimum of an objective function without calculating derivatives analytically or numerically. Direct methods are based upon heuristic rules which make no a priori assumptions about the objective function. They tend to have much poorer convergence rates than gradient methods when applied to smooth functions. Several authors claim that direct search methods are not as efficient and robust as the indirect or gradient search methods (Bard, 1974 Edgar and Himmelblau, 1988 Scales, 1986). However, in many instances direct search methods have proved to be robust and reliable particularly for systems that exhibit local minima or have complex nonlinear constraints (Wang and Luus, 1978). 

Sparse matrices are ones in which the majority of the elements are zero. If the structure of the matrix is exploited, the solution time on a computer is greatly reduced. See Duff, I. S., J. K. Reid, and A. M. Erisman (eds.), Direct Methods for Sparse Matrices, Clarendon Press, Oxford (1986) Saad, Y., Iterative Methods for Sparse Linear Systems, 2d ed., Society for Industrial and Applied Mathematics, Philadelphia (2003). The conjugate gradient method is one method for solving sparse matrix problems, since it only involves multiplication of a matrix times a vector. Thus the sparseness of the matrix is easy to exploit. The conjugate gradient method is an iterative method that converges for sure in n iterations where the matrix is an n x n matrix. 

The basic difficulty with the steepest descent method is that it is too sensitive to the scaling of/(x), so that convergence is very slow and what amounts to oscillation in the x space can easily occur. For these reasons steepest descent or ascent is not a very effective optimization technique. Fortunately, conjugate gradient methods are much faster and more accurate. 

---