Linear line search

The iteration process (5.14) together with the linear line search described by formula (5.21) gives us a numerical scheme for the steepest descent method for misfit functional minimization. Thus, this algorithm for the steepest descent method can be summarized as follows ... 

Applying a linear line search to the last problem, we obtain the optimum length of the step equal to... 

The algorithm of the Newton rnotliod wiUi the linear line search can be sum-... 

A linear line search in the conjugate gradient method... 

In particular, applying the linear line search, we find that the minimum of the parametric functional is reached if is determined by the following formula ... 

Solution of this minimization problem gives the following best estimation for the length of the step using a linear line search ... 

Derivations presented below show that in the case of a linear line search, the coefficient ko can be determined by the formula... 

If the BFGS algorithm is applied to a positive-definite quadratic function of n variables and the line search is exact, it will minimize the function in at most n iterations (Dennis and Schnabel, 1996, Chapter 9). This is also true for some other updating formulas. For nonquadratic functions, a good BFGS code usually requires more iterations than a comparable Newton implementation and may not be as accurate. Each BFGS iteration is generally faster, however, because second derivatives are not required and the system of linear equations (6.15) need not be solved. 

Note that as the line search process continues and the total step from the initial point gets larger, the number of Newton iterations generally increases. This increase occurs because the linear approximation to the active constraints, at the initial point (0.697,1.517), becomes less and less accurate as we move further from that point. 

The linear model, which may also be constructed from an approximate gradient, is simple but not particularly useful since it is unbounded and has no stationary point. It contains no information about the curvature of the function. It is the basis for the steepest descent method in which a step opposite the gradient is determined by line search vide infra). 

Quadratic convergence means that eventually the number of correct figures in Xc doubles at each step, clearly a desirable property. Close to x Newton s method Eq. (3.9) shows quadratic convergence while quasi-Newton methods Eq. (3.8) show superlinear convergence. The RF step Eq. (3.20) converges quadratically when the exact Hessian is used. Steepest descent with exact line search converges linearly for minimization. 

The simplest tcchnicgje of the line search ai ises if one assumes that in the last equation / l(mj ) is small enough that one can use a linearized representation of the... 

The length of each iteration step, the coefficient k°, can be determined with a linear or parabolic line search ... 

The classical method does not require a line search at each iteration, but it does require second order derivative information and a matrix inversion, or equivalently, the solution of a system of linear... 

An improvement on the steepest-descent method is the conjugate-gradient method. Here, the first step is the same as in the steepest-descent method, so q2 = qi - k VUi, where Ai is found fi"om a line search. The direction of each subsequent step k is defined by a vector (where k = 2,3,...) that is a linear combination of the negative gradient — Vf/ and the preceding search direction. The explicit formulas for the conjugate-gradient method are... 

A common array, shown in Figure 17.46(a), is a single linear line of hydrophones that makes up a device called a towed array, which in the oil exploration business are often called streamers. The line is towed behind the ship and is effective for searching for low-level and low-frequency signals without interference from the ship s self-noise. Figure 17.46(b) shows a more sophisticated bow array (sphere) assembly. 

In the quasi-Newton method, the next geometry is obtained from the Newton formula (15.72) plus a line search. A commonly used alternative to the quasi-Newton method is to calculate the next set of nuclear coordinates by a modified form of (15.72) in which the current coordinates Xj, Fj are replaced by linear combinations of the current coordinates and the coordinates in all the previous search steps, and the current gradient components... 

---