SciPy (borið fram sai pie) er stærðfræðipakki sem byggir á numpy sem inniheldur einnig C og Fortran bókasöfn. SciPy breytir gagnvirku Python-lotunni þinni í fullkomið gagnafræðiumhverfi eins og MATLAB, IDL, Octave, R eða SciLab.
Í þessari grein munum við skoða grunntækni stærðfræðilegrar forritunar - að leysa skilyrt hagræðingarvandamál fyrir stigstærðfall af nokkrum breytum með því að nota scipy.optimize pakkann. Óþvinguð hagræðingaralgrím hefur þegar verið rædd í . Ítarlegri og uppfærðari hjálp um scipy aðgerðir er alltaf hægt að fá með help() skipuninni, Shift+Tab eða í .
Inngangur
Sameiginlegt viðmót til að leysa bæði skilyrt og óþvinguð hagræðingarvandamál í scipy.optimize pakkanum er veitt af aðgerðinni minimize(). Hins vegar er vitað að það er engin alhliða aðferð til að leysa öll vandamál, þannig að val á fullnægjandi aðferð, eins og alltaf, fellur á herðar rannsakandans.
Viðeigandi hagræðingaralgrím er tilgreint með því að nota fallrök minimize(..., method="").
Til skilyrtrar hagræðingar á falli nokkurra breyta eru útfærslur á eftirfarandi aðferðum tiltækar:
trust-constr— leitaðu að staðbundnu lágmarki á sjálfstraustssvæðinu. , ;SLSQP— raðbundin fjórðungsforritun með takmörkunum, Newtonsk aðferð til að leysa Lagrange kerfið. .TNC- Styttur Newton takmarkaður, takmarkaður fjöldi endurtekningar, góður fyrir ólínuleg föll með miklum fjölda óháðra breyta. .L-BFGS-B— aðferð frá Broyden–Fletcher–Goldfarb–Shanno teyminu, útfærð með minni minnisnotkun vegna hlutahleðslu vigra úr Hessian fylkinu. , .COBYLA— MARE bundin hagræðing með línulegri nálgun, takmörkuð hagræðing með línulegri nálgun (án hallaútreiknings). .
Það fer eftir valinni aðferð, skilyrði og takmarkanir til að leysa vandamálið eru settar á annan hátt:
- flokks hlutur
Boundsfyrir aðferðir L-BFGS-B, TNC, SLSQP, trust-constr; - listinn
(min, max)fyrir sömu aðferðir L-BFGS-B, TNC, SLSQP, trust-constr; - hlutur eða lista yfir hluti
LinearConstraint,NonlinearConstraintfyrir COBYLA, SLSQP, trust-constr aðferðir; - orðabók eða lista yfir orðabækur
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}fyrir COBYLA, SLSQP aðferðir.
Yfirlit greinar:
1) Íhugaðu notkun skilyrts hagræðingaralgríms á traustasvæðinu (aðferð = "trust-constr") með takmörkunum sem eru tilgreindar sem hlutir Bounds, LinearConstraint, NonlinearConstraint ;
2) Íhugaðu raðbundna forritun með því að nota minnstu ferningsaðferðina (aðferð = "SLSQP") með takmörkunum sem tilgreindar eru í formi orðabókar {'type', 'fun', 'jac', 'args'};
3) Greindu dæmi um hagræðingu á framleiddum vörum með því að nota dæmi um vefstofu.
Skilyrt fínstillingaraðferð = "trust-constr"
Innleiðing aðferðarinnar trust-constr byggt á fyrir vandamál með hömlur á formi jafnréttis og áfram vegna vandamála með þvingunum í formi ójöfnuðar. Báðar aðferðirnar eru útfærðar með reikniritum til að finna staðbundið lágmark á öryggissvæðinu og henta vel fyrir stór vandamál.
Stærðfræðileg mótun vandamálsins við að finna lágmark í almennu formi:
Fyrir strangar jafnréttisþvinganir eru neðri mörkin sett jöfn efri mörkunum .
Fyrir einstefnu þvingun eru efri eða neðri mörkin sett np.inf með tilheyrandi merki.
Látum það vera nauðsynlegt að finna lágmark þekkts Rosenbrock falls af tveimur breytum:
Í þessu tilviki eru eftirfarandi takmarkanir settar á skilgreiningarsvið þess:
Í okkar tilviki er einstök lausn á þeim tímapunkti , þar sem aðeins fyrsta og fjórða takmörkunin gildir.
Við skulum fara í gegnum takmarkanirnar frá botni til topps og skoða hvernig við getum skrifað þær í scipy.
Takmarkanir и við skulum skilgreina það með Bounds hlutnum.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Takmarkanir и Við skulum skrifa það á línulegu formi:
Við skulum skilgreina þessar skorður sem LinearConstraint hlut:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Og að lokum ólínulega þvingunin í fylkisformi:
Við skilgreinum Jacobian fylkið fyrir þessa þvingun og línulega samsetningu af Hessian fylkinu með handahófskenndum vektor :
Nú getum við skilgreint ólínulega þvingun sem hlut 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)Ef stærðin er stór, er einnig hægt að tilgreina fylki í dreifðu formi:
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)eða sem hlutur 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)Þegar Hessian fylkið er reiknað út krefst mikillar fyrirhafnar, þú getur notað bekk . Eftirfarandi aðferðir eru í boði: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessian er einnig hægt að reikna með því að nota endanlegan mismun:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Jacobian fylki fyrir þvingun er einnig hægt að reikna með því að nota endanlegan mismun. Hins vegar, í þessu tilviki, er ekki hægt að reikna Hessian fylkið með því að nota endanlegan mismun. Hessian verður að vera skilgreint sem fall eða með því að nota HessianUpdateStrategy flokkinn.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Lausnin á hagræðingarvandanum lítur svona út:
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]Ef nauðsyn krefur er hægt að skilgreina fallið til að reikna út Hessian með því að nota LinearOperator flokkinn
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)eða margfeldi Hessíunnar og handahófskenndan vektor í gegnum færibreytuna 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)Að öðrum kosti er hægt að nálgast fyrstu og aðra afleiðu fallsins sem verið er að fínstilla. Til dæmis er hægt að nálgast hessíuna með því að nota fallið SR1 (hálf-Newtonsk nálgun). Hægt er að nálgast hallann með endanlegum mismun.
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)Skilyrt fínstillingaraðferð = "SLSQP"
SLSQP aðferðin er hönnuð til að leysa vandamál við að lágmarka aðgerð á formi:
Hvar и — sett af vísitölum orðasambanda sem lýsa takmörkunum í formi jafnréttis eða ójöfnuðar. — sett af neðri og efri mörkum fyrir skilgreiningarsvið fallsins.
Línulegum og ólínulegum takmörkunum er lýst í formi orðabóka með lyklum 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])
}Leitin að lágmarki fer fram sem hér segir:
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 ]Hagræðingardæmi
Í tengslum við umskipti yfir í fimmta tækniskipulagið skulum við skoða framleiðsluhagræðingu með því að nota dæmi um vefstofu, sem færir okkur litlar en stöðugar tekjur. Ímyndum okkur að við séum forstöðumaður eldhúss sem framleiðir þrjár tegundir af vörum:
- x0 - að selja áfangasíður, frá 10 tr.
- x1 - fyrirtækjavefsíður, frá 20 st.
- x2 - netverslanir, frá 30 st.
Vingjarnlega vinnuhópurinn okkar samanstendur af fjórum yngri flokkum, tveimur miðjumönnum og einum eldri. Mánaðarlegur vinnutímasjóður þeirra:
- júní:
4 * 150 = 600 чел * час, - miðja:
2 * 150 = 300 чел * час, - Senor:
150 чел * час.
Leyfðu fyrsta yngri tiltæka að eyða (0, 1, 2) klukkustundum í þróun og dreifingu á einni síðu af gerðinni (x10, x20, x30), miðjan - (7, 15, 20), eldri - (5, 10, 15 ) klukkustundir af besta tíma lífs þíns.
Eins og allir venjulegir leikstjórar viljum við hámarka mánaðarlegan hagnað. Fyrsta skrefið til að ná árangri er að skrifa niður hlutlæga aðgerðina value sem fjárhæð tekna af framleiðsluvörum á mánuði:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Þetta er ekki villa; þegar leitað er að hámarki er markmiðsfallið lágmarkað með öfugu formerki.
Næsta skref er að banna starfsfólki okkar að vinna of mikið og setja upp takmarkanir á vinnutíma:
Hvað jafngildir:
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]])
}Formleg takmörkun er sú að framleiðsla vöru verður aðeins að vera jákvæð:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Og að lokum, bjartasta forsendan er sú að vegna lágs verðs og hágæða sé stöðugt röð af ánægðum viðskiptavinum í röð fyrir okkur. Við getum valið mánaðarlegt framleiðslumagn sjálf, byggt á því að leysa þvingaða hagræðingarvandann 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]Námundum lauslega að heilum tölum og reiknum út mánaðarlegt álag róðra með ákjósanlegri dreifingu afurða x = (8, 6, 3) :
- júní:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - miðja:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - Senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Ályktun: Til þess að leikstjórinn fái verðskuldað hámark sitt er ákjósanlegt að búa til 8 áfangasíður, 6 meðalstórar síður og 3 verslanir á mánuði. Í þessu tilviki verður eldri að plægja án þess að horfa upp frá vélinni, álag miðjanna verður um það bil 2/3, yngri minna en helmingur.
Ályktun
Greinin útlistar helstu aðferðir til að vinna með pakkann scipy.optimize, notað til að leysa skilyrt lágmarksvandamál. Persónulega nota ég scipy eingöngu í fræðilegum tilgangi og þess vegna er dæmið sem gefið er af svo kómískum toga.
Mikið af kenningum og sýndardæmum er til dæmis að finna í bók I.L. Akulich „Stærðfræðiforritun í dæmum og vandamálum“. Meira harðkjarna forrit scipy.optimize að byggja upp þrívíddarbyggingu úr safni mynda () er hægt að skoða í .
Aðaluppspretta upplýsinga er þeir sem vilja leggja sitt af mörkum við þýðingu þessa og annarra hluta scipy Velkomin til .
Takk vegna þátttöku í gerð útgáfunnar.
Heimild: www.habr.com