scipy.optimize.

shgo#

scipy.optimize.shgo(func, bounds, args=(), constraints=None, n=100, iters=1, callback=None, minimizer_kwargs=None, options=None, sampling_method='simplicial', *, workers=1)[Quelle]#

Findet das globale Minimum einer Funktion mittels SHG-Optimierung.

SHGO steht für „simplicial homology global optimization“.

Parameter:

funccallable

Die zu minimierende Zielfunktion. Muss im Format f(x, *args) sein, wobei x das Argument in Form eines 1D-Arrays und args ein Tupel zusätzlicher fester Parameter ist, die zur vollständigen Spezifikation der Funktion erforderlich sind.

boundssequenz oder Bounds

Grenzen für Variablen. Es gibt zwei Möglichkeiten, die Grenzen festzulegen:

Instanz der Klasse Bounds.
Sequenz von (min, max) Paaren für jedes Element in x.

argstuple, optional

Alle zusätzlichen festen Parameter, die zur vollständigen Spezifikation der Zielfunktion erforderlich sind.

constraints{Constraint, dict} oder Liste von {Constraint, dict}, optional

Definition der Nebenbedingungen. Nur für COBYLA, COBYQA, SLSQP und trust-constr. Weitere Details zur Angabe von Nebenbedingungen finden Sie im Tutorial [5].

Hinweis

Nur die lokalen Minimierungsverfahren COBYLA, COBYQA, SLSQP und trust-constr unterstützen derzeit Argumente für Nebenbedingungen. Wenn die in minimizer_kwargs definierte Nebenbedingungssequenz für das lokale Optimierungsproblem nicht vorhanden ist und eine Nebenbedingungsmethode verwendet wird, werden die globalen constraints verwendet. (Die Definition einer constraints Sequenz in minimizer_kwargs bedeutet, dass constraints nicht hinzugefügt werden. Wenn also Gleichheitsnebenbedingungen usw. hinzugefügt werden müssen, müssen die Ungleichungsfunktionen in constraints ebenfalls zu minimizer_kwargs hinzugefügt werden). COBYLA unterstützt nur Ungleichungsnebenbedingungen.

Geändert in Version 1.11.0: constraints akzeptiert NonlinearConstraint, LinearConstraint.

nint, optional

Anzahl der Stichprobenpunkte, die bei der Konstruktion des simplizialen Komplexes verwendet werden. Für die Standardmethode simplicial werden 2**dim + 1 Stichprobenpunkte generiert, anstatt der Standardeinstellung n=100. Für alle anderen angegebenen Werte von n werden n Stichprobenpunkte generiert. Für sobol, halton und andere beliebige sampling_methods werden n=100 oder eine andere angegebene Anzahl von Stichprobenpunkten generiert.

itersint, optional

Anzahl der Iterationen, die bei der Konstruktion des simplizialen Komplexes verwendet werden. Standard ist 1.

callbackcallable, optional

Wird nach jeder Iteration als callback(xk) aufgerufen, wobei xk der aktuelle Parametervektor ist.

minimizer_kwargsdict, optional

Zusätzliche Schlüsselwortargumente, die an den Minimierer scipy.optimize.minimize übergeben werden sollen. Einige wichtige Optionen könnten sein:

methodstr: Die Minimierungsmethode. Wenn nicht angegeben, wird eine der Methoden BFGS, L-BFGS-B oder SLSQP gewählt, je nachdem, ob das Problem Nebenbedingungen oder Grenzen aufweist.
argstuple: Zusätzliche Argumente, die an die Zielfunktion (func) und deren Ableitungen (Jacobian, Hesse) übergeben werden.
optionsdict, optional: Beachten Sie, dass die Toleranz standardmäßig als {ftol: 1e-12} angegeben ist.

optionsdict, optional

Ein Wörterbuch mit Solver-Optionen. Viele der für die globale Routine angegebenen Optionen werden auch an die Routine scipy.optimize.minimize übergeben. Die Optionen, die auch an die lokale Routine übergeben werden, sind mit „(L)“ gekennzeichnet.

Abbruchkriterien: Der Algorithmus wird beendet, wenn eines der angegebenen Kriterien erfüllt ist. Der Standardalgorithmus erfordert jedoch keine Angabe.

