Optimierung und Wurzelsuche (scipy.optimize)

SciPy optimize bietet Funktionen zur Minimierung (oder Maximierung) von Zielfunktionen, möglicherweise unter Nebenbedingungen. Es enthält Löser für nichtlineare Probleme (mit Unterstützung für lokale und globale Optimierungsalgorithmen), lineare Programmierung, eingeschränkte und nichtlineare Kleinste-Quadrate-Anpassungen, Wurzelsuche und Kurvenanpassung.

Häufig verwendete Funktionen und Objekte, die über verschiedene Löser hinweg gemeinsam genutzt werden, sind

show_options([solver, method, disp])	Zeigt Dokumentation für zusätzliche Optionen von Optimierungs-Lösern an.
OptimizeResult	Repräsentiert das Optimierungsergebnis.
OptimizeWarning	Allgemeine Warnung für scipy.optimize.

Optimierung

Optimierung von skalaren Funktionen

minimize_scalar(fun[, bracket, bounds, ...])

Lokale Minimierung einer skalaren Funktion einer Variablen.

Die Funktion minimize_scalar unterstützt die folgenden Methoden

• minimize_scalar(method=’brent’)
• minimize_scalar(method=’bounded’)
• minimize_scalar(method=’golden’)

Lokale (multivariate) Optimierung

minimize(fun, x0[, args, method, jac, hess, ...])

Minimierung einer skalaren Funktion einer oder mehrerer Variablen.

Die Funktion minimize unterstützt die folgenden Methoden

• minimize(method=’Nelder-Mead’)
• minimize(method=’Powell’)
• minimize(method=’CG’)
• minimize(method=’BFGS’)
• minimize(method=’Newton-CG’)
• minimize(method=’L-BFGS-B’)
• minimize(method=’TNC’)
• minimize(method=’COBYLA’)
• minimize(method=’COBYQA’)
• minimize(method=’SLSQP’)
• minimize(method=’trust-constr’)
• minimize(method=’dogleg’)
• minimize(method=’trust-ncg’)
• minimize(method=’trust-krylov’)
• minimize(method=’trust-exact’)

Nebenbedingungen werden der Funktion minimize als einzelnes Objekt oder als Liste von Objekten aus den folgenden Klassen übergeben

NonlinearConstraint(fun, lb, ub[, jac, ...])	Nichtlineare Bedingung für die Variablen.
LinearConstraint(A[, lb, ub, keep_feasible])	Lineare Bedingung für die Variablen.

Einfache Grenzbedingungen werden separat behandelt und es gibt eine spezielle Klasse dafür

Bounds([lb, ub, keep_feasible])

Grenzbedingung für die Variablen.

Quasi-Newton-Strategien, die die HessianUpdateStrategy-Schnittstelle implementieren, können verwendet werden, um die Hesse-Matrix in der Funktion minimize zu approximieren (nur für die Methode ‚trust-constr‘ verfügbar). Verfügbare Quasi-Newton-Methoden, die diese Schnittstelle implementieren, sind

BFGS([exception_strategy, min_curvature, ...])	Broyden-Fletcher-Goldfarb-Shanno (BFGS) Hesse-Matrix-Update-Strategie.
SR1([min_denominator, init_scale])	Symmetrische Rang-1-Hesse-Matrix-Update-Strategie.

Globale Optimierung

basinhopping(func, x0[, niter, T, stepsize, ...])	Findet das globale Minimum einer Funktion mithilfe des Basin-Hopping-Algorithmus.
brute(func, ranges[, args, Ns, full_output, ...])	Minimiert eine Funktion über einen gegebenen Bereich durch Brute-Force.
differential_evolution(func, bounds[, args, ...])	Findet das globale Minimum einer multivariaten Funktion.
shgo(func, bounds[, args, constraints, n, ...])	Findet das globale Minimum einer Funktion mithilfe der SHG-Optimierung.
dual_annealing(func, bounds[, args, ...])	Findet das globale Minimum einer Funktion mithilfe von Dual Annealing.
direct(func, bounds, *[, args, eps, maxfun, ...])	Findet das globale Minimum einer Funktion mithilfe des DIRECT-Algorithmus.

Kleinste-Quadrate und Kurvenanpassung

