Dogleg method

In the original dogleg method, the parameter di is varied during the search in a complex way. It is sufficient to know that the selection of dj was based on the need to reasonably approximate the function by a quadratic function it is increased when the quadratic approximation is satisfactory and decreased otherwise. The original method can, therefore, be included in the family of trust region methods. Another strategy whereby dj is selected by means a onedimensional search is discussed later. 

As per the Levenberg-Marquardt method, even the dogleg method can be considered from other points of view ... 

One valid alternative to the Levenberg-Marquardt method is the dogleg method, also known as Powell s hybrid method (Rabinowitz, 1970). Once again, this couples the Newton and gradient methods. The original version of Powell s method was close to the tmst region concept. Powell proposed a strategy for the modification of parameter d subject to both the successes and failures of the procedure. 

There are several alternatives. For example, it is possible to perform a onedimensional search along the gradient direction. Better still, the two methods may be coupled as happens with the Levenberg-Marquardt algorithm or the dogleg method. Another choice is to perform a two-dimensional optimization on the plane defined by both the search directions. 

This technique is the basis of the MATLAB routine fsolve, whose use is demonstrated below. A further discussion of the trnst-region method, and the efficient dogleg method of implementing it, is provided in Chapter 5. 

The dogleg method solves the trust-region subproblem approximately, assuming that pW is positive-definite, although perhaps nearly singular. We say that this method solves the problem approximately, because we do not bother to find the true minimum, but merely an easily-found point within the trust region that lowers wP (p) more than the steepest descent method does. 

The dogleg method is based upon an analysis of how the trust-region minimum changes as a function of the trust radius A l. When A is very large, we have effectively an unconstrained problem and the trust-region minimum is the fiill Newton step the global minimum of m p). 

Figure 5.9 The trust-region Newton dogleg method finds the position on the two connected line segments that minimizes the model function while lying within the trust region.

The dogleg method allows us to identify quickly a point within the trust region that lowers the model cost function at least as much as the Cauchy point. The advantage over the Newton line search procedure is that the full Newton step is not automatically accepted as the search direction, avoiding the problems inherent in its erratic size and direction when... 

Currently there are several analytical methods available for calculating dogleg severity. 

It might be more interesting to use the dogieg method, by considering it from the second point of view the dogleg piecewise is used as a one-dimensional minimization, d is not given a priori according to validity considerations on the quadratic model, but it is used as an optimization variable. 

How is it possible to overcome the discussed shortcomings of line search methods and to embed more information about the function into the search for the local minimum One answer are trust-region methods (or restricted step methods). They do a search in a restricted neighborhood of the current iterate and try to minimize a quadratic model of /. For example in the double-dogleg implementation, it is a restricted step search in a two-dimensional subspace, spanned by the actual gradient and the Newton step (and further reduced to a non-smooth curve search). For information on trust region methods see e.g. Dennis and Schnabel [2], pp. 129ff. 

---