minimise.line_search.nocedal_wright

30 """A line search algorithm based on interpolation. 31 32 Pages 56-57, from 'Numerical Optimization' by Jorge Nocedal and Stephen J. Wright, 1999, 2nd ed. 33 34 Requires the gradient function. 35 36 37 Function options 38 ~~~~~~~~~~~~~~~~ 39 40 func - The function to minimise. 41 func_prime - The function which returns the gradient vector. 42 args - The tuple of arguments to supply to the functions func and dfunc. 43 x - The parameter vector at minimisation step k. 44 f - The function value at the point x. 45 g - The function gradient vector at the point x. 46 p - The descent direction. 47 a_init - Initial step length. 48 mu - Constant determining the slope for the sufficient decrease condition (0 < mu < 1). 49 """ 50 51 # Initialise values. 52 i = 1 53 f_count = 0 54 a0 = {} 55 a0['a'] = 0.0 56 a0['phi'] = f 57 a0['phi_prime'] = dot(g, p) 58 59 # Initialise sequence data. 60 a = {} 61 a['a'] = a_init 62 a['phi'] = apply(func, (x + a['a']*p,)+args) 63 f_count = f_count + 1 64 65 if print_flag: 66 print "\n<Line search initial values>" 67 print_data("Pre (a0)", i-1, a0) 68 69 # Test for errors. 70 if a0['phi_prime'] >= 0.0: 71 raise NameError, "The gradient at point 0 of this line search is positive, ie p is not a descent direction and the line search will not work." 72 73 # Check for sufficient decrease. If so, return a_init. Otherwise the interval [0, a_init] contains acceptable step lengths. 74 if a['phi'] <= a0['phi'] + mu * a['a'] * a0['phi_prime']: 75 return a['a'], f_count 76 77 # Backup a_last. 78 a_last = copy.deepcopy(a) 79 80 # Quadratic interpolation. 81 a_new = - 0.5 * a0['phi_prime'] * a['a']**2 / (a['phi'] - a0['phi'] - a0['phi_prime']*a['a']) 82 a['a'] = a_new 83 a['phi'] = apply(func, (x + a['a']*p,)+args) 84 f_count = f_count + 1 85 86 # Check for sufficient decrease. If so, return a['a']. 87 if a['phi'] <= a0['phi'] + mu * a['a'] * a0['phi_prime']: 88 return a['a'], f_count 89 90 while 1: 91 if print_flag: 92 print "<Line search iteration i = " + `i` + " >" 93 print_data("Initial (a)", i, a) 94 print_data("Initial (a_last)", i, a_last) 95 96 beta1 = 1.0 / (a_last['a']**2 * a['a']**2 * (a['a'] - a_last['a'])) 97 beta2 = a['phi'] - a0['phi'] - a0['phi_prime'] * a['a'] 98 beta3 = a_last['phi'] - a0['phi'] - a0['phi_prime'] * a_last['a'] 99 100 fact_a = beta1 * (a_last['a']**2 * beta2 - a['a']**2 * beta3) 101 fact_b = beta1 * (-a_last['a']**3 * beta2 + a['a']**3 * beta3) 102 103 a_new = {} 104 a_new['a'] = (-fact_b + sqrt(fact_b**2 - 3.0 * fact_a * a0['phi_prime'])) / (3.0 * fact_a) 105 a_new['phi'] = apply(func, (x + a_new['a']*p,)+args) 106 f_count = f_count + 1 107 108 # Check for sufficient decrease. If so, return a_new['a']. 109 if a_new['phi'] <= a0['phi'] + mu * a_new['a'] * a0['phi_prime']: 110 return a_new['a'], f_count 111 112 # Safeguarding. 113 if a['a'] - a_new['a'] > 0.5 * a['a'] or 1.0 - a_new['a']/a['a'] < 0.9: 114 a_new['a'] = 0.5 * a['a'] 115 a_new['phi'] = apply(func, (x + a_new['a']*p,)+args) 116 f_count = f_count + 1 117 118 # Updating. 119 a_last = copy.deepcopy(a) 120 a = copy.deepcopy(a_new)

Source Code for Module minimise.line_search.nocedal_wright_interpol