SciPy (shkruhet si sai pai) është një paketë procedurash matematikore aplikative, e bazuar në zgjerimin Numpy Python. Me SciPy, një seancë interaktive Python shndërrohet në një ambient të plotë për përpunimin e të dhënave dhe prototipimin e sistemeve të ndërlikuara, si MATLAB, IDL, Octave, R-Lab dhe SciLab. Sot do të flas shkurtimisht për mënyrën se si duhet të aplikohet disa algoritme të njohura optimizimi në paketën scipy.optimize. Informacion më të detajuar dhe të saktë për përdorimin e funksioneve gjithmonë mund të merrni me komandën help() ose me Shift+Tab.
Hyrje
Për të shpëtuar veten dhe lexuesit nga kërkimi dhe leximi i burimeve origjinale, lidhjet për përshkrimet e metodave do të jenë kryesisht në Wikipedia. Në përgjithësi, kjo informacion është e mjaftueshme për të kuptuar metodat në përmbledhje dhe kushtet e aplikimit të tyre. Për të kuptuar thelbin e metodave matematikore, do të shkojmë përmes lidhjeve për publikime më autoritative, të cilat mund të gjenden në fund të çdo artikulli ose në motorin tuaj të preferuar të kërkimit.
Pra, moduli scipy.optimize përfshin realizimin e procedurave të mëposhtme:
- Minimizimi i kushëzuar dhe i pakushtëzuar i funksioneve skalarë të disa variablave (minim) me ndihmën e algoritmeve të ndryshëm (metoda simpleks e Nelder-Mead, BFGS, gradientet e ndërlikuara të Newtonit, dhe )
- Optimizimi global (p.sh.: , )
- Minimizimi i mbetjeve (least_squares) dhe algoritmet e përshtatjes së kurbave të MNK-në e ndërlikuar (curve_fit)
- Minimizimi i funksioneve skalarë një variabli (minim_scalar) dhe gjetja e rrënjëve (root_scalar)
- Zgjidhësit shumëdimensionalë të sistemit të ekuacioneve (root) duke përdorur algoritme të ndryshme (hibridi i Powellit, ose metodat e mëdha, siç janë ).
Në këtë artikull ne do të shqyrtojmë vetëm pikën e parë nga e gjithë kjo listë.
Minimizimi i pakushtëzuar i një funksioni skalar të disa variablave
Funksioni minim nga paketa scipy.optimize ofron një ndërfaqe të përgjithshme për të zgjidhur problemet e minimizimit të kushëzuar dhe të pakushtëzuar të funksioneve skalarë të disa variablave. Për të demonstruar punën e tij, na nevojitet një funksion i përshtatshëm i disa variablave, që do të minimizojmë në mënyra të ndryshme.
Për këto qëllime, funksioni i Rosenbrockut nga N variabla i përshtatet në mënyrë të shkëlqyer, i cili ka formën:
Megjithëse funksioni i Rosenbrockut dhe matricat e tij Jacobi dhe Hessian (derivata e parë dhe e dytë përkatësisht) janë tashmë të përcaktuara në paketën scipy.optimize, le të e përcaktojmë atë vetë.
import numpy as np
def rosen(x):
"""Funksioni i Rosenbrockut"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Për qartësi, le të vizatojmë në 3D vlerat e funksionit të Rosenbrockut për dy variabla.
Kodi për vizatimin
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Konfigurojmë grafikën 3D
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Vendosim këndin e pamjes
ax.view_init(45, 30)
# Krijojmë të dhëna për grafik
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]))
# Vizatojmë sipërfaqen
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Duke e ditur paraprakisht se minima është 0 kur 
, le të shqyrtojmë shembuj se si mund të përcaktojmë vlerën minimale të funksionit të Rosenbrockut me ndihmën e procedurave të ndryshme scipy.optimize.
Metoda e simpleksit të Nelder-Mead
Le të themi se kemi një pikë fillestare x0 në një hapësirë 5-dimensionale. Të gjejmë pikën më të afërt me të në minimumin e funksionit të Rosenbrockut me ndihmën e algoritmit (algoritmi i caktuar si vlerë e parametrave method):
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.]Metoda e simpleksit është mënyra më e thjeshtë për të minimizuar një funksion të qartë dhe relativisht të lëmuar. Ajo nuk kërkon llogaritjen e derivativeve të funksionit, për sa kohë që mjafton të caktojmë vetëm vlerat e tij. Metoda e Nelder-Mead është një zgjedhje e mirë për problemet e thjeshta të minimizimit. Megjithatë, pasi ajo nuk përdor vlerësime të gradientit, mund të kërkojë më shumë kohë për të gjetur minimun.
Metoda e Powellit
NjĂ« algoritĂ«m tjetĂ«r optimizimi nĂ« tĂ« cilin llogariten vetĂ«m vlerat e funksioneve Ă«shtĂ« . PĂ«r ta pĂ«rdorur atĂ«, duhet tĂ« caktosh method = âpowellâ nĂ« funksionin minim.
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.]Algoritmi i Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Për të arritur një konvergjencë më të shpejtë në zgjidhje, procedura përdor gradientin e funksionit të synimit. Gradi mund të jepet si një funksion ose të llogaritet përmes diferencave të rendit të parë. Në çdo rast, zakonisht metoda BFGS kërkon më pak thirrje të funksioneve sesa metoda simpleks.
Të gjejmë derivatin e funksionit të Rosenbrock në formë analitike:
Ky shprehje është e vërtetë për derivatat e të gjitha variablave, përveç të parës dhe të fundit, të cilat përcaktohen si:
Le të shohim funksionin Python që llogarit këtë gradient:
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 derFunksioni që llogarit gradientin jepet si vlerë e parametrin jac të funksionit minim, si më poshtë.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimizimi u ndal me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracione: 25
Vlerësime funksionesh: 30
Vlerësime gradienesh: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Algoritmi i gradienteve të lidhura (Newton)
Algoritmi është një metodë e modifikuar e Newtonit.
Metoda e Newtonit bazohet në aproximimin e funksionit në një zonë lokale me një polinom të rendit të dytë:
ku 
është matrica e derivatave të dyta (matrica Hess, hessian).
Nëse hessian është pozitivisht i përcaktuar, atëherë minimumi lokal i këtij funksioni mund të gjendet duke e vënë gradienten zero të formës katrore në zero. Si rezultat, do të kemi shprehjen:
Hessian inverse llogaritet përmes metodës së gradienteve të lidhura. Një shembull i përdorimit të kësaj metode për minimizimin e funksionit të Rosenbrock jepet më poshtë. Për të përdorur metodën Newton-CG, duhet të specifikoni një funksion që llogarit hessian.
Hessiani i funksionit të Rosenbrock në formë analitike është:
ku 
dhe 
, përcakton matricën 
.
Elementet e tjera jo-zero të matricës janë:
Për shembull, në hapësirën pesëdimensional N = 5, matrica Hess e funksionit të Rosenbrock ka një formë bande:
Kodi që llogarit këtë hessian së bashku me kodin për minimizimin e funksionit të Rosenbrock me anë të metodës së gradienteve të lidhura (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)Optimizimi u ndal me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracione: 24
Vlerësime funksionesh: 33
Vlerësime gradienesh: 56
Vlerësime hessianesh: 24
[1. 1. 1. 0.99999999 0.99999999]Një shembull me përcaktimin e funksionit të produktit të hessianit dhe një vektori të rastësishëm
Në probleme reale, llogaritja dhe ruajtja e tërë matricës Hess mund të kërkojë burime të konsiderueshme kohe dhe memorje. Në të njëjtën kohë, në fakt nuk është e nevojshme të përcaktohet vetë matrica Hess, sepse për procedurën e minimizimit nevojitet vetëm një vektor, i barabartë me produktin e hessianit me një vektor tjetër të rastësishëm. Prandaj, nga këndvështrimi llogaritar, është shumë më e preferueshme të përcaktohet menjëherë një funksion që kthen rezultatin e produktit të hessianit me një vektor të rastësishëm.
Le tĂ« shqyrtojmĂ« funksionin hess, qĂ« merr vektorin e minimizimit si argumentin e parĂ«, dhe njĂ« vektor tĂ« rastĂ«sishĂ«m si argumentin e dytĂ« (bashkĂ« me argumente tĂ« tjera tĂ« funksionit tĂ« minimizuar). NĂ« rastin tonĂ«, llogaritja e produktit tĂ« hessianit tĂ« funksionit tĂ« Rosenbrock me njĂ« vektor tĂ« rastĂ«sishĂ«m nuk Ă«shtĂ« shumĂ« e komplikuar. NĂ«se p â vektori i rastĂ«sishĂ«m, atĂ«herĂ« produkti 
ka formën:
Funksioni që llogarit produktin e hessianit dhe një vektor të rastësishëm kalon si vlerë e argumentit hessp të funksionit 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})
Optimizimi u ndal me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracione: 24
Vlerësime funksionesh: 33
Vlerësime gradienesh: 56
Vlerësime hessianesh: 66Algoritmi i rajonit të besimit (trust region) të gradienteve të lidhura (Newton)
Keqësimi i matrix Hess dhe drejtimet e gabuara të kërkimit mund të çojnë në paaftësinë e algoritmit të gradienteve të lidhura të Newtonit. Në këto raste preferohet (trust-region) të gradienteve të lidhura të Newton.
Një shembull me përcaktimin e matricës Hess:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimizimi u ndal me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracione: 20
Vlerësime funksionesh: 21
Vlerësime gradienesh: 20
Vlerësime hessianesh: 19
[1. 1. 1. 1. 1.]Shembulli me funksionin e prodhimit të Hessian dhe një vektori të rastësishëm:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimizimi përfundoi me sukses.
Vlerë aktuale e funksionit: 0.000000
Iteracione: 20
Vlerësime të funksionit: 21
Vlerësime të gradientit: 20
Vlerësime të Hessian: 0
[1. 1. 1. 1. 1.]Metodat e tipit Krylov
Përveç metodës trust-ncg, metodat e tipit Krylov janë të përshtatshme për zgjidhjen e problemeve në shkallë të madhe, pasi ato përdorin vetëm prodhime matriçë-vektor. Essenca e tyre qëndron në zgjidhjen e problemit në një zonë besimi, të kufizuar nga një nënhapësirë e shkurtuar e Krylovit. Për problemet e pa përcaktuar, është më mirë të përdoret kjo metodë, sepse përdor një numër më të vogël iteracionesh jo-lineare duke rezultuar në një numër më të vogël prodhimesh matriçë-vektor për çdo nënproblem, krahasuar me metodën trust-ncg. Përveç kësaj, zgjidhja e nënproblemit katror gjenet më saktë se me metodën trust-ncg.
Një shembull me përcaktimin e matricës Hess:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimizimi përfundoi me sukses.
Vlerë aktuale e funksionit: 0.000000
Iteracione: 19
Vlerësime të funksionit: 20
Vlerësime të gradientit: 20
Vlerësime të Hessian: 18
print(res.x)
[1. 1. 1. 1. 1.]
Shembulli me funksionin e prodhimit të Hessian dhe një vektori të rastësishëm:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimizimi përfundoi me sukses.
Vlerë aktuale e funksionit: 0.000000
Iteracione: 19
Vlerësime të funksionit: 20
Vlerësime të gradientit: 20
Vlerësime të Hessian: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algoritmi i zgjidhjes aproximative në zonën e besimit
Të gjitha metodat (Newton-CG, trust-ncg dhe trust-krylov) janë shumë të përshtatshme për zgjidhjen e problemeve në shkallë të madhe (me mijëra variabla). Kjo është për shkak se algoritmi i gradientit të lidhur që qëndron pas tyre nënkupton një gjetje aproximative të matriçës inverse të Hessianit. Zgjidhja gjendet iterativisht, pa ndarjen e qartë të Hessianit. Duke qenë se kërkohet të përcaktohet vetëm funksioni për prodhimin e Hessian dhe një vektori të rastësishëm, ky algoritëm është veçanërisht i mirë për të punuar me matriça të rralla (diagonale të bandave). Kjo siguron kosto të ulët memorie dhe një kursim të konsiderueshëm kohor.
Në problemet e madhësisë së mesme, kostot për ruajtjen dhe faktorimin e Hessianit nuk kanë rëndësi vendimtare. Kjo do të thotë se mund të arrihet një zgjidhje për një numër më të vogël iteracionesh duke lejuar nënproblemet e zonës së besimit të zgjidhen thuajse saktësisht. Për këtë, disa ekuacione jo-lineare zgjidhen iterativisht për çdo nënproblem katror. Ky zgjidhje zakonisht kërkon 3 ose 4 ndarjen e matriçës së Hessianit përmes metodës Cholesky. Si rezultat, metoda konvergjon për një numër më të vogël iteracionesh dhe kërkon më pak llogaritje të funksionit të objektivit krahasuar me metodat e tjera të realizuara në zonën e besimit. Ky algoritëm përfshin vetëm përcaktimin e matriçës së plotë të Hessianit dhe nuk mbështet mundësinë për të përdorur funksionin për prodhimin e Hessian dhe një vektori të rastësishëm.
Shembulli me minimizimin e funksionit të Rosenbrock:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimizimi përfundoi me sukses.
Vlerë aktuale e funksionit: 0.000000
Iteracione: 13
Vlerësime të funksionit: 14
Vlerësime të gradientit: 13
Vlerësime të Hessian: 14
array([1., 1., 1., 1., 1.])Mendoj se këtu do të ndalëm. Në artikullin tjetër, do të përpiqem të flas për gjërat më interesante rreth minimizimit të kushtëzuar, aplikacionit të minimizimit në zgjidhjen e problemeve të aproksimimit, minimizimin e funksionit të një variabli, minimizatorët e rastësishëm dhe gjetjen e rrënjëve të sistemit të ekuacioneve me ndihmën e paketës scipy.optimize.
Burimi:
Burimi: habr.com
