SciPy (hÀÀldatakse kui sai pai) on NumPy-l pÔhinev matemaatika pakett, mis sisaldab ka C ja Fortrani raamatukogusid. SciPy muudab interaktiivse Python-seansi sama tÀielikuks andmete töötlemise keskkonnaks nagu MATLAB, IDL, Octave, R vÔi SciLab.
Selles artiklis kĂ€sitleme matemaatilise programmeerimise peamisi tehnikaid â tingimusliku optimeerimise probleemide lahendamine mitme muutuja skalaari funktsiooni jaoks scipy.optimize paketi abil. Tingimusteta optimeerimise algoritmid on juba kĂ€sitletud . TĂ€iendavat ja ajakohast teavet scipy funktsioonide kohta saab alati kĂ€ivitada kĂ€suga help(), Shift+Tab vĂ”i .
Sissejuhatus
scipy.optimize paketi ĂŒlesannete lahendamiseks on ĂŒldine liides, mida pakub funktsioon minimize(). Kuid on teada, et universaalset meetodit kĂ”igi probleemide lahendamiseks ei eksisteeri, seega langeb sobiva meetodi valik nagu alati uurija Ă”lgadele.
Sobiv optimeerimisalgoritm mÀÀratakse funktsiooni argumendi abil minimize(..., method="").
Tingimusliku optimeerimise jaoks mitme muutuja funktsiooni puhul on kergesti rakendatavad jÀrgmised meetodid:
trust-constrâ lokaal minima leidmine usaldusvÀÀrses piirkonnas. , ;SLSQPâ piiratud jĂ€rjestikune kvadratiivne programmeerimine, Newtoni meetod Lagrange'i sĂŒsteemi lahendamiseks. .TNCâ Truncated Newton Constrained, piiratud iteratsioonide arv, sobib suure hulga sĂ”ltumatute muutujaid omavate mittelineaarsete funktsioonide jaoks. .L-BFGS-Bâ BroydenâFletcherâGoldfarbâShanno meetod, rakendatud vĂ€iksema mĂ€lu tarbimisega, kasutades osalist matriitsi Hess'i vektorite laadimist. , .COBYLAâ KOBYLA piiratud optimeerimine lineaarse lĂ€henemise abil (ilma gradientide arvutamiseta). .
SÔltuvalt valitud meetodist mÀÀratakse probleemile lahenduse tingimused ja piirangud erinevalt:
- klass
Boundsmeetodite jaoks L-BFGS-B, TNC, SLSQP, trust-constr; - nimekirja
(min, max)samaksite meetodite L-BFGS-B, TNC, SLSQP, trust-constr jaoks; - objekti vÔi objekti nimekirja
LinearConstraint,NonlinearConstraintmeetodite jaoks COBYLA, SLSQP, trust-constr; - sÔnastiku vÔi sÔnastike nimekirja
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}meetodite COBYLA, SLSQP jaoks.
Artikli plaan:
1) Uurida tingimuslikku optimeerimise rakendust usaldusvÀÀrses valdkonnas (method=»trust-constr») tingimustega, mis on mÀÀratletud objektidena. Bounds, LinearConstraint, NonlinearConstraint ;
2) Uurida jÀrjestikust programmeerimist vÀikseimade ruutude meetodil (method=»SLSQP») tingimustega, mis on mÀÀratletud sÔnastikuna. {'type', 'fun', 'jac', 'args'};
3) AnalĂŒĂŒsida tooteoptimeerimise nĂ€idet veebistuudio kontekstis.
Tingimuslik optimeerimine method=»trust-constr»
Meetodi rakendamine trust-constr tugineb vÔrdsuspiirangute probleemide jaoks ja ebavÔrdsuspiirangute probleemide jaoks. MÔlemad meetodid on ellu viidud usaldusvÀÀrse piirkonna kohalikku miinimumi otsimise algoritmidega ja sobivad hÀsti suuremahuliste probleemide jaoks.
Matemaatiline ĂŒlesehitus miinimumi otsimise probleemist ĂŒldiselt:
Tuginedes rangete vĂ”rduspiirangute puhul, seadke alumine piir vĂ”rdsena ĂŒlemisega. 
.
Ăhepoolse piirangu korral seotakse ĂŒlemine vĂ”i alumine piir np.inf vastava mĂ€rgiga.
Oletame, et on vajalik leida miinimum Rosenbrooki funktsioonist, mis sÔltub kahest muutuja:
Sellest lÀhtuvalt on mÀÀratud jÀrgmised piirangud tema mÀÀratlemise valdkonnale:
Meil on antud juhtum, kus on ainult ĂŒks lahendus punktis 
, millele kehtivad ainult esimene ja neljas piirang.
LĂ€heme piirangutest alt ĂŒles ja vaatame, kuidas saame neid scipy-s vĂ€ljendada.
Piirangud 
ja 
mÀÀra objekti Bounds abil.
from scipy.optimize import Bounds
bounds = Bounds([0, -0.5], [1.0, 2.0])Piirangud 
ja 
vÀljendame lineaarse vormina:
MÀÀrame need piirangud LinearConstraint objekti kujul:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Ja lÔpuks mittelineaarne piirang maatriksi kujul:
MÀÀra selle piirangu Jakobian maatriks ja Hesseni maatriksi lineaarne kombinatsioon suvalise vektoriga 
:
NĂŒĂŒd saame mittelineaarse piirangu mÀÀrata objekti 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)Kui suurus on suur, saab maatrikseid mÀÀrata ka haruldases vormis:
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)vÔi objekti kujul 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)Kui Hesse'i maatriksi arvutamine 
nÔuab suuri ressursse, vÔib kasutada klassi . Saadaval on jÀrgmised strateegiad: BFGS ja SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hesse'i maatriksit saab samuti arvutada lÔppude diferentsidega:
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac='2-point', hess='2-point')Jakobi maatriksi piirangute jaoks saab samuti arvutada lÔppude diferentsidega. Kuid sel juhul Hesse'i maatriksit lÔppude diferentsidega enam ei arvutada. Hesse'i peab mÀÀrama funktsiooni kaudu vÔi klassi HessianUpdateStrategy abil.
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac='2-point', hess=BFGS())Optimeerimisprobleemi lahendamine nÀeb vÀlja jÀrgmine:
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` tÀitmise tingimus on tÀidetud.
Iteratsioonide arv: 12, funktsiooni hindamised: 8, CG iteratsioonid: 7, optimaalsus: 2.99e-09, piirangu rikkumine: 1.11e-16, tÀitmise aeg: 0.033 s.
[0.41494531 0.17010937]Vajadusel saab Hessiani arvutamise funktsiooni mÀÀrata klassi LinearOperator abil.
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)vÔi Hessiani ja suvalise vektori korrutamine parameetri kaudu. 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)Alternatiivselt vÔivad optimeeritava funktsiooni esimesed ja teised tuletised olla ligikaudsed. NÀiteks vÔib gessiaan olla ligikaudne funktsiooni abil. SR1 (kvasi-Newtoni ligikaudse kaudu). Gradient vÔib olla ligikaudne lÔpphindadega.
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)Konditsionaalne optimeerimine method=»SLSQP»
SLSQP meetod on mÔeldud funktsiooni minimeerimise probleemide lahendamiseks jÀrgmisel kujul:
Kus 
ja 
â hulk indekseid, mis kirjeldavad piiranguid vĂ”rduste vĂ”i ebavĂ”rdsustena. 
â hulk alumisi ja ĂŒlemisi piire funktsiooni mÀÀramispiirkonna jaoks.
Lineaarseid ja mittelineaarseid piiranguid kirjeldatakse diktsiooni kaudu, mille vÔtmed on type, lÔbu. ja 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])
}Minima otsimine toimub jÀrgmisel viisil:
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)Optimeerimine lĂ”petati edukalt. (VĂ€ljundreĆŸiim 0)
Praegune funktsiooni vÀÀrtus: 0.34271757499419825
Iteratsioonid: 4
Funktsiooni hindamised: 5
Gradientide hindamised: 4
[0.41494475 0.1701105 ]Optimeerimise nÀidis
Viies tehnoloogiline revolutsioon toob endaga kaasa vajaduse tootmise optimeerimise ĂŒlevaatuses, kasutades nĂ€itena webistuudiot, mis annab meile vĂ€ikese, kuid stabiilse sissetuleku. Kujutame ette, et me oleme galeri juhi, kus toodetakse kolme tĂŒĂŒpi tooteid:
- x0 â mĂŒĂŒvad maandumised, alates 10 000 RUB.
- x1 â ettevĂ”tte veebisaidid, alates 20 000 RUB.
- x2 â e-poed, alates 30 000 RUB.
Meie sĂ”bralik meeskond koosneb neljast algajast, kahest keskastmest ja ĂŒhest kogenud spetsialistist. Nende tööaeg kuus:
- algajad:
4 * 150 = 600 töötundi, - keskastmed:
2 * 150 = 300 töötundi, - kogenud spetsialist:
150 töötundi.
Oletame, et ĂŒhe veebisaidi tĂŒĂŒbi (x0, x1, x2) arendamiseks ja juurutamiseks peab esimene juhuslik algaja kulutama (10, 20, 30) tundi, keskastme spetsialist â (7, 15, 20), kogenud spetsialist â (5, 10, 15) tundi oma parimat elu.
Nagu igale normaalsele juhile, tahame ka meie maksimeerida kuu kasumit. Esimene samm edule â kirja paneme sihtfunktsiooni value toodetesse kuu jooksul teenitud tulude summana:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]See ei ole viga, sihtfunktsiooni maksimaalse otsimise kÀigus minimeeritakse negatiivse mÀrkiga.
JĂ€rgmiseks sammuks on keelata oma töötajatele ĂŒletöötamine ja kehtestada piirangud tööaja fondile:
See on ekvivalentne:
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]])
}Aformaalne piirang â toodangu vĂ€ljund peab olema ainult positiivne:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Ja viimaseks see kĂ”ige roosilisem eeldus â madala hinna ja kĂ”rge kvaliteedi tĂ”ttu seisab meie juurde pidevalt jĂ€rjekord rahulolevatest klientidest. Me saame ise valida igakuiseid tootmismahte, lĂ€htudes tingimuste optimeerimise arvutuste lahendamisest: 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]LĂ€hme mitte rangelt ĂŒmmardama tĂ€isarvudeni ja arvutame maksimaalse tsĂŒkli kuukoormuse, kui tooted on optimaalselt jaotatud. x = (8, 6, 3) :
- algajad:
8 * 10 + 6 * 20 + 3 * 30 = 290 inimene * tund; - keskastmed:
8 * 7 + 6 * 15 + 3 * 20 = 206 inimene * tund; - kogenud spetsialist:
8 * 5 + 6 * 10 + 3 * 15 = 145 inimene * tund.
JÀreldus: et direktor saaks oma teenitud maksimumi, on optimaalne kuus teha 8 maandumislehte, 6 keskmist saiti ja 3 poodi. Vanem peab samal ajal töötama katkematult, nooremate koormus ulatub umbes 2/3, noori vÀhem kui pool.
KokkuvÔte
Artiklis on vÀlja toodud peamised tehnikaid paketi scipy.optimize, mida kasutatakse tingimusliku minimeerimise probleemide lahendamiseks. Isiklikult kasutan ma scipy puhtalt akadeemilistel eesmÀrkidel, seega on antud nÀide sellises naljakas vormis.
Palju teooriat ja rariteetseid nĂ€iteid vĂ”ib leida nĂ€iteks I.L. Akulichi raamatust âMatemaatiline programmeerimine nĂ€idete ja ĂŒlesannete kauduâ. TĂ”sisema rakenduse scipy.optimize 3D struktuuri loomiseks pildihulgast () saab vaadata .
Peamine teabeallikas on , soovijad tÔlkida seda ja teisi osi scipy teretulnud .
AitÀh osalusele avaldamise ettevalmistamisel.
Allikas: habr.com