maxfevint (L): Maximale Anzahl von Funktionsauswertungen im zulässigen Bereich. (Beachten Sie, dass nur Methoden, die diese Option unterstützen, die Routine bei exakt angegebenem Wert beenden. Andernfalls wird das Kriterium nur während einer globalen Iteration beendet).
f_minfloat: Gibt den minimalen Zielfunktionswert an, falls er bekannt ist.
f_tolfloat: Präzisionsziel für den Wert von f im Abbruchkriterium. Beachten Sie, dass die globale Routine auch abbricht, wenn ein Stichprobenpunkt in der globalen Routine innerhalb dieser Toleranz liegt.
maxiterint: Maximale Anzahl durchzuführender Iterationen.
maxevint: Maximale Anzahl von durchzuführenden Stichprobenbewertungen (einschließlich der Suche an nicht zulässigen Punkten).
maxtimefloat: Maximale erlaubte Verarbeitungszeit.
minhgrdint: Minimale Rangdifferenz der Homologiegruppe. Die Homologiegruppe der Zielfunktion wird bei jeder Iteration (ungefähr) berechnet. Der Rang dieser Gruppe steht in eins-zu-eins-Entsprechung zur Anzahl der lokal konvexen Teilgebiete der Zielfunktion (nach ausreichender Stichprobennahme enthält jedes dieser Teilgebiete ein eindeutiges globales Minimum). Wenn die Differenz im hgr zwischen Iterationen für maxhgrd angegebene Iterationen 0 beträgt, wird der Algorithmus beendet.

Kenntnis der Zielfunktion

symmetrylist oder bool

Gibt an, ob die Zielfunktion symmetrische Variablen enthält. Der Suchraum (und damit die Leistung) wird im vollständig symmetrischen Fall um bis zu O(n!) reduziert. Wenn True angegeben wird, werden alle Variablen symmetrisch zur ersten Variablen gesetzt. Standard ist False.

Z.B. f(x) = (x_1 + x_2 + x_3) + (x_4)**2 + (x_5)**2 + (x_6)**2

In dieser Gleichung sind x_2 und x_3 symmetrisch zu x_1, während x_5 und x_6 symmetrisch zu x_4 sind. Dies kann dem Solver wie folgt angegeben werden:

symmetry = [0,  # Variable 1
            0,  # symmetric to variable 1
            0,  # symmetric to variable 1
            3,  # Variable 4
            3,  # symmetric to variable 4
            3,  # symmetric to variable 4
            ]

jacbool oder callable, optional

Jacobian (Gradient) der Zielfunktion. Nur für CG, BFGS, Newton-CG, L-BFGS-B, TNC, SLSQP, dogleg, trust-ncg. Wenn jac ein boolescher Wert ist und True ist, wird angenommen, dass fun den Gradienten zusammen mit der Zielfunktion zurückgibt. Wenn False, wird der Gradient numerisch geschätzt. jac kann auch ein Callable sein, das den Gradienten der Zielfunktion zurückgibt. In diesem Fall muss es die gleichen Argumente wie fun akzeptieren. (Wird automatisch an scipy.optimize.minimize übergeben)

hess, hesspcallable, optional

Hesse-Matrix (Matrix der zweiten Ableitungen) der Zielfunktion oder Hesse-Matrix der Zielfunktion multipliziert mit einem beliebigen Vektor p. Nur für Newton-CG, dogleg, trust-ncg. Nur eine der Optionen hessp oder hess muss angegeben werden. Wenn hess bereitgestellt wird, wird hessp ignoriert. Wenn weder hess noch hessp angegeben wird, wird das Produkt der Hesse-Matrix mittels finiter Differenzen von jac angenähert. hessp muss die Hesse-Matrix multipliziert mit einem beliebigen Vektor berechnen. (Wird automatisch an scipy.optimize.minimize übergeben)

Algorithmus-Einstellungen

