SciPy (shqip: sai pai) është një paketë matematike e bazuar në numpy, duke përfshirë gjithashtu biblioteka të shkruara në C dhe Fortran. Me SciPy, një seancë interaktive Python shndërrohet në një mjedis të plotë për përpunimin e të dhënave, si MATLAB, IDL, Octave, R ose SciLab.
NĂ« kĂ«tĂ« artikull do tĂ« shqyrtojmĂ« teknikat kryesore tĂ« programimit matematikor â zgjidhjen e problemeve tĂ« optimizimit kushtor pĂ«r njĂ« funksion skalar me shumĂ« variabla duke pĂ«rdorur paketĂ«n scipy.optimize. Algoritmet pĂ«r optimizim tĂ« pakushtĂ«zuar janĂ« shqyrtuar tashmĂ« nĂ« . NjĂ« informacion mĂ« i detajuar dhe i azhurnuar pĂ«r funksionet e scipy gjithmonĂ« mund tĂ« merret me komandĂ«n help(), Shift+Tab ose nĂ« .
Hyrje
Interface-i i përgjithshëm për zgjidhjen e problemeve si të optimizimit kushtor ashtu edhe të pakushtëzuar në paketën scipy.optimize ofrohet nga funksioni minimize(). Megjithatë, është e njohur se nuk ekziston një mënyrë universale për zgjidhjen e të gjitha problemeve, prandaj zgjedhja e metodës së duhur gjithmonë bie mbi shpatullat e hulumtuesit.
Algoritmi i përshtatshëm për optimizimin përcaktohet përmes argumentit të funksionit minimize(..., method="").
Për optimizimin e kushtor të funksioneve me shumë variabla, janë të disponueshme implementime të metodave të mëposhtme:
trust-constrâ kĂ«rkimi i minimumit lokal nĂ« njĂ« zonĂ« besimi. , ;SLSQPâ programim katror sekondar me kufizime, metoda e Njutonit pĂ«r zgjidhjen e sistemit Lagrangian. .TNCâ Truncated Newton Constrained, numĂ«r i kufizuar iteracionesh, i mirĂ« pĂ«r funksione jo-lineare me numĂ«r tĂ« madh variablash tĂ« pavarur. .L-BFGS-Bâ metoda nga katĂ«rshja BroydenâFletcherâGoldfarbâShanno, e implementuar me konsum tĂ« reduktuar tĂ« memories pĂ«rmes ngarkimit tĂ« pjesshĂ«m tĂ« vektorĂ«ve nga matrica Hessiane. , .COBYLAâ COBYLA Constrained Optimization By Linear Approximation, optimizimi i kufizuar me aproximacion linear (pa llogaritur gradienten). .
Në varësi të metodës së zgjedhur, kushtet dhe kufizimet për zgjidhjen e problemit përcaktohen në mënyra të ndryshme:
- objekti i klasës
Boundspër metodat L-BFGS-B, TNC, SLSQP, trust-constr; - lista
(min, max)për këto metoda L-BFGS-B, TNC, SLSQP, trust-constr; - objekti ose lista e objekteve
LinearConstraint,NonlinearConstraintpër metodat COBYLA, SLSQP, trust-constr; - fjalori ose lista fjalorësh
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}për metodat COBYLA, SLSQP.
Plani i artikullit:
1) Të shqyrtohet aplikimi i algoritmit të optimizimit kushtor në zonën e besimit (method=»trust-constr») me kufizimet e përcaktuara në formën e objekteve Bounds, LinearConstraint, NonlinearConstraint ;
2) Të shqyrtojmë programimin sekondar me metodën e katrorëve më të vogla (method=»SLSQP») me kufizime të vendosura në formën e një fjalori. {'type', 'fun', 'jac', 'args'};
3) Të analizohet shembulli i optimizimit të prodhimit duke marrë si model një agjenci web.
Optimizimi kushtor method=»trust-constr»
Implementimi i metodës trust-constr bazohet në për problemet me kufizime të llojit të barazisë dhe mbi për problemet me kufizime në formë pakushte. Të dy metodat janë implementuar me algoritme për gjetjen e minimumit lokal në një zonë besimi dhe përshtaten mirë për probleme me shkallë të madhe.
Formulimi matematikor i problemit të gjetjes së minimumit në mënyrë të përgjithshme:
Për kufizime strikte të barazisë, kufiri i poshtëm vendoset të jetë i barabartë me atë të sipërm. 
.
Për kufizim të njëanshëm, kufiri i sipërm ose i poshtëm vendoset np.inf me shenjën përkatëse.
Le të themi se duhet të gjejmë minimumin e funksionit të njohur të Rosenbrok nga dy variabla:
Me këtë, janë vendosur kufizimet e mëposhtme mbi zonën e saj të definimit:
Në rastin tonë ka një zgjidhje të vetme në pikën 
, për të cilën vlejnë vetëm kufizimet e para dhe të katërt.
Të shohim kufizimet nga poshtë lart dhe të shohim si mund t'i shkruajmë ato në scipy.
Kufizimet 
dhe 
të përcaktojmë me anë të objektit Bounds.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Kufizimet 
dhe 
të shkruajmë në formën lineare:
Të përcaktojmë këto kufizime në formën e objektit LinearConstraint:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Dhe përfundimisht, kufizimi jo-linear në formën matricore:
Të përcaktojmë matricën Jacobian për këtë kufizim dhe kombinimin linear të matricës Hessian me një vektor të rastësishëm. 
:
Tani kufizimi jo-linear mund të përcaktohet si objekt NonlinearConstraint:
from scipy.optimize import NonlinearConstraint
def cons_f(x):
return [x[0]**2 + x[1], x[0]**2 - x[1]]
def cons_J(x):
return [[2*x[0], 1], [2*x[0], -1]]
def cons_H(x, v):
return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H)Nëse dimensioni është i madh, matricat mund të përcaktohen edhe në formë të rrallë:
from scipy.sparse import csc_matrix
def cons_H_sparse(x, v):
return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_sparse)ose si objekt LinearOperator:
from scipy.sparse.linalg import LinearOperator
def cons_H_linear_operator(x, v):
def matvec(p):
return np.array([p[0]*2*(v[0]+v[1]), 0])
return LinearOperator((2, 2), matvec=matvec)
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_linear_operator)Kur matica Hessian llogaritet 
kërkon shumë burime, mund të përdorim klasën . Strategjitë e mëposhtme janë të disponueshme: BFGS dhe SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessiani gjithashtu mund të llogaritet nëpërmjet diferencave të kufizuara:
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac='2-point', hess='2-point')Matricën Jakobian të kërkesave gjithashtu mund ta llogarisim me anë të diferencave të kufizuara. Megjithatë, në këtë rast, matricën Hessian me anë të diferencave të kufizuara nuk mund ta llogarisim. Hessiani duhet të përcaktohet si një funksion ose nëpërmjet klasës HessianUpdateStrategy.
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac='2-point', hess=BFGS())Zgjidhja e problemit të optimizimit duket si më poshtë:
from scipy.optimize import minimize
from scipy.optimize import rosen, rosen_der, rosen_hess, rosen_hess_prod
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)`gtol` kushti i përfundimit është plotësuar.
Numri i iteracioneve: 12, vlerësime të funksionit: 8, iteracione CG: 7, optimaliteti: 2.99e-09, shkelja e kushtit: 1.11e-16, koha e ekzekutimit: 0.033 s.
[0.41494531 0.17010937]Nëse nevojitet, funksioni për llogaritjen e Hessian mund të përcaktohet me anë të klasës LinearOperator
def rosen_hess_linop(x):
def matvec(p):
return rosen_hess_prod(x, p)
return LinearOperator((2, 2), matvec=matvec)
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)ose produktin e Hessian dhe një vektori të rastësishëm përmes parametrin hessp:
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Alternativisht, derivatet e para dhe të dyta të funksionit që do të optimizohet mund të llogariten në mënyrë të afërt. Për shembull, Hessiani mund të aproximohet me anë të funksionit SR1 (afërsia quasi-Newton). Gradienti mund të aproximohet me diferenca të kufizuara.
from scipy.optimize import SR1
res = minimize(rosen, x0, method='trust-constr', jac='2-point', hess=SR1(),
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Optimizimi me kusht method='SLSQP'
Metoda SLSQP është e destinuar për zgjidhjen e problemeve të minimizimit të funksioneve në formën e:
Ku 
dhe 
- grumbuj indekse përshkruese të kufizimeve në formën e ekuacioneve ose pabarazive. 
- grumbuj kufijsh të poshtëm dhe të sipërm për domenin e përkufizimit të funksionit.
Kufijtë dhe kufizimet jo lineare përshkruhen në formën e fjalorëve me çelësa type, argëtim dhe jac.
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([1 - x [0] - 2 * x [1],
1 - x [0] ** 2 - x [1],
1 - x [0] ** 2 + x [1]]),
'jac': lambda x: np.array ([[- 1.0, -2.0],
[-2 * x [0], -1.0],
[-2 * x [0], 1.0]])
}
eq_cons = {'type': 'eq',
'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]),
'jac': lambda x: np.array ([2.0, 1.0])
}Kërkimi i minimumit realizohet në këtë mënyrë:
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='SLSQP', jac=rosen_der,
constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True},
bounds=bounds)
print(res.x)Optimizimi përfundoi me sukses. (Modaliteti i daljes 0)
Vlera aktuale e funksionit: 0.34271757499419825
Iteracionet: 4
Vlerësimet e funksionit: 5
Vlerësimet e gradientit: 4
[0.41494475 0.1701105 ]Shembulli i optimizimit
Me kalimin në sistemin e pestë teknologjik, le të shqyrtojmë optimizimin e prodhimit me shembullin e një studioje webi, e cila na sjell një të ardhur të vogël por stabile. Të imagjinojmë se jemi drejtor të një galerie, ku prodhohen tri lloje produktesh:
- x0 â landing pages tĂ« shitjes, nga 10.000 lekĂ«.
- x1 â faqe korporative, nga 20.000 lekĂ«.
- x2 â dyqane online, nga 30.000 lekĂ«.
Ekipi ynë i punës përbëhet nga katër juniorë, dy mid-level dhe një senior. Fondd i orëve të tyre të punës për muajin:
- juniorët:
4 * 150 = 600 orë punë, - mid-level:
2 * 150 = 300 orë punë, - seniori:
150 orë punë.
Le tĂ« supozojmĂ« se pĂ«r zhvillimin dhe shpĂ«rndarjen e njĂ« faqeje tĂ« tipit (x0, x1, x2) njĂ« junior i rastit duhet tĂ« shpenzojĂ« (10, 20, 30) orĂ«, mid-level â (7, 15, 20), senior â (5, 10, 15) orĂ« mĂ« tĂ« mirat e jetĂ«s sĂ« tij.
Siç i takon çdo drejtori normal, dĂ«shirojmĂ« tĂ« maksimizojmĂ« fitimin mujor. Hapi i parĂ« drejt suksesit â regjistrojmĂ« funksionin qĂ«llimor vlera si shumĂ«n e tĂ« ardhurave nga produktet e prodhuara gjatĂ« muajit:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Kjo nuk është një gabim, kur kërkojmë maksimumin, funksioni qëllimor minimizohet me shenjë të kundërt.
Hapi tjetĂ«r â ndalojmĂ« qĂ« punonjĂ«sit tanĂ« tĂ« punojnĂ« mĂ« shumĂ« dhe vendosim kufizime mbi fonddin e orĂ«ve tĂ« punĂ«s:
Që është ekuivalente me:
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2],
300 - 7 * x [0] - 15 * x [1] - 20 * x[2],
150 - 5 * x [0] - 10 * x [1] - 15 * x[2]])
}Kufizimi formal â prodhimi i produkteve duhet tĂ« jetĂ« vetĂ«m pozitiv:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Dhe fundi, supozimi më optimist - për shkak të çmimit të ulët dhe cilësisë së lartë, ne vazhdimisht kemi një radhë të kënaqur klientësh. Ne mund të zgjedhim vetë volumin mujor të prodhimit të produkteve, duke u bazuar në zgjidhjen e një problemi të optimizimit scipy.optimize:
x0 = np.array([10, 10, 10])
res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds)
print(res.x)[7.85714286 5.71428571 3.57142857]Të bëjmë një përafrim të thjeshtë dhe të llogarisim ngarkesën mujore të rrokjeve në një situatë optimale të produkteve x = (8, 6, 3) :
- juniorët:
8 * 10 + 6 * 20 + 3 * 30 = 290 njerëz * orë; - mid-level:
8 * 7 + 6 * 15 + 3 * 20 = 206 njerëz * orë; - seniori:
8 * 5 + 6 * 10 + 3 * 15 = 145 njerëz * orë.
Konkluzion: që drejtori të marrë maksimumin e merituar, është optimale të prodhohen muajshëm 8 landing pages, 6 webfaqe të mesme dhe 3 dyqane. Senioret duhet të punojnë pa pushim, ngarkesa e midleve do të jetë rreth 2/3, ndërsa ajo e juniorëve nën gjysmë.
PĂ«rfundimi
Ky artikull përmend teknikat themelore të punës me paketën scipy.optimize, të përdorura për zgjidhjen e problemeve të minimizimit të kushteve. Unë personalisht përdor scipy në qëllime të pastër akademike, prandaj shembulli i sjellë ka një karakter të tillë komik.
Shumë teori dhe exemple të rëndësishme mund të gjejnë, për shembull, në librin e I.L.Akulich "Programimi matematikor në shembuj dhe probleme". Një aplikim më serioz scipy.optimize për ndërtimin e strukturave 3D nga një seri imazhesh () mund të shihet në .
Burimi kryesor i informacionit është , ata që duan të kontribuojnë në përkthimin e kësaj dhe seksioneve të tjera scipy mirëpriten .
Faleminderit për pjesëmarrjen në përgatitjen e publikimit.
Burimi: habr.com
