1 #ifndef __TAOLINESEARCH_OWARMIJO_H 2 #define __TAOLINESEARCH_OWARMIJO_H 3 4 // Context for an Armijo (nonmonotone) linesearch for orthant wise unconstrained 5 // minimization. 6 // 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: 9 // 10 // f(x + (beta**i)d) <= f(x) + (sigma*beta**i)<grad f(x),d> 11 // 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: 14 // 15 // f(x + (beta**i)d) <= R + (sigma*beta**i)<grad f(x),d> 16 // 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. 23 // 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. 30 // 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). 35 // 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. 40 // 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. 49 // 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 "tao-private/taolinesearch_impl.h" 64 typedef struct { 65 PetscReal *memory; 66 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 73 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 78 79 PetscBool nondescending; 80 PetscBool memorySetup; 81 82 Vec x; // Maintain reference to variable vector to check for changes 83 Vec work; 84 } TAOLINESEARCH_OWARMIJO_CTX; 85 86 static PetscErrorCode ProjWork_OWLQN(Vec w,Vec x,Vec gv,PetscReal *gdx); 87 88 #endif 89