SciPy (të shqiptuar si sai pai) është një paketë e procedurave matematikore të aplikueshme, e ndërtuar mbi zgjerimin Numpy Python. Me SciPy, seanca interaktive Python shndërrohet në një mjedis të plotë për përpunimin e të dhënave dhe prototipizimin e sistemeve të komplikuara, si MATLAB, IDL, Octave, R-Lab dhe SciLab. Sot, dua të flas shkurtimisht për aplikimin e disa algoritmeve të njohura të optimizimit në paketën scipy.optimize. Për një informacion më të detajuar dhe të azhurnuar mbi përdorimin e funksioneve, gjithmonë mund të merrni ndihmë me komandën help() ose me Shift+Tab.
Hyrje
Për të kursyer 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, këto informacione janë të mjaftueshme për të kuptuar metodat në përgjithësi dhe kushtet e përdorimit të tyre. Për të kuptuar thelbin e metodave matematikore, ne ndjekim lidhjet për botime 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 implementimin e procedurave të mëposhtme:
- Minimizimi i kushtëzuar dhe i pa kushtëzuar i funksioneve skalarë me disa variabla (minim) përmes algoritmeve të ndryshme (simpelksi i Nelder-Mead, BFGS, gradientet e lidhura të Newtonit, и )
- Optimizimi global (p.sh: , )
- Minimizimi i mbetjeve (least_squares) dhe algoritmet për përshtatjen e kurbave me MNP jo-linear (curve_fit)
- Minimizimi i funksioneve skalarë me një variabël (minim_scalar) dhe kërkimi i rrënjëve (root_scalar)
- Zgjidhësit shumë-dimensionalë të sistemit të ekuacioneve (root) duke përdorur algoritmo të ndryshme (hibride të Powellit, ose metoda me shkallë të madhe, si ).
Në këtë artikull ne do të shqyrtojmë vetëm pikën e parë nga e gjithë kjo listë.
Minimizimi i pa kushtëzuar i funksioneve skalarë me disa variabla
Funksioni minim nga paketa scipy.optimize ofron një ndërfaqe të përgjithshme për zgjidhjen e problemeve të minimizimit të kushtëzuar dhe të pa kushtëzuar të funksioneve skalarë me disa variabla. Për të demonstruar funksionimin e tij, na nevojitet një funksion i përshtatshëm me disa variabla, që do ta minimizojmë në mënyra të ndryshme.
Për këto qëllime, funksioni i Rosenbrockut me N variabla është i përshtatshëm dhe ka formën:
Megjithëse funksioni i Rosenbrockut dhe matricat e tij Jacobian dhe Hessian (derivatet e para dhe të dyta 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 do të vizatojmë në 3D vlerat e funksionit të Rosenbrockut nga 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ë grafikun 3D
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Caktojmë këndin e shikimit
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 minimumi është 0 kur 
, le të shqyrtojmë shembuj se si mund të përcaktojmë vlerën minimale të funksionit të Rosenbrockut përmes procedurave të ndryshme scipy.optimize.
Metoda Simplex e Nelder-Mead
Supozoni se kemi një pikë fillestare x0 në hapësirën 5-dimensionale. Le të gjejmë pikën më të afërt të minimumit të funksionit të Rosenbrockut duke përdorur algoritmin (algoritmi u përmend 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)Optimizimi përfundoi me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracionet: 339
Vlerësimet e funksionit: 571
[1. 1. 1. 1. 1.]Metoda Simplex është mënyra më e thjeshtë për të minimizuar një funksion të përcaktuar qartë dhe mjaft të qetë. Ajo nuk kërkon llogaritjen e derivatave të funksionit, mjafton të jepen vetëm vlerat e tij. Metoda Nelder-Mead është një zgjedhje e mirë për detyrat e thjeshta të minimizimit. Megjithatë, pasi ajo nuk përdor vlerësime të gradientit, mund të kërkohet më shumë kohë për të gjetur minimumin.
Metoda Powell
Një tjetër algoritëm optimizimi, në të cilin llogariten vetëm vlerat e funksioneve, është . Për ta përdorur atë, duhet të vendosni 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)Optimizimi përfundoi me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracionet: 19
Vlerësimet e funksionit: 1622
[1. 1. 1. 1. 1.]Algoritmi Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Për të arritur një konvergjencë më të shpejtë në zgjidhje, procedura përdor gradientin e funksionit qëllimor. Gradianti mund të jepet në formën e një funksioni ose llogaritet përmes ndryshimeve të rendit të parë. Në çdo rast, zakonisht metoda BFGS kërkon më pak thirrje funksionesh sesa metoda simplex.
Të gjejmë derivatën e funksionit Rosenbrock në formë analitike:
Ky shprehje është e drejtë për derivatat e të gjitha variablave, përveç të parës dhe të fundit, të cilat përcaktohen si:
Le të shohim funksionin në 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 për llogaritjen e gradientit është specifikuar si vlerë e parametrave jac të funksionit minim, siç përshkruhet më poshtë.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimizimi përfundoi me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracionet: 25
Vlerësimet e funksionit: 30
Vlerësimet e gradientit: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Algoritmi i gradientëve të çiftëzuar (Newton)
Algoritmi është një metodë e modifikuar Newtonit.
Metoda e Newtonit bazohet në aproximimin e funksionit në një zonë lokale me një polinom të rendit të dytë:
ku 
është matrica e të dytave derivatave (matrica Hessiane, hessian).
Nëse hessian është pozitivisht i përcaktuar, atëherë mund të gjendet minimumi lokal i këtij funksioni duke e barazuar gradientin zero të formës katrore me zero. Si rezultat do të kemi shprehjen:
Hessiani i funksionit Rosenbrock llogaritet me metodën e gradientëve të çiftëzuar. Një shembull i përdorimit të kësaj metode për minimizimin e funksionit Rosenbrock jepet më poshtë. Përdorimi i metodës Newton-CG kërkon përcaktimin e funksionit që llogarit hessian-in.
Hessiani i funksionit Rosenbrock në formë analitike është:
ku 
и 
, përcaktojnë matricën 
.
Elementet e tjera jo zero të matricës janë:
Për shembull, në hapësirën pesëdimensional N = 5, matrica Hessiane për funksionin Rosenbrock ka një formë bande:
Kodi që llogarit këtë hessian së bashku me kodin për minimizimin e funksionit Rosenbrock me metodën e gradientëve të çiftëzuar (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 përfundua me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracionet: 24
Vlerësimet e funksionit: 33
Vlerësimet e gradientes: 56
Vlerësimet e Hessianit: 24
[1. 1. 1. 0.99999999 0.99999999]Shembulli me caktimin e funksionit të prodhimit të Hessianit dhe një vektori të rastshëm
Në problemet reale, llogaritja dhe ruajtja e të gjithë matricës së Hessianit mund të kërkojë burime të konsiderueshme kohe dhe memorie. Në të njëjtën kohë, në thelb, nuk ka nevojë për të caktuar vetë matricën e Hessianit, pasi për procedurën e minimizimit ne kemi nevojë vetëm për një vektor, i barabartë me produktin e Hessianit me një vektor tjetër të rastshëm. Prandaj, nga një këndvështrim llogaritës, është shumë më e preferueshme të caktojmë menjëherë një funksion që kthen rezultatin e produktit të Hessianit me një vektor të rastshëm.
Le të shqyrtojmë funksionin hess, i cili merr si argument të parë vektorin e minimizimit dhe si argument të dytë një vektor të rastshëm (përveç argumenteve të tjera të funksionit të minimizuar). Në rastin tonë, llogaritja e produktit të Hessianit të funksionit të Rosenbrock me një vektor të rastshëm nuk është shumë e vështirë. Nëse p — është një vektor i rastshëm, atëherë produkti 
ka formën:
Funksioni që llogarit produktin e Hessianit dhe një vektor të rastshë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 përfundua me sukses.
Vlera aktuale e funksionit: 0.000000
Iteracionet: 24
Vlerësimet e funksionit: 33
Vlerësimet e gradientes: 56
Vlerësimet e Hessianit: 66Algoritmi i rajonit të besimit (trust region) të gradientëve të lidhur (Newton)
Keq-kondicioni i matricës së Hessianit dhe drejtimet e gabuara të kërkimit mund të bëjnë që algoritmi i gradientëve të lidhur të Newtonit të jetë joefektiv. Në këto raste, preferohet (trust-region) të gradientëve të lidhur të Newtonit.
Shembulli me caktimin e matricës së Hessianit:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimizimi u përfundua me sukses.
Vlera e tanishme e funksionit: 0.000000
Iteracionet: 20
Vlerësime për funksionin: 21
Vlerësime për gradienin: 20
Vlerësime për hessianin: 19
[1. 1. 1. 1. 1.]Shembulli me funksionin e produktit të hessianit 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 u përfundua me sukses.
Vlera e tanishme e funksionit: 0.000000
Iteracionet: 20
Vlerësime për funksionin: 21
Vlerësime për gradienin: 20
Vlerësime për hessianin: 0
[1. 1. 1. 1. 1.]Metodat e tipit Krylov
Si metodat trust-ncg, metodat e tipit Krylov janë të përshtatshme për zgjidhjen e problemeve të mëdha, pasi ato përdorin vetëm produkte matricore-vektoriale. Thelbi i tyre është zgjidhja e problemeve në një zonë besimi të kufizuar nga një nën-hapsirë e prerë Krylov. Për problemet e pa-përcaktuara, ky metod është më i përshtatshëm, pasi përdor një numër më të vogël iteracionesh jo-lineare për shkak të numrit më të vogël të produkteve matricore-vektoriale për një detyrë të vogël, krahasuar me metodën trust-ncg. Për më tepër, zgjidhja e nën-problemit katror është më e sakta se me metodën trust-ncg.
Shembulli me caktimin e matricës së Hessianit:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimizimi u përfundua me sukses.
Vlera e tanishme e funksionit: 0.000000
Iteracionet: 19
Vlerësime për funksionin: 20
Vlerësime për gradienin: 20
Vlerësime për hessianin: 18
print(res.x)
[1. 1. 1. 1. 1.]
Shembulli me funksionin e produktit të hessianit 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 u përfundua me sukses.
Vlera e tanishme e funksionit: 0.000000
Iteracionet: 19
Vlerësime për funksionin: 20
Vlerësime për gradienin: 20
Vlerësime për hessianin: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algoritmi i zgjidhjes afatgjatë në zonën e besimit
Të gjitha metodat (Newton-CG, trust-ncg dhe trust-krylov) janë të përshtatshme për zgjidhjen e problemeve të mëdha (me mijëra variabla). Kjo lidhet me faktin se algoritmi i bazuar në to, i gradienteve të ndërlidhura, nënkupton gjetjen afatgjatë të matricës së inversë të Hessianit. Zgjidhja gjendet në mënyrë iteruese, pa shprehje të qarta Hessiane. Duke qenë se kërkohet të përcaktohet vetëm funksioni për produktin e Hessianit dhe një vektor të rastësishëm, ky algoritëm është veçanërisht i mirë për punën me matrix të hollë (diagona të shtrënguara). Kjo siguron kosto të ulët memorie dhe një kursim të rëndësishëm të kohës.
Në problemet me përmasat e mesme, kostot e ruajtjes dhe faktorizimi i hessianit nuk kanë rëndësi vendimtare. Kjo do të thotë se mund të arrihet një zgjidhje me një numër më të vogël iteracionesh, duke lejuar nën-problemet e zonës së besimit të zgjidhen pothuajse saktësisht. Për këtë, disa ekuacione jo-lineare zgjidhen iterativ për secilën nën-problem katror. Kjo zgjidhje zakonisht kërkon 3 ose 4 shpërbërje të matricës së Hessianit. Si rezultat, metoda konvergon në një numër më të vogël iteracionesh dhe kërkon më pak llogaritje të funksionit objektiv se metodat e tjera të zbatuara në zonën e besimit. Ky algoritëm nënkupton vetëm përcaktimin e matricës së plotë Hessiane dhe nuk mbështet përdorimin e funksionit të produktit të hessianit dhe një vektori të rastësishëm.
Shembulli me minimizimin e funksionit 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.
Vlera aktuale e funksionit: 0.000000
Iteracionet: 13
Vlerësimet e funksionit: 14
Vlerësimet e gradientit: 13
Vlerësimet e hessianit: 14
array([1., 1., 1., 1., 1.])Këtu, ndoshta, do të ndalojmë. Në artikullin e ardhshëm do të përpiqem të flas për gjëra më interesante rreth minimizimit të kushtëzuar, aplikacionit të minimizimit në zgjidhjen e problemeve të aproksimimit, minimizimit të funksioneve me një variabël, minimizatorëve të rastësishëm dhe gjetjes së rrënjëve të sistemit të ekuacioneve me ndihmën e paketës scipy.optimize.
Burimi:
Burimi: habr.com
