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