1 #pragma once 2 3 /* Context for an Armijo (nonmonotone) linesearch for unconstrained 4 minimization. 5 6 Given a function f, the current iterate x, and a descent direction d: 7 Find the smallest i in 0, 1, 2, ..., such that: 8 9 f(x + (beta**i)d) <= f(x) + (sigma*beta**i)<grad f(x),d> 10 11 The nonmonotone modification of this linesearch replaces the f(x) term 12 with a reference value, R, and seeks to find the smallest i such that: 13 14 f(x + (beta**i)d) <= R + (sigma*beta**i)<grad f(x),d> 15 16 This modification does effect neither the convergence nor rate of 17 convergence of an algorithm when R is chosen appropriately. Essentially, 18 R must decrease on average in some sense. The benefit of a nonmonotone 19 linesearch is that local minimizers can be avoided (by allowing increase 20 in function value), and typically, fewer iterations are performed in 21 the main code. 22 23 The reference value is chosen based upon some historical information 24 consisting of function values for previous iterates. The amount of 25 historical information used is determined by the memory size where the 26 memory is used to store the previous function values. The memory is 27 initialized to alpha*f(x^0) for some alpha >= 1, with alpha=1 signifying 28 that we always force decrease from the initial point. 29 30 The reference value can be the maximum value in the memory or can be 31 chosen to provide some mean descent. Elements are removed from the 32 memory with a replacement policy that either removes the oldest 33 value in the memory (FIFO), or the largest value in the memory (MRU). 34 35 Additionally, we can add a watchdog strategy to the search, which 36 essentially accepts small directions and only checks the nonmonotonic 37 descent criteria every m-steps. This strategy is NOT implemented in 38 the code. 39 40 Finally, care must be taken when steepest descent directions are used. 41 For example, when the Newton direction does not satisfy a sufficient 42 descent criteria. The code will apply the same test regardless of 43 the direction. This type of search may not be appropriate for all 44 algorithms. For example, when a gradient direction is used, we may 45 want to revert to the best point found and reset the memory so that 46 we stay in an appropriate level set after using a gradient steps. 47 This type of search is currently NOT supported by the code. 48 49 References: 50 + * - Armijo, "Minimization of Functions Having Lipschitz Continuous 51 First-Partial Derivatives," Pacific Journal of Mathematics, volume 16, 52 pages 1-3, 1966. 53 . * - Ferris and Lucidi, "Nonmonotone Stabilization Methods for Nonlinear 54 Equations," Journal of Optimization Theory and Applications, volume 81, 55 pages 53-71, 1994. 56 . * - Grippo, Lampariello, and Lucidi, "A Nonmonotone Line Search Technique 57 for Newton's Method," SIAM Journal on Numerical Analysis, volume 23, 58 pages 707-716, 1986. 59 - * - Grippo, Lampariello, and Lucidi, "A Class of Nonmonotone Stabilization 60 Methods in Unconstrained Optimization," Numerische Mathematik, volume 59, 61 pages 779-805, 1991. */ 62 #include <petsc/private/taolinesearchimpl.h> 63 typedef struct { 64 PetscReal *memory; 65 66 PetscReal alpha; /* Initial reference factor >= 1 */ 67 PetscReal beta; /* Steplength determination < 1 */ 68 PetscReal beta_inf; /* Steplength determination < 1 */ 69 PetscReal sigma; /* Acceptance criteria < 1) */ 70 PetscReal minimumStep; /* Minimum step size */ 71 PetscReal lastReference; /* Reference value of last iteration */ 72 73 PetscInt memorySize; /* Number of functions kept in memory */ 74 PetscInt current; /* Current element for FIFO */ 75 PetscInt referencePolicy; /* Integer for reference calculation rule */ 76 PetscInt replacementPolicy; /* Policy for replacing values in memory */ 77 78 PetscBool nondescending; 79 PetscBool memorySetup; 80 81 Vec x; /* Maintain reference to variable vector to check for changes */ 82 Vec work; 83 } TaoLineSearch_ARMIJO; 84