minfx.generic

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

Source Code for Module minfx.generic