minimise.generic

45 """Generic minimisation function. 46 47 This is a generic function which can be used to access all minimisers using the same set of 48 function arguments. These are the function tolerance value for convergence tests, the maximum 49 number of iterations, a flag specifying which data structures should be returned, and a flag 50 specifying the amount of detail to print to screen. 51 52 53 Keyword Arguments 54 ~~~~~~~~~~~~~~~~~ 55 56 func: The function which returns the value. 57 58 dfunc: The function which returns the gradient. 59 60 d2func: The function which returns the Hessian. 61 62 args: The tuple of arguments to supply to the functions func, dfunc, and d2func. 63 64 x0: The vector of initial parameter value estimates (as an array). 65 66 min_algor: A string specifying which minimisation technique to use. 67 68 min_options: A tuple to pass to the minimisation function as the min_options keyword. 69 70 func_tol: The function tolerance value. Once the function value between iterations decreases 71 below this value, minimisation is terminated. 72 73 grad_tol: The gradient tolerance value. 74 75 maxiter: The maximum number of iterations. 76 77 A: Linear constraint matrix m*n (A.x >= b). 78 79 b: Linear constraint scalar vector (A.x >= b). 80 81 l: Lower bound constraint vector (l <= x <= u). 82 83 u: Upper bound constraint vector (l <= x <= u). 84 85 c: User supplied constraint function. 86 87 dc: User supplied constraint gradient function. 88 89 d2c: User supplied constraint Hessian function. 90 91 full_output: A flag specifying which data structures should be returned. The following values 92 will return, in tuple form, the following data: 93 0 - xk 94 1 - (xk, fk, k, f_count, g_count, h_count, warning) 95 where the data names correspond to: 96 xk: The array of minimised parameter values. 97 fk: The minimised function value. 98 k: The number of iterations. 99 f_count: The number of function calls. 100 g_count: The number of gradient calls. 101 h_count: The number of Hessian calls. 102 warning: The warning string. 103 104 print_flag: A flag specifying how much information should be printed to standard output during 105 minimisation. 0 means no output, 1 means minimal output, and values above 1 increase the amount 106 of output printed. 107 108 109 Minimisation algorithms 110 ~~~~~~~~~~~~~~~~~~~~~~~ 111 112 A minimisation function is selected if the minimisation algorithm argument, which should be a 113 string, matches a certain pattern. Because the python regular expression 'match' statement is 114 used, various strings can be supplied to select the same minimisation algorithm. Below is a 115 list of the minimisation algorithms available together with the corresponding patterns. 116 117 This is a short description of python regular expression, for more information, see the 118 regular expression syntax section of the Python Library Reference. Some of the regular 119 expression syntax used in this function is: 120 121 [] - A sequence or set of characters to match to a single character. For example, 122 '[Nn]ewton' will match both 'Newton' and 'newton'. 123 124 ^ - Match the start of the string. 125 126 $ - Match the end of the string. For example, '^[Ll][Mm]$' will match 'lm' and 'LM' but 127 will not match if characters are placed either before or after these strings. 128 129 To select a minimisation algorithm, set the argument to a string which matches the given 130 pattern. 131 132 133 Parameter initialisation methods: 134 ___________________________________________________________________________________________ 135 | | | 136 | Minimisation algorithm | Patterns | 137 |___________________________________|_____________________________________________________| 138 | | | 139 | Grid search | '^[Gg]rid' | 140 |___________________________________|_____________________________________________________| 141 142 143 Unconstrained line search methods: 144 ___________________________________________________________________________________________ 145 | | | 146 | Minimisation algorithm | Patterns | 147 |___________________________________|_____________________________________________________| 148 | | | 149 | Back-and-forth coordinate descent | '^[Cc][Dd]$' or '^[Cc]oordinate[ _-][Dd]escent$' | 150 | Steepest descent | '^[Ss][Dd]$' or '^[Ss]teepest[ _-][Dd]escent$' | 151 | Quasi-Newton BFGS | '^[Bb][Ff][Gg][Ss]$' | 152 | Newton | '^[Nn]ewton$' | 153 | Newton-CG | '^[Nn]ewton[ _-][Cc][Gg]$' or '^[Nn][Cc][Gg]$' | 154 |___________________________________|_____________________________________________________| 155 156 157 Unconstrained trust-region methods: 158 ___________________________________________________________________________________________ 159 | | | 160 | Minimisation algorithm | Patterns | 161 |___________________________________|_____________________________________________________| 162 | | | 163 | Cauchy point | '^[Cc]auchy' | 164 | Dogleg | '^[Dd]ogleg' | 165 | CG-Steihaug | '^[Cc][Gg][-_ ][Ss]teihaug' or '^[Ss]teihaug' | 166 | Exact trust region | '^[Ee]xact' | 167 |___________________________________|_____________________________________________________| 168 169 170 Unconstrained conjugate gradient methods: 171 ___________________________________________________________________________________________ 172 | | | 173 | Minimisation algorithm | Patterns | 174 |___________________________________|_____________________________________________________| 175 | | | 176 | Fletcher-Reeves | '^[Ff][Rr]$' or '^[Ff]letcher[-_ ][Rr]eeves$' | 177 | Polak-Ribiere | '^[Pp][Rr]$' or '^[Pp]olak[-_ ][Rr]ibiere$' | 178 | Polak-Ribiere + | '^[Pp][Rr]\+$' or '^[Pp]olak[-_ ][Rr]ibiere\+$' | 179 | Hestenes-Stiefel | '^[Hh][Ss]$' or '^[Hh]estenes[-_ ][Ss]tiefel$' | 180 |___________________________________|_____________________________________________________| 181 182 183 Miscellaneous unconstrained methods: 184 ___________________________________________________________________________________________ 185 | | | 186 | Minimisation algorithm | Patterns | 187 |___________________________________|_____________________________________________________| 188 | | | 189 | Simplex | '^[Ss]implex$' | 190 | Levenberg-Marquardt | '^[Ll][Mm]$' or '^[Ll]evenburg-[Mm]arquardt$' | 191 |___________________________________|_____________________________________________________| 192 193 194 Constrained methods: 195 ___________________________________________________________________________________________ 196 | | | 197 | Minimisation algorithm | Patterns | 198 |___________________________________|_____________________________________________________| 199 | | | 200 | Method of Multipliers | '^[Mm][Oo][Mm]$' or '[Mm]ethod of [Mm]ultipliers$' | 201 |___________________________________|_____________________________________________________| 202 203 204 205 Minimisation options 206 ~~~~~~~~~~~~~~~~~~~~ 207 208 The minimisation options can be given in any order. 209 210 211 Line search algorithms. These are used in the line search methods and the conjugate gradient 212 methods. The default is the Backtracking line search. 213 ___________________________________________________________________________________________ 214 | | | 215 | Line search algorithm | Patterns | 216 |___________________________________|_____________________________________________________| 217 | | | 218 | Backtracking line search | '^[Bb]ack' | 219 |___________________________________|_____________________________________________________| 220 | | | 221 | Nocedal and Wright interpolation | '^[Nn][Ww][Ii]' or | 222 | based line search | '^[Nn]ocedal[ _][Ww]right[ _][Ii]nt' | 223 |___________________________________|_____________________________________________________| 224 | | | 225 | Nocedal and Wright line search | '^[Nn][Ww][Ww]' or | 226 | for the Wolfe conditions | '^[Nn]ocedal[ _][Ww]right[ _][Ww]olfe' | 227 |___________________________________|_____________________________________________________| 228 | | | 229 | More and Thuente line search | '^[Mm][Tt]' or '^[Mm]ore[ _][Tt]huente$' | 230 |___________________________________|_____________________________________________________| 231 | | | 232 | No line search | '^[Nn]one$' | 233 |___________________________________|_____________________________________________________| 234 235 236 237 Hessian modifications. These are used in the Newton, Dogleg, and Exact trust region algorithms. 238 ___________________________________________________________________________________________ 239 | | | 240 | Hessian modification | Patterns | 241 |___________________________________|_____________________________________________________| 242 | | | 243 | Unmodified Hessian | '[Nn]one' | 244 |___________________________________|_____________________________________________________| 245 | | | 246 | Eigenvalue modification | '^[Ee]igen' | 247 |___________________________________|_____________________________________________________| 248 | | | 249 | Cholesky with added multiple of | '^[Cc]hol' | 250 | the identity | | 251 |___________________________________|_____________________________________________________| 252 | | | 253 | The Gill, Murray, and Wright | '^[Gg][Mm][Ww]$' | 254 | modified Cholesky algorithm | | 255 |___________________________________|_____________________________________________________| 256 | | | 257 | The Schnabel and Eskow 1999 | '^[Ss][Ee]99' | 258 | algorithm | | 259 |___________________________________|_____________________________________________________| 260 261 262 263 Hessian type, these are used in a few of the trust region methods including the Dogleg and Exact 264 trust region algorithms. In these cases, when the Hessian type is set to Newton, a Hessian 265 modification can also be supplied as above. The default Hessian type is Newton, and the default 266 Hessian modification when Newton is selected is the GMW algorithm. 267 ___________________________________________________________________________________________ 268 | | | 269 | Hessian type | Patterns | 270 |___________________________________|_____________________________________________________| 271 | | | 272 | Quasi-Newton BFGS | '^[Bb][Ff][Gg][Ss]$' | 273 | Newton | '^[Nn]ewton$' | 274 |___________________________________|_____________________________________________________| 275 276 277 For Newton minimisation, the default line search algorithm is the More and Thuente line search, 278 while the default Hessian modification is the GMW algorithm. 279 """ 280 281 # Parameter initialisation methods. 282 ################################### 283 284 # Grid search. 285 if match('^[Gg]rid', min_algor): 286 xk, fk, k = grid(func=func, args=args, grid_ops=min_options, A=A, b=b, l=l, u=u, c=c, print_flag=print_flag) 287 if full_output: 288 results = (xk, fk, k, k, 0, 0, None) 289 else: 290 results = xk 291 292 293 # Unconstrained line search algorithms. 294 ####################################### 295 296 # Back-and-forth coordinate descent minimisation. 297 elif match('^[Cc][Dd]$', min_algor) or match('^[Cc]oordinate[ _-][Dd]escent$', min_algor): 298 results = coordinate_descent(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 299 300 # Steepest descent minimisation. 301 elif match('^[Ss][Dd]$', min_algor) or match('^[Ss]teepest[ _-][Dd]escent$', min_algor): 302 results = steepest_descent(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 303 304 # Quasi-Newton BFGS minimisation. 305 elif match('^[Bb][Ff][Gg][Ss]$', min_algor): 306 results = bfgs(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 307 308 # Newton minimisation. 309 elif match('^[Nn]ewton$', min_algor): 310 results = newton(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 311 312 # Newton-CG minimisation. 313 elif match('^[Nn]ewton[ _-][Cc][Gg]$', min_algor) or match('^[Nn][Cc][Gg]$', min_algor): 314 results = ncg(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 315 316 317 # Unconstrained trust-region algorithms. 318 ######################################## 319 320 # Cauchy point minimisation. 321 elif match('^[Cc]auchy', min_algor): 322 results = cauchy_point(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 323 324 # Dogleg minimisation. 325 elif match('^[Dd]ogleg', min_algor): 326 results = dogleg(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 327 328 # CG-Steihaug minimisation. 329 elif match('^[Cc][Gg][-_ ][Ss]teihaug', min_algor) or match('^[Ss]teihaug', min_algor): 330 results = steihaug(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 331 332 # Exact trust region minimisation. 333 elif match('^[Ee]xact', min_algor): 334 results = exact_trust_region(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 335 336 337 # Unconstrained conjugate gradient algorithms. 338 ############################################## 339 340 # Fletcher-Reeves conjugate gradient minimisation. 341 elif match('^[Ff][Rr]$', min_algor) or match('^[Ff]letcher[-_ ][Rr]eeves$', min_algor): 342 results = fletcher_reeves(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 343 344 # Polak-Ribiere conjugate gradient minimisation. 345 elif match('^[Pp][Rr]$', min_algor) or match('^[Pp]olak[-_ ][Rr]ibiere$', min_algor): 346 results = polak_ribiere(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 347 348 # Polak-Ribiere + conjugate gradient minimisation. 349 elif match('^[Pp][Rr]\+$', min_algor) or match('^[Pp]olak[-_ ][Rr]ibiere\+$', min_algor): 350 results = polak_ribiere_plus(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 351 352 # Hestenes-Stiefel conjugate gradient minimisation. 353 elif match('^[Hh][Ss]$', min_algor) or match('^[Hh]estenes[-_ ][Ss]tiefel$', min_algor): 354 results = hestenes_stiefel(func=func, dfunc=dfunc, args=args, x0=x0, min_options=min_options, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 355 356 357 # Miscellaneous unconstrained algorithms. 358 ######################################### 359 360 # Simplex minimisation. 361 elif match('^[Ss]implex$', min_algor): 362 if func_tol != None: 363 results = simplex(func=func, args=args, x0=x0, func_tol=func_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 364 elif grad_tol != None: 365 results = simplex(func=func, args=args, x0=x0, func_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 366 else: 367 raise NameError, "Simplex minimisation cannot be setup." 368 369 # Levenberg-Marquardt minimisation. 370 elif match('^[Ll][Mm]$', min_algor) or match('^[Ll]evenburg-[Mm]arquardt$', min_algor): 371 results = levenberg_marquardt(chi2_func=func, dchi2_func=dfunc, dfunc=min_options[0], errors=min_options[1], args=args, x0=x0, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag, print_prefix=print_prefix) 372 373 374 # Constrainted algorithms. 375 ########################## 376 377 # Method of Multipliers. 378 elif match('^[Mm][Oo][Mm]$', min_algor) or match('[Mm]ethod of [Mm]ultipliers$', min_algor): 379 results = method_of_multipliers(func=func, dfunc=dfunc, d2func=d2func, args=args, x0=x0, min_options=min_options, A=A, b=b, l=l, u=u, c=c, dc=dc, d2c=d2c, func_tol=func_tol, grad_tol=grad_tol, maxiter=maxiter, full_output=full_output, print_flag=print_flag) 380 381 382 # No match to minimiser string. 383 ############################### 384 385 else: 386 print print_prefix + "Minimiser type set incorrectly. The minimiser " + min_algor + " is not programmed.\n" 387 return 388 389 390 # Finish. 391 ######### 392 393 if print_flag and results != None: 394 print "" 395 if full_output: 396 xk, fk, k, f_count, g_count, h_count, warning = results 397 print print_prefix + "Parameter values: " + `xk` 398 print print_prefix + "Function value: " + `fk` 399 print print_prefix + "Iterations: " + `k` 400 print print_prefix + "Function calls: " + `f_count` 401 print print_prefix + "Gradient calls: " + `g_count` 402 print print_prefix + "Hessian calls: " + `h_count` 403 if warning: 404 print print_prefix + "Warning: " + warning 405 else: 406 print print_prefix + "Warning: None" 407 else: 408 print print_prefix + "Parameter values: " + `results` 409 print "" 410 411 return results

Source Code for Module minimise.generic