Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/scipy/optimize/_minimize.py: 10%
251 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-12-12 06:31 +0000
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
17# unconstrained minimization
18from ._optimize import (_minimize_neldermead, _minimize_powell, _minimize_cg,
19 _minimize_bfgs, _minimize_newtoncg,
20 _minimize_scalar_brent, _minimize_scalar_bounded,
21 _minimize_scalar_golden, MemoizeJac, OptimizeResult)
22from ._trustregion_dogleg import _minimize_dogleg
23from ._trustregion_ncg import _minimize_trust_ncg
24from ._trustregion_krylov import _minimize_trust_krylov
25from ._trustregion_exact import _minimize_trustregion_exact
26from ._trustregion_constr import _minimize_trustregion_constr
28# constrained minimization
29from ._lbfgsb_py import _minimize_lbfgsb
30from ._tnc import _minimize_tnc
31from ._cobyla_py import _minimize_cobyla
32from ._slsqp_py import _minimize_slsqp
33from ._constraints import (old_bound_to_new, new_bounds_to_old,
34 old_constraint_to_new, new_constraint_to_old,
35 NonlinearConstraint, LinearConstraint, Bounds,
36 PreparedConstraint)
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']
43MINIMIZE_SCALAR_METHODS = ['brent', 'bounded', 'golden']
45def minimize(fun, x0, args=(), method=None, jac=None, hess=None,
46 hessp=None, bounds=None, constraints=(), tol=None,
47 callback=None, options=None):
48 """Minimization of scalar function of one or more variables.
50 Parameters
51 ----------
52 fun : callable
53 The objective function to be minimized.
55 ``fun(x, *args) -> float``
57 where ``x`` is a 1-D array with shape (n,) and ``args``
58 is a tuple of the fixed parameters needed to completely
59 specify the function.
60 x0 : ndarray, shape (n,)
61 Initial guess. Array of real elements of size (n,),
62 where ``n`` is the number of independent variables.
63 args : tuple, optional
64 Extra arguments passed to the objective function and its
65 derivatives (`fun`, `jac` and `hess` functions).
66 method : str or callable, optional
67 Type of solver. Should be one of
69 - 'Nelder-Mead' :ref:`(see here) <optimize.minimize-neldermead>`
70 - 'Powell' :ref:`(see here) <optimize.minimize-powell>`
71 - 'CG' :ref:`(see here) <optimize.minimize-cg>`
72 - 'BFGS' :ref:`(see here) <optimize.minimize-bfgs>`
73 - 'Newton-CG' :ref:`(see here) <optimize.minimize-newtoncg>`
74 - 'L-BFGS-B' :ref:`(see here) <optimize.minimize-lbfgsb>`
75 - 'TNC' :ref:`(see here) <optimize.minimize-tnc>`
76 - 'COBYLA' :ref:`(see here) <optimize.minimize-cobyla>`
77 - 'SLSQP' :ref:`(see here) <optimize.minimize-slsqp>`
78 - 'trust-constr':ref:`(see here) <optimize.minimize-trustconstr>`
79 - 'dogleg' :ref:`(see here) <optimize.minimize-dogleg>`
80 - 'trust-ncg' :ref:`(see here) <optimize.minimize-trustncg>`
81 - 'trust-exact' :ref:`(see here) <optimize.minimize-trustexact>`
82 - 'trust-krylov' :ref:`(see here) <optimize.minimize-trustkrylov>`
83 - custom - a callable object, see below for description.
85 If not given, chosen to be one of ``BFGS``, ``L-BFGS-B``, ``SLSQP``,
86 depending on whether or not 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 a tuple ``(f, g)`` containing the objective
99 function and the gradient.
100 Methods 'Newton-CG', 'trust-ncg', 'dogleg', 'trust-exact', and
101 'trust-krylov' require that either a callable be supplied, or that
102 `fun` return the objective and gradient.
103 If None or False, the gradient will be estimated using 2-point finite
104 difference estimation with an absolute step size.
105 Alternatively, the keywords {'2-point', '3-point', 'cs'} can be used
106 to select a finite difference scheme for numerical estimation of the
107 gradient with a relative step size. These finite difference schemes
108 obey any specified `bounds`.
109 hess : {callable, '2-point', '3-point', 'cs', HessianUpdateStrategy}, optional
110 Method for computing the Hessian matrix. Only for Newton-CG, dogleg,
111 trust-ncg, trust-krylov, trust-exact and trust-constr.
112 If it is callable, it should return the Hessian matrix:
114 ``hess(x, *args) -> {LinearOperator, spmatrix, array}, (n, n)``
116 where ``x`` is a (n,) ndarray and ``args`` is a tuple with the fixed
117 parameters.
118 The keywords {'2-point', '3-point', 'cs'} can also be used to select
119 a finite difference scheme for numerical estimation of the hessian.
120 Alternatively, objects implementing the `HessianUpdateStrategy`
121 interface can be used to approximate the Hessian. Available
122 quasi-Newton methods implementing this interface are:
124 - `BFGS`;
125 - `SR1`.
127 Not all of the options are available for each of the methods; for
128 availability refer to the notes.
129 hessp : callable, optional
130 Hessian of objective function times an arbitrary vector p. Only for
131 Newton-CG, trust-ncg, trust-krylov, trust-constr.
132 Only one of `hessp` or `hess` needs to be given. If `hess` is
133 provided, then `hessp` will be ignored. `hessp` must compute the
134 Hessian times an arbitrary vector:
136 ``hessp(x, p, *args) -> ndarray shape (n,)``
138 where ``x`` is a (n,) ndarray, ``p`` is an arbitrary vector with
139 dimension (n,) and ``args`` is a tuple with the fixed
140 parameters.
141 bounds : sequence or `Bounds`, optional
142 Bounds on variables for Nelder-Mead, L-BFGS-B, TNC, SLSQP, Powell, and
143 trust-constr methods. There are two ways to specify the bounds:
145 1. Instance of `Bounds` class.
146 2. Sequence of ``(min, max)`` pairs for each element in `x`. None
147 is used to specify no bound.
149 constraints : {Constraint, dict} or List of {Constraint, dict}, optional
150 Constraints definition. Only for COBYLA, SLSQP and trust-constr.
152 Constraints for 'trust-constr' are defined as a single object or a
153 list of objects specifying constraints to the optimization problem.
154 Available constraints are:
156 - `LinearConstraint`
157 - `NonlinearConstraint`
159 Constraints for COBYLA, SLSQP are defined as a list of dictionaries.
160 Each dictionary with fields:
162 type : str
163 Constraint type: 'eq' for equality, 'ineq' for inequality.
164 fun : callable
165 The function defining the constraint.
166 jac : callable, optional
167 The Jacobian of `fun` (only for SLSQP).
168 args : sequence, optional
169 Extra arguments to be passed to the function and Jacobian.
171 Equality constraint means that the constraint function result is to
172 be zero whereas inequality means that it is to be non-negative.
173 Note that COBYLA only supports inequality constraints.
174 tol : float, optional
175 Tolerance for termination. When `tol` is specified, the selected
176 minimization algorithm sets some relevant solver-specific tolerance(s)
177 equal to `tol`. For detailed control, use solver-specific
178 options.
179 options : dict, optional
180 A dictionary of solver options. All methods except `TNC` accept the
181 following generic options:
183 maxiter : int
184 Maximum number of iterations to perform. Depending on the
185 method each iteration may use several function evaluations.
187 For `TNC` use `maxfun` instead of `maxiter`.
188 disp : bool
189 Set to True to print convergence messages.
191 For method-specific options, see :func:`show_options()`.
192 callback : callable, optional
193 Called after each iteration. For 'trust-constr' it is a callable with
194 the signature:
196 ``callback(xk, OptimizeResult state) -> bool``
198 where ``xk`` is the current parameter vector. and ``state``
199 is an `OptimizeResult` object, with the same fields
200 as the ones from the return. If callback returns True
201 the algorithm execution is terminated.
202 For all the other methods, the signature is:
204 ``callback(xk)``
206 where ``xk`` is the current parameter vector.
208 Returns
209 -------
210 res : OptimizeResult
211 The optimization result represented as a ``OptimizeResult`` object.
212 Important attributes are: ``x`` the solution array, ``success`` a
213 Boolean flag indicating if the optimizer exited successfully and
214 ``message`` which describes the cause of the termination. See
215 `OptimizeResult` for a description of other attributes.
217 See also
218 --------
219 minimize_scalar : Interface to minimization algorithms for scalar
220 univariate functions
221 show_options : Additional options accepted by the solvers
223 Notes
224 -----
225 This section describes the available solvers that can be selected by the
226 'method' parameter. The default method is *BFGS*.
228 **Unconstrained minimization**
230 Method :ref:`CG <optimize.minimize-cg>` uses a nonlinear conjugate
231 gradient algorithm by Polak and Ribiere, a variant of the
232 Fletcher-Reeves method described in [5]_ pp.120-122. Only the
233 first derivatives are used.
235 Method :ref:`BFGS <optimize.minimize-bfgs>` uses the quasi-Newton
236 method of Broyden, Fletcher, Goldfarb, and Shanno (BFGS) [5]_
237 pp. 136. It uses the first derivatives only. BFGS has proven good
238 performance even for non-smooth optimizations. This method also
239 returns an approximation of the Hessian inverse, stored as
240 `hess_inv` in the OptimizeResult object.
242 Method :ref:`Newton-CG <optimize.minimize-newtoncg>` uses a
243 Newton-CG algorithm [5]_ pp. 168 (also known as the truncated
244 Newton method). It uses a CG method to the compute the search
245 direction. See also *TNC* method for a box-constrained
246 minimization with a similar algorithm. Suitable for large-scale
247 problems.
249 Method :ref:`dogleg <optimize.minimize-dogleg>` uses the dog-leg
250 trust-region algorithm [5]_ for unconstrained minimization. This
251 algorithm requires the gradient and Hessian; furthermore the
252 Hessian is required to be positive definite.
254 Method :ref:`trust-ncg <optimize.minimize-trustncg>` uses the
255 Newton conjugate gradient trust-region algorithm [5]_ for
256 unconstrained minimization. This algorithm requires the gradient
257 and either the Hessian or a function that computes the product of
258 the Hessian with a given vector. Suitable for large-scale problems.
260 Method :ref:`trust-krylov <optimize.minimize-trustkrylov>` uses
261 the Newton GLTR trust-region algorithm [14]_, [15]_ for unconstrained
262 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.
265 On indefinite problems it requires usually less iterations than the
266 `trust-ncg` method and is recommended for medium and large-scale problems.
268 Method :ref:`trust-exact <optimize.minimize-trustexact>`
269 is a trust-region method for unconstrained minimization in which
270 quadratic subproblems are solved almost exactly [13]_. This
271 algorithm requires the gradient and the Hessian (which is
272 *not* required to be positive definite). It is, in many
273 situations, the Newton method to converge in fewer iterations
274 and the most recommended for small and medium-size problems.
276 **Bound-Constrained minimization**
278 Method :ref:`Nelder-Mead <optimize.minimize-neldermead>` uses the
279 Simplex algorithm [1]_, [2]_. This algorithm is robust in many
280 applications. However, if numerical computation of derivative can be
281 trusted, other algorithms using the first and/or second derivatives
282 information might be preferred for their better performance in
283 general.
285 Method :ref:`L-BFGS-B <optimize.minimize-lbfgsb>` uses the L-BFGS-B
286 algorithm [6]_, [7]_ for bound constrained minimization.
288 Method :ref:`Powell <optimize.minimize-powell>` is a modification
289 of Powell's method [3]_, [4]_ which is a conjugate direction
290 method. It performs sequential one-dimensional minimizations along
291 each vector of the directions set (`direc` field in `options` and
292 `info`), which is updated at each iteration of the main
293 minimization loop. The function need not be differentiable, and no
294 derivatives are taken. If bounds are not provided, then an
295 unbounded line search will be used. If bounds are provided and
296 the initial guess is within the bounds, then every function
297 evaluation throughout the minimization procedure will be within
298 the bounds. If bounds are provided, the initial guess is outside
299 the bounds, and `direc` is full rank (default has full rank), then
300 some function evaluations during the first iteration may be
301 outside the bounds, but every function evaluation after the first
302 iteration will be within the bounds. If `direc` is not full rank,
303 then some parameters may not be optimized and the solution is not
304 guaranteed to be within the bounds.
306 Method :ref:`TNC <optimize.minimize-tnc>` uses a truncated Newton
307 algorithm [5]_, [8]_ to minimize a function with variables subject
308 to bounds. This algorithm uses gradient information; it is also
309 called Newton Conjugate-Gradient. It differs from the *Newton-CG*
310 method described above as it wraps a C implementation and allows
311 each variable to be given upper and lower bounds.
313 **Constrained Minimization**
315 Method :ref:`COBYLA <optimize.minimize-cobyla>` uses the
316 Constrained Optimization BY Linear Approximation (COBYLA) method
317 [9]_, [10]_, [11]_. The algorithm is based on linear
318 approximations to the objective function and each constraint. The
319 method wraps a FORTRAN implementation of the algorithm. The
320 constraints functions 'fun' may return either a single number
321 or an array or list of numbers.
323 Method :ref:`SLSQP <optimize.minimize-slsqp>` uses Sequential
324 Least SQuares Programming to minimize a function of several
325 variables with any combination of bounds, equality and inequality
326 constraints. The method wraps the SLSQP Optimization subroutine
327 originally implemented by Dieter Kraft [12]_. Note that the
328 wrapper handles infinite values in bounds by converting them into
329 large floating values.
331 Method :ref:`trust-constr <optimize.minimize-trustconstr>` is a
332 trust-region algorithm for constrained optimization. It swiches
333 between two implementations depending on the problem definition.
334 It is the most versatile constrained minimization algorithm
335 implemented in SciPy and the most appropriate for large-scale problems.
336 For equality constrained problems it is an implementation of Byrd-Omojokun
337 Trust-Region SQP method described in [17]_ and in [5]_, p. 549. When
338 inequality constraints are imposed as well, it swiches to the trust-region
339 interior point method described in [16]_. This interior point algorithm,
340 in turn, solves inequality constraints by introducing slack variables
341 and solving a sequence of equality-constrained barrier problems
342 for progressively smaller values of the barrier parameter.
343 The previously described equality constrained SQP method is
344 used to solve the subproblems with increasing levels of accuracy
345 as the iterate gets closer to a solution.
347 **Finite-Difference Options**
349 For Method :ref:`trust-constr <optimize.minimize-trustconstr>`
350 the gradient and the Hessian may be approximated using
351 three finite-difference schemes: {'2-point', '3-point', 'cs'}.
352 The scheme 'cs' is, potentially, the most accurate but it
353 requires the function to correctly handle complex inputs and to
354 be differentiable in the complex plane. The scheme '3-point' is more
355 accurate than '2-point' but requires twice as many operations. If the
356 gradient is estimated via finite-differences the Hessian must be
357 estimated using one of the quasi-Newton strategies.
359 **Method specific options for the** `hess` **keyword**
361 +--------------+------+----------+-------------------------+-----+
362 | method/Hess | None | callable | '2-point/'3-point'/'cs' | HUS |
363 +==============+======+==========+=========================+=====+
364 | Newton-CG | x | (n, n) | x | x |
365 | | | LO | | |
366 +--------------+------+----------+-------------------------+-----+
367 | dogleg | | (n, n) | | |
368 +--------------+------+----------+-------------------------+-----+
369 | trust-ncg | | (n, n) | x | x |
370 +--------------+------+----------+-------------------------+-----+
371 | trust-krylov | | (n, n) | x | x |
372 +--------------+------+----------+-------------------------+-----+
373 | trust-exact | | (n, n) | | |
374 +--------------+------+----------+-------------------------+-----+
375 | trust-constr | x | (n, n) | x | x |
376 | | | LO | | |
377 | | | sp | | |
378 +--------------+------+----------+-------------------------+-----+
380 where LO=LinearOperator, sp=Sparse matrix, HUS=HessianUpdateStrategy
382 **Custom minimizers**
384 It may be useful to pass a custom minimization method, for example
385 when using a frontend to this method such as `scipy.optimize.basinhopping`
386 or a different library. You can simply pass a callable as the ``method``
387 parameter.
389 The callable is called as ``method(fun, x0, args, **kwargs, **options)``
390 where ``kwargs`` corresponds to any other parameters passed to `minimize`
391 (such as `callback`, `hess`, etc.), except the `options` dict, which has
392 its contents also passed as `method` parameters pair by pair. Also, if
393 `jac` has been passed as a bool type, `jac` and `fun` are mangled so that
394 `fun` returns just the function values and `jac` is converted to a function
395 returning the Jacobian. The method shall return an `OptimizeResult`
396 object.
398 The provided `method` callable must be able to accept (and possibly ignore)
399 arbitrary parameters; the set of parameters accepted by `minimize` may
400 expand in future versions and then these parameters will be passed to
401 the method. You can find an example in the scipy.optimize tutorial.
403 References
404 ----------
405 .. [1] Nelder, J A, and R Mead. 1965. A Simplex Method for Function
406 Minimization. The Computer Journal 7: 308-13.
407 .. [2] Wright M H. 1996. Direct search methods: Once scorned, now
408 respectable, in Numerical Analysis 1995: Proceedings of the 1995
409 Dundee Biennial Conference in Numerical Analysis (Eds. D F
410 Griffiths and G A Watson). Addison Wesley Longman, Harlow, UK.
411 191-208.
412 .. [3] Powell, M J D. 1964. An efficient method for finding the minimum of
413 a function of several variables without calculating derivatives. The
414 Computer Journal 7: 155-162.
415 .. [4] Press W, S A Teukolsky, W T Vetterling and B P Flannery.
416 Numerical Recipes (any edition), Cambridge University Press.
417 .. [5] Nocedal, J, and S J Wright. 2006. Numerical Optimization.
418 Springer New York.
419 .. [6] Byrd, R H and P Lu and J. Nocedal. 1995. A Limited Memory
420 Algorithm for Bound Constrained Optimization. SIAM Journal on
421 Scientific and Statistical Computing 16 (5): 1190-1208.
422 .. [7] Zhu, C and R H Byrd and J Nocedal. 1997. L-BFGS-B: Algorithm
423 778: L-BFGS-B, FORTRAN routines for large scale bound constrained
424 optimization. ACM Transactions on Mathematical Software 23 (4):
425 550-560.
426 .. [8] Nash, S G. Newton-Type Minimization Via the Lanczos Method.
427 1984. SIAM Journal of Numerical Analysis 21: 770-778.
428 .. [9] Powell, M J D. A direct search optimization method that models
429 the objective and constraint functions by linear interpolation.
430 1994. Advances in Optimization and Numerical Analysis, eds. S. Gomez
431 and J-P Hennart, Kluwer Academic (Dordrecht), 51-67.
432 .. [10] Powell M J D. Direct search algorithms for optimization
433 calculations. 1998. Acta Numerica 7: 287-336.
434 .. [11] Powell M J D. A view of algorithms for optimization without
435 derivatives. 2007.Cambridge University Technical Report DAMTP
436 2007/NA03
437 .. [12] Kraft, D. A software package for sequential quadratic
438 programming. 1988. Tech. Rep. DFVLR-FB 88-28, DLR German Aerospace
439 Center -- Institute for Flight Mechanics, Koln, Germany.
440 .. [13] Conn, A. R., Gould, N. I., and Toint, P. L.
441 Trust region methods. 2000. Siam. pp. 169-200.
442 .. [14] F. Lenders, C. Kirches, A. Potschka: "trlib: A vector-free
443 implementation of the GLTR method for iterative solution of
444 the trust region problem", :arxiv:`1611.04718`
445 .. [15] N. Gould, S. Lucidi, M. Roma, P. Toint: "Solving the
446 Trust-Region Subproblem using the Lanczos Method",
447 SIAM J. Optim., 9(2), 504--525, (1999).
448 .. [16] Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. 1999.
449 An interior point algorithm for large-scale nonlinear programming.
450 SIAM Journal on Optimization 9.4: 877-900.
451 .. [17] Lalee, Marucha, Jorge Nocedal, and Todd Plantega. 1998. On the
452 implementation of an algorithm for large-scale equality constrained
453 optimization. SIAM Journal on Optimization 8.3: 682-706.
455 Examples
456 --------
457 Let us consider the problem of minimizing the Rosenbrock function. This
458 function (and its respective derivatives) is implemented in `rosen`
459 (resp. `rosen_der`, `rosen_hess`) in the `scipy.optimize`.
461 >>> from scipy.optimize import minimize, rosen, rosen_der
463 A simple application of the *Nelder-Mead* method is:
465 >>> x0 = [1.3, 0.7, 0.8, 1.9, 1.2]
466 >>> res = minimize(rosen, x0, method='Nelder-Mead', tol=1e-6)
467 >>> res.x
468 array([ 1., 1., 1., 1., 1.])
470 Now using the *BFGS* algorithm, using the first derivative and a few
471 options:
473 >>> res = minimize(rosen, x0, method='BFGS', jac=rosen_der,
474 ... options={'gtol': 1e-6, 'disp': True})
475 Optimization terminated successfully.
476 Current function value: 0.000000
477 Iterations: 26
478 Function evaluations: 31
479 Gradient evaluations: 31
480 >>> res.x
481 array([ 1., 1., 1., 1., 1.])
482 >>> print(res.message)
483 Optimization terminated successfully.
484 >>> res.hess_inv
485 array([[ 0.00749589, 0.01255155, 0.02396251, 0.04750988, 0.09495377], # may vary
486 [ 0.01255155, 0.02510441, 0.04794055, 0.09502834, 0.18996269],
487 [ 0.02396251, 0.04794055, 0.09631614, 0.19092151, 0.38165151],
488 [ 0.04750988, 0.09502834, 0.19092151, 0.38341252, 0.7664427 ],
489 [ 0.09495377, 0.18996269, 0.38165151, 0.7664427, 1.53713523]])
492 Next, consider a minimization problem with several constraints (namely
493 Example 16.4 from [5]_). The objective function is:
495 >>> fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2
497 There are three constraints defined as:
499 >>> cons = ({'type': 'ineq', 'fun': lambda x: x[0] - 2 * x[1] + 2},
500 ... {'type': 'ineq', 'fun': lambda x: -x[0] - 2 * x[1] + 6},
501 ... {'type': 'ineq', 'fun': lambda x: -x[0] + 2 * x[1] + 2})
503 And variables must be positive, hence the following bounds:
505 >>> bnds = ((0, None), (0, None))
507 The optimization problem is solved using the SLSQP method as:
509 >>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds,
510 ... constraints=cons)
512 It should converge to the theoretical solution (1.4 ,1.7).
514 """
515 x0 = np.atleast_1d(np.asarray(x0))
517 if x0.ndim != 1:
518 message = ('Use of `minimize` with `x0.ndim != 1` is deprecated. '
519 'Currently, singleton dimensions will be removed from '
520 '`x0`, but an error will be raised in SciPy 1.11.0.')
521 warn(message, DeprecationWarning, stacklevel=2)
522 x0 = np.atleast_1d(np.squeeze(x0))
524 if x0.dtype.kind in np.typecodes["AllInteger"]:
525 x0 = np.asarray(x0, dtype=float)
527 if not isinstance(args, tuple):
528 args = (args,)
530 if method is None:
531 # Select automatically
532 if constraints:
533 method = 'SLSQP'
534 elif bounds is not None:
535 method = 'L-BFGS-B'
536 else:
537 method = 'BFGS'
539 if callable(method):
540 meth = "_custom"
541 else:
542 meth = method.lower()
544 if options is None:
545 options = {}
546 # check if optional parameters are supported by the selected method
547 # - jac
548 if meth in ('nelder-mead', 'powell', 'cobyla') and bool(jac):
549 warn('Method %s does not use gradient information (jac).' % method,
550 RuntimeWarning)
551 # - hess
552 if meth not in ('newton-cg', 'dogleg', 'trust-ncg', 'trust-constr',
553 'trust-krylov', 'trust-exact', '_custom') and hess is not None:
554 warn('Method %s does not use Hessian information (hess).' % method,
555 RuntimeWarning)
556 # - hessp
557 if meth not in ('newton-cg', 'trust-ncg', 'trust-constr',
558 'trust-krylov', '_custom') \
559 and hessp is not None:
560 warn('Method %s does not use Hessian-vector product '
561 'information (hessp).' % method, RuntimeWarning)
562 # - constraints or bounds
563 if (meth not in ('cobyla', 'slsqp', 'trust-constr', '_custom') and
564 np.any(constraints)):
565 warn('Method %s cannot handle constraints.' % method,
566 RuntimeWarning)
567 if meth not in ('nelder-mead', 'powell', 'l-bfgs-b', 'tnc', 'slsqp',
568 'trust-constr', '_custom') and bounds is not None:
569 warn('Method %s cannot handle bounds.' % method,
570 RuntimeWarning)
571 # - return_all
572 if (meth in ('l-bfgs-b', 'tnc', 'cobyla', 'slsqp') and
573 options.get('return_all', False)):
574 warn('Method %s does not support the return_all option.' % method,
575 RuntimeWarning)
577 # check gradient vector
578 if callable(jac):
579 pass
580 elif jac is True:
581 # fun returns func and grad
582 fun = MemoizeJac(fun)
583 jac = fun.derivative
584 elif (jac in FD_METHODS and
585 meth in ['trust-constr', 'bfgs', 'cg', 'l-bfgs-b', 'tnc', 'slsqp']):
586 # finite differences with relative step
587 pass
588 elif meth in ['trust-constr']:
589 # default jac calculation for this method
590 jac = '2-point'
591 elif jac is None or bool(jac) is False:
592 # this will cause e.g. LBFGS to use forward difference, absolute step
593 jac = None
594 else:
595 # default if jac option is not understood
596 jac = None
598 # set default tolerances
599 if tol is not None:
600 options = dict(options)
601 if meth == 'nelder-mead':
602 options.setdefault('xatol', tol)
603 options.setdefault('fatol', tol)
604 if meth in ('newton-cg', 'powell', 'tnc'):
605 options.setdefault('xtol', tol)
606 if meth in ('powell', 'l-bfgs-b', 'tnc', 'slsqp'):
607 options.setdefault('ftol', tol)
608 if meth in ('bfgs', 'cg', 'l-bfgs-b', 'tnc', 'dogleg',
609 'trust-ncg', 'trust-exact', 'trust-krylov'):
610 options.setdefault('gtol', tol)
611 if meth in ('cobyla', '_custom'):
612 options.setdefault('tol', tol)
613 if meth == 'trust-constr':
614 options.setdefault('xtol', tol)
615 options.setdefault('gtol', tol)
616 options.setdefault('barrier_tol', tol)
618 if meth == '_custom':
619 # custom method called before bounds and constraints are 'standardised'
620 # custom method should be able to accept whatever bounds/constraints
621 # are provided to it.
622 return method(fun, x0, args=args, jac=jac, hess=hess, hessp=hessp,
623 bounds=bounds, constraints=constraints,
624 callback=callback, **options)
626 constraints = standardize_constraints(constraints, x0, meth)
628 remove_vars = False
629 if bounds is not None:
630 if meth in {"tnc", "slsqp", "l-bfgs-b"}:
631 # These methods can't take the finite-difference derivatives they
632 # need when a variable is fixed by the bounds. To avoid this issue,
633 # remove fixed variables from the problem.
634 # NOTE: if this list is expanded, then be sure to update the
635 # accompanying tests and test_optimize.eb_data. Consider also if
636 # default OptimizeResult will need updating.
638 # convert to new-style bounds so we only have to consider one case
639 bounds = standardize_bounds(bounds, x0, 'new')
641 # determine whether any variables are fixed
642 i_fixed = (bounds.lb == bounds.ub)
644 if np.all(i_fixed):
645 # all the parameters are fixed, a minimizer is not able to do
646 # anything
647 return _optimize_result_for_equal_bounds(
648 fun, bounds, meth, args=args, constraints=constraints
649 )
651 # determine whether finite differences are needed for any grad/jac
652 fd_needed = (not callable(jac))
653 for con in constraints:
654 if not callable(con.get('jac', None)):
655 fd_needed = True
657 # If finite differences are ever used, remove all fixed variables
658 # Always remove fixed variables for TNC; see gh-14565
659 remove_vars = i_fixed.any() and (fd_needed or meth == "tnc")
660 if remove_vars:
661 x_fixed = (bounds.lb)[i_fixed]
662 x0 = x0[~i_fixed]
663 bounds = _remove_from_bounds(bounds, i_fixed)
664 fun = _remove_from_func(fun, i_fixed, x_fixed)
665 if callable(callback):
666 callback = _remove_from_func(callback, i_fixed, x_fixed)
667 if callable(jac):
668 jac = _remove_from_func(jac, i_fixed, x_fixed, remove=1)
670 # make a copy of the constraints so the user's version doesn't
671 # get changed. (Shallow copy is ok)
672 constraints = [con.copy() for con in constraints]
673 for con in constraints: # yes, guaranteed to be a list
674 con['fun'] = _remove_from_func(con['fun'], i_fixed,
675 x_fixed, min_dim=1,
676 remove=0)
677 if callable(con.get('jac', None)):
678 con['jac'] = _remove_from_func(con['jac'], i_fixed,
679 x_fixed, min_dim=2,
680 remove=1)
681 bounds = standardize_bounds(bounds, x0, meth)
683 if meth == 'nelder-mead':
684 res = _minimize_neldermead(fun, x0, args, callback, bounds=bounds,
685 **options)
686 elif meth == 'powell':
687 res = _minimize_powell(fun, x0, args, callback, bounds, **options)
688 elif meth == 'cg':
689 res = _minimize_cg(fun, x0, args, jac, callback, **options)
690 elif meth == 'bfgs':
691 res = _minimize_bfgs(fun, x0, args, jac, callback, **options)
692 elif meth == 'newton-cg':
693 res = _minimize_newtoncg(fun, x0, args, jac, hess, hessp, callback,
694 **options)
695 elif meth == 'l-bfgs-b':
696 res = _minimize_lbfgsb(fun, x0, args, jac, bounds,
697 callback=callback, **options)
698 elif meth == 'tnc':
699 res = _minimize_tnc(fun, x0, args, jac, bounds, callback=callback,
700 **options)
701 elif meth == 'cobyla':
702 res = _minimize_cobyla(fun, x0, args, constraints, callback=callback,
703 **options)
704 elif meth == 'slsqp':
705 res = _minimize_slsqp(fun, x0, args, jac, bounds,
706 constraints, callback=callback, **options)
707 elif meth == 'trust-constr':
708 res = _minimize_trustregion_constr(fun, x0, args, jac, hess, hessp,
709 bounds, constraints,
710 callback=callback, **options)
711 elif meth == 'dogleg':
712 res = _minimize_dogleg(fun, x0, args, jac, hess,
713 callback=callback, **options)
714 elif meth == 'trust-ncg':
715 res = _minimize_trust_ncg(fun, x0, args, jac, hess, hessp,
716 callback=callback, **options)
717 elif meth == 'trust-krylov':
718 res = _minimize_trust_krylov(fun, x0, args, jac, hess, hessp,
719 callback=callback, **options)
720 elif meth == 'trust-exact':
721 res = _minimize_trustregion_exact(fun, x0, args, jac, hess,
722 callback=callback, **options)
723 else:
724 raise ValueError('Unknown solver %s' % method)
726 if remove_vars:
727 res.x = _add_to_array(res.x, i_fixed, x_fixed)
728 res.jac = _add_to_array(res.jac, i_fixed, np.nan)
729 if "hess_inv" in res:
730 res.hess_inv = None # unknown
732 return res
735def minimize_scalar(fun, bracket=None, bounds=None, args=(),
736 method=None, tol=None, options=None):
737 """Minimization of scalar function of one variable.
739 Parameters
740 ----------
741 fun : callable
742 Objective function.
743 Scalar function, must return a scalar.
744 bracket : sequence, optional
745 For methods 'brent' and 'golden', `bracket` defines the bracketing
746 interval and can either have three items ``(a, b, c)`` so that
747 ``a < b < c`` and ``fun(b) < fun(a), fun(c)`` or two items ``a`` and
748 ``c`` which are assumed to be a starting interval for a downhill
749 bracket search (see `bracket`); it doesn't always mean that the
750 obtained solution will satisfy ``a <= x <= c``.
751 bounds : sequence, optional
752 For method 'bounded', `bounds` is mandatory and must have two finite
753 items corresponding to the optimization bounds.
754 args : tuple, optional
755 Extra arguments passed to the objective function.
756 method : str or callable, optional
757 Type of solver. Should be one of:
759 - :ref:`Brent <optimize.minimize_scalar-brent>`
760 - :ref:`Bounded <optimize.minimize_scalar-bounded>`
761 - :ref:`Golden <optimize.minimize_scalar-golden>`
762 - custom - a callable object (added in version 0.14.0), see below
764 Default is "Bounded" if bounds are provided and "Brent" otherwise.
765 See the 'Notes' section for details of each solver.
767 tol : float, optional
768 Tolerance for termination. For detailed control, use solver-specific
769 options.
770 options : dict, optional
771 A dictionary of solver options.
773 maxiter : int
774 Maximum number of iterations to perform.
775 disp : bool
776 Set to True to print convergence messages.
778 See :func:`show_options()` for solver-specific options.
780 Returns
781 -------
782 res : OptimizeResult
783 The optimization result represented as a ``OptimizeResult`` object.
784 Important attributes are: ``x`` the solution array, ``success`` a
785 Boolean flag indicating if the optimizer exited successfully and
786 ``message`` which describes the cause of the termination. See
787 `OptimizeResult` for a description of other attributes.
789 See also
790 --------
791 minimize : Interface to minimization algorithms for scalar multivariate
792 functions
793 show_options : Additional options accepted by the solvers
795 Notes
796 -----
797 This section describes the available solvers that can be selected by the
798 'method' parameter. The default method is the ``"Bounded"`` Brent method if
799 `bounds` are passed and unbounded ``"Brent"`` otherwise.
801 Method :ref:`Brent <optimize.minimize_scalar-brent>` uses Brent's
802 algorithm [1]_ to find a local minimum. The algorithm uses inverse
803 parabolic interpolation when possible to speed up convergence of
804 the golden section method.
806 Method :ref:`Golden <optimize.minimize_scalar-golden>` uses the
807 golden section search technique [1]_. It uses analog of the bisection
808 method to decrease the bracketed interval. It is usually
809 preferable to use the *Brent* method.
811 Method :ref:`Bounded <optimize.minimize_scalar-bounded>` can
812 perform bounded minimization [2]_ [3]_. It uses the Brent method to find a
813 local minimum in the interval x1 < xopt < x2.
815 **Custom minimizers**
817 It may be useful to pass a custom minimization method, for example
818 when using some library frontend to minimize_scalar. You can simply
819 pass a callable as the ``method`` parameter.
821 The callable is called as ``method(fun, args, **kwargs, **options)``
822 where ``kwargs`` corresponds to any other parameters passed to `minimize`
823 (such as `bracket`, `tol`, etc.), except the `options` dict, which has
824 its contents also passed as `method` parameters pair by pair. The method
825 shall return an `OptimizeResult` object.
827 The provided `method` callable must be able to accept (and possibly ignore)
828 arbitrary parameters; the set of parameters accepted by `minimize` may
829 expand in future versions and then these parameters will be passed to
830 the method. You can find an example in the scipy.optimize tutorial.
832 .. versionadded:: 0.11.0
834 References
835 ----------
836 .. [1] Press, W., S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery.
837 Numerical Recipes in C. Cambridge University Press.
838 .. [2] Forsythe, G.E., M. A. Malcolm, and C. B. Moler. "Computer Methods
839 for Mathematical Computations." Prentice-Hall Series in Automatic
840 Computation 259 (1977).
841 .. [3] Brent, Richard P. Algorithms for Minimization Without Derivatives.
842 Courier Corporation, 2013.
844 Examples
845 --------
846 Consider the problem of minimizing the following function.
848 >>> def f(x):
849 ... return (x - 2) * x * (x + 2)**2
851 Using the *Brent* method, we find the local minimum as:
853 >>> from scipy.optimize import minimize_scalar
854 >>> res = minimize_scalar(f)
855 >>> res.fun
856 -9.9149495908
858 The minimizer is:
860 >>> res.x
861 1.28077640403
863 Using the *Bounded* method, we find a local minimum with specified
864 bounds as:
866 >>> res = minimize_scalar(f, bounds=(-3, -1), method='bounded')
867 >>> res.fun # minimum
868 3.28365179850e-13
869 >>> res.x # minimizer
870 -2.0000002026
872 """
873 if not isinstance(args, tuple):
874 args = (args,)
876 if callable(method):
877 meth = "_custom"
878 elif method is None:
879 meth = 'brent' if bounds is None else 'bounded'
880 else:
881 meth = method.lower()
882 if options is None:
883 options = {}
885 if bounds is not None and meth in {'brent', 'golden'}:
886 message = f"Use of `bounds` is incompatible with 'method={method}'."
887 raise ValueError(message)
889 if tol is not None:
890 options = dict(options)
891 if meth == 'bounded' and 'xatol' not in options:
892 warn("Method 'bounded' does not support relative tolerance in x; "
893 "defaulting to absolute tolerance.", RuntimeWarning)
894 options['xatol'] = tol
895 elif meth == '_custom':
896 options.setdefault('tol', tol)
897 else:
898 options.setdefault('xtol', tol)
900 # replace boolean "disp" option, if specified, by an integer value.
901 disp = options.get('disp')
902 if isinstance(disp, bool):
903 options['disp'] = 2 * int(disp)
905 if meth == '_custom':
906 return method(fun, args=args, bracket=bracket, bounds=bounds, **options)
907 elif meth == 'brent':
908 return _minimize_scalar_brent(fun, bracket, args, **options)
909 elif meth == 'bounded':
910 if bounds is None:
911 raise ValueError('The `bounds` parameter is mandatory for '
912 'method `bounded`.')
913 return _minimize_scalar_bounded(fun, bounds, args, **options)
914 elif meth == 'golden':
915 return _minimize_scalar_golden(fun, bracket, args, **options)
916 else:
917 raise ValueError('Unknown solver %s' % method)
920def _remove_from_bounds(bounds, i_fixed):
921 """Removes fixed variables from a `Bounds` instance"""
922 lb = bounds.lb[~i_fixed]
923 ub = bounds.ub[~i_fixed]
924 return Bounds(lb, ub) # don't mutate original Bounds object
927def _remove_from_func(fun_in, i_fixed, x_fixed, min_dim=None, remove=0):
928 """Wraps a function such that fixed variables need not be passed in"""
929 def fun_out(x_in, *args, **kwargs):
930 x_out = np.zeros_like(i_fixed, dtype=x_in.dtype)
931 x_out[i_fixed] = x_fixed
932 x_out[~i_fixed] = x_in
933 y_out = fun_in(x_out, *args, **kwargs)
934 y_out = np.array(y_out)
936 if min_dim == 1:
937 y_out = np.atleast_1d(y_out)
938 elif min_dim == 2:
939 y_out = np.atleast_2d(y_out)
941 if remove == 1:
942 y_out = y_out[..., ~i_fixed]
943 elif remove == 2:
944 y_out = y_out[~i_fixed, ~i_fixed]
946 return y_out
947 return fun_out
950def _add_to_array(x_in, i_fixed, x_fixed):
951 """Adds fixed variables back to an array"""
952 i_free = ~i_fixed
953 if x_in.ndim == 2:
954 i_free = i_free[:, None] @ i_free[None, :]
955 x_out = np.zeros_like(i_free, dtype=x_in.dtype)
956 x_out[~i_free] = x_fixed
957 x_out[i_free] = x_in.ravel()
958 return x_out
961def standardize_bounds(bounds, x0, meth):
962 """Converts bounds to the form required by the solver."""
963 if meth in {'trust-constr', 'powell', 'nelder-mead', 'new'}:
964 if not isinstance(bounds, Bounds):
965 lb, ub = old_bound_to_new(bounds)
966 bounds = Bounds(lb, ub)
967 elif meth in ('l-bfgs-b', 'tnc', 'slsqp', 'old'):
968 if isinstance(bounds, Bounds):
969 bounds = new_bounds_to_old(bounds.lb, bounds.ub, x0.shape[0])
970 return bounds
973def standardize_constraints(constraints, x0, meth):
974 """Converts constraints to the form required by the solver."""
975 all_constraint_types = (NonlinearConstraint, LinearConstraint, dict)
976 new_constraint_types = all_constraint_types[:-1]
977 if constraints is None:
978 constraints = []
979 elif isinstance(constraints, all_constraint_types):
980 constraints = [constraints]
981 else:
982 constraints = list(constraints) # ensure it's a mutable sequence
984 if meth in ['trust-constr', 'new']:
985 for i, con in enumerate(constraints):
986 if not isinstance(con, new_constraint_types):
987 constraints[i] = old_constraint_to_new(i, con)
988 else:
989 # iterate over copy, changing original
990 for i, con in enumerate(list(constraints)):
991 if isinstance(con, new_constraint_types):
992 old_constraints = new_constraint_to_old(con, x0)
993 constraints[i] = old_constraints[0]
994 constraints.extend(old_constraints[1:]) # appends 1 if present
996 return constraints
999def _optimize_result_for_equal_bounds(
1000 fun, bounds, method, args=(), constraints=()
1001):
1002 """
1003 Provides a default OptimizeResult for when a bounded minimization method
1004 has (lb == ub).all().
1006 Parameters
1007 ----------
1008 fun: callable
1009 bounds: Bounds
1010 method: str
1011 constraints: Constraint
1012 """
1013 success = True
1014 message = 'All independent variables were fixed by bounds.'
1016 # bounds is new-style
1017 x0 = bounds.lb
1019 if constraints:
1020 message = ("All independent variables were fixed by bounds at values"
1021 " that satisfy the constraints.")
1022 constraints = standardize_constraints(constraints, x0, 'new')
1024 maxcv = 0
1025 for c in constraints:
1026 pc = PreparedConstraint(c, x0)
1027 violation = pc.violation(x0)
1028 if np.sum(violation):
1029 maxcv = max(maxcv, np.max(violation))
1030 success = False
1031 message = (f"All independent variables were fixed by bounds, but "
1032 f"the independent variables do not satisfy the "
1033 f"constraints exactly. (Maximum violation: {maxcv}).")
1035 return OptimizeResult(
1036 x=x0, fun=fun(x0, *args), success=success, message=message, nfev=1,
1037 njev=0, nhev=0,
1038 )