Other methods

Nelder-Mead simplex

Some optimisation algorithms cannot be classified within line search, trust region, or conjugate gradient categories. For example the well known Nelder-Mead simplex optimisation algorithm. The technique is often used as the only the function value is employed and hence the derivation of the gradient and Hessian can be avoided. The simplex is created as an n-dimensional geometric object with n + 1 vertices. The first vertex is the starting position. Each of the other n vertices are created by shifting the starting position by a small amount parallel to one of unit vectors defining the coordinate system of the space. Four simple rules are used to move the simplex through the space: reflection, extension, contraction, and a shrinkage of the entire simplex. The result of these movements is that the simplex moves in an ameoboid-like fashion downhill, shrinking to pass through tight gaps and expanding to quickly move through non-convoluted space, eventually finding the minimum.

Key to these four movements is the pivot point, the centre of the face created by the n vertices with the lowest function values. The first movement is a reflection - the vertex with the greatest function value is reflected through the pivot point on the opposite face of the simplex. If the function value at this new position is less than all others the simplex is allowed to extend - the point is moved along the line to twice the distance between the current position and the pivot point. Otherwise if the function value is greater than the second highest value but less than the highest value, the reflected simplex is contracted. The reflected point is moved to be closer to the simplex, its position being half way between the reflected position and the pivot point. Otherwise if the function value at the reflected point is greater than all other vertices, then the original simplex is contracted - the highest vertex is moved to a position half way between the current position and the pivot point. Finally if none of these four movements yield an improvement, then the simplex is shrunk halfway towards the vertex with the lowest function value.

Levenberg-Marquardt algorithm

Another algorithm is the commonly used Levenberg-Marquardt algorithm (Marquardt, 1963; Levenberg, 1944). This is the algorithm used by the model-free analysis programs Modelfree4, Dasha, and Tensor2. This technique is designed for least-squares problems to which the chi-squared equation (14.2) belongs. The key to the algorithm is the replacement of the Hessian with the Levenberg-Marquardt matrix J^TJ + λI, where J is the Jacobian of the system calculated as the matrix of partial derivatives of the residuals, λ > 0 is a factor related to the trust-region radius, and I is the identity matrix. The algorithm is conceptually allied to the trust region methods and its performance varies finely between that of the steepest descent and the pure Newton step. When far from the minimum λ is large and the algorithm takes steps close to the gradient; when in vicinity of the minimum λ heads towards zero and the steps taken approximate the Newton direction. Hence the algorithm avoids the problems of the Newton algorithm when non-convex curvature is encountered and approximates the Newton step in convex regions of the space.

The technique does have one weak point though which is often mentioned only in the small print. That is that the algorithm catastrophically fails when the Levenberg-Marquardt matrix is singular. This occurs whenever a parameter is undefined. For example in a model-free analysis if the order parameter is one, then the corresponding internal correlation time can take any value. Performing a grid search with such undefined points greatly amplifies the problem and is the reason why many published model-free papers contain results with order parameters fixed at one (d'Auvergne and Gooley, 2008b).