1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 """Generic minimisation function for easy access to all of the optimization algorithms.
25
26 This file is part of the U{minfx optimisation library<https://gna.org/projects/minfx>}.
27 """
28
29
30 from re import match, search
31
32
33 from minfx.bfgs import bfgs
34 from minfx.cauchy_point import cauchy_point
35 from minfx.coordinate_descent import coordinate_descent
36 from minfx.dogleg import dogleg
37 from minfx.errors import MinfxError
38 from minfx.exact_trust_region import exact_trust_region
39 from minfx.fletcher_reeves_cg import fletcher_reeves
40 from minfx.hestenes_stiefel_cg import hestenes_stiefel
41 from minfx.levenberg_marquardt import levenberg_marquardt
42 from minfx.log_barrier_function import log_barrier_function
43 from minfx.method_of_multipliers import method_of_multipliers
44 from minfx.ncg import ncg
45 from minfx.newton import newton
46 from minfx.polak_ribiere_cg import polak_ribiere
47 from minfx.polak_ribiere_plus_cg import polak_ribiere_plus
48 from minfx.simplex import simplex
49 from minfx.steepest_descent import steepest_descent
50 from minfx.steihaug_cg import steihaug
51
52
53 try:
54 from minfx.scipy_subset.anneal import anneal
55 except ImportError:
56 SA_flag = False
57 else:
58 SA_flag = True
59
60
61
62 -def generic_minimise(func=None, dfunc=None, d2func=None, args=(), x0=None, min_algor=None, min_options=None, func_tol=1e-25, grad_tol=None, maxiter=1e6, A=None, b=None, l=None, u=None, c=None, dc=None, d2c=None, print_flag=0, print_prefix="", full_output=False):
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
295
296
297 if not len(x0):
298
299 if print_flag:
300 print("Cannot run optimisation on a model with zero parameters, directly calculating the function value.")
301
302
303 fk = func(x0)
304
305
306 results = (x0, fk, 0, 1, 0, 0, "No optimisation")
307
308
309
310
311
312
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
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
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
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
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
334
335
336
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
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
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
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
354
355
356
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
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
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
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
374
375
376
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
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
391
392
393
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
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
403
404
405
406 elif match('^[Ss][Aa]$', min_algor) or match('^[Ss]imulated [Aa]nnealing$', min_algor):
407
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
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
423 results = [
424 output[0],
425 output[1],
426 output[4],
427 output[3],
428 0,
429 0,
430 warning
431 ]
432
433
434
435
436
437 else:
438 raise MinfxError("The '%s' minimisation algorithm is not available.\n" % min_algor)
439
440
441
442
443
444 if print_flag and results is not 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
463