Nichtlineare Kleinste-Quadrate

least_squares(fun, x0[, jac, bounds, ...])

Löst ein nichtlineares Kleinste-Quadrate-Problem mit Grenzen für die Variablen.

Lineare Kleinste-Quadrate

nnls(A, b, *[, maxiter, atol])	Löst argmin_x || Ax - b ||_2 für x>=0.
lsq_linear(A, b[, bounds, method, tol, ...])	Löst ein lineares Kleinste-Quadrate-Problem mit Grenzen für die Variablen.
isotonic_regression(y, *[, weights, increasing])	Nichtparametrische isotonische Regression.

Kurvenanpassung

curve_fit(f, xdata, ydata[, p0, sigma, ...])

Verwendet nichtlineare Kleinste-Quadrate, um eine Funktion f an Daten anzupassen.

Wurzelsuche

Skalare Funktionen

root_scalar(f[, args, method, bracket, ...])	Findet eine Wurzel einer skalaren Funktion.
brentq(f, a, b[, args, xtol, rtol, maxiter, ...])	Findet eine Wurzel einer Funktion in einem Intervall mithilfe von Brents Methode.
brenth(f, a, b[, args, xtol, rtol, maxiter, ...])	Findet eine Wurzel einer Funktion in einem Intervall mithilfe von Brents Methode mit hyperbolischer Extrapolation.
ridder(f, a, b[, args, xtol, rtol, maxiter, ...])	Findet eine Wurzel einer Funktion in einem Intervall mithilfe von Ridders Methode.
bisect(f, a, b[, args, xtol, rtol, maxiter, ...])	Findet die Wurzel einer Funktion in einem Intervall mithilfe der Bisektionsmethode.
newton(func, x0[, fprime, args, tol, ...])	Findet eine Wurzel einer reellen oder komplexen Funktion mithilfe der Newton-Raphson (oder Sekanten- oder Hallley'schen) Methode.
toms748(f, a, b[, args, k, xtol, rtol, ...])	Findet eine Wurzel mithilfe der TOMS-Algorithmus 748 Methode.
RootResults(root, iterations, ...)	Repräsentiert das Ergebnis der Wurzelsuche.

Die Funktion root_scalar unterstützt die folgenden Methoden

• root_scalar(method=’brentq’)
• root_scalar(method=’brenth’)
• root_scalar(method=’bisect’)
• root_scalar(method=’ridder’)
• root_scalar(method=’newton’)
• root_scalar(method=’toms748’)
• root_scalar(method=’secant’)
• root_scalar(method=’halley’)

Die folgende Tabelle listet Situationen und geeignete Methoden auf, zusammen mit den *asymptotischen* Konvergenzraten pro Iteration (und pro Funktionsauswertung) für die erfolgreiche Konvergenz zu einer einfachen Wurzel(*). Die Bisektionsmethode ist die langsamste von allen und fügt bei jeder Funktionsauswertung ein Bit an Genauigkeit hinzu, garantiert aber die Konvergenz. Die anderen bracketing-Methoden erhöhen alle (schließlich) die Anzahl der genauen Bits um etwa 50 % bei jeder Funktionsauswertung. Die ableitungsbasierten Methoden, die alle auf newton basieren, können sehr schnell konvergieren, wenn der Startwert nahe an der Wurzel liegt. Sie können auch auf Funktionen angewendet werden, die auf (einer Teilmenge) der komplexen Ebene definiert sind.

Definitionsbereich von f	Geklammert?	Ableitungen?		Löser	Konvergenz
		fprime	fprime2		Garantiert?	Rate(n)(*)
R	Ja	N/A	N/A	bisection brentq brenth ridder toms748	Ja Ja Ja Ja Ja	1 "Linear" >=1, <= 1.62 >=1, <= 1.62 2.0 (1.41) 2.7 (1.65)
R oder C	Nein	Nein	Nein	secant	Nein	1.62 (1.62)
R oder C	Nein	Ja	Nein	newton	Nein	2.00 (1.41)
R oder C	Nein	Ja	Ja	halley	Nein	3.00 (1.44)

Siehe auch

scipy.optimize.cython_optimize – Typisierte Cython-Versionen von Wurzelsuchfunktionen

Fixpunktfindung

fixed_point(func, x0[, args, xtol, maxiter, ...])

Findet einen Fixpunkt der Funktion.

Mehrdimensional

root(fun, x0[, args, method, jac, tol, ...])

Finde eine Wurzel einer Vektorfunktion.

Die Funktion root unterstützt die folgenden Methoden

• root(method=’hybr’)
• root(method=’lm’)
• root(method=’broyden1’)
• root(method=’broyden2’)
• root(method=’anderson’)
• root(method=’linearmixing’)
• root(method=’diagbroyden’)
• root(method=’excitingmixing’)
• root(method=’krylov’)
• root(method=’df-sane’)

Elementweise Minimierung und Wurzelsuche

• Elementweise Skalaroptimierung (scipy.optimize.elementwise)
  • Nullstellenfindung
    • find_root
    • bracket_root
  • Minimierung
    • find_minimum
    • bracket_minimum

Lineare Programmierung / MILP

milp(c, *[, integrality, bounds, ...])	Gemischt-ganzzahlige lineare Programmierung
linprog(c[, A_ub, b_ub, A_eq, b_eq, bounds, ...])	Lineare Programmierung: Minimiert eine lineare Zielfunktion unter linearen Gleichheits- und Ungleichheitsbedingungen.

Die Funktion linprog unterstützt die folgenden Methoden

• linprog(method=’simplex’)
• linprog(method=’interior-point’)
• linprog(method=’revised simplex’)
• linprog(method=’highs-ipm’)
• linprog(method=’highs-ds’)
• linprog(method=’highs’)

Die Methoden Simplex, Interior-Point und Revised Simplex unterstützen Callback-Funktionen, wie z.B.

linprog_verbose_callback(res)

Eine Beispiel-Callback-Funktion, die die linprog-Callback-Schnittstelle demonstriert.

Zuordnungsprobleme

linear_sum_assignment	Löst das lineare Summenzuordnungsproblem.
quadratic_assignment(A, B[, method, options])	Approximiert die Lösung für das quadratische Zuordnungsproblem und das Graph-Matching-Problem.

Die Funktion quadratic_assignment unterstützt die folgenden Methoden

• quadratic_assignment(method=’faq’)
• quadratic_assignment(method=’2opt’)

Dienstprogramme

Finite-Differenzen-Approximation

approx_fprime(xk, f[, epsilon])	Finite-Differenzen-Approximation der Ableitungen einer skalaren oder vektorwertigen Funktion.
check_grad(func, grad, x0, *args[, epsilon, ...])	Überprüft die Korrektheit einer Gradientenfunktion, indem sie mit einer (Vorwärts-)Finite-Differenzen-Approximation des Gradienten verglichen wird.

Zeilensuche

bracket(func[, xa, xb, args, grow_limit, ...])	Klammert das Minimum einer Funktion ein.
line_search(f, myfprime, xk, pk[, gfk, ...])	Findet ein Alpha, das die starken Wolfe-Bedingungen erfüllt.

Hesse-Matrix-Approximation

LbfgsInvHessProduct(*args, **kwargs)	Linearer Operator für die L-BFGS-approximierte inverse Hesse-Matrix.
HessianUpdateStrategy()	Schnittstelle zur Implementierung von Hesse-Matrix-Update-Strategien.

Benchmark-Probleme

rosen(x)	Die Rosenbrock-Funktion.
rosen_der(x)	Die Ableitung (d.h. der Gradient) der Rosenbrock-Funktion.
rosen_hess(x)	Die Hesse-Matrix der Rosenbrock-Funktion.
rosen_hess_prod(x, p)	Produkt der Hesse-Matrix der Rosenbrock-Funktion mit einem Vektor.

Legacy-Funktionen

Die unten aufgeführten Funktionen werden für die Verwendung in neuen Skripten nicht empfohlen; alle diese Methoden sind über neuere, konsistentere Schnittstellen zugänglich, die von den oben genannten Schnittstellen bereitgestellt werden.

Optimierung

Allzweck-multivariate Methoden

fmin(func, x0[, args, xtol, ftol, maxiter, ...])	Minimiert eine Funktion mithilfe des Downhill-Simplex-Algorithmus.
fmin_powell(func, x0[, args, xtol, ftol, ...])	Minimiert eine Funktion mithilfe der modifizierten Powell-Methode.
fmin_cg(f, x0[, fprime, args, gtol, norm, ...])	Minimiert eine Funktion mithilfe eines nichtlinearen konjugierten Gradientenalgorithmus.
fmin_bfgs(f, x0[, fprime, args, gtol, norm, ...])	Minimiert eine Funktion mithilfe des BFGS-Algorithmus.
fmin_ncg(f, x0, fprime[, fhess_p, fhess, ...])	Unbeschränkte Minimierung einer Funktion mithilfe der Newton-CG-Methode.

Beschränkte multivariate Methoden

fmin_l_bfgs_b(func, x0[, fprime, args, ...])	Minimiert eine Funktion func mithilfe des L-BFGS-B-Algorithmus.
fmin_tnc(func, x0[, fprime, args, ...])	Minimiert eine Funktion mit Variablen, die Grenzen unterliegen, unter Verwendung von Gradienteninformationen in einem abgeschnittenen Newton-Algorithmus.
fmin_cobyla(func, x0, cons[, args, ...])	Minimiert eine Funktion mithilfe der COBYLA-Methode (Constrained Optimization By Linear Approximation).
fmin_slsqp(func, x0[, eqcons, f_eqcons, ...])	Minimiert eine Funktion mithilfe von Sequential Least Squares Programming

Univariate (skalare) Minimierungsmethoden

fminbound(func, x1, x2[, args, xtol, ...])	Beschränkte Minimierung für skalare Funktionen.
brent(func[, args, brack, tol, full_output, ...])	Gibt bei einer Funktion einer Variablen und einer möglichen Klammer einen lokalen Minimierer der Funktion zurück, der bis zu einer Bruchteilgenauigkeit von tol isoliert ist.
golden(func[, args, brack, tol, ...])	Gibt den Minimierer einer Funktion einer Variablen mithilfe der Golden-Section-Methode zurück.

Kleinste Quadrate

leastsq(func, x0[, args, Dfun, full_output, ...])

Minimiert die Summe der Quadrate eines Gleichungssystems.

Wurzelsuche

Allgemeine nichtlineare Löser

fsolve(func, x0[, args, fprime, ...])	Findet die Wurzeln einer Funktion.
broyden1(F, xin[, iter, alpha, ...])	Findet eine Wurzel einer Funktion mithilfe von Broydens erster Jacobi-Approximation.
broyden2(F, xin[, iter, alpha, ...])	Findet eine Wurzel einer Funktion mithilfe von Broydens zweiter Jacobi-Approximation.
NoConvergence	Ausnahme, die ausgelöst wird, wenn ein nichtlinearer Löser nicht innerhalb der angegebenen maxiter konvergiert.

Großskalige nichtlineare Löser

newton_krylov(F, xin[, iter, rdiff, method, ...])	Findet eine Wurzel einer Funktion mithilfe einer Krylov-Approximation für die inverse Jacobi-Matrix.
anderson(F, xin[, iter, alpha, w0, M, ...])	Findet eine Wurzel einer Funktion mithilfe von (erweitertem) Anderson-Mixing.
BroydenFirst([alpha, reduction_method, max_rank])	Findet eine Wurzel einer Funktion mithilfe von Broydens erster Jacobi-Approximation.
InverseJacobian(jacobian)	Ein einfacher Wrapper, der die Jacobi-Matrix mithilfe der solve-Methode invertiert.
KrylovJacobian([rdiff, method, ...])	Findet eine Wurzel einer Funktion mithilfe einer Krylov-Approximation für die inverse Jacobi-Matrix.

Einfache Iterationslöser

excitingmixing(F, xin[, iter, alpha, ...])	Findet eine Wurzel einer Funktion mithilfe einer abgestimmten diagonalen Jacobi-Approximation.
linearmixing(F, xin[, iter, alpha, verbose, ...])	Findet eine Wurzel einer Funktion mithilfe einer skalaren Jacobi-Approximation.
diagbroyden(F, xin[, iter, alpha, verbose, ...])	Findet eine Wurzel einer Funktion mithilfe der diagonalen Broyden-Jacobi-Approximation.