ProHoster > Blog > Interneteko albisteak > SciPy, optimizazioa

SciPy, optimizazioa

SciPy, optimizazioa

SciPy (sai pie ahoskatua) Numpy Python luzapenean oinarritutako aplikazio matematikoen paketea da. SciPy-rekin, zure Python saio interaktiboa MATLAB, IDL, Octave, R-Lab eta SciLab bezalako datu-zientzia eta sistema konplexuen prototipo-ingurune berdina bihurtzen da. Gaur scipy.optimize paketean optimizazio algoritmo ezagun batzuk nola erabili laburki hitz egin nahi dut. Funtzioak erabiltzeko laguntza zehatzagoa eta eguneratuagoa beti lor daiteke help() komandoa erabiliz edo Shift+Tab erabiliz.

Sarrera

Zure burua eta irakurleak lehen mailako iturriak bilatu eta irakurtzetik salbatzeko, metodoen deskribapenetarako estekak Wikipedian egongo dira batez ere. Oro har, informazio hori nahikoa da metodoak baldintza orokorretan eta horiek aplikatzeko baldintzak ulertzeko. Metodo matematikoen funtsa ulertzeko, jarraitu argitalpen autoritarioen estekak, artikulu bakoitzaren amaieran edo zure gogoko bilatzailean aurki daitezkeenak.

Beraz, scipy.optimize moduluak honako prozedura hauek ezartzea barne hartzen du:

  1. Hainbat aldagairen (gutxieneko) funtzio eskalarren baldintzapeko eta baldintzarik gabeko minimizazioa hainbat algoritmo erabiliz (Nelder-Mead simplex, BFGS, Newton konjugate gradienteak, COBYLA ΠΈ SLSQP)
  2. Optimizazio globala (adibidez: arroa-jotzea, bilakaera_diferentzia)
  3. Hondakinak gutxitzea MNC (karratu_txikienak) eta kurba egokitzeko algoritmoak karratu minimo ez-linealak erabiliz (curve_fit)
  4. Aldagai baten funtzio eskalarrak minimizatzea (minim_scalar) eta erroak bilatzea (root_scalar)
  5. Ekuazio-sistemen dimentsio anitzeko solutzaileak (erroa) hainbat algoritmo erabiliz (Powell hibridoa, Levenberg-Marquardt edo eskala handiko metodoak, esaterako Newton-Krylov).

Artikulu honetan zerrenda osoko lehen elementua bakarrik hartuko dugu kontuan.

Hainbat aldagairen funtzio eskalar baten baldintzarik gabeko minimizazioa

Scipy.optimize paketearen minim funtzioak hainbat aldagairen funtzio eskalarren baldintzapeko eta baldintzarik gabeko minimizazio-arazoak ebazteko interfaze orokorra eskaintzen du. Nola funtzionatzen duen erakusteko, hainbat aldagairen funtzio egoki bat beharko dugu, modu ezberdinetan minimizatuko duguna.

Helburu horietarako, N aldagaien Rosenbrock funtzioa perfektua da, eta forma hau dauka:

SciPy, optimizazioa

Rosenbrock funtzioa eta bere Jacobi eta Hessian matrizeak (lehen eta bigarren deribatuak, hurrenez hurren) scipy.optimize paketean dagoeneko definituta dauden arren, guk geuk definituko dugu.

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)

Argitasuna lortzeko, marraz ditzagun 3Dn bi aldagairen Rosenbrock funtzioaren balioak.

Marrazki kodea

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()

SciPy, optimizazioa

Aldez aurretik minimoa 0 at dela jakinda SciPy, optimizazioa, ikus ditzagun zenbait scipy.optimize prozedura erabiliz Rosenbrock funtzioaren balio minimoa zehazteko adibideak.

Nelder-Mead simplex metodoa

Izan bedi x0 hasierako puntu bat 5 dimentsioko espazioan. Aurki dezagun Rosenbrock funtzioaren gutxieneko puntua bertatik hurbilen dagoen algoritmoa erabiliz Nelder-Mead simplex (algoritmoa metodoaren parametroaren balio gisa zehazten da):

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.]

Simplex metodoa esplizituki definitutako eta nahiko leun funtzio bat minimizatzeko modurik errazena da. Ez du eskatzen funtzio baten deribatuak kalkulatzea; nahikoa da bere balioak soilik zehaztea. Nelder-Mead metodoa aukera ona da minimizazio arazo sinpleetarako. Hala ere, gradienteen estimazioak erabiltzen ez dituenez, baliteke denbora gehiago behar izatea minimoa aurkitzeko.