minimize_every_iterbool: Wenn True, werden vielversprechende globale Stichprobenpunkte bei jeder Iteration an eine lokale Minimierungsroutine übergeben. Wenn False, wird nur der finale Minimiererpool ausgeführt. Standard ist True.
local_iterint: Wertet nur einige der besten Kandidaten aus dem Minimiererpool bei jeder Iteration aus. Wenn False, werden alle potenziellen Punkte an die lokale Minimierungsroutine übergeben.
infty_constraintsbool: Wenn True, werden alle generierten Stichprobenpunkte, die außerhalb des zulässigen Bereichs liegen, gespeichert und erhalten den Zielfunktionswert inf. Wenn False, werden diese Punkte verworfen. Die Verwendung dieser Funktionalität kann zu einer höheren Leistung in Bezug auf Funktionsauswertungen führen, bevor das globale Minimum gefunden wird. Die Angabe von False verbraucht weniger Speicher, auf Kosten einer leichten Leistungseinbuße. Standard ist True.

Feedback

dispbool (L): Auf True setzen, um Konvergenz-Meldungen auszugeben.

sampling_methodstr oder Funktion, optional

Die derzeit integrierten Stichprobenmethoden sind halton, sobol und simplicial. Die Standardmethode simplicial bietet die theoretische Garantie der Konvergenz zum globalen Minimum in endlicher Zeit. Die Methoden halton und sobol sind schneller in Bezug auf die Generierung von Stichprobenpunkten, allerdings mit dem Verlust der garantierten Konvergenz. Sie eignen sich besser für die meisten „einfacheren“ Probleme, bei denen die Konvergenz relativ schnell erfolgt. Benutzerdefinierte Stichprobenfunktionen müssen zwei Argumente entgegennehmen: n Stichprobenpunkte der Dimension dim pro Aufruf und ein Array von Stichprobenpunkten mit der Form n x dim zurückgeben.

workersint oder Map-ähnliches aufrufbare Objekt, optional

Führt die lokalen seriellen Minimierungen parallel aus. Geben Sie -1 an, um alle verfügbaren CPU-Kerne zu nutzen, oder eine Ganzzahl, um diese Anzahl von Prozessen zu verwenden (verwendet multiprocessing.Pool).

Alternativ kann eine Map-ähnliche aufrufbare Funktion, wie z.B. multiprocessing.Pool.map, für die parallele Auswertung angegeben werden. Diese Auswertung erfolgt als workers(func, iterable). Erfordert, dass func pickelbar ist.

Hinzugefügt in Version 1.11.0.

Rückgabe:

resOptimizeResult: Das Optimierungsergebnis, dargestellt als OptimizeResult-Objekt. Wichtige Attribute sind: x das Lösungsarray, das dem globalen Minimum entspricht, fun der Funktionswert an der globalen Lösung, xl eine geordnete Liste von lokalen Minima-Lösungen, funl der Funktionswert an den entsprechenden lokalen Lösungen, success ein boolesches Flag, das anzeigt, ob der Optimierer erfolgreich beendet wurde, message, das den Grund für die Beendigung beschreibt, nfev die Gesamtzahl der Zielfunktionsauswertungen, einschließlich der Stichprobenaufrufe, nlfev die Gesamtzahl der Zielfunktionsauswertungen, die aus allen lokalen Suchoptimierungen resultieren, nit die Anzahl der von der globalen Routine durchgeführten Iterationen.

Hinweise

Globale Optimierung mittels simplizialer Homologie-Globaloptimierung [1]. Geeignet für die Lösung allgemeiner NLP- und Blackbox-Optimierungsprobleme auf globale Optimalität (niedrigdimensionale Probleme).

Im Allgemeinen sind die Optimierungsprobleme von der Form

minimize f(x) subject to

g_i(x) >= 0,  i = 1,...,m
h_j(x)  = 0,  j = 1,...,p

wobei x ein Vektor aus einer oder mehreren Variablen ist. f(x) ist die Zielfunktion R^n -> R, g_i(x) sind die Ungleichungsnebenbedingungen und h_j(x) sind die Gleichheitsnebenbedingungen.

Optional können die unteren und oberen Grenzen für jedes Element in x auch mit dem Argument bounds angegeben werden.

Obwohl die meisten theoretischen Vorteile von SHGO nur für Lipschitz-glatte Funktionen f(x) bewiesen sind, konvergiert der Algorithmus auch für den allgemeineren Fall, bei dem f(x) nicht-kontinuierlich, nicht-konvex und nicht-glatt ist, nachweislich zum globalen Optimum, wenn die Standard-Stichprobenmethode verwendet wird [1].

