Search and Trust Region Steps

A line search consists of an approximate one-dimensional minimization of the objective function along the computed direction p. This produces an acceptable step X and a new iterate xk + Xp. Function and gradient evaluations of the objective function are required in each line search iteration. In contrast, the trust region strategy minimizes approximately a local quadratic model of the function using current Hessian information. An optimal step that lies within 

The trust radius in the trust region approach is estimated on the basis of the local Hessian s characteristics (positive-definite, positive-semidefinite, indefinite). The basic idea is to choose s nearly in the current negative gradient direction (—gk) when the trust radius is small, and approach the Newton step -Hk x%k as the trust region is increased. (Hk and g denote the Hessian and gradient, respectively, at xk). Note from condition [12] that these two choices correspond to the extremal cases (M = / and M = H) of general descent directions of form p = — M 1g, where M is a positive-definite approximation to the Hessian. 

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. 

In general, there has been no clear evidence for superiority of one approach over another. Indeed, both techniques are incorporated into minimization software with approximately equal success. Later we sketch the line search procedure, which we find easier to grasp and simpler to implement in practice. For further perspective and algorithmic details, the reader is referred to the recent review of Dennis and Schnabel and references cited therein.54 

At the first step, a cubic polynomial can be constructed from the two function values f(0), f Kt) and the two slopes g(0),g(Xt). The slopes are the directional derivatives defined as g(k) = g(xk + Xp )Tp. Note in the figure a negative slope at X = 0, as p is a descent direction. 

---