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""" 

2===================================================== 

3Optimization and root finding (:mod:`scipy.optimize`) 

4===================================================== 

5 

6.. currentmodule:: scipy.optimize 

7 

8SciPy ``optimize`` provides functions for minimizing (or maximizing) 

9objective functions, possibly subject to constraints. It includes 

10solvers for nonlinear problems (with support for both local and global 

11optimization algorithms), linear programing, constrained 

12and nonlinear least-squares, root finding, and curve fitting. 

13 

14Common functions and objects, shared across different solvers, are: 

15 

16.. autosummary:: 

17 :toctree: generated/ 

18 

19 show_options - Show specific options optimization solvers. 

20 OptimizeResult - The optimization result returned by some optimizers. 

21 OptimizeWarning - The optimization encountered problems. 

22 

23 

24Optimization 

25============ 

26 

27Scalar functions optimization 

28----------------------------- 

29 

30.. autosummary:: 

31 :toctree: generated/ 

32 

33 minimize_scalar - Interface for minimizers of univariate functions 

34 

35The `minimize_scalar` function supports the following methods: 

36 

37.. toctree:: 

38 

39 optimize.minimize_scalar-brent 

40 optimize.minimize_scalar-bounded 

41 optimize.minimize_scalar-golden 

42 

43Local (multivariate) optimization 

44--------------------------------- 

45 

46.. autosummary:: 

47 :toctree: generated/ 

48 

49 minimize - Interface for minimizers of multivariate functions. 

50 

51The `minimize` function supports the following methods: 

52 

53.. toctree:: 

54 

55 optimize.minimize-neldermead 

56 optimize.minimize-powell 

57 optimize.minimize-cg 

58 optimize.minimize-bfgs 

59 optimize.minimize-newtoncg 

60 optimize.minimize-lbfgsb 

61 optimize.minimize-tnc 

62 optimize.minimize-cobyla 

63 optimize.minimize-slsqp 

64 optimize.minimize-trustconstr 

65 optimize.minimize-dogleg 

66 optimize.minimize-trustncg 

67 optimize.minimize-trustkrylov 

68 optimize.minimize-trustexact 

69 

70Constraints are passed to `minimize` function as a single object or 

71as a list of objects from the following classes: 

72 

73.. autosummary:: 

74 :toctree: generated/ 

75 

76 NonlinearConstraint - Class defining general nonlinear constraints. 

77 LinearConstraint - Class defining general linear constraints. 

78 

79Simple bound constraints are handled separately and there is a special class 

80for them: 

81 

82.. autosummary:: 

83 :toctree: generated/ 

84 

85 Bounds - Bound constraints. 

86 

87Quasi-Newton strategies implementing `HessianUpdateStrategy` 

88interface can be used to approximate the Hessian in `minimize` 

89function (available only for the 'trust-constr' method). Available 

90quasi-Newton methods implementing this interface are: 

91 

92.. autosummary:: 

93 :toctree: generated/ 

94 

95 BFGS - Broyden-Fletcher-Goldfarb-Shanno (BFGS) Hessian update strategy. 

96 SR1 - Symmetric-rank-1 Hessian update strategy. 

97 

98Global optimization 

99------------------- 

100 

101.. autosummary:: 

102 :toctree: generated/ 

103 

104 basinhopping - Basinhopping stochastic optimizer. 

105 brute - Brute force searching optimizer. 

106 differential_evolution - stochastic minimization using differential evolution. 

107 

108 shgo - simplicial homology global optimisation 

109 dual_annealing - Dual annealing stochastic optimizer. 

110 

111 

112Least-squares and curve fitting 

113=============================== 

114 

115Nonlinear least-squares 

116----------------------- 

117 

118.. autosummary:: 

119 :toctree: generated/ 

120 

121 least_squares - Solve a nonlinear least-squares problem with bounds on the variables. 

122 

123Linear least-squares 

124-------------------- 

125 

126.. autosummary:: 

127 :toctree: generated/ 

128 

129 nnls - Linear least-squares problem with non-negativity constraint. 

130 lsq_linear - Linear least-squares problem with bound constraints. 

131 

132Curve fitting 

133------------- 

134 

135.. autosummary:: 

136 :toctree: generated/ 

137 

138 curve_fit -- Fit curve to a set of points. 

139 

140Root finding 

141============ 

142 

143Scalar functions 

144---------------- 

145.. autosummary:: 

146 :toctree: generated/ 

147 

148 root_scalar - Unified interface for nonlinear solvers of scalar functions. 

149 brentq - quadratic interpolation Brent method. 

150 brenth - Brent method, modified by Harris with hyperbolic extrapolation. 

151 ridder - Ridder's method. 

152 bisect - Bisection method. 

153 newton - Newton's method (also Secant and Halley's methods). 

154 toms748 - Alefeld, Potra & Shi Algorithm 748. 

155 RootResults - The root finding result returned by some root finders. 

156 

157The `root_scalar` function supports the following methods: 

158 

159.. toctree:: 

160 

161 optimize.root_scalar-brentq 

162 optimize.root_scalar-brenth 

163 optimize.root_scalar-bisect 

164 optimize.root_scalar-ridder 

165 optimize.root_scalar-newton 

166 optimize.root_scalar-toms748 

167 optimize.root_scalar-secant 

168 optimize.root_scalar-halley 

169 

170 

171 

172The table below lists situations and appropriate methods, along with 

173*asymptotic* convergence rates per iteration (and per function evaluation) 

174for successful convergence to a simple root(*). 

175Bisection is the slowest of them all, adding one bit of accuracy for each 

176function evaluation, but is guaranteed to converge. 

177The other bracketing methods all (eventually) increase the number of accurate 

178bits by about 50% for every function evaluation. 

179The derivative-based methods, all built on `newton`, can converge quite quickly 

180if the initial value is close to the root. They can also be applied to 

181functions defined on (a subset of) the complex plane. 

182 

183+-------------+----------+----------+-----------+-------------+-------------+----------------+ 

184| Domain of f | Bracket? | Derivatives? | Solvers | Convergence | 

185+ + +----------+-----------+ +-------------+----------------+ 

186| | | `fprime` | `fprime2` | | Guaranteed? | Rate(s)(*) | 

187+=============+==========+==========+===========+=============+=============+================+ 

188| `R` | Yes | N/A | N/A | - bisection | - Yes | - 1 "Linear" | 

189| | | | | - brentq | - Yes | - >=1, <= 1.62 | 

190| | | | | - brenth | - Yes | - >=1, <= 1.62 | 

191| | | | | - ridder | - Yes | - 2.0 (1.41) | 

192| | | | | - toms748 | - Yes | - 2.7 (1.65) | 

193+-------------+----------+----------+-----------+-------------+-------------+----------------+ 

194| `R` or `C` | No | No | No | secant | No | 1.62 (1.62) | 

195+-------------+----------+----------+-----------+-------------+-------------+----------------+ 

196| `R` or `C` | No | Yes | No | newton | No | 2.00 (1.41) | 

197+-------------+----------+----------+-----------+-------------+-------------+----------------+ 

198| `R` or `C` | No | Yes | Yes | halley | No | 3.00 (1.44) | 

199+-------------+----------+----------+-----------+-------------+-------------+----------------+ 

200 

201.. seealso:: 

202 

203 `scipy.optimize.cython_optimize` -- Typed Cython versions of zeros functions 

204 

205Fixed point finding: 

206 

207.. autosummary:: 

208 :toctree: generated/ 

209 

210 fixed_point - Single-variable fixed-point solver. 

211 

212Multidimensional 

213---------------- 

214 

215.. autosummary:: 

216 :toctree: generated/ 

217 

218 root - Unified interface for nonlinear solvers of multivariate functions. 

219 

220The `root` function supports the following methods: 

221 

222.. toctree:: 

223 

224 optimize.root-hybr 

225 optimize.root-lm 

226 optimize.root-broyden1 

227 optimize.root-broyden2 

228 optimize.root-anderson 

229 optimize.root-linearmixing 

230 optimize.root-diagbroyden 

231 optimize.root-excitingmixing 

232 optimize.root-krylov 

233 optimize.root-dfsane 

234 

235Linear programming 

236================== 

237 

238.. autosummary:: 

239 :toctree: generated/ 

240 

241 linprog -- Unified interface for minimizers of linear programming problems. 

242 

243The `linprog` function supports the following methods: 

244 

245.. toctree:: 

246 

247 optimize.linprog-simplex 

248 optimize.linprog-interior-point 

249 optimize.linprog-revised_simplex 

250 

251The simplex method supports callback functions, such as: 

252 

253.. autosummary:: 

254 :toctree: generated/ 

255 

256 linprog_verbose_callback -- Sample callback function for linprog (simplex). 

257 

258Assignment problems: 

259 

260.. autosummary:: 

261 :toctree: generated/ 

262 

263 linear_sum_assignment -- Solves the linear-sum assignment problem. 

264 

265Utilities 

266========= 

267 

268Finite-difference approximation 

269------------------------------- 

270 

271.. autosummary:: 

272 :toctree: generated/ 

273 

274 approx_fprime - Approximate the gradient of a scalar function. 

275 check_grad - Check the supplied derivative using finite differences. 

276 

277 

278Line search 

279----------- 

280 

281.. autosummary:: 

282 :toctree: generated/ 

283 

284 bracket - Bracket a minimum, given two starting points. 

285 line_search - Return a step that satisfies the strong Wolfe conditions. 

286 

287Hessian approximation 

288--------------------- 

289 

290.. autosummary:: 

291 :toctree: generated/ 

292 

293 LbfgsInvHessProduct - Linear operator for L-BFGS approximate inverse Hessian. 

294 HessianUpdateStrategy - Interface for implementing Hessian update strategies 

295 

296Benchmark problems 

297------------------ 

298 

299.. autosummary:: 

300 :toctree: generated/ 

301 

302 rosen - The Rosenbrock function. 

303 rosen_der - The derivative of the Rosenbrock function. 

304 rosen_hess - The Hessian matrix of the Rosenbrock function. 

305 rosen_hess_prod - Product of the Rosenbrock Hessian with a vector. 

306 

307Legacy functions 

308================ 

309 

310The functions below are not recommended for use in new scripts; 

311all of these methods are accessible via a newer, more consistent 

312interfaces, provided by the interfaces above. 

313 

314Optimization 

315------------ 

316 

317General-purpose multivariate methods: 

318 

319.. autosummary:: 

320 :toctree: generated/ 

321 

322 fmin - Nelder-Mead Simplex algorithm. 

323 fmin_powell - Powell's (modified) level set method. 

324 fmin_cg - Non-linear (Polak-Ribiere) conjugate gradient algorithm. 

325 fmin_bfgs - Quasi-Newton method (Broydon-Fletcher-Goldfarb-Shanno). 

326 fmin_ncg - Line-search Newton Conjugate Gradient. 

327 

328Constrained multivariate methods: 

329 

330.. autosummary:: 

331 :toctree: generated/ 

332 

333 fmin_l_bfgs_b - Zhu, Byrd, and Nocedal's constrained optimizer. 

334 fmin_tnc - Truncated Newton code. 

335 fmin_cobyla - Constrained optimization by linear approximation. 

336 fmin_slsqp - Minimization using sequential least-squares programming. 

337 

338Univariate (scalar) minimization methods: 

339 

340.. autosummary:: 

341 :toctree: generated/ 

342 

343 fminbound - Bounded minimization of a scalar function. 

344 brent - 1-D function minimization using Brent method. 

345 golden - 1-D function minimization using Golden Section method. 

346 

347Least-squares 

348------------- 

349 

350.. autosummary:: 

351 :toctree: generated/ 

352 

353 leastsq - Minimize the sum of squares of M equations in N unknowns. 

354 

355Root finding 

356------------ 

357 

358General nonlinear solvers: 

359 

360.. autosummary:: 

361 :toctree: generated/ 

362 

363 fsolve - Non-linear multivariable equation solver. 

364 broyden1 - Broyden's first method. 

365 broyden2 - Broyden's second method. 

366 

367Large-scale nonlinear solvers: 

368 

369.. autosummary:: 

370 :toctree: generated/ 

371 

372 newton_krylov 

373 anderson 

374 

375Simple iteration solvers: 

376 

377.. autosummary:: 

378 :toctree: generated/ 

379 

380 excitingmixing 

381 linearmixing 

382 diagbroyden 

383 

384:mod:`Additional information on the nonlinear solvers <scipy.optimize.nonlin>` 

385""" 

386 

387from .optimize import * 

388from ._minimize import * 

389from ._root import * 

390from ._root_scalar import * 

391from .minpack import * 

392from .zeros import * 

393from .lbfgsb import fmin_l_bfgs_b, LbfgsInvHessProduct 

394from .tnc import fmin_tnc 

395from .cobyla import fmin_cobyla 

396from .nonlin import * 

397from .slsqp import fmin_slsqp 

398from ._nnls import nnls 

399from ._basinhopping import basinhopping 

400from ._linprog import linprog, linprog_verbose_callback 

401from ._lsap import linear_sum_assignment 

402from ._differentialevolution import differential_evolution 

403from ._lsq import least_squares, lsq_linear 

404from ._constraints import (NonlinearConstraint, 

405 LinearConstraint, 

406 Bounds) 

407from ._hessian_update_strategy import HessianUpdateStrategy, BFGS, SR1 

408from ._shgo import shgo 

409from ._dual_annealing import dual_annealing 

410 

411__all__ = [s for s in dir() if not s.startswith('_')] 

412 

413from scipy._lib._testutils import PytestTester 

414test = PytestTester(__name__) 

415del PytestTester