SciPy (prononcohet si sai pai) është një paketë matemaatike e bazuar në numpy, që përfshin gjithashtu biblioteka në C dhe Fortran. Me SciPy, seanca interaktive Python kthehet në një ambient të plotë të përpunimit të 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 ndĂ«rlidhĂ«s pĂ«r njĂ« funksion skalar me disa variabla duke pĂ«rdorur paketĂ«n scipy.optimize. Algoritmet e optimizimit tĂ« pakufizuar janĂ« shqyrtuar tashmĂ« nĂ« . MĂ« shumĂ« informacion dhe udhĂ«zime tĂ« detajuara rreth funksioneve scipy gjithmonĂ« mund tĂ« merrni me komandĂ«n help(), Shift+Tab ose nĂ« .
Hyrje
Interfejsi i përgjithshëm për zgjidhjen e problemeve si të optimizimit ndërlidhës, ashtu dhe të pakufizuar ofrohet nga funksioni minimize(). Megjithatë, është e njohur se nuk ekziston një mënyrë universale për të zgjidhur të gjitha problemet, prandaj zgjedhja e metodës së duhur gjithmonë bie mbi shpatullat e hulumtuesit.
Algoritmi i përshtatshëm të optimizimit përcaktohet nga argumenti i funksionit minimize(..., method="").
Për optimizimin ndërlidhës të një funksioni me disa variabla, janë të disponueshme implementime të metodave të mëposhtme:
trust-constrâ kĂ«rkimi i minimumit lokal nĂ« njĂ« zonĂ« besimi. , ;SLSQPâ programim katror tĂ« radhĂ«s me kufizime, metoda e Newton-it pĂ«r zgjidhjen e sistemit Lagrange. .TNCâ Truncated Newton Constrained, numĂ«r i kufizuar iteraciones, i mirĂ« pĂ«r funksione jo-lineare me shumĂ« variabla tĂ« pavarur. .L-BFGS-Bâ metoda nga katĂ«rshja BroydenâFletcherâGoldfarbâShanno, e realizuar me konsum mĂ« tĂ« ulĂ«t tĂ« memories pĂ«rmes ngarkimit tĂ« pjesshĂ«m tĂ« vektorĂ«ve nga matrica Hessian. , .COBYLAâ KOBYLA Constrained Optimization By Linear Approximation, optimizim i kufizuar me aproximim linear (pa llogaritjen e gradientit). .
Në varësi të metodës së zgjedhur, kushtet dhe kufizimet për zgjidhjen e problemit përcaktohen ndryshe:
- objekti i klasës
Boundspër metodat L-BFGS-B, TNC, SLSQP, trust-constr; - lista
(min, max)për këto metoda të njëjta L-BFGS-B, TNC, SLSQP, trust-constr; - objekti ose lista e objekteve
LinearConstraint,NonlinearConstraintpër metodat COBYLA, SLSQP, trust-constr; - fjalori ose lista e fjalorëve
{'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 të kushtëzuar në zonën e besueshme (method=»trust-constr») me kufizime të përcaktuara si objekte Bounds, LinearConstraint, NonlinearConstraint ;
2) Të shqyrtohet programimi sekondar me metodën e katrorëve të minimalit (method=»SLSQP») me kufizime të përcaktuara si fjalor {'type', 'fun', 'jac', 'args'};
3) Të shqyrtohet një shembull optimizimi të prodhimit në shembullin e një studiot të uebit.
Optimización e kushtëzuar method=»trust-constr»
Implementimi i metodës trust-constr bazohet në për problemet me kufizime të barazisë dhe mbi për problemet me kufizime si pabarazi. Të dy metodat implementohen nga algoritmet e kërkimit të minimumeve lokale në zonën e besueshme dhe përshtaten mjaft mirë për problemet me shkallë të madhe.
Formulimi matematikor i problemit të kërkimit të minimumeve në formën e përgjithshme:
Për kufizimet e barazisë të rreptë, kufiri i poshtëm vendoset të barabartë me atë të sipërm 
.
Për kufizim njëanësh, kufiri i sipërm ose poshtëm vendoset np.inf me shenjën përkatëse.
Supozoni se duhet të gjendet minimumi i funksionit të njohur të Rosenbrock nga dy variabla:
Në këtë rast janë vendosur kufizimet e mëposhtme në fushën e saj të përkufizimit:
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ërta.
Të kalojmë përmes kufizimeve nga poshtë lart dhe të shqyrtojmë se si mund t'i shkruajmë ato në scipy.
Kufizimet 
dhe 
do të përcaktohen me ndihmën e objektit Bounds.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Kufizimet 
dhe 
të shkruajmë në formë lineare:
Të përcaktojmë këto kufizime si objekt LinearConstraint:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Dhe në fund, kufizimi jo-linear në formën matrike:
Të përcaktojmë matricën Jacobin për këtë kufizim dhe kombinimin linear të matricës Hessian me një vektor arbitrar 
:
Tani, kufizimin jo-linear mund ta përcaktojmë 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 gjithashtu në formë të sparse:
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ë llogaritja e matricës Hessian 
duhet shpenzime të mëdha, mund të përdoret klasa . Strategjitë e mëposhtme janë disponibile: BFGS dhe SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessian gjithashtu mund të llogaritet duke përdorur diferencat e fundit:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Matricën Jakobian për kufizimet gjithashtu mund ta llogarisim me anë të diferencave të fundit. Megjithatë, në këtë rast, matrica Hessian nuk mund të llogaritet me diferenca të fundit. Hessian duhet të definohet si një funksion ose me anë të 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 ndaljes është plotësuar.
Numri i iteracioneve: 12, vlerësime të funksionit: 8, iteracione CG: 7, optimaliteti: 2.99e-09, shkelja e kufizimeve: 1.11e-16, koha e ekzekutimit: 0.033 s.
[0.41494531 0.17010937]Nëse është e nevojshme, funksioni për llogaritjen e Hessian mund të definohet 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)apo produkti i 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 të optimizuar mund të llogariten në mënyrë afërsish. Për shembull, Hessian mund të aproksimohet me anë të funksionit SR1 (afërsimi quasi-Newtown). Gradienti mund të aproksohet me diferenca të fundit.
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 kushtor method=»SLSQP»
Metoda SLSQP është e destinuar për të zgjidhur problemet e minimizimit të funksionit në formën e:
Ku 
dhe 
â shumĂ« indekse tĂ« shprehjeve, qĂ« pĂ«rshkruajnĂ« kufizimet nĂ« formĂ«n e barazimeve ose pabarazimeve. 
â shumĂ« kufij tĂ« poshtĂ«m dhe tĂ« sipĂ«rm pĂ«r territorin e funksionit.
Kufizimet lineare dhe jolineare përshkruhen në formën e fjalorëve me çelësa lloji, fun 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 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)Optimizimi përfundoi me sukses. (Modaliteti i daljes 0)
Vlera aktuale e funksionit: 0.34271757499419825
Iteracione: 4
Vlerësime të funksionit: 5
Vlerësime të gradientit: 4
[0.41494475 0.1701105 ]Shembulli i optimizimit
Me kalimin në të pestin teknologjik, le të shqyrtojmë optimizimin e prodhimit në shembullin e një studioje web, e cila na sjell një të ardhur të vogël, por stabile. Le të imagjinojmë se jemi drejtori i një galerie, ku prodhohen tri lloje produktesh:
- x0 â faqe shiste, nga 10 mijĂ« lekĂ«.
- x1 â faqe korporate, nga 20 mijĂ« lekĂ«.
- x2 â dyqane online, nga 30 mijĂ« lekĂ«.
Ekipi ynë i punës përbëhet nga katër juniorë, dy mid-level dhe një senior. Fondi i orëve të punës për muajin:
- juniorët:
4 * 150 = 600 orë punë, - mid-level:
2 * 150 = 300 orë punë, - senior:
150 orë punë.
Supozoni qĂ« pĂ«r zhvillimin dhe vendosjen e njĂ« faqeje tĂ« tipit (x0, x1, x2) njĂ« junior duhet tĂ« shpenzojĂ« (10, 20, 30) orĂ«, mid-level â (7, 15, 20), senior â (5, 10, 15) orĂ« tĂ« kohĂ«s mĂ« tĂ« mirĂ« tĂ« jetĂ«s sĂ« tij.
Si çdo drejtori normal, ne duam tĂ« maksimizojmĂ« fitimin e pĂ«rmuajshĂ«m. Hapi i parĂ« pĂ«r suksesin â shkruajmĂ« funksionin e synuar vlera si shumĂ«n e tĂ« ardhurave nga produktet e prodhuara pĂ«r muajin:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Kjo nuk është një gabim, në kërkimin për maksimumin funksioni i synuar minimizohet me shenjën e kundërt.
Hapi i ardhshĂ«m â ndalojmĂ« punonjĂ«sit tanĂ« qĂ« tĂ« punojnĂ« mĂ« shumĂ« dhe vendosim kufizime mbi fondin e orĂ«ve tĂ« punĂ«s:
E cila ë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]])
}Kufiri formale â prodhimi duhet tĂ« jetĂ« vetĂ«m pozitiv:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Dhe nĂ« fund, supozimi mĂ« roza â pĂ«r shkak tĂ« çmimit tĂ« ulĂ«t dhe cilĂ«sisĂ« sĂ« lartĂ«, ne gjithmonĂ« 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 problemit tĂ« optimizimit tĂ« kushtĂ«zuar me 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ë rrumbullakosim në mënyrë të thjeshtë në numra të plotë dhe të llogarisim ngarkesën mujore të rrembuesve në përputhje me disponimin optimal të produkteve x = (8, 6, 3) :
- juniorët:
8 * 10 + 6 * 20 + 3 * 30 = 290 persona * orë; - mid-level:
8 * 7 + 6 * 15 + 3 * 20 = 206 persona * orë; - senior:
8 * 5 + 6 * 10 + 3 * 15 = 145 persona * orë.
Përfundimi: për të siguruar që drejtori të marrë maksimumin e merituar, është optimale të bëjmë në muaj 8 landing pages, 6 faqe mesatare dhe 3 dyqane. Seniori duhet të punojë pa pushim, ngarkesa e mid-levelëve do të jetë rreth 2/3, ndërsa juniorët më pak se gjysma.
PĂ«rfundim
Artikulli paraqet teknikate kryesore të punës me paketën scipy.optimize, të përdorura për zgjidhjen e problemeve të minimizimit të kushtëzuar. Personal, unë përdor scipy për qëllime krejt akademike, prandaj shembulli i dhënë ka një karakter shaka.
Shumë teori dhe shembuj fituar mund të gjenden, për shembull, në librin e I.L. Akulic «Programimi matematikor në shembuj dhe probleme». Një përdorim më të avancuar scipy.optimize për ndërtimin e strukturës 3D nga një set imazhesh () mund të shikohet në .
Burimi kryesor i informacionit është , ata që duan të kontribuojnë në përkthimin e këtij dhe seksioneve të tjera scipy janë të mirëpritur në .
anonim kommentatorit për pjesëmarrjen në përgatitjen e publikimit.
Burimi: habr.com