Powell metodoa

Funtzioen balioak bakarrik kalkulatzen diren optimizazio algoritmo bat da Powell-en metodoa. Erabiltzeko, method = 'powell' ezarri behar duzu minim funtzioan.

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) algoritmoa

Soluzio baterako konbergentzia azkarragoa lortzeko, prozedura BFGS objektibo-funtzioaren gradientea erabiltzen du. Gradientea funtzio gisa zehaztu daiteke edo lehen mailako diferentziak erabiliz kalkula daiteke. Nolanahi ere, BFGS metodoak normalean simplex metodoak baino funtzio-dei gutxiago behar ditu.

Aurki dezagun Rosenbrock-en funtzioaren deribatua forma analitikoan:

SciPy, optimizazioa

SciPy, optimizazioa

Adierazpen honek balio du aldagai guztien deribatuetarako, lehenengoa eta azkena izan ezik, hauek honela definitzen direnak:

SciPy, optimizazioa

SciPy, optimizazioa

Ikus dezagun gradiente hau kalkulatzen duen Python funtzioa:

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 der

Gradientea kalkulatzeko funtzioa minim funtzioaren jac parametroaren balio gisa zehazten da, behean erakusten den moduan.

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]

Gradienteen algoritmo konjokatua (Newton)

Algoritmoa Newtonen gradiente konjokatuak Newtonen metodo aldatua da.
Newtonen metodoa tokiko eremu bateko funtzio bat bigarren graduko polinomio baten bidez hurbiltzean oinarritzen da:

SciPy, optimizazioa

non SciPy, optimizazioa bigarren deribatuen matrizea da (hessiar matrizea, hessiera).
Hessiarra definitu positiboa bada, orduan funtzio honen minimo lokala aurki daiteke forma koadratikoko zero gradientea zerorekin berdinduz. Emaitza adierazpena izango da:

SciPy, optimizazioa

Alderantzizko Hessiarra gradiente konjokatuaren metodoa erabiliz kalkulatzen da. Rosenbrock funtzioa minimizatzeko metodo hau erabiltzearen adibide bat behean ematen da. Newton-CG metodoa erabiltzeko, hessiarra kalkulatzen duen funtzio bat zehaztu behar duzu.
Rosenbrock-en funtzioaren hessiarra forma analitikoan berdina da:

SciPy, optimizazioa

SciPy, optimizazioa

non SciPy, optimizazioa ΠΈ SciPy, optimizazioa, zehaztu matrizea SciPy, optimizazioa.

Matrizearen gainerako elementu ez-zeroak honako hauek dira:

SciPy, optimizazioa

SciPy, optimizazioa

SciPy, optimizazioa

SciPy, optimizazioa

Adibidez, bost dimentsioko espazio batean N = 5, Rosenbrock funtzioaren matrize hessiarrak banda baten forma du:

SciPy, optimizazioa

Hessian hau kalkulatzen duen kodea Rosenbrock funtzioa minimizatzeko kodearekin batera gradiente konjokatua (Newton) metodoa erabiliz:

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]

Adibide bat Hessiaren eta bektore arbitrarioaren produktu-funtzioaren definizioarekin

Mundu errealeko arazoetan, Hessiar matrize osoa kalkulatzeak eta biltegiratzeak denbora eta memoria baliabide garrantzitsuak behar ditzake. Kasu honetan, ez dago benetan Hessiar matrizea bera zehaztu beharrik, zeren minimizatzeko prozedurak beste bektore arbitrario batekin hessaren biderkaduraren berdina den bektore bat baino ez du behar. Beraz, kalkuluaren ikuspuntutik, askoz hobeagoa da berehala hessaren produktuaren emaitza bektore arbitrario batekin itzultzen duen funtzio bat definitzea.

Demagun hess funtzioa, minimizatzeko bektorea lehen argumentu gisa hartzen duena eta bigarren argumentu gisa bektore arbitrarioa (minimizatu beharreko funtzioaren beste argumentu batzuekin batera). Gure kasuan, Rosenbrock funtzioaren hessaren produktua bektore arbitrario batekin kalkulatzea ez da oso zaila. Bada p bektore arbitrarioa da, gero produktua SciPy, optimizazioa dirudi:

