Actual source code: armijo.h

      1: // Context for an Armijo (nonmonotone) linesearch for unconstrained
      2: // minimization.
      3: //
      4: // Given a function f, the current iterate x, and a descent direction d:
      5: // Find the smallest i in 0, 1, 2, ..., such that:
      6: //
      7: //    f(x + (beta**i)d) <= f(x) + (sigma*beta**i)<grad f(x),d>
      8: //
      9: // The nonmonotone modification of this linesearch replaces the f(x) term
     10: // with a reference value, R, and seeks to find the smallest i such that:
     11: //
     12: //    f(x + (beta**i)d) <= R + (sigma*beta**i)<grad f(x),d>
     13: //
     14: // This modification does effect neither the convergence nor rate of
     15: // convergence of an algorithm when R is chosen appropriately.  Essentially,
     16: // R must decrease on average in some sense.  The benefit of a nonmonotone
     17: // linesearch is that local minimizers can be avoided (by allowing increase
     18: // in function value), and typically, fewer iterations are performed in
     19: // the main code.
     20: //
     21: // The reference value is chosen based upon some historical information
     22: // consisting of function values for previous iterates.  The amount of
     23: // historical information used is determined by the memory size where the
     24: // memory is used to store the previous function values.  The memory is
     25: // initialized to alpha*f(x^0) for some alpha >= 1, with alpha=1 signifying
     26: // that we always force decrease from the initial point.
     27: //
     28: // The reference value can be the maximum value in the memory or can be
     29: // chosen to provide some mean descent.  Elements are removed from the
     30: // memory with a replacement policy that either removes the oldest
     31: // value in the memory (FIFO), or the largest value in the memory (MRU).
     32: //
     33: // Additionally, we can add a watchdog strategy to the search, which
     34: // essentially accepts small directions and only checks the nonmonotonic
     35: // descent criteria every m-steps.  This strategy is NOT implemented in
     36: // the code.
     37: //
     38: // Finally, care must be taken when steepest descent directions are used.
     39: // For example, when the Newton direction is not not satisfy a sufficient
     40: // descent criteria.  The code will apply the same test regardless of
     41: // the direction.  This type of search may not be appropriate for all
     42: // algorithms.  For example, when a gradient direction is used, we may
     43: // want to revert to the best point found and reset the memory so that
     44: // we stay in an appropriate level set after using a gradient steps.
     45: // This type of search is currently NOT supported by the code.
     46: //
     47: // References:
     48: //  Armijo, "Minimization of Functions Having Lipschitz Continuous
     49: //    First-Partial Derivatives," Pacific Journal of Mathematics, volume 16,
     50: //    pages 1-3, 1966.
     51: //  Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear
     52: //    Equations," Journal of Optimization Theory and Applications, volume 81,
     53: //    pages 53-71, 1994.
     54: //  Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique
     55: //    for Newton's Method," SIAM Journal on Numerical Analysis, volume 23,
     56: //    pages 707-716, 1986.
     57: //  Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization
     58: //    Methods in Unconstrained Optimization," Numerische Mathematik, volume 59,
     59: //    pages 779-805, 1991.

     61: #ifndef __TAO_ARMIJO_H

     64: #include "src/tao_impl.h"
     65: #include "tao_solver.h"

     67: typedef struct {
     68:   double *memory;

     70:   double alpha;                        // Initial reference factor >= 1
     71:   double beta;                        // Steplength determination < 1
     72:   double sigma;                        // Acceptance criteria < 1)
     73:   double minimumStep;                // Minimum step size
     74:   double lastReference;                // Reference value of last iteration

     76:   int memorySize;                // Number of functions kept in memory
     77:   int current;                        // Current element for FIFO
     78:   int referencePolicy;                // Integer for reference calculation rule
     79:   int replacementPolicy;        // Policy for replacing values in memory
     80: } TAO_ARMIJO;

     82: #endif