Hide keyboard shortcuts

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. 

3 

4Functions 

5--------- 

6- minimize : minimization of a function of several variables. 

7- minimize_scalar : minimization of a function of one variable. 

8""" 

9 

10__all__ = ['minimize', 'minimize_scalar'] 

11 

12 

13from warnings import warn 

14 

15import numpy as np 

16 

17 

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 

28 

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 

38 

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'] 

42 

43 

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. 

48 

49 Parameters 

50 ---------- 

51 fun : callable 

52 The objective function to be minimized. 

53 

54 ``fun(x, *args) -> float`` 

55 

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 

67 

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. 

84 

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: 

93 

94 ``jac(x, *args) -> array_like, shape (n,)`` 

95 

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: 

112 

113 ``hess(x, *args) -> {LinearOperator, spmatrix, array}, (n, n)`` 

114 

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: 

123 

124 - `BFGS`; 

125 - `SR1`. 

126 

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: 

139 

140 ``hessp(x, p, *args) -> ndarray shape (n,)`` 

141 

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: 

148 

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. 

152 

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: 

158 

159 - `LinearConstraint` 

160 - `NonlinearConstraint` 

161 

162 Constraints for COBYLA, SLSQP are defined as a list of dictionaries. 

163 Each dictionary with fields: 

164 

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. 

173 

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: 

183 

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. 

189 

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: 

194 

195 ``callback(xk, OptimizeResult state) -> bool`` 

196 

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: 

202 

203 ``callback(xk)`` 

204 

205 where ``xk`` is the current parameter vector. 

206 

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. 

215 

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 

221 

222 Notes 

223 ----- 

224 This section describes the available solvers that can be selected by the 

225 'method' parameter. The default method is *BFGS*. 

226 

227 **Unconstrained minimization** 

228 

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. 

235 

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. 

240 

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. 

247 

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. 

254 

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. 

259 

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. 

265 

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. 

273 

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. 

281 

282 **Bound-Constrained minimization** 

283 

284 Method :ref:`L-BFGS-B <optimize.minimize-lbfgsb>` uses the L-BFGS-B 

285 algorithm [6]_, [7]_ for bound constrained minimization. 

286 

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. 

304 

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. 

311 

312 **Constrained Minimization** 

313 

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. 

321 

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. 

329 

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. 

345 

346 **Finite-Difference Options** 

347 

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. 

355 

356 **Custom minimizers** 

357 

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. 

362 

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. 

371 

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. 

376 

377 .. versionadded:: 0.11.0 

378 

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. 

430 

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`. 

436 

437 >>> from scipy.optimize import minimize, rosen, rosen_der 

438 

439 A simple application of the *Nelder-Mead* method is: 

440 

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.]) 

445 

446 Now using the *BFGS* algorithm, using the first derivative and a few 

447 options: 

448 

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]]) 

466 

467 

468 Next, consider a minimization problem with several constraints (namely 

469 Example 16.4 from [5]_). The objective function is: 

470 

471 >>> fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2 

472 

473 There are three constraints defined as: 

474 

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}) 

478 

479 And variables must be positive, hence the following bounds: 

480 

481 >>> bnds = ((0, None), (0, None)) 

482 

483 The optimization problem is solved using the SLSQP method as: 

484 

485 >>> res = minimize(fun, (2, 0), method='SLSQP', bounds=bnds, 

486 ... constraints=cons) 

487 

488 It should converge to the theoretical solution (1.4 ,1.7). 

489 

490 """ 

491 x0 = np.asarray(x0) 

492 if x0.dtype.kind in np.typecodes["AllInteger"]: 

493 x0 = np.asarray(x0, dtype=float) 

494 

495 if not isinstance(args, tuple): 

496 args = (args,) 

497 

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' 

506 

507 if callable(method): 

508 meth = "_custom" 

509 else: 

510 meth = method.lower() 

511 

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) 

549 

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 

570 

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) 

590 

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) 

598 

599 if bounds is not None: 

600 bounds = standardize_bounds(bounds, x0, meth) 

601 

602 if constraints is not None: 

603 constraints = standardize_constraints(constraints, x0, meth) 

604 

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) 

645 

646 

647def minimize_scalar(fun, bracket=None, bounds=None, args=(), 

648 method='brent', tol=None, options=None): 

649 """Minimization of scalar function of one variable. 

650 

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: 

670 

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 

675 

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. 

681 

682 maxiter : int 

683 Maximum number of iterations to perform. 

684 disp : bool 

685 Set to True to print convergence messages. 

686 

687 See :func:`show_options()` for solver-specific options. 

688 

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. 

697 

698 See also 

699 -------- 

700 minimize : Interface to minimization algorithms for scalar multivariate 

701 functions 

702 show_options : Additional options accepted by the solvers 

703 

704 Notes 

705 ----- 

706 This section describes the available solvers that can be selected by the 

707 'method' parameter. The default method is *Brent*. 

708 

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. 

713 

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. 

718 

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. 

722 

723 **Custom minimizers** 

724 

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. 

728 

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. 

734 

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. 

739 

740 .. versionadded:: 0.11.0 

741 

742 Examples 

743 -------- 

744 Consider the problem of minimizing the following function. 

745 

746 >>> def f(x): 

747 ... return (x - 2) * x * (x + 2)**2 

748 

749 Using the *Brent* method, we find the local minimum as: 

750 

751 >>> from scipy.optimize import minimize_scalar 

752 >>> res = minimize_scalar(f) 

753 >>> res.x 

754 1.28077640403 

755 

756 Using the *Bounded* method, we find a local minimum with specified 

757 bounds as: 

758 

759 >>> res = minimize_scalar(f, bounds=(-3, -1), method='bounded') 

760 >>> res.x 

761 -2.0000002026 

762 

763 """ 

764 if not isinstance(args, tuple): 

765 args = (args,) 

766 

767 if callable(method): 

768 meth = "_custom" 

769 else: 

770 meth = method.lower() 

771 if options is None: 

772 options = {} 

773 

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) 

784 

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) 

803 

804 

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 

815 

816 

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 

824 

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 

836 

837 return constraints