Die lokale Suchmethode kann über den Parameter minimizer_kwargs spezifiziert werden, der an scipy.optimize.minimize übergeben wird. Standardmäßig wird die Methode SLSQP verwendet. Im Allgemeinen wird empfohlen, die lokale Minimierung mit SLSQP, COBYLA oder COBYQA zu verwenden, wenn Ungleichungsnebenbedingungen für das Problem definiert sind, da die anderen Methoden keine Nebenbedingungen verwenden.

Die Methoden halton und sobol erzeugen Punkte mittels scipy.stats.qmc. Jede andere QMC-Methode kann verwendet werden.

Referenzen

[1] (1,2)

Endres, SC, Sandrock, C, Focke, WW (2018) „A simplicial homology algorithm for lipschitz optimisation“, Journal of Global Optimization.

[2]

Joe, SW und Kuo, FY (2008) „Constructing Sobol’ sequences with better two-dimensional projections“, SIAM J. Sci. Comput. 30, 2635-2654.

[3] (1,2)

Hock, W und Schittkowski, K (1981) „Test examples for nonlinear programming codes“, Lecture Notes in Economics and Mathematical Systems, 187. Springer-Verlag, New York. http://www.ai7.uni-bayreuth.de/test_problem_coll.pdf

[4]

Wales, DJ (2015) „Perspective: Insight into reaction coordinates and dynamics from the potential energy landscape“, Journal of Chemical Physics, 142(13), 2015.

[5]

https://docs.scipy.de/doc/scipy/tutorial/optimize.html#constrained-minimization-of-multivariate-scalar-functions-minimize

Beispiele

Betrachten wir zunächst das Problem der Minimierung der Rosenbrock-Funktion, rosen

>>> from scipy.optimize import rosen, shgo
>>> bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)]
>>> result = shgo(rosen, bounds)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 2.920392374190081e-18)

Beachten Sie, dass die Grenzen die Dimensionalität der Zielfunktion bestimmen und daher eine erforderliche Eingabe sind. Sie können jedoch leere Grenzen mit None oder Objekten wie np.inf angeben, die in große Gleitkommazahlen umgewandelt werden.

>>> bounds = [(None, None), ]*4
>>> result = shgo(rosen, bounds)
>>> result.x
array([0.99999851, 0.99999704, 0.99999411, 0.9999882 ])

