
SciPy (izgovara se kao saj paj) je matematiÄki paket temeljen na numpy, koji ukljuÄuje i biblioteke napisane u C i Fortran. Sa SciPy, interaktivna Python sesija postaje jednako snažno okruženje za obradu podataka kao Å”to su MATLAB, IDL, Octave, R ili SciLab.
U ovom Älanku Äemo razmotriti osnovne tehnike matematiÄkog programiranja ā rjeÅ”enja zadataka uvjetne optimizacije za skalarne funkcije viÅ”e varijabli koriÅ”tenjem paketa scipy.optimize. Algoritmi bezuvjetne optimizacije veÄ su razmatrani u . Detaljnije i ažurnije informacije o funkcijama scipy uvijek možete dobiti putem komande help(), Shift+Tab ili na .
Uvod
OpÄi ŠøŠ½ŃŠµŃŃŠµŠ¹Ń za rjeÅ”avanje zadataka, kako uvjetne, tako i bezuvjetne optimizacije u paketu scipy.optimize, osigurava funkcija minimize(). MeÄutim, poznato je da ne postoji univerzalni naÄin za rjeÅ”avanje svih zadataka, stoga izbor odgovarajuÄe metode uvijek pada na ramena istraživaÄa.
OdgovarajuÄi algoritam optimizacije postavlja se putem argumenta funkcije minimize(..., method="").
Za uvjetnu optimizaciju funkcija viÅ”e varijabli dostupne su implementacije sljedeÄih metoda:
trust-constrā pronalaženje lokalnog minimuma u povjereniÄkom podruÄju. , ;SLSQPā sekvencijalno kvadratno programiranje s ograniÄenjima, Newtonova metoda rjeÅ”avanja Lagrangeovog sustava. .TNCā Truncated Newton Constrained, ograniÄen broj iteracija, dobar za nelinearne funkcije s velikim brojem neovisnih varijabli. .L-BFGS-Bā metoda Äetvorke BroydenāFletcherāGoldfarbāShanno, implementirana s smanjenom potroÅ”njom memorije zahvaljujuÄi djelomiÄnom uÄitavanju vektora iz Hessove matrice. , .COBYLAā KOBYLA Constrained Optimization By Linear Approximation, ograniÄena optimizacija s linearnom aproksimacijom (bez izraÄunavanja gradijenta). .
Ovisno o odabranoj metodi, uvjeti i ograniÄenja za rjeÅ”avanje zadatka postavljaju se na razliÄite naÄine:
- objektom klase
Boundsza metode L-BFGS-B, TNC, SLSQP, trust-constr; - popisom
(min, max)za iste metode L-BFGS-B, TNC, SLSQP, trust-constr; - objektom ili popisom objekata
LinearConstraint,NonlinearConstraintza metode COBYLA, SLSQP, trust-constr; - rijeÄnikom ili popisom rjeÄnika
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}za metode COBYLA, SLSQP.
Plan Älanka:
1) Razmotriti primjenu algoritma uvjetne optimizacije u povjerenju (method=Ā»trust-constrĀ») s ograniÄenjima koja su definirana kao objekti Bounds, LinearConstraint, NonlinearConstraint ;
2) Razmotriti sekvencijsko programiranje metodom najmanjih kvadrata (method=Ā»SLSQPĀ») s ograniÄenjima koja su definirana kao rjeÄnik {'type', 'fun', 'jac', 'args'};
3) Razraditi primjer optimizacije proizvodnje na primjeru web studija.
Uvjetna optimizacija method=»trust-constr»
Implementacija metode trust-constr se temelji na za zadatke s ograniÄenjima tipa jednakosti i na za zadatke s ograniÄenjima u obliku nejednakosti. Obje metode su implementirane algoritmima za pretraživanje lokalnog minimuma u povjerenju i dobro su prilagoÄene za velike zadatke.
MatematiÄka formulacija problema pronalaska minimuma u opÄem obliku:



Za ograniÄenja stroge jednakosti donja granica se postavlja jednaka gornjoj
.
Za jednostrano ograniÄenje gornja ili donja granica se postavlja np.inf s odgovarajuÄim znakom.
Pretpostavimo da je potrebno pronaÄi minimum poznate Rosenbrockove funkcije od dvije varijable:

Pri tome su zadana sljedeÄa ograniÄenja na njeno podruÄje definicije:






U naÅ”em sluÄaju postoji jedino rjeÅ”enje u taÄki
, za koju su važeÄa samo prvo i Äetvrto ograniÄenje.
ProÄi Äemo kroz ograniÄenja odozdo prema gore i razmotriti kako ih možemo zapisati u scipy.
OgraniÄenja
i
odrediti pomoÄu objekta Bounds.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])OgraniÄenja
i
zapisati u linearnoj formi:

DefiniraÄemo ta ograniÄenja u obliku objekta LinearConstraint:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])I konaÄno, nekonzistentno ograniÄenje u matriÄnom obliku:

Odredite Jacobijevu matricu za to ograniÄenje i linearne kombinacije Hessove matrice s proizvoljnim vektorom
:


Sada nekonzistentno ograniÄenje možemo definirati kao objekat 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)Ako je dimenzija velika, matrice se mogu zadavati i u rijetkom obliku:
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)ili kao objekat LinearOperator:
iz scipy.sparse.linalg uvozi 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)Kada izraÄunavanje Hesijanove matrice
zahteva velika sredstva, može se koristiti klasa . Dostupne su sledeÄe strategije: BFGS i SR1.
iz scipy.optimize uvozi BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hesijan se takoÄe može izraÄunati pomoÄu konaÄnih razlika:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Jakobijeva matrica za ograniÄenja takoÄe se može izraÄunati pomoÄu konaÄnih razlika. MeÄutim, u ovom sluÄaju, Hesijan se veÄ ne može izraÄunati pomoÄu konaÄnih razlika. Hesijan mora biti definisan u obliku funkcije ili pomoÄu klase HessianUpdateStrategy.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())ReŔenje optimizacijskog problema izgleda ovako:
iz scipy.optimize uvozi minimize
iz scipy.optimize uvozi 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` uslov prekidanja je zadovoljen.
Broj iteracija: 12, evaluacija funkcije: 8, CG iteracije: 7, optimalnost: 2.99e-09, krÅ”enje ograniÄenja: 1.11e-16, vreme izvrÅ”avanja: 0.033 s.
[0.41494531 0.17010937]Ako je potrebno, funkciju za izraÄunavanje hesijana može se definisati pomoÄu klase 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)ili proizvod hesijana i proizvoljnog vektora kroz parametar 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)Alternativno, prva i druga derivacije optimizovane funkcije mogu se približno izraÄunati. Na primer, hesijan se može aproksimirati pomoÄu funkcije SR1 (kvazi-Njutnovskog približavanja). Gradient se može približiti konaÄnim razlikama.
iz scipy.optimize uvozi 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)Uslovna optimizacija method=»SLSQP»
Metod SLSQP je dizajniran za reŔavanje problema minimizacije funkcije u obliku:




Gde
i
ā množine indeksa izraza koji opisuju ograniÄenja u obliku jednakosti ili nejednakosti.
ā mnoÅ”tvo donjih i gornjih granica za domenu funkcije.
Linijska i nelinijska ograniÄenja opisuju se u obliku reÄnika sa kljuÄevima tip, fun i 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])
}Pretraživanje minimuma vrÅ”i se na sledeÄi naÄin:
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)Optimizacija je uspeŔno zavrŔena. (Izlazni režim 0)
Trenutna vrednost funkcije: 0.34271757499419825
Iteracije: 4
Evaluacije funkcije: 5
Evaluacije gradijenta: 4
[0.41494475 0.1701105 ]Primer optimizacije
S obzirom na prelazak na petu tehnoloŔku fazu, razmatramo optimizaciju proizvodnje na primeru veb studija, koja nam donosi mali, ali stabilan prihod. Pretpostavljamo da smo direktori galerije, na kojoj se proizvode tri vrste proizvoda:
- x0 ā prodajni landing page-evi, od 10.000 RSD.
- x1 ā korporativni sajtovi, od 20.000 RSD.
- x2 ā internet prodavnice, od 30.000 RSD.
NaÅ” pravi radni kolektiv ukljuÄuje Äetiri juniora, dva mid-level i jednog seniora. Fond njihovog radnog vremena za mesec:
- juniori:
4 * 150 = 600 Äovek-sati, - mid-level:
2 * 150 = 300 Äovek-sati, - senior:
150 Äovek-sati.
Pretpostavimo da na razvoj i deploy jednog sajta tipa (x0, x1, x2) prvi naiÅ”ao junior mora potroÅ”iti (10, 20, 30) sati, mid-level ā (7, 15, 20), senior ā (5, 10, 15) sati najboljeg vremena svog života.
Kao bilo kojem normalnom direktoru, želimo da maksimiziramo meseÄni profit. Prvi korak ka uspehu ā zapiÅ”emo ciljnu funkciju value kao sumu prihoda od proizvedenih proizvoda tokom meseca:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]To nije greŔka, kada se traži maksimum, ciljna funkcija se minimizira sa obrnutim znakom.
SledeÄi korak ā zabranjujemo prekovremeni rad naÅ”im zaposlenima i uvodimo ograniÄenja na fond radnog vremena:

Å to ekvivalentno ispoljava:

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]])
}Formalna ograniÄenja ā proizvodnja treba biti iskljuÄivo pozitivna:
bnds = Granice ([0, 0, 0], [np.inf, np.inf, np.inf])I konaÄno, najoptimistiÄnija pretpostavka ā zbog niske cijene i visoke kvalitete, stalno se formira red zadovoljnih klijenata. Možemo sami birati mjeseÄne obime proizvodnje proizvoda, u skladu sa rjeÅ”enjem problema uslovne optimizacije sa 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]Nestriktno zaokružimo na cijele brojeve i izraÄunajmo mjeseÄno optereÄenje Äamaca prema optimalnoj raspodjeli proizvoda x = (8, 6, 3) :
- juniori:
8 * 10 + 6 * 20 + 3 * 30 = 290 ljudi * sati; - mid-level:
8 * 7 + 6 * 15 + 3 * 20 = 206 ljudi * sati; - senior:
8 * 5 + 6 * 10 + 3 * 15 = 145 ljudi * sati.
ZakljuÄak: da bi direktor dobio svoj zasluženi maksimum, optimalno je raditi 8 odrediÅ”nih stranica, 6 srednjih web stranica i 3 prodavnice mjeseÄno. Senior bi pritom trebao raditi bez odmora, optereÄenje midlevel-a Äe iznositi otprilike 2/3, a junior manje od polovine.
ZakljuÄak
U Älanku su izložene osnovne tehnike rada sa paketom scipy.optimize, koriÅ”tene za rjeÅ”avanje problema uslovne minimizacije. Ja liÄno koristim scipy iskljuÄivo u akademske svrhe, pa je dati primjer viÅ”e Å”ale.
Mnogo teorije i primjera u WinRAR-u možete pronaÄi, primjerice, u knjizi I.L.Akulicha āMatematiÄko programiranje kroz primjere i zadatkeā. O ozbiljnijoj primjeni scipy.optimize za izradu 3D struktura na osnovu skupa slika () možete pogledati u .
Glavni izvor informacija ā , oni koji žele doprinijeti prijevodu ovog i drugih odjeljaka scipy dobrodoÅ”li na .
Hvala za uÄeÅ”Äe u pripremi publikacije.
Izvor: habr.com
