SciPy (hääldatakse sai pie) on numpy-põhine matemaatikapakett, mis sisaldab ka C- ja Fortrani teeke. SciPy muudab teie interaktiivse Pythoni seansi täielikuks andmeteaduse keskkonnaks, nagu MATLAB, IDL, Octave, R või SciLab.
Selles artiklis vaatleme matemaatilise programmeerimise põhitehnikaid – mitme muutuja skalaarfunktsiooni tingimusliku optimeerimise ülesannete lahendamist paketi scipy.optimize abil. Piiramatuid optimeerimisalgoritme on juba käsitletud . Üksikasjalikumat ja ajakohasemat abi scipy funktsioonide kohta saab alati kasutades käsku help(), Shift+Tab või .
Sissejuhatus
Ühise liidese nii tingimuslike kui ka piiramatute optimeerimisprobleemide lahendamiseks paketi scipy.optimize pakub funktsioon minimize(). Siiski on teada, et universaalset meetodit kõigi probleemide lahendamiseks ei ole olemas, seega langeb adekvaatse meetodi valik, nagu ikka, uurija õlgadele.
Sobiv optimeerimisalgoritm määratakse funktsiooni argumendi abil minimize(..., method="").
Mitme muutuja funktsiooni tingimuslikuks optimeerimiseks on saadaval järgmised meetodid:
trust-constr— otsida usalduspiirkonnas kohalikku miinimumi. , ;SLSQP— järjestikune ruutprogrammeerimine piirangutega, Newtoni meetod Lagrange'i süsteemi lahendamiseks. .TNC- Kärbitud Newton Piiratud, piiratud arv iteratsioone, sobib mittelineaarsete funktsioonide jaoks, millel on suur hulk sõltumatuid muutujaid. .L-BFGS-B— Broyden-Fletcher-Goldfarb-Shanno meeskonna meetod, mida rakendati Hesse maatriksist vektorite osalise laadimise tõttu vähendatud mälutarbimisega. , .COBYLA— MARE piiratud optimeerimine lineaarse lähendusega, piiratud optimeerimine lineaarse lähendusega (ilma gradiendi arvutamiseta). .
Sõltuvalt valitud meetodist seatakse probleemi lahendamise tingimused ja piirangud erinevalt:
- klassi objekt
Boundsmeetodite jaoks L-BFGS-B, TNC, SLSQP, trust-constr; - nimekiri
(min, max)samade meetodite jaoks L-BFGS-B, TNC, SLSQP, trust-constr; - objekt või objektide loend
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, trust-constr meetodite jaoks; - sõnastik või sõnaraamatute loend
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP meetodite jaoks.
Artikli ülevaade:
1) Kaaluge tingimusliku optimeerimisalgoritmi kasutamist usalduspiirkonnas (method=”trust-constr”) koos objektidena määratud piirangutega Bounds, LinearConstraint, NonlinearConstraint ;
2) Kaaluge järjestikust programmeerimist, kasutades vähimruutude meetodit (meetod = "SLSQP"), mille piirangud on määratletud sõnastiku kujul {'type', 'fun', 'jac', 'args'};
3) Analüüsige valmistatud toodete optimeerimise näidet veebistuudio näitel.
Tingimuslik optimeerimismeetod="trust-constr"
Meetodi rakendamine trust-constr põhineb võrdõiguslikkuse vormi piirangutega seotud probleemide puhul ja edasi ebavõrdsuse kujul esinevate piirangutega seotud probleemide jaoks. Mõlemat meetodit rakendavad usalduspiirkonnas lokaalse miinimumi leidmise algoritmid ja need sobivad hästi suuremahuliste probleemide lahendamiseks.
Üldkujul miinimumi leidmise ülesande matemaatiline sõnastus:
Rangete võrdsuse piirangute korral määratakse alumine piir võrdseks ülemise piiriga .
Ühesuunalise piirangu jaoks määratakse ülemine või alumine piir np.inf vastava märgiga.
Olgu vaja leida kahe muutuja teadaoleva Rosenbrocki funktsiooni miinimum:
Sel juhul on selle määratluspiirkonnale seatud järgmised piirangud:
Meie puhul on punktis ainulaadne lahendus , mille puhul kehtivad ainult esimene ja neljas piirang.
Vaatame piirangud alt üles ja vaatame, kuidas neid scipy keeles kirjutada.
Piirangud и defineerime selle objekti Piirid kasutades.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Piirangud и Kirjutame selle lineaarsel kujul:
Määratleme need piirangud LinearConstraint objektina:
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:
Selle piirangu jaoks määratleme Jacobi maatriksi ja Hesse maatriksi lineaarse kombinatsiooni suvalise vektoriga :
Nüüd saame objektina määratleda mittelineaarse piirangu 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 maatriksid määrata ka hõredalt:
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 objektina 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)Hesse maatriksi arvutamisel nõuab palju pingutust, saate kasutada klassi . Saadaval on järgmised strateegiad: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hesseni saab arvutada ka lõplike erinevuste abil:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Piirangute Jacobi maatriksit saab arvutada ka lõplike erinevuste abil. Kuid sel juhul ei saa Hessi maatriksit lõplike erinevuste abil arvutada. Hessian peab olema defineeritud funktsioonina või kasutades klassi HessianUpdateStrategy.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Optimeerimisprobleemi lahendus 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` 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]Vajadusel saab Hessi arvutamise funktsiooni defineerida 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 Hessi ja suvalise vektori korrutis 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 saab optimeeritava funktsiooni esimest ja teist tuletist ligikaudselt hinnata. Näiteks Hesseni saab ligikaudselt määrata funktsiooni abil SR1 (kvaasi-Newtoni lähendus). Gradienti saab ligikaudselt hinnata lõplike erinevustega.
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)Tingimuslik optimeerimismeetod = SLSQP
SLSQP meetod on mõeldud funktsiooni minimeerimise probleemide lahendamiseks järgmisel kujul:
kus и — avaldiste indeksite komplektid, mis kirjeldavad piiranguid võrdsuse või ebavõrdsuse kujul. — funktsiooni määratluspiirkonna alumiste ja ülemiste piiride komplektid.
Lineaarseid ja mittelineaarseid piiranguid kirjeldatakse võtmetega sõnaraamatute kujul 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])
}Miinimumi otsimine toimub järgmiselt:
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 ]Optimeerimise näide
Seoses üleminekuga viiendale tehnoloogilisele struktuurile vaatame veebistuudio näitel tootmise optimeerimist, mis toob meile väikese, kuid stabiilse sissetuleku. Kujutagem end ette kolme tüüpi tooteid tootva kambüüsi direktorina:
- x0 - maandumislehtede müük, alates 10 tr.
- x1 - ettevõtete veebisaidid, alates 20 tr.
- x2 - veebipoed, alates 30 tr.
Meie sõbralikus kollektiivis on neli juuniorit, kaks keskmist ja üks seenior. Nende igakuine tööajafond:
- juunid:
4 * 150 = 600 чел * час, - keskmised:
2 * 150 = 300 чел * час, - senor:
150 чел * час.
Laske esimesel juunioril kulutada (0, 1, 2) tunde ühe tüüpi (x10, x20, x30), keskmise (7, 15, 20), vanem (5, 10, 15) saidi arendamiseks ja kasutuselevõtuks. ) tundi oma elu parimast ajast.
Nagu iga tavaline direktor, tahame ka meie igakuist kasumit maksimeerida. Esimene samm edu saavutamiseks on eesmärgifunktsiooni üleskirjutamine value tulu summana toodetud toodetest kuus:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]See ei ole viga, maksimumi otsimisel minimeeritakse sihtfunktsioon vastupidise märgiga.
Järgmise sammuna keelame oma töötajatel ületöötamise ja kehtestame tööaja piirangud:
Mis on samaväärne:
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]])
}Formaalne piirang on see, et toote väljund peab olema ainult positiivne:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Ja lõpuks on kõige roosilisem oletus, et madala hinna ja kõrge kvaliteedi tõttu on meie jaoks pidevalt järjekord rahulolevatest klientidest. Igakuised tootmismahud saame ise valida, lähtudes piiratud optimeerimisprobleemi 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]Ümardame lõdvalt täisarvudeks ja arvutame optimaalse tootejaotusega sõudjate kuukoormuse x = (8, 6, 3) :
- juunid:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - keskmised:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Järeldus: selleks, et direktor saaks oma väljateenitud maksimumi, on optimaalne luua kuus 8 sihtlehte, 6 keskmise suurusega saiti ja 3 kauplust. Sel juhul peab seenior kündma ilma masinalt üles vaatamata, keskmiste koormus jääb ligikaudu 2/3, juunioritel alla poole.
Järeldus
Artiklis kirjeldatakse paketiga töötamise põhivõtteid scipy.optimize, mida kasutatakse tingimusliku minimeerimise probleemide lahendamiseks. Isiklikult kasutan scipy puhtalt akadeemilistel eesmärkidel, mistõttu on toodud näide nii koomilist laadi.
Palju teooriat ja virtuaalseid näiteid võib leida näiteks I. L. Akulichi raamatust “Matemaatika programmeerimine näidetes ja probleemides”. Rohkem hardcore rakendust scipy.optimize piltide komplektist 3D-struktuuri loomiseks () saab vaadata .
Peamine teabeallikas on need, kes soovivad anda oma panuse selle ja teiste osade tõlkimisse scipy Tere tulemast .
Tänan väljaande koostamises osalemise eest.
Allikas: www.habr.com