Line data    Source code

       1            0 : // Distributed under the MIT License.
       2              : // See LICENSE.txt for details.
       3              : 
       4              : #pragma once
       5              : 
       6              : #include <cstddef>
       7              : 
       8              : namespace NonlinearSolver::newton_raphson {
       9              : /*!
      10              :  * \brief Find the next step length for the line-search globalization
      11              :  *
      12              :  * The next step length is chosen such that it minimizes the quadratic (first
      13              :  * globalization step, i.e., when `globalization_iteration_id` is 0) or cubic
      14              :  * (subsequent globalization steps) polynomial interpolation. This function
      15              :  * implements Algorithm A6.3.1 in \cite DennisSchnabel (p. 325). This is how
      16              :  * argument names map to symbols in that algorithm:
      17              :  *
      18              :  * - `step_length`: \f$\lambda\f$
      19              :  * - `prev_step_length`: \f$\lambda_\mathrm{prev}\f$
      20              :  * - `residual`: \f$f_c\f$
      21              :  * - `residual_slope`: \f$g^T p < 0\f$
      22              :  * - `next_residual`: \f$f_+\f$
      23              :  * - `prev_residual`: \f$f_{+,\mathrm{prev}}\f$
      24              :  *
      25              :  * Note that the argument `residual_slope` is the derivative of the residual
      26              :  * function \f$f\f$ w.r.t. the step length, i.e.
      27              :  * \f$\frac{\mathrm{d}f}{\mathrm{d}\lambda}\f$, which must be negative. For the
      28              :  * common scenario where \f$f(x)=|\boldsymbol{r}(x)|^2\f$, i.e. the residual
      29              :  * function is the L2 norm of a residual vector \f$\boldsymbol{r}(x)\f$, and
      30              :  * where that in turn is the residual of a nonlinear equation
      31              :  * \f$\boldsymbol{r}(x)=b-A_\mathrm{nonlinear}(x)\f$ in a Newton-Raphson step as
      32              :  * described in `NonlinearSolver::newton_raphson::NewtonRaphson`, then the
      33              :  * `residual_slope` reduces to
      34              :  *
      35              :  * \f{equation}
      36              :  * \frac{\mathrm{d}f}{\mathrm{d}\lambda} =
      37              :  * \frac{\mathrm{d}f}{\mathrm{d}x^i} \frac{\mathrm{d}x^i}{\mathrm{d}\lambda} =
      38              :  * 2 \boldsymbol{r}(x) \cdot \frac{\mathrm{d}\boldsymbol{r}}{\mathrm{d}x^i}
      39              :  * \frac{\mathrm{d}x^i}{\mathrm{d}\lambda} =
      40              :  * -2 |\boldsymbol{r}(x)|^2 = -2 f(x) \equiv -2 f_c
      41              :  * \text{.}
      42              :  * \f}
      43              :  *
      44              :  * Here we have used the relation
      45              :  *
      46              :  * \f{equation}
      47              :  * \frac{\mathrm{d}\boldsymbol{r}}{\mathrm{d}x^i}
      48              :  * \frac{\mathrm{d}x^i}{\mathrm{d}\lambda} =
      49              :  * -\frac{\delta A_\mathrm{nonlinear}}{\delta x}\cdot\delta x = -r
      50              :  * \f}
      51              :  *
      52              :  * of a Newton-Raphson step of full length \f$\delta x\f$.
      53              :  */
      54            1 : double next_step_length(size_t globalization_iteration_id, double step_length,
      55              :                         double prev_step_length, double residual,
      56              :                         double residual_slope, double next_residual,
      57              :                         double prev_residual);
      58              : }  // namespace NonlinearSolver::newton_raphson