A SciPy (ejtsd: sai pie) egy matematikai alkalmazáscsomag, amely a Numpy Python kiterjesztésen alapul. A SciPy segítségével az interaktív Python-munkamenet ugyanolyan teljes adattudományi és komplex rendszerprototípus-készítő környezetté válik, mint a MATLAB, az IDL, az Octave, az R-Lab és a SciLab. Ma arról szeretnék röviden beszélni, hogyan használhatunk néhány jól ismert optimalizálási algoritmust a scipy.optimize csomagban. A függvények használatához részletesebb és naprakész súgó mindig a help() paranccsal vagy a Shift+Tab billentyűkombinációval érhető el.
Bevezetés
Annak érdekében, hogy megkímélje magát és olvasóit az elsődleges források keresésétől és olvasásától, a módszerek leírására mutató hivatkozások főként a Wikipédián lesznek. Általában ez az információ elegendő a módszerek általános megértéséhez és alkalmazásuk feltételeinek megértéséhez. A matematikai módszerek lényegének megértéséhez kövesse a hitelesebb publikációkra mutató hivatkozásokat, amelyek az egyes cikkek végén vagy kedvenc keresőjében találhatók.
Tehát a scipy.optimize modul a következő eljárások végrehajtását tartalmazza:
- Több változó skaláris függvényeinek feltételes és feltétel nélküli minimalizálása (minimum) különféle algoritmusok segítségével (Nelder-Mead szimplex, BFGS, Newton konjugált gradiensek, и )
- Globális optimalizálás (például: , )
- A maradékanyagok minimalizálása (legkisebb_négyzetek) és görbeillesztő algoritmusok nemlineáris legkisebb négyzetek használatával (curve_fit)
- Egy változó skaláris függvényeinek minimalizálása (minim_scalar) és gyökérkeresés (root_scalar)
- Egyenletrendszer (gyök) többdimenziós megoldói különféle algoritmusok segítségével (hibrid Powell, vagy nagy léptékű módszerek, mint pl ).
Ebben a cikkben csak az első elemet vesszük figyelembe a teljes listából.
Több változó skalárfüggvényének feltétel nélküli minimalizálása
A scipy.optimize csomagból származó minim függvény általános felületet biztosít több változó skalárfüggvényeinek feltételes és feltétel nélküli minimalizálási problémáinak megoldására. Működésének bemutatásához több változó megfelelő függvényére lesz szükségünk, amelyeket különböző módokon minimalizálunk.
Erre a célra tökéletes az N változó Rosenbrock-függvénye, amelynek alakja:
Annak ellenére, hogy a Rosenbrock-függvény és Jacobi- és Hess-mátrixai (az első és második derivált) már definiáltak a scipy.optimize csomagban, mi magunk fogjuk meghatározni.
import numpy as np
def rosen(x):
"""The Rosenbrock function"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Az érthetőség kedvéért rajzoljuk meg 3D-ben két változó Rosenbrock-függvényének értékeit.
Rajzkód
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Настраиваем 3D график
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Задаем угол обзора
ax.view_init(45, 30)
# Создаем данные для графика
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))
# Рисуем поверхность
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Előre tudva, hogy a minimum 0 at , nézzünk példákat a Rosenbrock függvény minimális értékének meghatározására különböző scipy.optimize eljárások segítségével.
Nelder-Mead szimplex módszer
Legyen egy x0 kezdőpont az 5-dimenziós térben. Keressük meg az algoritmus segítségével a Rosenbrock függvény hozzá legközelebb eső minimumpontját (az algoritmus a metódusparaméter értékeként van megadva):
from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 339
Function evaluations: 571
[1. 1. 1. 1. 1.]A szimplex módszer a legegyszerűbb módja egy kifejezetten meghatározott és meglehetősen sima függvény minimalizálásának. Nem igényli a függvény deriváltjainak kiszámítását, elég csak az értékeit megadni. A Nelder-Mead módszer jó választás egyszerű minimalizálási problémák esetén. Mivel azonban nem használ gradiens becsléseket, hosszabb ideig tarthat a minimum megtalálása.
Powell módszer
Egy másik optimalizálási algoritmus, amelyben csak a függvényértékek kerülnek kiszámításra . Használatához a method = 'powell' értéket kell beállítani a minimum függvényben.
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) algoritmus
A megoldáshoz való gyorsabb konvergencia elérése érdekében az eljárás a célfüggvény gradiensét használja. A gradiens megadható függvényként vagy kiszámítható elsőrendű különbségek segítségével. Mindenesetre a BFGS metódus jellemzően kevesebb függvényhívást igényel, mint a szimplex metódus.
Keressük meg a Rosenbrock-függvény deriváltját analitikus formában:
Ez a kifejezés az összes változó származékára érvényes, kivéve az első és az utolsó változót, amelyek meghatározása a következő:
Nézzük meg a Python függvényt, amely ezt a gradienst számítja ki:
def rosen_der (x):
xm = x [1: -1]
xm_m1 = x [: - 2]
xm_p1 = x [2:]
der = np.zeros_like (x)
der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
der [-1] = 200 * (x [-1] -x [-2] ** 2)
return derA gradiens számítási függvény a minimum függvény jac paraméterének értékeként van megadva, az alábbiak szerint.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 25
Function evaluations: 30
Gradient evaluations: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Konjugált gradiens algoritmus (Newton)
Algoritmus egy módosított Newton-módszer.
A Newton-módszer azon alapul, hogy egy lokális területen lévő függvényt egy másodfokú polinommal közelítenek:
ahol a második deriváltok mátrixa (Hess-mátrix, Hessian).
Ha a Hess-féle pozitív definit, akkor ennek a függvénynek a lokális minimumát úgy találhatjuk meg, hogy a másodfokú forma nulla gradiensét nullával egyenlővé tesszük. Az eredmény a következő kifejezés lesz:
Az inverz Hessian kiszámítása a konjugált gradiens módszerrel történik. Az alábbiakban egy példa látható ennek a módszernek a használatára a Rosenbrock függvény minimalizálására. A Newton-CG módszer használatához meg kell adnia egy függvényt, amely kiszámítja a Hess-t.
A Rosenbrock-függvény Hess-függvénye analitikus formában egyenlő:
ahol и , határozza meg a mátrixot .
A mátrix többi nem nulla eleme egyenlő:
Például egy N = 5 ötdimenziós térben a Rosenbrock-függvény Hess-mátrixa sáv alakú:
Kód, amely kiszámítja ezt a Hess-t, valamint a Rosenbrock-függvény minimalizálását a konjugált gradiens (Newton) módszerrel:
def rosen_hess(x):
x = np.asarray(x)
H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
diagonal = np.zeros_like(x)
diagonal[0] = 1200*x[0]**2-400*x[1]+2
diagonal[-1] = 200
diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
H = H + np.diag(diagonal)
return H
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hess=rosen_hess,
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 24
[1. 1. 1. 0.99999999 0.99999999]Példa a Hess-féle és egy tetszőleges vektor szorzatfüggvényének meghatározására
Valós problémák esetén a teljes hesseni mátrix kiszámítása és tárolása jelentős idő- és memóriaerőforrást igényelhet. Ebben az esetben tulajdonképpen nem szükséges magát a hesseni mátrixot megadni, mert a minimalizálási eljáráshoz csak egy vektorra van szükség, amely megegyezik a Hess-féle és egy másik tetszőleges vektor szorzatával. Így számítási szempontból sokkal előnyösebb, ha azonnal definiálunk egy függvényt, amely a Hess-féle szorzat eredményét adja vissza egy tetszőleges vektorral.
Tekintsük a Hess függvényt, amely a minimalizálási vektort veszi első argumentumnak, és egy tetszőleges vektort a második argumentumnak (a minimalizálandó függvény egyéb argumentumaival együtt). Esetünkben a Rosenbrock-függvény Hess-féle szorzatának kiszámítása tetszőleges vektorral nem túl nehéz. Ha p egy tetszőleges vektor, akkor a szorzat úgy néz ki, mint a:
A Hess-féle és egy tetszőleges vektor szorzatát kiszámító függvény a hessp argumentum értékeként kerül átadásra a minimalizáló függvénynek:
def rosen_hess_p(x, p):
x = np.asarray(x)
Hp = np.zeros_like(x)
Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1]
-400*x[1:-1]*p[2:]
Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
return Hp
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hessp=rosen_hess_p,
options={'xtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 66Konjugált gradiens megbízhatósági régió algoritmus (Newton)
A Hess-mátrix rossz kondicionálása és a helytelen keresési irányok a Newton-féle konjugált gradiens algoritmus hatástalanságát okozhatják. Ilyen esetekben előnyben részesítik (bizalom-régió) konjugált Newton gradiensek.
Példa a Hess-mátrix definíciójával:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 19
[1. 1. 1. 1. 1.]Példa a Hess-féle szorzatfüggvényre és egy tetszőleges vektorra:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 0
[1. 1. 1. 1. 1.]Krylov típusú módszerek
A bizalom-ncg módszerhez hasonlóan a Krylov-típusú módszerek is kiválóan alkalmasak nagy léptékű problémák megoldására, mivel csak mátrix-vektor szorzatokat használnak. A lényegük egy probléma megoldása egy olyan bizalmi régióban, amelyet egy csonka Krilov-altér korlátoz. Bizonytalan problémák esetén célszerűbb ezt a módszert használni, mivel kisebb számú nemlineáris iterációt használ a részproblémánkénti mátrix-vektor szorzatok kisebb száma miatt, mint a bizalom-ncg módszer. Ezenkívül a kvadratikus részprobléma megoldása pontosabban megtalálható, mint a bizalom-ncg módszer használata.
Példa a Hess-mátrix definíciójával:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 18
print(res.x)
[1. 1. 1. 1. 1.]
Példa a Hess-féle szorzatfüggvényre és egy tetszőleges vektorra:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algoritmus közelítő megoldáshoz a megbízhatósági tartományban
Valamennyi módszer (Newton-CG, trust-ncg és trust-krylov) kiválóan alkalmas nagy léptékű (több ezer változós) problémák megoldására. Ez annak a ténynek köszönhető, hogy az alapul szolgáló konjugált gradiens algoritmus az inverz Hess-mátrix hozzávetőleges meghatározását foglalja magában. A megoldást iteratív módon találjuk meg, a Hessian kifejezett kiterjesztése nélkül. Mivel csak egy Hess-vektor és egy tetszőleges vektor szorzatára kell függvényt definiálni, ez az algoritmus különösen jó ritka (sávátlós) mátrixokkal való munkához. Ez alacsony memóriaköltséget és jelentős időmegtakarítást biztosít.
Közepes méretű problémák esetén a Hessian tárolási és faktorálási költsége nem kritikus. Ez azt jelenti, hogy kevesebb iterációval lehet megoldást kapni, szinte pontosan megoldva a bizalmi régió részproblémáit. Ennek érdekében néhány nemlineáris egyenletet iteratív módon oldunk meg minden másodfokú részfeladatra. Egy ilyen megoldás általában a Hess-mátrix 3 vagy 4 Cholesky-féle dekompozícióját igényli. Ennek eredményeként a módszer kevesebb iterációban konvergál, és kevesebb célfüggvény számítást igényel, mint a többi megvalósított konfidenciarégió módszer. Ez az algoritmus csak a teljes Hess-mátrix meghatározását tartalmazza, és nem támogatja a Hess-féle és tetszőleges vektor szorzatfüggvényének használatát.
Példa a Rosenbrock függvény minimalizálására:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization terminated successfully.
Current function value: 0.000000
Iterations: 13
Function evaluations: 14
Gradient evaluations: 13
Hessian evaluations: 14
array([1., 1., 1., 1., 1.])Valószínűleg itt megállunk. A következő cikkben megpróbálom elmondani a legérdekesebb dolgokat a feltételes minimalizálásról, a minimalizálás alkalmazásáról közelítési feladatok megoldásában, egy változó függvényének minimalizálásáról, tetszőleges minimalizálókról, valamint egy egyenletrendszer gyökereinek megtalálásáról a scipy.optimize segítségével. csomag.
Forrás:
Forrás: will.com