Skip to content

Line search

The Newton-Raphson method (and iterative methods in general) is based on a reasonable prediction, so that the iteration process converges to the ''exact'' numerical solution. If the prediction is too far from equilibrium the iteration process will not converge. This easily takes place in structures with strong nonlinearities.

The rationale behind Line Search is that the direction found by the Newton-Raphson method is often a good direction, but the step size (magnitude of the solution) is not. Furthermore, it is cheaper to compute the residual for several points along \(\boldsymbol{c}\) rather than form and factor a new system Jacobian.

The Line Search algorithm uses a prediction of the iterative solution increment \(\boldsymbol{c}^i\) as obtained by the Newton-Raphson algorithm and scales this vector by a value to minimize the energy potential1. \(\Pi = \boldsymbol{r}^T \boldsymbol{c}^{(i)}\). Note that only the magnitude is scaled, the direction of the prediction remains unchanged. While the local minimum of the energy potential represents the equilibrium, the minimum in the line search direction can be regarded as the best solution in the predicted direction. The scaled iterative increment reads:

\[ \Delta \boldsymbol{d}^{i+1} = \Delta \boldsymbol{d}^i + \lambda \boldsymbol{c}^{i+1} \]

where \(\lambda\) is a scalar scaling variable. For \(\lambda > 1.0\) an extrapolation is performed. The scaling factor is bound to \(\lambda_{min} \leq \lambda \leq \lambda_{max}\), per default numgeo uses \(\lambda_{min}=0.25\) and \(\lambda_{max}=1.0\) (no extrapolation). A minimum of \(\Pi\) in the line search direction requires that the derivative of \(\Pi\) to \(\eta\) must be zero:

\[ s(\lambda) = \frac{\partial \Pi}{\partial \lambda} = \frac{\partial \Pi}{\partial \mathbf{d}} \frac{\partial \mathbf{d}}{\partial \lambda} = \boldsymbol{r}(\lambda) \boldsymbol{c}^{i+1} = 0 \]

The above can be interpreted as follows: at the minimum, the residual \(\boldsymbol{r}\) is orthogonal to the direction \(\boldsymbol{c}\). Equation (2) can be solved by iterative refinement of \(\lambda\). In numgeo, the purpose of the Line Search is to accelerate the Newton-Raphson method or to ''help'' finding convergence where none would be achieved otherwise.

In its simplest form a linear relation between the potential at the beginning and the end of the present increment is assumed. The residual for \(\lambda=0\) is known from the previous increment, and the residual for \(\lambda=1\) is known from the present increment. Assuming a linear relation in between yields the value of \(\lambda\) without extra calculations:

\[ \lambda = - \dfrac{\boldsymbol{r}^T_0 \boldsymbol{c}^{(i)}}{\boldsymbol{r}^T \boldsymbol{c}^{(i)} - \boldsymbol{r}^T_0 \boldsymbol{c}^{(i)}} \]

The Regula-Falsi Line Search is currently not part of the public release of numgeo

  1. Strictly speaking ''energy potential'' is the correct terminology for the physical behavior, e.g. in case of plastic deformation. However, this poses no problem for the algorithmic implementation within an increment. ↩