1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 from re import match
25 from grid import grid
26 from coordinate_descent import coordinate_descent
27 from steepest_descent import steepest_descent
28 from bfgs import bfgs
29 from newton import newton
30 from ncg import ncg
31 from cauchy_point import cauchy_point
32 from dogleg import dogleg
33 from steihaug_cg import steihaug
34 from exact_trust_region import exact_trust_region
35 from fletcher_reeves_cg import fletcher_reeves
36 from polak_ribiere_cg import polak_ribiere
37 from polak_ribiere_plus_cg import polak_ribiere_plus
38 from hestenes_stiefel_cg import hestenes_stiefel
39 from simplex import simplex
40 from levenberg_marquardt import levenberg_marquardt
41 from method_of_multipliers import method_of_multipliers
42
43
44 -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, full_output=0, print_flag=0, print_prefix=""):
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.
92
93 print_flag: A flag specifying how much information should be printed to standard output during
94 minimisation. 0 means no output, 1 means minimal output, and values above 1 increase the amount
95 of output printed.
96
97
98 Minimisation output
99 ~~~~~~~~~~~~~~~~~~~
100
101 The following values of the 'full_output' flag will return, in tuple form, the following data
102
103 0: 'xk',
104 1: '(xk, fk, k, f_count, g_count, h_count, warning)',
105
106 where the data names correspond to
107
108 'xk': The array of minimised parameter values,
109 'fk': The minimised function value,
110 'k': The number of iterations,
111 'f_count': The number of function calls,
112 'g_count': The number of gradient calls,
113 'h_count': The number of Hessian calls,
114 'warning': The warning string.
115
116
117 Minimisation algorithms
118 ~~~~~~~~~~~~~~~~~~~~~~~
119
120 A minimisation function is selected if the minimisation algorithm argument, which should be a
121 string, matches a certain pattern. Because the python regular expression 'match' statement is
122 used, various strings can be supplied to select the same minimisation algorithm. Below is a
123 list of the minimisation algorithms available together with the corresponding patterns.
124
125 This is a short description of python regular expression, for more information, see the
126 regular expression syntax section of the Python Library Reference. Some of the regular
127 expression syntax used in this function is:
128
129 '[]': A sequence or set of characters to match to a single character. For example,
130 '[Nn]ewton' will match both 'Newton' and 'newton'.
131
132 '^': Match the start of the string.
133
134 '$': Match the end of the string. For example, '^[Ll][Mm]$' will match 'lm' and 'LM' but
135 will not match if characters are placed either before or after these strings.
136
137 To select a minimisation algorithm, set the argument to a string which matches the given
138 pattern.
139
140
141 Parameter initialisation methods:
142 ___________________________________________________________________________________________
143 | | |
144 | Minimisation algorithm | Patterns |
145 |___________________________________|_____________________________________________________|
146 | | |
147 | Grid search | '^[Gg]rid' |
148 |___________________________________|_____________________________________________________|
149
150
151 Unconstrained line search methods:
152 ___________________________________________________________________________________________
153 | | |
154 | Minimisation algorithm | Patterns |
155 |___________________________________|_____________________________________________________|
156 | | |
157 | Back-and-forth coordinate descent | '^[Cc][Dd]$' or '^[Cc]oordinate[ _-][Dd]escent$' |
158 | | |
159 | Steepest descent | '^[Ss][Dd]$' or '^[Ss]teepest[ _-][Dd]escent$' |
160 | | |
161 | Quasi-Newton BFGS | '^[Bb][Ff][Gg][Ss]$' |
162 | | |
163 | Newton | '^[Nn]ewton$' |
164 | | |
165 | Newton-CG | '^[Nn]ewton[ _-][Cc][Gg]$' or '^[Nn][Cc][Gg]$' |
166 |___________________________________|_____________________________________________________|
167
168
169 Unconstrained trust-region methods:
170 ___________________________________________________________________________________________
171 | | |
172 | Minimisation algorithm | Patterns |
173 |___________________________________|_____________________________________________________|
174 | | |
175 | Cauchy point | '^[Cc]auchy' |
176 | | |
177 | Dogleg | '^[Dd]ogleg' |
178 | | |
179 | CG-Steihaug | '^[Cc][Gg][-_ ][Ss]teihaug' or '^[Ss]teihaug' |
180 | | |
181 | Exact trust region | '^[Ee]xact' |
182 |___________________________________|_____________________________________________________|
183
184
185 Unconstrained conjugate gradient methods:
186 ___________________________________________________________________________________________
187 | | |
188 | Minimisation algorithm | Patterns |
189 |___________________________________|_____________________________________________________|
190 | | |
191 | Fletcher-Reeves | '^[Ff][Rr]$' or '^[Ff]letcher[-_ ][Rr]eeves$' |
192 | | |
193 | Polak-Ribiere | '^[Pp][Rr]$' or '^[Pp]olak[-_ ][Rr]ibiere$' |
194 | | |
195 | Polak-Ribiere + | '^[Pp][Rr]\+$' or '^[Pp]olak[-_ ][Rr]ibiere\+$' |
196 | | |
197 | Hestenes-Stiefel | '^[Hh][Ss]$' or '^[Hh]estenes[-_ ][Ss]tiefel$' |
198 |___________________________________|_____________________________________________________|
199
200
201 Miscellaneous unconstrained methods:
202 ___________________________________________________________________________________________
203 | | |
204 | Minimisation algorithm | Patterns |
205 |___________________________________|_____________________________________________________|
206 | | |
207 | Simplex | '^[Ss]implex$' |
208 | | |
209 | Levenberg-Marquardt | '^[Ll][Mm]$' or '^[Ll]evenburg-[Mm]arquardt$' |
210 |___________________________________|_____________________________________________________|
211
212
213 Constrained methods:
214 ___________________________________________________________________________________________
215 | | |
216 | Minimisation algorithm | Patterns |
217 |___________________________________|_____________________________________________________|
218 | | |
219 | Method of Multipliers | '^[Mm][Oo][Mm]$' or '[Mm]ethod of [Mm]ultipliers$' |
220 |___________________________________|_____________________________________________________|
221
222
223
224 Minimisation options
225 ~~~~~~~~~~~~~~~~~~~~
226
227 The minimisation options can be given in any order.
228
229
230 Line search algorithms. These are used in the line search methods and the conjugate gradient
231 methods. The default is the Backtracking line search.
232 ___________________________________________________________________________________________
233 | | |
234 | Line search algorithm | Patterns |
235 |___________________________________|_____________________________________________________|
236 | | |
237 | Backtracking line search | '^[Bb]ack' |
238 | | |
239 | Nocedal and Wright interpolation | '^[Nn][Ww][Ii]' or |
240 | based line search | '^[Nn]ocedal[ _][Ww]right[ _][Ii]nt' |
241 | | |
242 | Nocedal and Wright line search | '^[Nn][Ww][Ww]' or |
243 | for the Wolfe conditions | '^[Nn]ocedal[ _][Ww]right[ _][Ww]olfe' |
244 | | |
245 | More and Thuente line search | '^[Mm][Tt]' or '^[Mm]ore[ _][Tt]huente$' |
246 | | |
247 | No line search | '^[Nn]one$' |
248 |___________________________________|_____________________________________________________|
249
250
251
252 Hessian modifications. These are used in the Newton, Dogleg, and Exact trust region algorithms.
253 ___________________________________________________________________________________________
254 | | |
255 | Hessian modification | Patterns |
256 |___________________________________|_____________________________________________________|
257 | | |
258 | Unmodified Hessian | '[Nn]one' |
259 | | |
260 | Eigenvalue modification | '^[Ee]igen' |
261 | | |
262 | Cholesky with added multiple of | '^[Cc]hol' |
263 | the identity | |
264 | | |
265 | The Gill, Murray, and Wright | '^[Gg][Mm][Ww]$' |
266 | modified Cholesky algorithm | |
267 | | |
268 | The Schnabel and Eskow 1999 | '^[Ss][Ee]99' |
269 | algorithm | |
270 |___________________________________|_____________________________________________________|
271
272
273 As both the line search algorithm and Hessian modification can be specified for Newton
274 optimisation, supplying the option 'None' may appear to be ambiguous. In fact, the Hessian
275 takes precedence over the line search. Hence supplying the option 'None' with the Newton
276 algorithm selects the unmodified Hessian. Supplying 'None' twice will turn off the Hessian
277 modification and no step length selection (or line search) will be performed.
278
279
280 Hessian type, these are used in a few of the trust region methods including the Dogleg and Exact
281 trust region algorithms. In these cases, when the Hessian type is set to Newton, a Hessian
282 modification can also be supplied as above. The default Hessian type is Newton, and the default
283 Hessian modification when Newton is selected is the GMW algorithm.
284 ___________________________________________________________________________________________
285 | | |
286 | Hessian type | Patterns |
287 |___________________________________|_____________________________________________________|
288 | | |
289 | Quasi-Newton BFGS | '^[Bb][Ff][Gg][Ss]$' |
290 | | |
291 | Newton | '^[Nn]ewton$' |
292 |___________________________________|_____________________________________________________|
293
294
295 For Newton minimisation, the default line search algorithm is the More and Thuente line search,
296 while the default Hessian modification is the GMW algorithm.
297 """
298
299
300
301
302
303 if match('^[Gg]rid', min_algor):
304 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)
305 if full_output:
306 results = (xk, fk, k, k, 0, 0, None)
307 else:
308 results = xk
309
310
311
312
313
314
315 elif match('^[Cc][Dd]$', min_algor) or match('^[Cc]oordinate[ _-][Dd]escent$', min_algor):
316 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)
317
318
319 elif match('^[Ss][Dd]$', min_algor) or match('^[Ss]teepest[ _-][Dd]escent$', min_algor):
320 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)
321
322
323 elif match('^[Bb][Ff][Gg][Ss]$', min_algor):
324 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)
325
326
327 elif match('^[Nn]ewton$', min_algor):
328 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)
329
330
331 elif match('^[Nn]ewton[ _-][Cc][Gg]$', min_algor) or match('^[Nn][Cc][Gg]$', min_algor):
332 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)
333
334
335
336
337
338
339 elif match('^[Cc]auchy', min_algor):
340 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)
341
342
343 elif match('^[Dd]ogleg', min_algor):
344 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)
345
346
347 elif match('^[Cc][Gg][-_ ][Ss]teihaug', min_algor) or match('^[Ss]teihaug', min_algor):
348 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)
349
350
351 elif match('^[Ee]xact', min_algor):
352 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)
353
354
355
356
357
358
359 elif match('^[Ff][Rr]$', min_algor) or match('^[Ff]letcher[-_ ][Rr]eeves$', min_algor):
360 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)
361
362
363 elif match('^[Pp][Rr]$', min_algor) or match('^[Pp]olak[-_ ][Rr]ibiere$', min_algor):
364 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)
365
366
367 elif match('^[Pp][Rr]\+$', min_algor) or match('^[Pp]olak[-_ ][Rr]ibiere\+$', min_algor):
368 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)
369
370
371 elif match('^[Hh][Ss]$', min_algor) or match('^[Hh]estenes[-_ ][Ss]tiefel$', min_algor):
372 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)
373
374
375
376
377
378
379 elif match('^[Ss]implex$', min_algor):
380 if func_tol != None:
381 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)
382 elif grad_tol != None:
383 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)
384 else:
385 raise NameError, "Simplex minimisation cannot be setup."
386
387
388 elif match('^[Ll][Mm]$', min_algor) or match('^[Ll]evenburg-[Mm]arquardt$', min_algor):
389 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)
390
391
392
393
394
395
396 elif match('^[Mm][Oo][Mm]$', min_algor) or match('[Mm]ethod of [Mm]ultipliers$', min_algor):
397 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)
398
399
400
401
402
403 else:
404 print print_prefix + "Minimiser type set incorrectly. The minimiser " + min_algor + " is not programmed.\n"
405 return
406
407
408
409
410
411 if print_flag and results != None:
412 print ""
413 if full_output:
414 xk, fk, k, f_count, g_count, h_count, warning = results
415 print print_prefix + "Parameter values: " + `xk`
416 print print_prefix + "Function value: " + `fk`
417 print print_prefix + "Iterations: " + `k`
418 print print_prefix + "Function calls: " + `f_count`
419 print print_prefix + "Gradient calls: " + `g_count`
420 print print_prefix + "Hessian calls: " + `h_count`
421 if warning:
422 print print_prefix + "Warning: " + warning
423 else:
424 print print_prefix + "Warning: None"
425 else:
426 print print_prefix + "Parameter values: " + `results`
427 print ""
428
429 return results
430