SciPy, optimizazioa

Hessaren eta bektore arbitrario baten biderkadura kalkulatzen duen funtzioa hessp argumentuaren balio gisa pasatzen da minimize funtzioari:

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: 66

Gradiente konjugatu konfiantza-eskualde algoritmoa (Newton)

Hessiar matrizearen baldintzatze txarrak eta bilaketa-norabide okerrak eragin dezake Newton-en gradiente konjokatuaren algoritmoa eraginkorra ez izatea. Horrelakoetan, lehentasuna ematen zaio trust region metodoa (konfiantza-eskualdea) Newton gradienteak konjugatu.

Adibidea Hessiar matrizearen definizioarekin:

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.]

Hessaren eta bektore arbitrario baten produktu funtzioarekin adibidea:

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 motako metodoak

Trust-ncg metodoa bezala, Krylov motako metodoak oso egokiak dira eskala handiko problemak ebazteko, matrize-bektore produktuak soilik erabiltzen baitituzte. Haien funtsa Krylov azpiespazio moztu batek mugatutako konfiantza-eskualde batean arazo bat konpontzea da. Ziurgabeko arazoetarako, hobe da metodo hau erabiltzea, iterazio ez-lineal kopuru txikiagoa erabiltzen baitu azpiproblema bakoitzeko matrize-bektore produktuen kopuru txikiagoa dela eta, konfiantza-ncg metodoarekin alderatuta. Gainera, azpiproblema koadratikoaren soluzioa trust-ncg metodoa erabiliz baino zehatzago aurkitzen da.
Adibidea Hessiar matrizearen definizioarekin:

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.]

Hessaren eta bektore arbitrario baten produktu funtzioarekin adibidea:

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.]

Konfiantza-eskualdean gutxi gorabeherako soluziorako algoritmoa

Metodo guztiak (Newton-CG, trust-ncg eta trust-krylov) oso egokiak dira eskala handiko problemak (milaka aldagairekin) ebazteko. Hau da, azpian dagoen gradiente konjokatuaren algoritmoak alderantzizko Hessiar matrizearen gutxi gorabeherako determinazioa inplikatzen duelako. Irtenbidea iteratiboki aurkitzen da, hesieraren hedapen espliziturik gabe. Hessiar baten eta bektore arbitrario baten biderkadurarako funtzio bat definitu behar duzunez, algoritmo hau bereziki ona da matrize eskasekin (banda diagonalarekin) lan egiteko. Honek memoria kostu baxuak eta denbora aurrezten nabarmena eskaintzen du.

Tamaina ertaineko arazoetarako, Hessian biltegiratzeko eta factoring kostua ez da kritikoa. Horrek esan nahi du irtenbide bat iterazio gutxiagotan lortzea posible dela, konfiantza-eskualdearen azpiarazoak ia zehatz-mehatz ebatziz. Horretarako, ekuazio ez-lineal batzuk iteratiboki ebazten dira azpiproblema koadratiko bakoitzeko. Horrelako soluzio batek Hessiar matrizearen 3 edo 4 Cholesky deskonposizio behar ditu normalean. Ondorioz, metodoak iterazio gutxiagotan bat egiten du eta inplementatutako konfiantza-eskualdeetako beste metodo batzuek baino funtzio objektiboen kalkulu gutxiago behar ditu. Algoritmo honek Hessiar matrize osoa zehaztea besterik ez du inplikatzen eta ez du onartzen Hessiararen produktuaren funtzioa eta bektore arbitrarioa erabiltzeko gaitasuna.

Rosenbrock funtzioaren minimizazioa duen adibidea:

res = minimize(rosen, x0, method='trust-exact',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
res.x

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 13
         Function evaluations: 14
         Gradient evaluations: 13
         Hessian evaluations: 14

array([1., 1., 1., 1., 1.])

Seguruenik hor geldituko gara. Hurrengo artikuluan baldintzapeko minimizazioari buruzko gauzarik interesgarrienak kontatzen saiatuko naiz, hurbilketa-problemak ebazteko minimizazioaren aplikazioa, aldagai baten funtzio bat minimizatzea, minimizatzaile arbitrarioak eta scipy.optimize erabiliz ekuazio-sistema baten erroak aurkitzen. paketea.

Iturria: https://docs.scipy.org/doc/scipy/reference/

Iturria: www.habr.com

Gehitu iruzkin berria