SciPy (sai pie ahoskatua) C eta Fortran liburutegiak ere barne hartzen dituen numpy-n oinarritutako pakete matematiko bat da. SciPy-k zure Python saio interaktiboa datu zientzien ingurune oso batean bihurtzen du MATLAB, IDL, Octave, R edo SciLab bezalakoak.
Artikulu honetan, programazio matematikoaren oinarrizko teknikak aztertuko ditugu: hainbat aldagairen funtzio eskalar baten baldintzazko optimizazio-problemak ebaztea scipy.optimize paketea erabiliz. Mugarik gabeko optimizazio algoritmoak dagoeneko eztabaidatu dira . Scipy funtzioei buruzko laguntza zehatzagoa eta eguneratua beti lor daiteke help() komandoa erabiliz, Shift+Tab edo hemen. .
Sarrera
Scipy.optimize paketean baldintzapeko eta mugarik gabeko optimizazio-arazoak ebazteko interfaze komuna funtzioak eskaintzen du. minimize(). Hala ere, jakina da ez dagoela arazo guztiak konpontzeko metodo unibertsala, beraz, metodo egokia aukeratzea, beti bezala, ikertzailearen sorbaldetan dago.
Optimizazio-algoritmo egokia funtzioaren argumentua erabiliz zehazten da minimize(..., method="").
Hainbat aldagairen funtzio baten baldintzapeko optimizaziorako, metodo hauen inplementazioak eskuragarri daude:
trust-constr— Konfiantza eskualdean tokiko gutxieneko bat bilatzea. , ;SLSQP— murrizketekin programazio koadratiko sekuentziala, Lagrange sistema ebazteko metodo newtoniarra. .TNC- Newton tronkatua Mugatua, iterazio kopuru mugatua, ona aldagai independente ugari dituzten funtzio ez-linealetarako. .L-BFGS-B— Broyden–Fletcher–Goldfarb–Shanno taldeko metodo bat, memoria-kontsumo murriztuarekin inplementatua, Hessiar matrizeko bektoreen karga partzialaren ondorioz. , .COBYLA— MARE Constrained Optimization By Linear Approximation, optimizazio mugatua hurbilketa linealarekin (gradienteen kalkulurik gabe). .
Aukeratutako metodoaren arabera, arazoa konpontzeko baldintzak eta murrizketak ezberdin ezartzen dira:
- klaseko objektua
BoundsL-BFGS-B, TNC, SLSQP, trust-constr metodoetarako; - zerrenda
(min, max)metodo berdinetarako L-BFGS-B, TNC, SLSQP, trust-constr; - objektu bat edo objektuen zerrenda bat
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, trust-constr metodoak; - hiztegia edo hiztegien zerrenda
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP metodoetarako.
Artikuluaren eskema:
1) Kontuan izan konfiantzazko eskualdean (method=”trust-constr”) baldintzazko optimizazio-algoritmo baten erabilera objektu gisa zehaztutako murrizketekin Bounds, LinearConstraint, NonlinearConstraint ;
2) Demagun programazio sekuentziala karratu txikienen metodoa erabiliz (metodoa = "SLSQP") hiztegi moduan zehaztutako murrizketekin {'type', 'fun', 'jac', 'args'};
3) Aztertu fabrikatutako produktuen optimizazioaren adibide bat web estudio baten adibidea erabiliz.
Optimizazio baldintzapeko metodoa="trust-constr"
Metodoaren ezarpena trust-constr oinarrituta berdintasun-formaren mugak dituzten arazoetarako eta on desberdintasunen formako mugak dituzten arazoetarako. Bi metodoak konfiantza-eskualdean tokiko minimo bat aurkitzeko algoritmoen bidez inplementatzen dira eta eskala handiko arazoetarako oso egokiak dira.
Forma orokorrean minimo bat aurkitzeko problemaren formulazio matematikoa:
Berdintasun-murrizketa zorrotzetarako, beheko muga goiko mugaren berdina ezartzen da .
Norabide bakarreko muga baterako, goiko edo beheko muga ezartzen da np.inf dagokion zeinuarekin.
Beharrezkoa da bi aldagairen Rosenbrock funtzio ezagun baten minimoa aurkitzea:
Kasu honetan, muga hauek ezartzen dira bere definizio-eremuan:
Gure kasuan, irtenbide bakarra dago puntuan , eta horretarako lehen eta laugarren murrizketak baino ez dira balio.
Joan ditzagun murrizketak behetik gora eta ikus ditzagun nola idatz ditzakegun scipy-n.
Murrizketak и definitu dezagun Bounds objektua erabiliz.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Murrizketak и Idatz dezagun forma linealean:
Defini ditzagun muga hauek LinearConstraint objektu gisa:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Eta azkenik muga ez-lineala matrize moduan:
Murrizketa honetarako matrize jakobiarra eta Hessiar matrizearen konbinazio lineal bat bektore arbitrario batekin definitzen dugu. :
Orain muga ez-lineal bat objektu gisa defini dezakegu 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)Tamaina handia bada, matrizeak forma eskasean ere zehaztu daitezke:
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)edo objektu gisa 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)Hessiar matrizea kalkulatzean esfortzu handia eskatzen du, klase bat erabil dezakezu . Estrategia hauek daude eskuragarri: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessiarra diferentzia finituak erabiliz ere kalkula daiteke:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Murrizketen matrize jakobiarra ere kalkula daiteke diferentzia finituak erabiliz. Hala ere, kasu honetan Hessiar matrizea ezin da diferentzia finituak erabiliz kalkulatu. Hessian funtzio gisa edo HessianUpdateStrategy klasea erabiliz definitu behar da.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Optimizazio-arazoaren irtenbidea honelakoa da:
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]Beharrezkoa izanez gero, Hessiana kalkulatzeko funtzioa defini daiteke LinearOperator klasea erabiliz
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)edo parametroaren bidez hessaren eta bektore arbitrario baten biderkadura 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)Bestela, optimizatzen ari den funtzioaren lehen eta bigarren deribatuak hurbil daitezke. Adibidez, Hessera gutxi gorabehera funtzioa erabiliz SR1 (hurbilketa ia newtoniarra). Gradientea diferentzia finituekin hurbil daiteke.
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)Optimizazio baldintzapeko metodoa="SLSQP"
SLSQP metodoa funtzio bat minimizatzeko arazoak ebazteko diseinatuta dago:
non и — berdintasun edo desberdintasun moduan murrizketak deskribatzen dituzten adierazpideen indizeen multzoak. — funtzioaren definizio-eremurako beheko eta goiko mugen multzoak.
Muga linealak eta ez-linealak gakodun hiztegien moduan deskribatzen dira 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])
}Gutxieneko bilaketa honela egiten da:
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 ]Optimizazio Adibidea
Bosgarren egitura teknologikorako trantsizioarekin lotuta, ikus dezagun ekoizpenaren optimizazioa web estudio baten adibidea erabiliz, diru sarrera txiki baina egonkor bat ekartzen diguna. Imajina dezagun gure burua hiru produktu mota ekoizten dituen galera baten zuzendari gisa:
- x0 - helmuga orriak saltzen, 10 tr.
- x1 - webgune korporatiboak, 20 tr.
- x2 - lineako dendak, 30 tr.
Gure lagunarteko lantaldeak lau junior, bi erdi eta senior bat osatzen dute. Hileko lanaldiaren funtsa:
- Ekainak:
4 * 150 = 600 чел * час, - erdikoak:
2 * 150 = 300 чел * час, - jauna:
150 чел * час.
Utzi erabilgarri dauden lehen juniorrek (0, 1, 2) ordu motako gune bat garatzen eta inplementatzen (x10, x20, x30), erdikoa - (7, 15, 20), senior - (5, 10, 15). ) zure bizitzako denborarik onenaren orduak.
Edozein zuzendari arrunt bezala, hileko irabaziak maximizatu nahi ditugu. Arrakasta lortzeko lehen urratsa funtzio objektiboa idaztea da value hilean ekoitzitako produktuen diru-sarreren zenbatekoa:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Hau ez da errore bat; maximoa bilatzean, objektiboa funtzioa kontrako zeinuarekin minimizatu egiten da.
Hurrengo urratsa gure langileei gehiegizko lan egitea debekatzea eta lanaldia murriztea da:
Zer da baliokidea:
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]])
}Murrizketa formal bat da produktuaren irteera positiboa izan behar dela:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Eta, azkenik, hipotesirik arrosarena da prezio baxua eta kalitate handikoa dela eta, bezero pozik dauden ilara etengabe bat egiten ari zaigula. Hileroko produkzio-bolumenak guk geuk aukeratu ditzakegu, optimizazio-arazo mugatua ebatziz 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]Biribil gaitezen zenbaki osoetara eta kalkula ditzagun arraunlarien hileroko karga produktuen banaketa optimoarekin x = (8, 6, 3) :
- Ekainak:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - erdikoak:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - jauna:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Ondorioa: zuzendariak merezi duen maximoa jaso dezan, optimoa da hilabetean 8 landing page, 6 gune ertain eta 3 denda sortzea. Kasu honetan, seniorrak makinatik begiratu gabe goldatu behar du, erdikoen karga gutxi gorabehera 2/3koa izango da, juniorrek erdia baino gutxiago.
Ondorioa
Artikuluak paketearekin lan egiteko oinarrizko teknikak zehazten ditu scipy.optimize, baldintzapeko minimizazio-problemak ebazteko erabiltzen da. Pertsonalki erabiltzen dut scipy helburu akademiko hutsez, horregatik ematen den adibideak hain komiko izaera du.
Teoria eta adibide birtual asko aurki daitezke, adibidez, I.L. Akulich-en "Programazio matematikoa adibideetan eta arazoetan" liburuan. Hardcore aplikazio gehiago scipy.optimize irudi multzo batetik 3D egitura bat eraikitzeko () atalean ikus daiteke .
Informazio iturri nagusia da atal honen eta beste batzuen itzulpenean lagundu nahi dutenak scipy Ongi etorria .
Eskerrik asko argitalpenaren prestaketan parte hartzeagatik.
Iturria: www.habr.com