Actual source code: armijo.h

      1: #ifndef __TAOLINESEARCH_ARMIJO_H

      4: /* Context for an Armijo (nonmonotone) linesearch for unconstrained
      5:    minimization.

      7:    Given a function f, the current iterate x, and a descent direction d:
      8:    Find the smallest i in 0, 1, 2, ..., such that:

     10:       f(x + (beta**i)d) <= f(x) + (sigma*beta**i)<grad f(x),d>

     12:    The nonmonotone modification of this linesearch replaces the f(x) term
     13:    with a reference value, R, and seeks to find the smallest i such that:

     15:       f(x + (beta**i)d) <= R + (sigma*beta**i)<grad f(x),d>

     17:    This modification does effect neither the convergence nor rate of
     18:    convergence of an algorithm when R is chosen appropriately.  Essentially,
     19:    R must decrease on average in some sense.  The benefit of a nonmonotone
     20:    linesearch is that local minimizers can be avoided (by allowing increase
     21:    in function value), and typically, fewer iterations are performed in
     22:    the main code.

     24:    The reference value is chosen based upon some historical information
     25:    consisting of function values for previous iterates.  The amount of
     26:    historical information used is determined by the memory size where the
     27:    memory is used to store the previous function values.  The memory is
     28:    initialized to alpha*f(x^0) for some alpha >= 1, with alpha=1 signifying
     29:    that we always force decrease from the initial point.

     31:    The reference value can be the maximum value in the memory or can be
     32:    chosen to provide some mean descent.  Elements are removed from the
     33:    memory with a replacement policy that either removes the oldest
     34:    value in the memory (FIFO), or the largest value in the memory (MRU).

     36:    Additionally, we can add a watchdog strategy to the search, which
     37:    essentially accepts small directions and only checks the nonmonotonic
     38:    descent criteria every m-steps.  This strategy is NOT implemented in
     39:    the code.

     41:    Finally, care must be taken when steepest descent directions are used.
     42:    For example, when the Newton direction is not not satisfy a sufficient
     43:    descent criteria.  The code will apply the same test regardless of
     44:    the direction.  This type of search may not be appropriate for all
     45:    algorithms.  For example, when a gradient direction is used, we may
     46:    want to revert to the best point found and reset the memory so that
     47:    we stay in an appropriate level set after using a gradient steps.
     48:    This type of search is currently NOT supported by the code.

     50:    References:
     51:     Armijo, "Minimization of Functions Having Lipschitz Continuous
     52:       First-Partial Derivatives," Pacific Journal of Mathematics, volume 16,
     53:       pages 1-3, 1966.
     54:     Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear
     55:       Equations," Journal of Optimization Theory and Applications, volume 81,
     56:       pages 53-71, 1994.
     57:     Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique
     58:       for Newton's Method," SIAM Journal on Numerical Analysis, volume 23,
     59:       pages 707-716, 1986.
     60:     Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization
     61:       Methods in Unconstrained Optimization," Numerische Mathematik, volume 59,
     62:       pages 779-805, 1991. */
     63: #include <petsc/private/taolinesearchimpl.h>
     64: typedef struct {
     65:   PetscReal *memory;

     67:   PetscReal alpha;                      /* Initial reference factor >= 1 */
     68:   PetscReal beta;                       /* Steplength determination < 1 */
     69:   PetscReal beta_inf;           /* Steplength determination < 1 */
     70:   PetscReal sigma;                      /* Acceptance criteria < 1) */
     71:   PetscReal minimumStep;                /* Minimum step size */
     72:   PetscReal lastReference;              /* Reference value of last iteration */

     74:   PetscInt memorySize;          /* Number of functions kept in memory */
     75:   PetscInt current;                     /* Current element for FIFO */
     76:   PetscInt referencePolicy;             /* Integer for reference calculation rule */
     77:   PetscInt replacementPolicy;   /* Policy for replacing values in memory */

     79:   PetscBool nondescending;
     80:   PetscBool memorySetup;

     82:   Vec x;        /* Maintain reference to variable vector to check for changes */
     83:   Vec work;
     84: } TaoLineSearch_ARMIJO;

     86: #endif