SciPy (pronunzjata sai pie) huwa pakkett ta' applikazzjoni matematika bbażat fuq l-estensjoni Numpy Python. B'SciPy, is-sessjoni interattiva tiegħek ta' Python issir l-istess xjenza sħiħa tad-dejta u ambjent ta' prototipi ta' sistema kumplessi bħal MATLAB, IDL, Octave, R-Lab, u SciLab. Illum irrid nitkellem fil-qosor dwar kif tuża xi algoritmi ta 'ottimizzazzjoni magħrufa sew fil-pakkett scipy.optimize. Għajnuna aktar dettaljata u aġġornata dwar l-użu tal-funzjonijiet tista' dejjem tinkiseb billi tuża l-kmand help() jew billi tuża Shift+Tab.
Introduzzjoni
Sabiex issalva lilek innifsek u lill-qarrejja milli jfittxu u jaqraw sorsi primarji, links għal deskrizzjonijiet ta' metodi se jkunu prinċipalment fuq il-Wikipedija. Bħala regola, din l-informazzjoni hija biżżejjed biex tifhem il-metodi f'termini ġenerali u l-kundizzjonijiet għall-applikazzjoni tagħhom. Biex tifhem l-essenza tal-metodi matematiċi, segwi l-links għal pubblikazzjonijiet aktar awtorevoli, li jistgħu jinstabu fl-aħħar ta 'kull artiklu jew fil-magna tat-tiftix favorita tiegħek.
Allura, il-modulu scipy.optimize jinkludi l-implimentazzjoni tal-proċeduri li ġejjin:
- Minimizzazzjoni kondizzjonali u inkondizzjonata ta’ funzjonijiet skalari ta’ diversi varjabbli (minimi) bl-użu ta’ diversi algoritmi (Nelder-Mead simplex, BFGS, gradjenti konjugati Newton, и )
- Ottimizzazzjoni globali (per eżempju: , )
- Minimizzazzjoni tar-residwi (least_squares) u algoritmi ta' twaħħil tal-kurva li jużaw l-inqas kwadri mhux lineari (curve_fit)
- It-tnaqqis tal-funzjonijiet skalari ta' varjabbli waħda (minim_scalar) u t-tfittxija għall-għeruq (root_scalar)
- Solvers multidimensjonali ta’ sistema ta’ ekwazzjonijiet (għerq) li jużaw diversi algoritmi (Powell ibridu, jew metodi fuq skala kbira bħal ).
F'dan l-artikolu se nikkunsidraw biss l-ewwel oġġett minn din il-lista kollha.
Minimizzazzjoni inkondizzjonata ta 'funzjoni skalari ta' diversi varjabbli
Il-funzjoni minimi mill-pakkett scipy.optimize tipprovdi interface ġenerali biex issolvi problemi ta 'minimizzazzjoni kondizzjonali u inkondizzjonali ta' funzjonijiet skalari ta 'diversi varjabbli. Biex nuru kif taħdem, ser ikollna bżonn funzjoni xierqa ta 'diversi varjabbli, li aħna se nimminimizzaw b'modi differenti.
Għal dawn l-għanijiet, il-funzjoni Rosenbrock ta 'N varjabbli hija perfetta, li għandha l-forma:
Minkejja l-fatt li l-funzjoni Rosenbrock u l-matriċi Jacobi u Hessian tagħha (l-ewwel u t-tieni derivattivi, rispettivament) huma diġà definiti fil-pakkett scipy.optimize, aħna se niddefinixxuha nfusna.
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)Għaċ-ċarezza, ejja niġbdu fi 3D il-valuri tal-funzjoni Rosenbrock ta 'żewġ varjabbli.
Kodiċi tat-tpinġija
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()
Jafu minn qabel li l-minimu huwa 0 at , ejja nħarsu lejn eżempji ta 'kif tiddetermina l-valur minimu tal-funzjoni Rosenbrock billi tuża diversi proċeduri scipy.optimize.
Metodu Nelder-Mead simplex
Ħalli jkun hemm punt inizjali x0 fl-ispazju 5-dimensjonali. Ejja nsibu l-punt minimu tal-funzjoni Rosenbrock l-eqreb lejha billi tuża l-algoritmu (l-algoritmu huwa speċifikat bħala l-valur tal-parametru tal-metodu):
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.]Il-metodu simplex huwa l-aktar mod sempliċi biex timminimizza funzjoni definita b'mod espliċitu u pjuttost bla xkiel. Ma teħtieġx il-kalkolu tad-derivattivi ta 'funzjoni; huwa biżżejjed li jiġu speċifikati biss il-valuri tagħha. Il-metodu Nelder-Mead huwa għażla tajba għal problemi ta 'minimizzazzjoni sempliċi. Madankollu, peress li ma jużax estimi tal-gradjent, jista 'jieħu aktar żmien biex jinstab il-minimu.
Metodu Powell
Algoritmu ieħor ta 'ottimizzazzjoni li fih huma kkalkulati biss il-valuri tal-funzjoni huwa . Biex tużah, trid tissettja method = 'powell' fil-funzjoni minimi.
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.]Algoritmu Broyden-Fletcher-Goldfarb-Shanno (BFGS).
Biex tikseb konverġenza aktar mgħaġġla għal soluzzjoni, il-proċedura juża l-gradjent tal-funzjoni oġġettiva. Il-gradjent jista 'jiġi speċifikat bħala funzjoni jew ikkalkulat bl-użu ta' differenzi tal-ewwel ordni. Fi kwalunkwe każ, il-metodu BFGS tipikament jeħtieġ inqas sejħiet ta 'funzjoni mill-metodu simplex.
Ejja nsibu d-derivattiva tal-funzjoni Rosenbrock f'forma analitika:
Din l-espressjoni hija valida għad-derivattivi tal-varjabbli kollha minbarra l-ewwel u l-aħħar, li huma definiti bħala:
Ejja nħarsu lejn il-funzjoni Python li tikkalkula dan il-gradjent:
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 derIl-funzjoni tal-kalkolu tal-gradjent hija speċifikata bħala l-valur tal-parametru jac tal-funzjoni minimi, kif muri hawn taħt.
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]Algoritmu tal-gradjent konjugat (Newton)
Algoritmu huwa metodu ta' Newton modifikat.
Il-metodu ta' Newton huwa bbażat fuq approssimazzjoni ta' funzjoni f'żona lokali b'polinomju tat-tieni grad:
fejn hija l-matriċi tat-tieni derivattivi (Matriċi Hessian, Hessian).
Jekk il-Hessian huwa definit pożittiv, allura l-minimu lokali ta 'din il-funzjoni jista' jinstab billi l-gradjent żero tal-forma kwadratika tiġi ekwiparata għal żero. Ir-riżultat se jkun l-espressjoni:
Il-Hessian invers huwa kkalkulat bl-użu tal-metodu tal-gradjent konjugat. Eżempju ta 'użu ta' dan il-metodu biex jimminimizza l-funzjoni Rosenbrock huwa mogħti hawn taħt. Biex tuża l-metodu Newton-CG, trid tispeċifika funzjoni li tikkalkula l-Hessian.
Il-Hessian tal-funzjoni Rosenbrock f'forma analitika hija ugwali għal:
fejn и , iddefinixxi l-matriċi .
L-elementi mhux żero li fadal tal-matriċi huma ugwali għal:
Per eżempju, fi spazju ta 'ħames dimensjonijiet N = 5, il-matriċi Hessian għall-funzjoni Rosenbrock għandha l-forma ta' faxxa:
Kodiċi li jikkalkula dan il-Hessian flimkien mal-kodiċi biex tiġi minimizzata l-funzjoni Rosenbrock billi tuża l-metodu tal-gradjent konjugat (Newton):
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]Eżempju bid-definizzjoni tal-funzjoni tal-prodott tal-Hessian u vettur arbitrarju
Fi problemi tad-dinja reali, il-kompjuters u l-ħażna tal-matriċi Hessian kollha jistgħu jeħtieġu ħin sinifikanti u riżorsi tal-memorja. F'dan il-każ, fil-fatt m'hemm l-ebda ħtieġa li tispeċifika l-matriċi Hessian innifsu, għaliex il-proċedura ta 'minimizzazzjoni teħtieġ biss vettur ugwali għall-prodott tal-Hessian ma' vettur arbitrarju ieħor. Għalhekk, mil-lat komputazzjonali, huwa ferm preferibbli li tiddefinixxi immedjatament funzjoni li tirritorna r-riżultat tal-prodott tal-Hessian b'vettur arbitrarju.
Ikkunsidra l-funzjoni hess, li tieħu l-vettur ta 'minimizzazzjoni bħala l-ewwel argument, u vettur arbitrarju bħala t-tieni argument (flimkien ma' argumenti oħra tal-funzjoni li għandha tiġi minimizzata). Fil-każ tagħna, il-kalkolu tal-prodott tal-Hessian tal-funzjoni Rosenbrock b'vettur arbitrarju mhuwiex diffiċli ħafna. Jekk p huwa vettur arbitrarju, allura l-prodott qisu:
Il-funzjoni li tikkalkula l-prodott tal-Hessian u vettur arbitrarju hija mgħoddija bħala l-valur tal-argument hessp għall-funzjoni minimize:
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: 66Konjuga l-algoritmu tar-reġjun tal-fiduċja tal-gradjent (Newton)
Kundizzjonament ħażin tal-matriċi Hessian u direzzjonijiet ta 'tfittxija mhux korretti jistgħu jikkawżaw li l-algoritmu tal-gradjent konjugat ta' Newton ikun ineffettiv. F'każijiet bħal dawn, tingħata preferenza lil (trust-region) konjugati gradjenti Newton.
Eżempju bid-definizzjoni tal-matriċi Hessian:
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.]Eżempju bil-funzjoni tal-prodott tal-Hessian u vettur arbitrarju:
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.]Metodi tat-tip Krylov
Bħall-metodu trust-ncg, il-metodi tat-tip Krylov huma adattati sew biex isolvu problemi fuq skala kbira minħabba li jużaw biss prodotti ta 'matriċi-vettur. L-essenza tagħhom hija li jsolvu problema f'reġjun ta 'fiduċja limitat minn subspazju Krylov maqtugħ. Għal problemi inċerti, huwa aħjar li tuża dan il-metodu, peress li juża numru iżgħar ta 'iterazzjonijiet mhux lineari minħabba n-numru iżgħar ta' prodotti tal-matriċi-vettur għal kull sottoproblema, meta mqabbel mal-metodu trust-ncg. Barra minn hekk, is-soluzzjoni għas-subproblema kwadratika tinstab b'mod aktar preċiż milli tuża l-metodu trust-ncg.
Eżempju bid-definizzjoni tal-matriċi Hessian:
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.]
Eżempju bil-funzjoni tal-prodott tal-Hessian u vettur arbitrarju:
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.]
Algoritmu għal soluzzjoni approssimattiva fir-reġjun ta' kunfidenza
Il-metodi kollha (Newton-CG, trust-ncg u trust-krylov) huma adattati sew biex isolvu problemi fuq skala kbira (b'eluf ta 'varjabbli). Dan huwa dovut għall-fatt li l-algoritmu tal-gradjent konjugat sottostanti jimplika determinazzjoni approssimattiva tal-matriċi Hessian inversa. Is-soluzzjoni tinstab b'mod iterattiv, mingħajr espansjoni espliċita tal-Hessian. Peress li għandek bżonn biss tiddefinixxi funzjoni għall-prodott ta 'Hessian u vettur arbitrarju, dan l-algoritmu huwa speċjalment tajjeb biex taħdem ma' matriċi skarsa (djagonali tal-medda). Dan jipprovdi spejjeż ta 'memorja baxxi u iffrankar ta' ħin sinifikanti.
Għal problemi ta 'daqs medju, l-ispiża tal-ħażna u l-fatturar tal-Hessian mhix kritika. Dan ifisser li huwa possibbli li tinkiseb soluzzjoni f'inqas iterazzjonijiet, issolvi s-subproblemi tar-reġjun tal-fiduċja kważi eżattament. Biex tagħmel dan, xi ekwazzjonijiet mhux lineari jiġu solvuti b'mod iterattiv għal kull subproblema kwadratika. Soluzzjoni bħal din ġeneralment teħtieġ 3 jew 4 dekompożizzjonijiet Cholesky tal-matriċi Hessian. Bħala riżultat, il-metodu jikkonverġi f'inqas iterazzjonijiet u jeħtieġ inqas kalkoli ta 'funzjoni oġġettiva minn metodi oħra implimentati tar-reġjun ta' kunfidenza. Dan l-algoritmu jinvolvi biss id-determinazzjoni tal-matriċi Hessian kompluta u ma jappoġġjax l-abbiltà li tuża l-funzjoni tal-prodott tal-Hessian u vettur arbitrarju.
Eżempju bil-minimizzazzjoni tal-funzjoni Rosenbrock:
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.])Probabbilment nieqfu hemm. Fl-artiklu li jmiss ser nipprova ngħid l-aktar affarijiet interessanti dwar il-minimizzazzjoni kondizzjonali, l-applikazzjoni tal-minimizzazzjoni fis-soluzzjoni ta’ problemi ta’ approssimazzjoni, timminimizza funzjoni ta’ varjabbli wieħed, minimizers arbitrarji, u nsib l-għeruq ta’ sistema ta’ ekwazzjonijiet bl-użu ta’ scipy.optimize pakkett.
Sors:
Sors: www.habr.com