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
274 Hessian type, these are used in a few of the trust region methods including the Dogleg and Exact
275 trust region algorithms. In these cases, when the Hessian type is set to Newton, a Hessian
276 modification can also be supplied as above. The default Hessian type is Newton, and the default
277 Hessian modification when Newton is selected is the GMW algorithm.
278 ___________________________________________________________________________________________
279 | | |
280 | Hessian type | Patterns |
281 |___________________________________|_____________________________________________________|
282 | | |
283 | Quasi-Newton BFGS | '^[Bb][Ff][Gg][Ss]$' |
284 | | |
285 | Newton | '^[Nn]ewton$' |
286 |___________________________________|_____________________________________________________|
287
288
289 For Newton minimisation, the default line search algorithm is the More and Thuente line search,
290 while the default Hessian modification is the GMW algorithm.
291 """
292
293
294
295
296
297 if match('^[Gg]rid', min_algor):
298 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)
299 if full_output:
300 results = (xk, fk, k, k, 0, 0, None)
301 else:
302 results = xk
303
304
305
306
307
308
309 elif match('^[Cc][Dd]$', min_algor) or match('^[Cc]oordinate[ _-][Dd]escent$', min_algor):
310 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)
311
312
313 elif match('^[Ss][Dd]$', min_algor) or match('^[Ss]teepest[ _-][Dd]escent$', min_algor):
314 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)
315
316
317 elif match('^[Bb][Ff][Gg][Ss]$', min_algor):
318 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)
319
320
321 elif match('^[Nn]ewton$', min_algor):
322 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)
323
324
325 elif match('^[Nn]ewton[ _-][Cc][Gg]$', min_algor) or match('^[Nn][Cc][Gg]$', min_algor):
326 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)
327
328
329
330
331
332
333 elif match('^[Cc]auchy', min_algor):
334 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)
335
336
337 elif match('^[Dd]ogleg', min_algor):
338 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)
339
340
341 elif match('^[Cc][Gg][-_ ][Ss]teihaug', min_algor) or match('^[Ss]teihaug', min_algor):
342 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)
343
344
345 elif match('^[Ee]xact', min_algor):
346 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)
347
348
349
350
351
352
353 elif match('^[Ff][Rr]$', min_algor) or match('^[Ff]letcher[-_ ][Rr]eeves$', min_algor):
354 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)
355
356
357 elif match('^[Pp][Rr]$', min_algor) or match('^[Pp]olak[-_ ][Rr]ibiere$', min_algor):
358 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)
359
360
361 elif match('^[Pp][Rr]\+$', min_algor) or match('^[Pp]olak[-_ ][Rr]ibiere\+$', min_algor):
362 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)
363
364
365 elif match('^[Hh][Ss]$', min_algor) or match('^[Hh]estenes[-_ ][Ss]tiefel$', min_algor):
366 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)
367
368
369
370
371
372
373 elif match('^[Ss]implex$', min_algor):
374 if func_tol != None:
375 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)
376 elif grad_tol != None:
377 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)
378 else:
379 raise NameError, "Simplex minimisation cannot be setup."
380
381
382 elif match('^[Ll][Mm]$', min_algor) or match('^[Ll]evenburg-[Mm]arquardt$', min_algor):
383 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)
384
385
386
387
388
389
390 elif match('^[Mm][Oo][Mm]$', min_algor) or match('[Mm]ethod of [Mm]ultipliers$', min_algor):
391 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)
392
393
394
395
396
397 else:
398 print print_prefix + "Minimiser type set incorrectly. The minimiser " + min_algor + " is not programmed.\n"
399 return
400
401
402
403
404
405 if print_flag and results != None:
406 print ""
407 if full_output:
408 xk, fk, k, f_count, g_count, h_count, warning = results
409 print print_prefix + "Parameter values: " + `xk`
410 print print_prefix + "Function value: " + `fk`
411 print print_prefix + "Iterations: " + `k`
412 print print_prefix + "Function calls: " + `f_count`
413 print print_prefix + "Gradient calls: " + `g_count`
414 print print_prefix + "Hessian calls: " + `h_count`
415 if warning:
416 print print_prefix + "Warning: " + warning
417 else:
418 print print_prefix + "Warning: None"
419 else:
420 print print_prefix + "Parameter values: " + `results`
421 print ""
422
423 return results
424