SciPy (útsprutsen sai pie) is in wiskundich applikaasjepakket basearre op de Numpy Python-útwreiding. Mei SciPy wurdt jo ynteraktive Python-sesje deselde folsleine gegevenswittenskip en komplekse systeemprototyping-omjouwing as MATLAB, IDL, Octave, R-Lab, en SciLab. Hjoed wol ik koart prate oer hoe't jo guon bekende optimisaasjealgoritmen brûke yn it pakket scipy.optimize. Mear detaillearre en aktualisearre help by it brûken fan funksjes kin altyd wurde krigen mei help fan it kommando help() of mei Shift+Tab.
Ynlieding
Om josels en lêzers te besparjen fan it sykjen en lêzen fan primêre boarnen, sille keppelings nei beskriuwingen fan metoaden benammen op Wikipedia stean. As regel is dizze ynformaasje genôch om de metoaden yn algemiene betingsten en de betingsten foar har tapassing te begripen. Om de essinsje fan wiskundige metoaden te begripen, folgje de keppelings nei mear autoritative publikaasjes, dy't kinne fûn wurde oan 'e ein fan elk artikel of yn jo favorite sykmasine.
Dat, de scipy.optimize-module omfettet de ymplemintaasje fan 'e folgjende prosedueres:
- Betingst en sûnder betingst minimalisearjen fan skalêre funksjes fan ferskate fariabelen (minimum) mei ferskate algoritmen (Nelder-Mead simplex, BFGS, Newton konjugearre gradients, и )
- Globale optimisaasje (bygelyks: , )
- Minimalisearjen fan oerbliuwsels (minste_kwadraten) en kromme-passende algoritmen mei net-lineêre minste kwadraten (curve_fit)
- Minimalisearjen fan skalêre funksjes fan ien fariabele (minim_scalar) en sykjen nei woartels (root_scalar)
- Multidimensionale oplossers fan systeem fan fergelikingen (root) mei ferskate algoritmen (hybride Powell, of grutskalige metoaden lykas ).
Yn dit artikel sille wy allinich it earste item fan dizze heule list beskôgje.
Betingstleaze minimearring fan in skalêre funksje fan ferskate fariabelen
De minimfunksje fan it scipy.optimize-pakket biedt in algemiene ynterface foar it oplossen fan betingsten en sûnder betingsten minimisaasjeproblemen fan skalêre funksjes fan ferskate fariabelen. Om te demonstrearjen hoe't it wurket, sille wy in gaadlike funksje fan ferskate fariabelen nedich hawwe, dy't wy op ferskate manieren sille minimalisearje.
Foar dizze doelen is de Rosenbrock-funksje fan N fariabelen perfekt, dy't de foarm hat:
Nettsjinsteande it feit dat de Rosenbrock-funksje en syn Jacobi- en Hessyske matriksen (de earste en twadde derivatives, respektivelik) al definieare binne yn it pakket scipy.optimize, sille wy it sels definiearje.
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)Lit ús foar dúdlikens de wearden fan 'e Rosenbrock-funksje fan twa fariabelen yn 3D tekenje.
Drawing koade
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()
Witte fan tefoaren dat it minimum is 0 at , litte wy nei foarbylden sjen hoe't jo de minimale wearde fan 'e Rosenbrock-funksje kinne bepale mei ferskate scipy.optimize-prosedueres.
Nelder-Mead simplex metoade
Lit der in begjinpunt x0 wêze yn 5-diminsjonale romte. Litte wy it minimale punt fan 'e Rosenbrock-funksje it tichtstby fine mei it algoritme (it algoritme wurdt oantsjutte as de wearde fan de metoade parameter):
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.]De simpleksmetoade is de ienfâldichste manier om in eksplisyt definieare en frij glêde funksje te minimalisearjen. It is net nedich om de derivatives fan in funksje te berekkenjen; it is genôch om allinich de wearden op te jaan. De Nelder-Mead metoade is in goede kar foar ienfâldige minimization problemen. Om't it lykwols gjin gradientskattingen brûkt, kin it langer duorje om it minimum te finen.
Powell metoade
In oar optimalisaasjealgoritme wêryn allinich de funksjewearden wurde berekkene is . Om it te brûken, moatte jo metoade = 'powell' ynstelle yn 'e minimfunksje.
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) algoritme
Om te krijen flugger konverginsje nei in oplossing, de proseduere brûkt de gradient fan 'e objektive funksje. De gradient kin wurde oantsjutte as in funksje of berekkene mei earste-order ferskillen. Yn alle gefallen fereasket de BFGS-metoade typysk minder funksjeoproppen dan de simplexmetoade.
Litte wy de derivative fan 'e Rosenbrock-funksje yn analytyske foarm fine:
Dizze útdrukking is jildich foar de derivatives fan alle fariabelen útsein de earste en lêste, dy't definiearre binne as:
Litte wy nei de Python-funksje sjen dy't dizze gradient berekkent:
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 derDe gradient berekkening funksje wurdt oantsjutte as de wearde fan de jac parameter fan de minim funksje, lykas werjûn hjirûnder.
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]Conjugate gradient algoritme (Newton)
Algoritme is in wizige Newton's metoade.
Newton's metoade is basearre op it benaderjen fan in funksje yn in lokaal gebiet troch in polynomium fan 'e twadde graad:
wêr is de matrix fan twadde derivatives (Hessian matrix, Hessian).
As de Hessian posityf definityf is, dan kin it lokale minimum fan dizze funksje fûn wurde troch de nulgradient fan 'e kwadratyske foarm lyk te meitsjen oan nul. It resultaat sil de útdrukking wêze:
De omkearde Hessian wurdt berekkene mei de konjugearre gradientmetoade. In foarbyld fan it brûken fan dizze metoade om de Rosenbrock-funksje te minimalisearjen wurdt hjirûnder jûn. Om de Newton-CG-metoade te brûken, moatte jo in funksje opjaan dy't de Hessian berekkenet.
De Hessian fan 'e Rosenbrock-funksje yn analytyske foarm is gelyk oan:
wêr и , definiearje de matrix .
De oerbleaune net-nul eleminten fan 'e matrix binne gelyk oan:
Bygelyks, yn in fiifdiminsjonale romte N = 5, hat de Hessyske matrix foar de Rosenbrock-funksje de foarm fan in band:
Koade dy't dizze Hessian berekkenet tegearre mei koade foar it minimalisearjen fan de Rosenbrock-funksje mei de konjugaasjegradient (Newton) metoade:
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]In foarbyld mei de definysje fan 'e produktfunksje fan' e Hessian en in willekeurige vector
Yn echte wrâldproblemen kin it berekkenjen en opslaan fan 'e heule Hessyske matrix wichtige tiid en ûnthâldboarnen fereaskje. Yn dit gefal is it eins net nedich om de Hessyske matrix sels oan te jaan, om't de minimization proseduere fereasket allinnich in fektor gelyk oan it produkt fan de Hessian mei in oare willekeurige vector. Sa, út in berekkening eachpunt, is it folle de foarkar om fuortendaliks definiearje in funksje dy't jout it resultaat fan it produkt fan 'e Hessian mei in willekeurige fektor.
Beskôgje de hessfunksje, dy't de minimisaasjevektor nimt as it earste argumint, en in willekeurige fektor as it twadde argumint (tegearre mei oare arguminten fan 'e funksje dy't minimaal wurde moat). Yn ús gefal is it berekkenjen fan it produkt fan 'e Hessian fan' e Rosenbrock-funksje mei in willekeurige fektor net heul lestich. As p is in willekeurige vector, dan it produkt liket op:
De funksje dy't it produkt fan 'e Hessian en in willekeurige fektor berekkenet wurdt trochjûn as de wearde fan it hessp-argumint nei de minimalisearjende funksje:
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: 66Conjugate gradient trust region algoritme (Newton)
Slechte kondysje fan 'e Hessyske matrix en ferkearde sykrjochtings kinne feroarsaakje dat Newton's konjugearre gradientalgoritme net effektyf is. Yn sokke gefallen wurdt foarkar jûn oan (fertrouwen-regio) konjugearje Newton-gradiënten.
Foarbyld mei de definysje fan 'e Hessyske matrix:
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.]Foarbyld mei de produktfunksje fan 'e Hessian en in willekeurige fektor:
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 type metoaden
Lykas de trust-ncg-metoade binne metoaden fan Krylov-type goed geskikt foar it oplossen fan grutskalige problemen, om't se allinich matrix-vektorprodukten brûke. Harren essinsje is in oplosse in probleem yn in fertrouwen regio beheind troch in ôfkoarte Krylov subspace. Foar ûnwisse problemen is it better om dizze metoade te brûken, om't it in lytser oantal net-lineêre iteraasjes brûkt troch it lytsere oantal matrix-vektorprodukten per subprobleem, yn ferliking mei de trust-ncg-metoade. Derneist wurdt de oplossing foar it kwadratyske subprobleem krekter fûn as it brûken fan de trust-ncg-metoade.
Foarbyld mei de definysje fan 'e Hessyske matrix:
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.]
Foarbyld mei de produktfunksje fan 'e Hessian en in willekeurige fektor:
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.]
Algoritme foar benadere oplossing yn it fertrouwen regio
Alle metoaden (Newton-CG, trust-ncg en trust-krylov) binne goed geskikt foar it oplossen fan grutskalige problemen (mei tûzenen fariabelen). Dit komt troch it feit dat it ûnderlizzende konjugearre gradientalgoritme in ûngefear fêststelling fan 'e omkearde Hessyske matrix ymplisearret. De oplossing wurdt iteratyf fûn, sûnder eksplisite útwreiding fan it Hessian. Om't jo allinich in funksje moatte definiearje foar it produkt fan in Hessian en in willekeurige vector, is dit algoritme benammen goed foar it wurkjen mei sparse (band diagonale) matriksen. Dit soarget foar lege ûnthâldkosten en signifikante tiidbesparring.
Foar middelgrutte problemen binne de kosten foar it bewarjen en faktorearjen fan 'e Hessian net kritysk. Dit betsjut dat it mooglik is om in oplossing te krijen yn minder iteraasjes, wêrtroch't de subproblemen fan 'e trustregio hast krekt oplost. Om dit te dwaan, wurde guon net-lineêre fergelikingen iteratyf oplost foar elk kwadratyske subprobleem. Sa'n oplossing fereasket meastentiids 3 of 4 Cholesky decompositions fan de Hessyske matrix. As gefolch, de metoade konvergeart yn minder iteraasjes en fereasket minder objektive funksje berekkeningen as oare ymplemintearre metoaden fan fertrouwen regio. Dit algoritme omfettet allinich it bepalen fan 'e folsleine Hessyske matrix en stipet net de mooglikheid om it produktfunksje fan' e Hessian en in willekeurige vector te brûken.
Foarbyld mei minimalisearjen fan de Rosenbrock-funksje:
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.])Wy sille dêr wierskynlik ophâlde. Yn it folgjende artikel sil ik besykje de meast nijsgjirrige dingen te fertellen oer betingst minimearring, de tapassing fan minimisaasje by it oplossen fan approximaasjeproblemen, minimalisearjen fan in funksje fan ien fariabele, willekeurige minimizers, en it finen fan de woartels fan in systeem fan fergelikingen mei de scipy.optimize pakket.
Boarne:
Boarne: www.habr.com