SciPy (shqiptohet byrek sai) është një paketë matematikore e bazuar në numpy që përfshin gjithashtu bibliotekat C dhe Fortran. SciPy e kthen një sesion interaktiv Python në një mjedis të plotë të shkencës së të dhënave si MATLAB, IDL, Octave, R ose SciLab.
Në këtë artikull, ne do të shikojmë teknikat bazë të programimit matematik - zgjidhjen e problemeve të optimizimit të kushtëzuar për një funksion skalar të disa variablave duke përdorur paketën scipy.optimize. Algoritmet e optimizimit të pakufizuar janë diskutuar tashmë në . Ndihmë më e detajuar dhe më e përditësuar për funksionet scipy gjithmonë mund të merret duke përdorur komandën help(), Shift+Tab ose në .
Paraqitje
Një ndërfaqe e përbashkët për zgjidhjen e problemeve të optimizimit të kushtëzuar dhe të pakufizuar në paketën scipy.optimize ofrohet nga funksioni minimize(). Megjithatë, dihet se nuk ekziston një metodë universale për zgjidhjen e të gjitha problemeve, kështu që zgjedhja e një metode adekuate, si gjithmonë, bie mbi supet e studiuesit.
Algoritmi i duhur i optimizimit specifikohet duke përdorur argumentin e funksionit minimize(..., method="").
Për optimizimin e kushtëzuar të një funksioni të disa variablave, janë në dispozicion zbatimet e metodave të mëposhtme:
trust-constr— kërkoni për një minimum lokal në rajonin e besimit. , ;SLSQP— programim kuadratik sekuencial me kufizime, metoda Njutoniane për zgjidhjen e sistemit të Lagranzhit. .TNC- Njuton i shkurtuar I kufizuar, numër i kufizuar përsëritjesh, i mirë për funksione jolineare me një numër të madh variablash të pavarur. .L-BFGS-B- një metodë nga ekipi Broyden-Fletcher-Goldfarb-Shanno, e zbatuar me konsum të reduktuar të memories për shkak të ngarkimit të pjesshëm të vektorëve nga matrica Hessian. , .COBYLA— MARE Optimization Constrained By Linear Aproximation, optimization constrained me përafrim linear (pa llogaritje gradient). .
Në varësi të metodës së zgjedhur, kushtet dhe kufizimet për zgjidhjen e problemit vendosen ndryshe:
- objekti i klasës
Boundspër metodat L-BFGS-B, TNC, SLSQP, trust-constr; - Lista
(min, max)për të njëjtat metoda L-BFGS-B, TNC, SLSQP, trust-constr; - një objekt ose një listë objektesh
LinearConstraint,NonlinearConstraintpër metodat COBYLA, SLSQP, trust-constr; - fjalor ose listë fjalorësh
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}për metodat COBYLA, SLSQP.
Përmbledhja e artikullit:
1) Merrni parasysh përdorimin e një algoritmi të optimizimit të kushtëzuar në rajonin e besimit (metodë = "trust-constr") me kufizime të specifikuara si objekte Bounds, LinearConstraint, NonlinearConstraint ;
2) Merrni parasysh programimin vijues të katrorëve më të vegjël (metoda =”SLSQP”) me kufizime të specifikuara si fjalor {'type', 'fun', 'jac', 'args'};
3) Analizoni një shembull të optimizimit të produkteve të prodhuara duke përdorur shembullin e një studioje në internet.
Metoda e optimizimit të kushtëzuar = "trust-constr"
Zbatimi i metodës trust-constr bazuar në për probleme me kufizime të formës së barazisë dhe në për problemet me kufizime në formën e pabarazive. Të dyja metodat zbatohen nga algoritme për gjetjen e një minimumi lokal në rajonin e besimit dhe janë të përshtatshme për probleme në shkallë të gjerë.
Formulimi matematikor i problemit të gjetjes së një minimumi në formë të përgjithshme:
Për kufizime strikte të barazisë, kufiri i poshtëm vendoset i barabartë me kufirin e sipërm .
Për një kufizim me një drejtim, është vendosur kufiri i sipërm ose i poshtëm np.inf me shenjën përkatëse.
Le të jetë e nevojshme të gjejmë minimumin e një funksioni të njohur Rosenbrock të dy variablave:
Në këtë rast, kufizimet e mëposhtme vendosen në fushën e përkufizimit të tij:
Në rastin tonë, ekziston një zgjidhje unike në pikën , për të cilat vlejnë vetëm kufizimet e para dhe të katërt.
Le të kalojmë nëpër kufizimet nga poshtë lart dhe të shohim se si mund t'i shkruajmë ato në mënyrë të qartë.
Kufizimet и le ta përcaktojmë duke përdorur objektin Bounds.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Kufizimet и Le ta shkruajmë në formë lineare:
Le t'i përcaktojmë këto kufizime si një objekt LinearConstraint:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Dhe së fundi kufizimi jolinear në formën e matricës:
Ne përcaktojmë matricën Jakobiane për këtë kufizim dhe një kombinim linear të matricës Hessian me një vektor arbitrar :
Tani mund të përcaktojmë një kufizim jolinear si një 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 madhësia është e madhe, matricat mund të specifikohen gjithashtu 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)Gjatë llogaritjes së matricës Hessian kërkon shumë përpjekje, mund të përdorni një klasë . Strategjitë e mëposhtme janë në dispozicion: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessian mund të llogaritet gjithashtu duke përdorur diferencat e fundme:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Matrica Jakobiane për kufizimet mund të llogaritet gjithashtu duke përdorur diferencat e fundme. Megjithatë, në këtë rast matrica Hessian nuk mund të llogaritet duke përdorur diferencat e fundme. Hessian duhet të përcaktohet si një funksion ose duke përdorur klasën HessianUpdateStrategy.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Zgjidhja e problemit të optimizimit duket si kjo:
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` termination condition is satisfied.
Number of iterations: 12, function evaluations: 8, CG iterations: 7, optimality: 2.99e-09, constraint violation: 1.11e-16, execution time: 0.033 s.
[0.41494531 0.17010937]Nëse është e nevojshme, funksioni për llogaritjen e Hessian mund të përcaktohet duke përdorur klasën 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 prodhimi i hesianit dhe një vektori arbitrar përmes parametrit 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)Përndryshe, derivatet e parë dhe të dytë të funksionit që optimizohet mund të përafrohen. Për shembull, Hessian mund të përafrohet duke përdorur funksionin SR1 (përafrim kuazi-njutonian). Gradienti mund të përafrohet me diferenca të fundme.
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)Metoda e optimizimit të kushtëzuar = "SLSQP"
Metoda SLSQP është krijuar për të zgjidhur problemet e minimizimit të një funksioni në formën:
ku и - grupe indeksesh shprehjesh që përshkruajnë kufizime në formën e barazive ose pabarazive. - grupe kufijsh të poshtëm dhe të sipërm për domenin e përcaktimit të funksionit.
Kufizimet lineare dhe jolineare përshkruhen në formën e fjalorëve me çelësa type, fun и 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 për minimumin kryhet si më poshtë:
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)Optimization terminated successfully. (Exit mode 0)
Current function value: 0.34271757499419825
Iterations: 4
Function evaluations: 5
Gradient evaluations: 4
[0.41494475 0.1701105 ]Shembull i optimizmit
Në lidhje me kalimin në strukturën e pestë teknologjike, le të shohim optimizimin e prodhimit duke përdorur shembullin e një studioje në internet, e cila na sjell të ardhura të vogla por të qëndrueshme. Le ta imagjinojmë veten si drejtor i një galerie që prodhon tre lloje produktesh:
- x0 - shitja e faqeve të uljes, nga 10 tr.
- x1 - faqet e internetit të korporatave, nga 20 tr.
- x2 - dyqane online, nga 30 tr.
Ekipi ynë miqësor i punës përfshin katër juniorë, dy të mesëm dhe një të moshuar. Fondi i tyre mujor i kohës së punës:
- Qershor:
4 * 150 = 600 чел * час, - të mesmet:
2 * 150 = 300 чел * час, - senor:
150 чел * час.
Lëreni të riun e parë në dispozicion të shpenzojë (0, 1, 2) orë në zhvillimin dhe vendosjen e një siti të tipit (x10, x20, x30), i mesëm - (7, 15, 20), i moshuar - (5, 10, 15 ) orët e kohës më të mirë të jetës suaj.
Si çdo drejtor normal, ne duam të maksimizojmë fitimet mujore. Hapi i parë drejt suksesit është të shkruani funksionin objektiv value si shuma e të ardhurave nga produktet e prodhuara në muaj:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Ky nuk është një gabim; kur kërkoni për maksimumin, funksioni objektiv minimizohet me shenjën e kundërt.
Hapi tjetër është të ndalojmë punonjësit tanë të punojnë mbi të dhe të vendosim kufizime në orarin e punës:
Çfarë është ekuivalente:
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]])
}Një kufizim formal është që prodhimi i produktit duhet të jetë vetëm pozitiv:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Dhe së fundi, supozimi më rozë është se për shkak të çmimit të ulët dhe cilësisë së lartë, një radhë klientësh të kënaqur vazhdimisht janë në radhë për ne. Ne mund të zgjedhim vetë vëllimet e prodhimit mujor, bazuar në zgjidhjen e problemit të optimizimit të kufizuar 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]Le të rrumbullakohemi lirshëm në numrat e plotë dhe të llogarisim ngarkesën mujore të vozitësve me një shpërndarje optimale të produkteve x = (8, 6, 3) :
- Qershor:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - të mesmet:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Përfundim: në mënyrë që drejtori të marrë maksimumin e tij të merituar, është optimale të krijohen 8 faqe ulje, 6 faqe të mesme dhe 3 dyqane në muaj. Në këtë rast, i moshuari duhet të lërojë pa parë nga makina, ngarkesa e mesit do të jetë afërsisht 2/3, të rinjtë më pak se gjysma.
Përfundim
Artikulli përshkruan teknikat themelore për të punuar me paketën scipy.optimize, përdoret për të zgjidhur problemet e minimizimit të kushtëzuar. Personalisht e përdor scipy thjesht për qëllime akademike, prandaj shembulli i dhënë është i një natyre kaq komike.
Shumë teori dhe shembuj virtualë mund të gjenden, për shembull, në librin e I.L. Akulich "Programimi matematikor në shembuj dhe probleme". Më shumë aplikacion hardcore scipy.optimize për të ndërtuar një strukturë 3D nga një grup imazhesh () mund të shihet në .
Burimi kryesor i informacionit është ata që dëshirojnë të kontribuojnë në përkthimin e këtij dhe seksioneve të tjera scipy Mire se erdhet ne .
Falënderim për pjesëmarrje në përgatitjen e botimit.
Burimi: www.habr.com