Als Nächstes betrachten wir die Eggholder-Funktion, ein Problem mit mehreren lokalen und einem globalen Minimum. Wir werden die Verwendung von Argumenten und die Fähigkeiten von shgo demonstrieren. (https://en.wikipedia.org/wiki/Test_functions_for_optimization)

>>> import numpy as np
>>> def eggholder(x):
...     return (-(x[1] + 47.0)
...             * np.sin(np.sqrt(abs(x[0]/2.0 + (x[1] + 47.0))))
...             - x[0] * np.sin(np.sqrt(abs(x[0] - (x[1] + 47.0))))
...             )
...
>>> bounds = [(-512, 512), (-512, 512)]

shgo verfügt über integrierte Niedrigdiskrepanz-Stichprobenfolgen. Zuerst geben wir 64 anfängliche Stichprobenpunkte der *Sobol’*-Folge ein.

>>> result = shgo(eggholder, bounds, n=64, sampling_method='sobol')
>>> result.x, result.fun
(array([512.        , 404.23180824]), -959.6406627208397)

shgo gibt auch alle anderen gefundenen lokalen Minima zurück. Diese können aufgerufen werden mit

>>> result.xl
array([[ 512.        ,  404.23180824],
       [ 283.0759062 , -487.12565635],
       [-294.66820039, -462.01964031],
       [-105.87688911,  423.15323845],
       [-242.97926   ,  274.38030925],
       [-506.25823477,    6.3131022 ],
       [-408.71980731, -156.10116949],
       [ 150.23207937,  301.31376595],
       [  91.00920901, -391.283763  ],
       [ 202.89662724, -269.38043241],
       [ 361.66623976, -106.96493868],
       [-219.40612786, -244.06020508]])

>>> result.funl
array([-959.64066272, -718.16745962, -704.80659592, -565.99778097,
       -559.78685655, -557.36868733, -507.87385942, -493.9605115 ,
       -426.48799655, -421.15571437, -419.31194957, -410.98477763])

Diese Ergebnisse sind nützlich in Anwendungen, bei denen viele globale Minima vorhanden sind und die Werte anderer globaler Minima gewünscht werden oder bei denen die lokalen Minima Einblicke in das System geben können (z.B. Morphologien in der physikalischen Chemie [4]).

Wenn wir eine größere Anzahl lokaler Minima finden wollen, können wir die Anzahl der Stichprobenpunkte oder die Anzahl der Iterationen erhöhen. Wir erhöhen die Anzahl der Stichprobenpunkte auf 64 und die Anzahl der Iterationen von der Standardeinstellung 1 auf 3. Mit simplicial hätten wir 64 x 3 = 192 anfängliche Stichprobenpunkte erhalten.

>>> result_2 = shgo(eggholder,
...                 bounds, n=64, iters=3, sampling_method='sobol')
>>> len(result.xl), len(result_2.xl)
(12, 23)

Beachten Sie den Unterschied zwischen z.B. n=192, iters=1 und n=64, iters=3. Im ersten Fall werden die vielversprechenden Punkte im Minimiererpool nur einmal verarbeitet. Im letzteren Fall wird dies alle 64 Stichprobenpunkte für insgesamt 3 Mal verarbeitet.

Um die Lösung von Problemen mit nichtlinearen Nebenbedingungen zu demonstrieren, betrachten wir das folgende Beispiel aus Hock und Schittkowski Problem 73 (cattle-feed) [3]

minimize: f = 24.55 * x_1 + 26.75 * x_2 + 39 * x_3 + 40.50 * x_4

subject to: 2.3 * x_1 + 5.6 * x_2 + 11.1 * x_3 + 1.3 * x_4 - 5    >= 0,

            12 * x_1 + 11.9 * x_2 + 41.8 * x_3 + 52.1 * x_4 - 21
                -1.645 * sqrt(0.28 * x_1**2 + 0.19 * x_2**2 +
                              20.5 * x_3**2 + 0.62 * x_4**2)      >= 0,

            x_1 + x_2 + x_3 + x_4 - 1                             == 0,

            1 >= x_i >= 0 for all i

Die ungefähre Antwort in [3] lautet

f([0.6355216, -0.12e-11, 0.3127019, 0.05177655]) = 29.894378

>>> def f(x):  # (cattle-feed)
...     return 24.55*x[0] + 26.75*x[1] + 39*x[2] + 40.50*x[3]
...
>>> def g1(x):
...     return 2.3*x[0] + 5.6*x[1] + 11.1*x[2] + 1.3*x[3] - 5  # >=0
...
>>> def g2(x):
...     return (12*x[0] + 11.9*x[1] +41.8*x[2] + 52.1*x[3] - 21
...             - 1.645 * np.sqrt(0.28*x[0]**2 + 0.19*x[1]**2
...                             + 20.5*x[2]**2 + 0.62*x[3]**2)
...             ) # >=0
...
>>> def h1(x):
...     return x[0] + x[1] + x[2] + x[3] - 1  # == 0
...
>>> cons = ({'type': 'ineq', 'fun': g1},
...         {'type': 'ineq', 'fun': g2},
...         {'type': 'eq', 'fun': h1})
>>> bounds = [(0, 1.0),]*4
>>> res = shgo(f, bounds, n=150, constraints=cons)
>>> res
 message: Optimization terminated successfully.
 success: True
     fun: 29.894378159142136
    funl: [ 2.989e+01]
       x: [ 6.355e-01  1.137e-13  3.127e-01  5.178e-02] # may vary
      xl: [[ 6.355e-01  1.137e-13  3.127e-01  5.178e-02]] # may vary
     nit: 1
    nfev: 142 # may vary
   nlfev: 35 # may vary
   nljev: 5
   nlhev: 0

>>> g1(res.x), g2(res.x), h1(res.x)
(-5.062616992290714e-14, -2.9594104944408173e-12, 0.0)