Coverage for /home/martinb/.local/share/virtualenvs/camcops/lib/python3.6/site-packages/scipy/optimize/_minimize.py : 12%

Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Unified interfaces to minimization algorithms.
4Functions
5---------
6- minimize : minimization of a function of several variables.
7- minimize_scalar : minimization of a function of one variable.
8"""
10__all__ = ['minimize', 'minimize_scalar']
13from warnings import warn
15import numpy as np
18# unconstrained minimization
19from .optimize import (_minimize_neldermead, _minimize_powell, _minimize_cg,
20 _minimize_bfgs, _minimize_newtoncg,
21 _minimize_scalar_brent, _minimize_scalar_bounded,
22 _minimize_scalar_golden, MemoizeJac)
23from ._trustregion_dogleg import _minimize_dogleg
24from ._trustregion_ncg import _minimize_trust_ncg
25from ._trustregion_krylov import _minimize_trust_krylov
26from ._trustregion_exact import _minimize_trustregion_exact
27from ._trustregion_constr import _minimize_trustregion_constr
29# constrained minimization
30from .lbfgsb import _minimize_lbfgsb
31from .tnc import _minimize_tnc
32from .cobyla import _minimize_cobyla
33from .slsqp import _minimize_slsqp
34from ._constraints import (old_bound_to_new, new_bounds_to_old,
35 old_constraint_to_new, new_constraint_to_old,
36 NonlinearConstraint, LinearConstraint, Bounds)
37from ._differentiable_functions import FD_METHODS
39MINIMIZE_METHODS = ['nelder-mead', 'powell', 'cg', 'bfgs', 'newton-cg',
40 'l-bfgs-b', 'tnc', 'cobyla', 'slsqp', 'trust-constr',
41 'dogleg', 'trust-ncg', 'trust-exact', 'trust-krylov']
44def minimize(fun, x0, args=(), method=None, jac=None, hess=None,
45 hessp=None, bounds=None, constraints=(), tol=None,
46 callback=None, options=None):
47 """Minimization of scalar function of one or more variables.
49 Parameters
50 ----------
51 fun : callable
52 The objective function to be minimized.
54 ``fun(x, *args) -> float``
56 where ``x`` is an 1-D array with shape (n,) and ``args``
57 is a tuple of the fixed parameters needed to completely
58 specify the function.
59 x0 : ndarray, shape (n,)
60 Initial guess. Array of real elements of size (n,),
61 where 'n' is the number of independent variables.
62 args : tuple, optional
63 Extra arguments passed to the objective function and its
64 derivatives (`fun`, `jac` and `hess` functions).
65 method : str or callable, optional
66 Type of solver. Should be one of
68 - 'Nelder-Mead' :ref:`(see here) <optimize.minimize-neldermead>`
69 - 'Powell' :ref:`(see here) <optimize.minimize-powell>`
70 - 'CG' :ref:`(see here) <optimize.minimize-cg>`
71 - 'BFGS' :ref:`(see here) <optimize.minimize-bfgs>`
72 - 'Newton-CG' :ref:`(see here) <optimize.minimize-newtoncg>`
73 - 'L-BFGS-B' :ref:`(see here) <optimize.minimize-lbfgsb>`
74 - 'TNC' :ref:`(see here) <optimize.minimize-tnc>`
75 - 'COBYLA' :ref:`(see here) <optimize.minimize-cobyla>`
76 - 'SLSQP' :ref:`(see here) <optimize.minimize-slsqp>`
77 - 'trust-constr':ref:`(see here) <optimize.minimize-trustconstr>`
78 - 'dogleg' :ref:`(see here) <optimize.minimize-dogleg>`
79 - 'trust-ncg' :ref:`(see here) <optimize.minimize-trustncg>`
80 - 'trust-exact' :ref:`(see here) <optimize.minimize-trustexact>`
81 - 'trust-krylov' :ref:`(see here) <optimize.minimize-trustkrylov>`
82 - custom - a callable object (added in version 0.14.0),
83 see below for description.
85 If not given, chosen to be one of ``BFGS``, ``L-BFGS-B``, ``SLSQP``,
86 depending if the problem has constraints or bounds.
87 jac : {callable, '2-point', '3-point', 'cs', bool}, optional
88 Method for computing the gradient vector. Only for CG, BFGS,
89 Newton-CG, L-BFGS-B, TNC, SLSQP, dogleg, trust-ncg, trust-krylov,
90 trust-exact and trust-constr.
91 If it is a callable, it should be a function that returns the gradient
92 vector:
94 ``jac(x, *args) -> array_like, shape (n,)``
96 where ``x`` is an array with shape (n,) and ``args`` is a tuple with
97 the fixed parameters. If `jac` is a Boolean and is True, `fun` is
98 assumed to return and objective and gradient as and ``(f, g)`` tuple.
99 Methods 'Newton-CG', 'trust-ncg', 'dogleg', 'trust-exact', and
100 'trust-krylov' require that either a callable be supplied, or that
101 `fun` return the objective and gradient.
102 If None or False, the gradient will be estimated using 2-point finite
103 difference estimation with an absolute step size.
104 Alternatively, the keywords {'2-point', '3-point', 'cs'} can be used
105 to select a finite difference scheme for numerical estimation of the
106 gradient with a relative step size. These finite difference schemes
107 obey any specified `bounds`.
108 hess : {callable, '2-point', '3-point', 'cs', HessianUpdateStrategy}, optional
109 Method for computing the Hessian matrix. Only for Newton-CG, dogleg,
110 trust-ncg, trust-krylov, trust-exact and trust-constr. If it is
111 callable, it should return the Hessian matrix:
113 ``hess(x, *args) -> {LinearOperator, spmatrix, array}, (n, n)``
115 where x is a (n,) ndarray and `args` is a tuple with the fixed
116 parameters. LinearOperator and sparse matrix returns are
117 allowed only for 'trust-constr' method. Alternatively, the keywords
118 {'2-point', '3-point', 'cs'} select a finite difference scheme
119 for numerical estimation. Or, objects implementing
120 `HessianUpdateStrategy` interface can be used to approximate
121 the Hessian. Available quasi-Newton methods implementing
122 this interface are:
124 - `BFGS`;
125 - `SR1`.
127 Whenever the gradient is estimated via finite-differences,
128 the Hessian cannot be estimated with options
129 {'2-point', '3-point', 'cs'} and needs to be
130 estimated using one of the quasi-Newton strategies.
131 Finite-difference options {'2-point', '3-point', 'cs'} and
132 `HessianUpdateStrategy` are available only for 'trust-constr' method.
133 hessp : callable, optional
134 Hessian of objective function times an arbitrary vector p. Only for
135 Newton-CG, trust-ncg, trust-krylov, trust-constr.
136 Only one of `hessp` or `hess` needs to be given. If `hess` is
137 provided, then `hessp` will be ignored. `hessp` must compute the
138 Hessian times an arbitrary vector:
140 ``hessp(x, p, *args) -> ndarray shape (n,)``
142 where x is a (n,) ndarray, p is an arbitrary vector with
143 dimension (n,) and `args` is a tuple with the fixed
144 parameters.
145 bounds : sequence or `Bounds`, optional
146 Bounds on variables for L-BFGS-B, TNC, SLSQP, Powell, and
147 trust-constr methods. There are two ways to specify the bounds:
149 1. Instance of `Bounds` class.
150 2. Sequence of ``(min, max)`` pairs for each element in `x`. None
151 is used to specify no bound.
153 constraints : {Constraint, dict} or List of {Constraint, dict}, optional
154 Constraints definition (only for COBYLA, SLSQP and trust-constr).
155 Constraints for 'trust-constr' are defined as a single object or a
156 list of objects specifying constraints to the optimization problem.
157 Available constraints are:
159 - `LinearConstraint`
160 - `NonlinearConstraint`
162 Constraints for COBYLA, SLSQP are defined as a list of dictionaries.
163 Each dictionary with fields:
165 type : str
166 Constraint type: 'eq' for equality, 'ineq' for inequality.
167 fun : callable
168 The function defining the constraint.
169 jac : callable, optional
170 The Jacobian of `fun` (only for SLSQP).
171 args : sequence, optional
172 Extra arguments to be passed to the function and Jacobian.
174 Equality constraint means that the constraint function result is to
175 be zero whereas inequality means that it is to be non-negative.
176 Note that COBYLA only supports inequality constraints.
177 tol : float, optional
178 Tolerance for termination. For detailed control, use solver-specific
179 options.
180 options : dict, optional
181 A dictionary of solver options. All methods accept the following
182 generic options:
184 maxiter : int
185 Maximum number of iterations to perform. Depending on the
186 method each iteration may use several function evaluations.
187 disp : bool
188 Set to True to print convergence messages.
190 For method-specific options, see :func:`show_options()`.
191 callback : callable, optional
192 Called after each iteration. For 'trust-constr' it is a callable with
193 the signature:
195 ``callback(xk, OptimizeResult state) -> bool``
197 where ``xk`` is the current parameter vector. and ``state``
198 is an `OptimizeResult` object, with the same fields
199 as the ones from the return. If callback returns True
200 the algorithm execution is terminated.
201 For all the other methods, the signature is:
203 ``callback(xk)``
205 where ``xk`` is the current parameter vector.
207 Returns
208 -------
209 res : OptimizeResult
210 The optimization result represented as a ``OptimizeResult`` object.
211 Important attributes are: ``x`` the solution array, ``success`` a
212 Boolean flag indicating if the optimizer exited successfully and
213 ``message`` which describes the cause of the termination. See
214 `OptimizeResult` for a description of other attributes.
216 See also
217 --------
218 minimize_scalar : Interface to minimization algorithms for scalar
219 univariate functions
220 show_options : Additional options accepted by the solvers
222 Notes
223 -----
224 This section describes the available solvers that can be selected by the
225 'method' parameter. The default method is *BFGS*.
227 **Unconstrained minimization**
229 Method :ref:`Nelder-Mead <optimize.minimize-neldermead>` uses the
230 Simplex algorithm [1]_, [2]_. This algorithm is robust in many
231 applications. However, if numerical computation of derivative can be
232 trusted, other algorithms using the first and/or second derivatives
233 information might be preferred for their better performance in
234 general.
236 Method :ref:`CG <optimize.minimize-cg>` uses a nonlinear conjugate
237 gradient algorithm by Polak and Ribiere, a variant of the
238 Fletcher-Reeves method described in [5]_ pp.120-122. Only the
239 first derivatives are used.
241 Method :ref:`BFGS <optimize.minimize-bfgs>` uses the quasi-Newton
242 method of Broyden, Fletcher, Goldfarb, and Shanno (BFGS) [5]_
243 pp. 136. It uses the first derivatives only. BFGS has proven good
244 performance even for non-smooth optimizations. This method also
245 returns an approximation of the Hessian inverse, stored as
246 `hess_inv` in the OptimizeResult object.
248 Method :ref:`Newton-CG <optimize.minimize-newtoncg>` uses a
249 Newton-CG algorithm [5]_ pp. 168 (also known as the truncated
250 Newton method). It uses a CG method to the compute the search
251 direction. See also *TNC* method for a box-constrained
252 minimization with a similar algorithm. Suitable for large-scale
253 problems.
255 Method :ref:`dogleg <optimize.minimize-dogleg>` uses the dog-leg
256 trust-region algorithm [5]_ for unconstrained minimization. This
257 algorithm requires the gradient and Hessian; furthermore the
258 Hessian is required to be positive definite.
260 Method :ref:`trust-ncg <optimize.minimize-trustncg>` uses the
261 Newton conjugate gradient trust-region algorithm [5]_ for
262 unconstrained minimization. This algorithm requires the gradient
263 and either the Hessian or a function that computes the product of
264 the Hessian with a given vector. Suitable for large-scale problems.
266 Method :ref:`trust-krylov <optimize.minimize-trustkrylov>` uses
267 the Newton GLTR trust-region algorithm [14]_, [15]_ for unconstrained
268 minimization. This algorithm requires the gradient
269 and either the Hessian or a function that computes the product of
270 the Hessian with a given vector. Suitable for large-scale problems.
271 On indefinite problems it requires usually less iterations than the
272 `trust-ncg` method and is recommended for medium and large-scale problems.
274 Method :ref:`trust-exact <optimize.minimize-trustexact>`
275 is a trust-region method for unconstrained minimization in which
276 quadratic subproblems are solved almost exactly [13]_. This
277 algorithm requires the gradient and the Hessian (which is
278 *not* required to be positive definite). It is, in many
279 situations, the Newton method to converge in fewer iteraction
280 and the most recommended for small and medium-size problems.
282 **Bound-Constrained minimization**
284 Method :ref:`L-BFGS-B <optimize.minimize-lbfgsb>` uses the L-BFGS-B
285 algorithm [6]_, [7]_ for bound constrained minimization.
287 Method :ref:`Powell <optimize.minimize-powell>` is a modification
288 of Powell's method [3]_, [4]_ which is a conjugate direction
289 method. It performs sequential one-dimensional minimizations along
290 each vector of the directions set (`direc` field in `options` and
291 `info`), which is updated at each iteration of the main
292 minimization loop. The function need not be differentiable, and no
293 derivatives are taken. If bounds are not provided, then an
294 unbounded line search will be used. If bounds are provided and
295 the initial guess is within the bounds, then every function
296 evaluation throughout the minimization procedure will be within
297 the bounds. If bounds are provided, the initial guess is outside
298 the bounds, and `direc` is full rank (default has full rank), then
299 some function evaluations during the first iteration may be
300 outside the bounds, but every function evaluation after the first
301 iteration will be within the bounds. If `direc` is not full rank,
302 then some parameters may not be optimized and the solution is not
303 guaranteed to be within the bounds.
305 Method :ref:`TNC <optimize.minimize-tnc>` uses a truncated Newton
306 algorithm [5]_, [8]_ to minimize a function with variables subject
307 to bounds. This algorithm uses gradient information; it is also
308 called Newton Conjugate-Gradient. It differs from the *Newton-CG*
309 method described above as it wraps a C implementation and allows
310 each variable to be given upper and lower bounds.
312 **Constrained Minimization**
314 Method :ref:`COBYLA <optimize.minimize-cobyla>` uses the
315 Constrained Optimization BY Linear Approximation (COBYLA) method
316 [9]_, [10]_, [11]_. The algorithm is based on linear
317 approximations to the objective function and each constraint. The
318 method wraps a FORTRAN implementation of the algorithm. The
319 constraints functions 'fun' may return either a single number
320 or an array or list of numbers.
322 Method :ref:`SLSQP <optimize.minimize-slsqp>` uses Sequential
323 Least SQuares Programming to minimize a function of several
324 variables with any combination of bounds, equality and inequality
325 constraints. The method wraps the SLSQP Optimization subroutine
326 originally implemented by Dieter Kraft [12]_. Note that the
327 wrapper handles infinite values in bounds by converting them into
328 large floating values.
330 Method :ref:`trust-constr <optimize.minimize-trustconstr>` is a
331 trust-region algorithm for constrained optimization. It swiches
332 between two implementations depending on the problem definition.
333 It is the most versatile constrained minimization algorithm
334 implemented in SciPy and the most appropriate for large-scale problems.
335 For equality constrained problems it is an implementation of Byrd-Omojokun
336 Trust-Region SQP method described in [17]_ and in [5]_, p. 549. When
337 inequality constraints are imposed as well, it swiches to the trust-region
338 interior point method described in [16]_. This interior point algorithm,
339 in turn, solves inequality constraints by introducing slack variables
340 and solving a sequence of equality-constrained barrier problems
341 for progressively smaller values of the barrier parameter.
342 The previously described equality constrained SQP method is
343 used to solve the subproblems with increasing levels of accuracy
344 as the iterate gets closer to a solution.
346 **Finite-Difference Options**
348 For Method :ref:`trust-constr <optimize.minimize-trustconstr>`
349 the gradient and the Hessian may be approximated using
350 three finite-difference schemes: {'2-point', '3-point', 'cs'}.
351 The scheme 'cs' is, potentially, the most accurate but it
352 requires the function to correctly handles complex inputs and to
353 be differentiable in the complex plane. The scheme '3-point' is more
354 accurate than '2-point' but requires twice as many operations.
356 **Custom minimizers**
358 It may be useful to pass a custom minimization method, for example
359 when using a frontend to this method such as `scipy.optimize.basinhopping`
360 or a different library. You can simply pass a callable as the ``method``
361 parameter.
363 The callable is called as ``method(fun, x0, args, **kwargs, **options)``
364 where ``kwargs`` corresponds to any other parameters passed to `minimize`
365 (such as `callback`, `hess`, etc.), except the `options` dict, which has
366 its contents also passed as `method` parameters pair by pair. Also, if
367 `jac` has been passed as a bool type, `jac` and `fun` are mangled so that
368 `fun` returns just the function values and `jac` is converted to a function
369 returning the Jacobian. The method shall return an `OptimizeResult`
370 object.
372 The provided `method` callable must be able to accept (and possibly ignore)
373 arbitrary parameters; the set of parameters accepted by `minimize` may
374 expand in future versions and then these parameters will be passed to
375 the method. You can find an example in the scipy.optimize tutorial.
377 .. versionadded:: 0.11.0
379 References
380 ----------
381 .. [1] Nelder, J A, and R Mead. 1965. A Simplex Method for Function
382 Minimization. The Computer Journal 7: 308-13.
383 .. [2] Wright M H. 1996. Direct search methods: Once scorned, now
384 respectable, in Numerical Analysis 1995: Proceedings of the 1995
385 Dundee Biennial Conference in Numerical Analysis (Eds. D F
386 Griffiths and G A Watson). Addison Wesley Longman, Harlow, UK.
387 191-208.
388 .. [3] Powell, M J D. 1964. An efficient method for finding the minimum of
389 a function of several variables without calculating derivatives. The
390 Computer Journal 7: 155-162.
391 .. [4] Press W, S A Teukolsky, W T Vetterling and B P Flannery.
392 Numerical Recipes (any edition), Cambridge University Press.
393 .. [5] Nocedal, J, and S J Wright. 2006. Numerical Optimization.
394 Springer New York.
395 .. [6] Byrd, R H and P Lu and J. Nocedal. 1995. A Limited Memory
396 Algorithm for Bound Constrained Optimization. SIAM Journal on
397 Scientific and Statistical Computing 16 (5): 1190-1208.
398 .. [7] Zhu, C and R H Byrd and J Nocedal. 1997. L-BFGS-B: Algorithm
399 778: L-BFGS-B, FORTRAN routines for large scale bound constrained
400 optimization. ACM Transactions on Mathematical Software 23 (4):
401 550-560.
402 .. [8] Nash, S G. Newton-Type Minimization Via the Lanczos Method.
403 1984. SIAM Journal of Numerical Analysis 21: 770-778.
404 .. [9] Powell, M J D. A direct search optimization method that models
405 the objective and constraint functions by linear interpolation.
406 1994. Advances in Optimization and Numerical Analysis, eds. S. Gomez
407 and J-P Hennart, Kluwer Academic (Dordrecht), 51-67.
408 .. [10] Powell M J D. Direct search algorithms for optimization
409 calculations. 1998. Acta Numerica 7: 287-336.
410 .. [11] Powell M J D. A view of algorithms for optimization without
411 derivatives. 2007.Cambridge University Technical Report DAMTP
412 2007/NA03
413 .. [12] Kraft, D. A software package for sequential quadratic
414 programming. 1988. Tech. Rep. DFVLR-FB 88-28, DLR German Aerospace
415 Center -- Institute for Flight Mechanics, Koln, Germany.
416 .. [13] Conn, A. R., Gould, N. I., and Toint, P. L.
417 Trust region methods. 2000. Siam. pp. 169-200.
418 .. [14] F. Lenders, C. Kirches, A. Potschka: "trlib: A vector-free
419 implementation of the GLTR method for iterative solution of
420 the trust region problem", https://arxiv.org/abs/1611.04718
421 .. [15] N. Gould, S. Lucidi, M. Roma, P. Toint: "Solving the
422 Trust-Region Subproblem using the Lanczos Method",
423 SIAM J. Optim., 9(2), 504--525, (1999).
424 .. [16] Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. 1999.
425 An interior point algorithm for large-scale nonlinear programming.
426 SIAM Journal on Optimization 9.4: 877-900.
427 .. [17] Lalee, Marucha, Jorge Nocedal, and Todd Plantega. 1998. On the
428 implementation of an algorithm for large-scale equality constrained
429 optimization. SIAM Journal on Optimization 8.3: 682-706.
431 Examples
432 --------
433 Let us consider the problem of minimizing the Rosenbrock function. This
434 function (and its respective derivatives) is implemented in `rosen`
435 (resp. `rosen_der`, `rosen_hess`) in the `scipy.optimize`.
437 >>> from scipy.optimize import minimize, rosen, rosen_der
439 A simple application of the *Nelder-Mead* method is:
441 >>> x0 = [1.3, 0.7, 0.8, 1.9, 1.2]
442 >>> res = minimize(rosen, x0, method='Nelder-Mead', tol=1e-6)
443 >>> res.x
444 array([ 1., 1., 1., 1., 1.])
446 Now using the *BFGS* algorithm, using the first derivative and a few
447 options:
449 >>> res = minimize(rosen, x0, method='BFGS', jac=rosen_der,
450 ... options={'gtol': 1e-6, 'disp': True})
451 Optimization terminated successfully.
452 Current function value: 0.000000
453 Iterations: 26
454 Function evaluations: 31
455 Gradient evaluations: 31
456 >>> res.x
457 array([ 1., 1., 1., 1., 1.])
458 >>> print(res.message)
459 Optimization terminated successfully.
460 >>> res.hess_inv
461 array([[ 0.00749589, 0.01255155, 0.02396251, 0.04750988, 0.09495377], # may vary
462 [ 0.01255155, 0.02510441, 0.04794055, 0.09502834, 0.18996269],
463 [ 0.02396251, 0.04794055, 0.09631614, 0.19092151, 0.38165151],
464 [ 0.04750988, 0.09502834, 0.19092151, 0.38341252, 0.7664427 ],
465 [ 0.09495377, 0.18996269, 0.38165151, 0.7664427, 1.53713523]])
468 Next, consider a minimization problem with several constraints (namely
469 Example 16.4 from [5]_). The objective function is:
471 >>> fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2
473 There are three constraints defined as:
475 >>> cons = ({'type': 'ineq', 'fun': lambda x: x[0] - 2 * x[1] + 2},
476 ... {'type': 'ineq', 'fun': lambda x: -x[0] - 2 * x[1] + 6},
477 ... {'type': 'ineq', 'fun': lambda x: -x[0] + 2 * x[1] + 2})
479 And variables must be positive, hence the following bounds:
481 >>> bnds = ((0, None), (0, None))
483 The optimization problem is solved using the SLSQP method as:
485 >>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds,
486 ... constraints=cons)
488 It should converge to the theoretical solution (1.4 ,1.7).
490 """
491 x0 = np.asarray(x0)
492 if x0.dtype.kind in np.typecodes["AllInteger"]:
493 x0 = np.asarray(x0, dtype=float)
495 if not isinstance(args, tuple):
496 args = (args,)
498 if method is None:
499 # Select automatically
500 if constraints:
501 method = 'SLSQP'
502 elif bounds is not None:
503 method = 'L-BFGS-B'
504 else:
505 method = 'BFGS'
507 if callable(method):
508 meth = "_custom"
509 else:
510 meth = method.lower()
512 if options is None:
513 options = {}
514 # check if optional parameters are supported by the selected method
515 # - jac
516 if meth in ('nelder-mead', 'powell', 'cobyla') and bool(jac):
517 warn('Method %s does not use gradient information (jac).' % method,
518 RuntimeWarning)
519 # - hess
520 if meth not in ('newton-cg', 'dogleg', 'trust-ncg', 'trust-constr',
521 'trust-krylov', 'trust-exact', '_custom') and hess is not None:
522 warn('Method %s does not use Hessian information (hess).' % method,
523 RuntimeWarning)
524 # - hessp
525 if meth not in ('newton-cg', 'dogleg', 'trust-ncg', 'trust-constr',
526 'trust-krylov', '_custom') \
527 and hessp is not None:
528 warn('Method %s does not use Hessian-vector product '
529 'information (hessp).' % method, RuntimeWarning)
530 # - constraints or bounds
531 if (meth in ('nelder-mead', 'cg', 'bfgs', 'newton-cg', 'dogleg',
532 'trust-ncg') and (bounds is not None or np.any(constraints))):
533 warn('Method %s cannot handle constraints nor bounds.' % method,
534 RuntimeWarning)
535 if meth in ('l-bfgs-b', 'tnc', 'powell') and np.any(constraints):
536 warn('Method %s cannot handle constraints.' % method,
537 RuntimeWarning)
538 if meth == 'cobyla' and bounds is not None:
539 warn('Method %s cannot handle bounds.' % method,
540 RuntimeWarning)
541 # - callback
542 if (meth in ('cobyla',) and callback is not None):
543 warn('Method %s does not support callback.' % method, RuntimeWarning)
544 # - return_all
545 if (meth in ('l-bfgs-b', 'tnc', 'cobyla', 'slsqp') and
546 options.get('return_all', False)):
547 warn('Method %s does not support the return_all option.' % method,
548 RuntimeWarning)
550 # check gradient vector
551 if callable(jac):
552 pass
553 elif jac is True:
554 # fun returns func and grad
555 fun = MemoizeJac(fun)
556 jac = fun.derivative
557 elif (jac in FD_METHODS and
558 meth in ['trust-constr', 'bfgs', 'cg', 'l-bfgs-b', 'tnc']):
559 # finite differences
560 pass
561 elif meth in ['trust-constr']:
562 # default jac calculation for this method
563 jac = '2-point'
564 elif jac is None or bool(jac) is False:
565 # this will cause e.g. LBFGS to use forward difference, absolute step
566 jac = None
567 else:
568 # default if jac option is not understood
569 jac = None
571 # set default tolerances
572 if tol is not None:
573 options = dict(options)
574 if meth == 'nelder-mead':
575 options.setdefault('xatol', tol)
576 options.setdefault('fatol', tol)
577 if meth in ('newton-cg', 'powell', 'tnc'):
578 options.setdefault('xtol', tol)
579 if meth in ('powell', 'l-bfgs-b', 'tnc', 'slsqp'):
580 options.setdefault('ftol', tol)
581 if meth in ('bfgs', 'cg', 'l-bfgs-b', 'tnc', 'dogleg',
582 'trust-ncg', 'trust-exact', 'trust-krylov'):
583 options.setdefault('gtol', tol)
584 if meth in ('cobyla', '_custom'):
585 options.setdefault('tol', tol)
586 if meth == 'trust-constr':
587 options.setdefault('xtol', tol)
588 options.setdefault('gtol', tol)
589 options.setdefault('barrier_tol', tol)
591 if meth == '_custom':
592 # custom method called before bounds and constraints are 'standardised'
593 # custom method should be able to accept whatever bounds/constraints
594 # are provided to it.
595 return method(fun, x0, args=args, jac=jac, hess=hess, hessp=hessp,
596 bounds=bounds, constraints=constraints,
597 callback=callback, **options)
599 if bounds is not None:
600 bounds = standardize_bounds(bounds, x0, meth)
602 if constraints is not None:
603 constraints = standardize_constraints(constraints, x0, meth)
605 if meth == 'nelder-mead':
606 return _minimize_neldermead(fun, x0, args, callback, **options)
607 elif meth == 'powell':
608 return _minimize_powell(fun, x0, args, callback, bounds, **options)
609 elif meth == 'cg':
610 return _minimize_cg(fun, x0, args, jac, callback, **options)
611 elif meth == 'bfgs':
612 return _minimize_bfgs(fun, x0, args, jac, callback, **options)
613 elif meth == 'newton-cg':
614 return _minimize_newtoncg(fun, x0, args, jac, hess, hessp, callback,
615 **options)
616 elif meth == 'l-bfgs-b':
617 return _minimize_lbfgsb(fun, x0, args, jac, bounds,
618 callback=callback, **options)
619 elif meth == 'tnc':
620 return _minimize_tnc(fun, x0, args, jac, bounds, callback=callback,
621 **options)
622 elif meth == 'cobyla':
623 return _minimize_cobyla(fun, x0, args, constraints, **options)
624 elif meth == 'slsqp':
625 return _minimize_slsqp(fun, x0, args, jac, bounds,
626 constraints, callback=callback, **options)
627 elif meth == 'trust-constr':
628 return _minimize_trustregion_constr(fun, x0, args, jac, hess, hessp,
629 bounds, constraints,
630 callback=callback, **options)
631 elif meth == 'dogleg':
632 return _minimize_dogleg(fun, x0, args, jac, hess,
633 callback=callback, **options)
634 elif meth == 'trust-ncg':
635 return _minimize_trust_ncg(fun, x0, args, jac, hess, hessp,
636 callback=callback, **options)
637 elif meth == 'trust-krylov':
638 return _minimize_trust_krylov(fun, x0, args, jac, hess, hessp,
639 callback=callback, **options)
640 elif meth == 'trust-exact':
641 return _minimize_trustregion_exact(fun, x0, args, jac, hess,
642 callback=callback, **options)
643 else:
644 raise ValueError('Unknown solver %s' % method)
647def minimize_scalar(fun, bracket=None, bounds=None, args=(),
648 method='brent', tol=None, options=None):
649 """Minimization of scalar function of one variable.
651 Parameters
652 ----------
653 fun : callable
654 Objective function.
655 Scalar function, must return a scalar.
656 bracket : sequence, optional
657 For methods 'brent' and 'golden', `bracket` defines the bracketing
658 interval and can either have three items ``(a, b, c)`` so that
659 ``a < b < c`` and ``fun(b) < fun(a), fun(c)`` or two items ``a`` and
660 ``c`` which are assumed to be a starting interval for a downhill
661 bracket search (see `bracket`); it doesn't always mean that the
662 obtained solution will satisfy ``a <= x <= c``.
663 bounds : sequence, optional
664 For method 'bounded', `bounds` is mandatory and must have two items
665 corresponding to the optimization bounds.
666 args : tuple, optional
667 Extra arguments passed to the objective function.
668 method : str or callable, optional
669 Type of solver. Should be one of:
671 - 'Brent' :ref:`(see here) <optimize.minimize_scalar-brent>`
672 - 'Bounded' :ref:`(see here) <optimize.minimize_scalar-bounded>`
673 - 'Golden' :ref:`(see here) <optimize.minimize_scalar-golden>`
674 - custom - a callable object (added in version 0.14.0), see below
676 tol : float, optional
677 Tolerance for termination. For detailed control, use solver-specific
678 options.
679 options : dict, optional
680 A dictionary of solver options.
682 maxiter : int
683 Maximum number of iterations to perform.
684 disp : bool
685 Set to True to print convergence messages.
687 See :func:`show_options()` for solver-specific options.
689 Returns
690 -------
691 res : OptimizeResult
692 The optimization result represented as a ``OptimizeResult`` object.
693 Important attributes are: ``x`` the solution array, ``success`` a
694 Boolean flag indicating if the optimizer exited successfully and
695 ``message`` which describes the cause of the termination. See
696 `OptimizeResult` for a description of other attributes.
698 See also
699 --------
700 minimize : Interface to minimization algorithms for scalar multivariate
701 functions
702 show_options : Additional options accepted by the solvers
704 Notes
705 -----
706 This section describes the available solvers that can be selected by the
707 'method' parameter. The default method is *Brent*.
709 Method :ref:`Brent <optimize.minimize_scalar-brent>` uses Brent's
710 algorithm to find a local minimum. The algorithm uses inverse
711 parabolic interpolation when possible to speed up convergence of
712 the golden section method.
714 Method :ref:`Golden <optimize.minimize_scalar-golden>` uses the
715 golden section search technique. It uses analog of the bisection
716 method to decrease the bracketed interval. It is usually
717 preferable to use the *Brent* method.
719 Method :ref:`Bounded <optimize.minimize_scalar-bounded>` can
720 perform bounded minimization. It uses the Brent method to find a
721 local minimum in the interval x1 < xopt < x2.
723 **Custom minimizers**
725 It may be useful to pass a custom minimization method, for example
726 when using some library frontend to minimize_scalar. You can simply
727 pass a callable as the ``method`` parameter.
729 The callable is called as ``method(fun, args, **kwargs, **options)``
730 where ``kwargs`` corresponds to any other parameters passed to `minimize`
731 (such as `bracket`, `tol`, etc.), except the `options` dict, which has
732 its contents also passed as `method` parameters pair by pair. The method
733 shall return an `OptimizeResult` object.
735 The provided `method` callable must be able to accept (and possibly ignore)
736 arbitrary parameters; the set of parameters accepted by `minimize` may
737 expand in future versions and then these parameters will be passed to
738 the method. You can find an example in the scipy.optimize tutorial.
740 .. versionadded:: 0.11.0
742 Examples
743 --------
744 Consider the problem of minimizing the following function.
746 >>> def f(x):
747 ... return (x - 2) * x * (x + 2)**2
749 Using the *Brent* method, we find the local minimum as:
751 >>> from scipy.optimize import minimize_scalar
752 >>> res = minimize_scalar(f)
753 >>> res.x
754 1.28077640403
756 Using the *Bounded* method, we find a local minimum with specified
757 bounds as:
759 >>> res = minimize_scalar(f, bounds=(-3, -1), method='bounded')
760 >>> res.x
761 -2.0000002026
763 """
764 if not isinstance(args, tuple):
765 args = (args,)
767 if callable(method):
768 meth = "_custom"
769 else:
770 meth = method.lower()
771 if options is None:
772 options = {}
774 if tol is not None:
775 options = dict(options)
776 if meth == 'bounded' and 'xatol' not in options:
777 warn("Method 'bounded' does not support relative tolerance in x; "
778 "defaulting to absolute tolerance.", RuntimeWarning)
779 options['xatol'] = tol
780 elif meth == '_custom':
781 options.setdefault('tol', tol)
782 else:
783 options.setdefault('xtol', tol)
785 if meth == '_custom':
786 return method(fun, args=args, bracket=bracket, bounds=bounds, **options)
787 elif meth == 'brent':
788 return _minimize_scalar_brent(fun, bracket, args, **options)
789 elif meth == 'bounded':
790 if bounds is None:
791 raise ValueError('The `bounds` parameter is mandatory for '
792 'method `bounded`.')
793 # replace boolean "disp" option, if specified, by an integer value, as
794 # expected by _minimize_scalar_bounded()
795 disp = options.get('disp')
796 if isinstance(disp, bool):
797 options['disp'] = 2 * int(disp)
798 return _minimize_scalar_bounded(fun, bounds, args, **options)
799 elif meth == 'golden':
800 return _minimize_scalar_golden(fun, bracket, args, **options)
801 else:
802 raise ValueError('Unknown solver %s' % method)
805def standardize_bounds(bounds, x0, meth):
806 """Converts bounds to the form required by the solver."""
807 if meth in {'trust-constr', 'powell'}:
808 if not isinstance(bounds, Bounds):
809 lb, ub = old_bound_to_new(bounds)
810 bounds = Bounds(lb, ub)
811 elif meth in ('l-bfgs-b', 'tnc', 'slsqp'):
812 if isinstance(bounds, Bounds):
813 bounds = new_bounds_to_old(bounds.lb, bounds.ub, x0.shape[0])
814 return bounds
817def standardize_constraints(constraints, x0, meth):
818 """Converts constraints to the form required by the solver."""
819 all_constraint_types = (NonlinearConstraint, LinearConstraint, dict)
820 new_constraint_types = all_constraint_types[:-1]
821 if isinstance(constraints, all_constraint_types):
822 constraints = [constraints]
823 constraints = list(constraints) # ensure it's a mutable sequence
825 if meth == 'trust-constr':
826 for i, con in enumerate(constraints):
827 if not isinstance(con, new_constraint_types):
828 constraints[i] = old_constraint_to_new(i, con)
829 else:
830 # iterate over copy, changing original
831 for i, con in enumerate(list(constraints)):
832 if isinstance(con, new_constraint_types):
833 old_constraints = new_constraint_to_old(con, x0)
834 constraints[i] = old_constraints[0]
835 constraints.extend(old_constraints[1:]) # appends 1 if present
837 return constraints