Trust region methods

The above subproblem can be solved very efficiently for fixed values of the multipliers X and v and penalty parameter p. Here a gradient projection trust region method is applied. Once subproblem (3-104) is solved, the multipliers and penalty parameter are updated in an outer loop and the cycle repeats until the KKT conditions for (3-85) are satisfied. LANCELOT works best when exact second derivatives are available. This promotes a fast convergence rate in solving each... 

Difficulty 3 can be ameliorated by using (properly) finite difference approximation as substitutes for derivatives. To overcome difficulty 4, two classes of methods exist to modify the pure Newton s method so that it is guaranteed to converge to a local minimum from an arbitrary starting point. The first of these, called trust region methods, minimize the quadratic approximation, Equation (6.10), within an elliptical region, whose size is adjusted so that the objective improves at each iteration see Section 6.3.2. The second class, line search methods, modifies the pure Newton s method in two ways (1) instead of taking a step size of one, a line search is used and (2) if the Hessian matrix H(x ) is not positive-definite, it is replaced by a positive-definite matrix that is close to H(x ). This is motivated by the easily verified fact that, if H(x ) is positive-definite, the Newton direction... 

The trust region method is usually implemented with the exact Hessian. Updated Hessians may also be used but an approximate Hessian usually does not contain enough information about the function to make the trust region reliable in all directions. The trust region method provides us with the possibility to carry out an unbiased search in all directions at each step. An updated Hessian does not contain the information necessary for such a search. 

One advantage of the KF minimization over trust region RSO minimization is that we need only calculate the lowest eigenvalue and eigenvector of the augmented Hessian. In the trust region method we must first calculate the lowest eigenvalue of the Hessian and then solve a set of Unear equations to obtain the step. 

In conclusion, the trust region method is more intuitive than the RF model and provides a more natural step control. On the other hand, RF optimization avoids the solution of one set of linear equations, which is important when the number of variables is large. 

Although line searches are typically easier to program, trust region methods may be effective when the procedure for determining the search direction p is not necessarily one of descent. This may be the case for methods that use finite-difference approximations to the Hessian in the procedure for specifying p (discussed in later sections). As we shall see later, in BFGS quasi-Newton or truncated Newton methods line searches may be preferable because descent directions are guaranteed. 

The quality of line search in these nonlinear CG algorithms is crucial. (Typically, line searches are used rather than the trust region methods.) Adjustments must be made not only to preserve the mutual conjugacy of the search directions—a property critical for finite termination of the method—but also to ensure that each generated direction is one of descent. A technique known as... 

G. Korte, Eds., pp. 256-287, Springer-Verlag, New York, 1983. Recent Developments in Algorithms and Software for Trust Region Methods. 

The region where the objective function can be represented by a quadratic function is reduced (trust region methods). 

Methods based on relations (3.111) and (3.112) are called reduced step methods or trust region methods. 

It is worth stressing that the trust region methods choose the direction and length of the step simultaneously. In fact, in general, both the direction and the step length change any time the size of the trust region is modified. 

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. 

The trust region method is the most interesting when a reduction of the search zone is involved. In that case, it is essential to identify the correction d that minimizes the auxiliary function (7.65) with the constraint ... 

There is a third reason why Feasible Direction Methods should not be called methods that use the active constraints strategy it is possible to ejqjloit the direction di also including the bound for the variables (beyond the bounds already existing) to limit the search region. In this case, the direction d is not used to perform a onedimensional search, since a Trust region method or Reduced-step method is used. 

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. 

Notice that the quasi-Newton methods, descent methods and trust region methods form a hierarchy with respect to the goodness of the initial guess when searching for a minimizer of E, see Table 3. Whenever x ... 

The basic structure of an iterative local optimization algorithm is one of greedy descent . It is based on one of the following two algorithmic frameworks line-search or trust-region methods. Both are found throughout the literature and in software packages and are essential components of effective... 

---