SciPy (izrunā sai pīrāgs) ir matemātikas pakotne, kas balstīta uz numpy, kas ietver arī C un Fortran bibliotēkas. SciPy pārvērš jūsu interaktīvo Python sesiju par pilnīgu datu zinātnes vidi, piemēram, MATLAB, IDL, Octave, R vai SciLab.
Šajā rakstā mēs apskatīsim matemātiskās programmēšanas pamatmetodes – nosacītās optimizācijas uzdevumu risināšanu vairāku mainīgo skalārai funkcijai, izmantojot pakotni scipy.optimize. Neierobežoti optimizācijas algoritmi jau ir apspriesti . Detalizētāku un jaunāko palīdzību par scipy funkcijām vienmēr var iegūt, izmantojot komandu help(), Shift+Tab vai .
Ievads
Kopēju interfeisu gan nosacītu, gan neierobežotu optimizācijas problēmu risināšanai pakotnē scipy.optimize nodrošina funkcija minimize(). Taču zināms, ka nav universālas metodes visu problēmu risināšanai, tāpēc adekvātas metodes izvēle, kā vienmēr, gulstas uz pētnieka pleciem.
Atbilstošais optimizācijas algoritms tiek norādīts, izmantojot funkcijas argumentu minimize(..., method="").
Vairāku mainīgo funkcijas nosacītai optimizācijai ir pieejamas šādas metodes:
trust-constr— meklēt vietējo minimumu uzticības reģionā. , ;SLSQP— secīga kvadrātiskā programmēšana ar ierobežojumiem, Ņūtona metode Lagranža sistēmas risināšanai. .TNC- Saīsināts Ņūtons Ierobežots, ierobežots iterāciju skaits, piemērots nelineārām funkcijām ar lielu skaitu neatkarīgu mainīgo. .L-BFGS-B— Broyden–Fletcher–Goldfarb–Shanno komandas metode, kas ieviesta ar samazinātu atmiņas patēriņu, jo vektoru daļēja ielāde no Hesenes matricas. , .COBYLA— MARE ierobežota optimizācija ar lineāru tuvināšanu, ierobežota optimizācija ar lineāru tuvinājumu (bez gradienta aprēķina). .
Atkarībā no izvēlētās metodes problēmas risināšanas nosacījumi un ierobežojumi tiek noteikti atšķirīgi:
- klases objekts
Boundsmetodēm L-BFGS-B, TNC, SLSQP, trust-constr; - saraksts
(min, max)tām pašām metodēm L-BFGS-B, TNC, SLSQP, trust-constr; - objekts vai objektu saraksts
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, uzticības-constr metodēm; - vārdnīca vai vārdnīcu saraksts
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP metodēm.
Raksta izklāsts:
1) Apsveriet iespēju izmantot nosacītu optimizācijas algoritmu uzticamības reģionā (method=”trust-constr”) ar ierobežojumiem, kas norādīti kā objekti. Bounds, LinearConstraint, NonlinearConstraint ;
2) Apsveriet secīgu programmēšanu, izmantojot mazāko kvadrātu metodi (metode = "SLSQP") ar ierobežojumiem, kas norādīti vārdnīcas veidā. {'type', 'fun', 'jac', 'args'};
3) Analizējiet ražoto produktu optimizācijas piemēru, izmantojot tīmekļa studijas piemēru.
Nosacījuma optimizācijas metode = "trust-constr"
Metodes ieviešana trust-constr balstoties uz problēmām ar vienlīdzības formas ierobežojumiem un tālāk problēmām ar ierobežojumiem nevienlīdzības veidā. Abas metodes realizē algoritmi lokālā minimuma atrašanai ticamības reģionā, un tās ir labi piemērotas liela mēroga problēmām.
Vispārīgā formā minimuma atrašanas problēmas matemātiskais formulējums:
Stingriem vienlīdzības ierobežojumiem apakšējā robeža ir iestatīta vienāda ar augšējo robežu .
Vienvirziena ierobežojumam ir iestatīta augšējā vai apakšējā robeža np.inf ar atbilstošo zīmi.
Ļaujiet mums atrast zināmās Rozenbroka funkcijas minimumu no diviem mainīgajiem:
Šajā gadījumā tās definīcijas domēnam ir noteikti šādi ierobežojumi:
Mūsu gadījumā šajā punktā ir unikāls risinājums , kam ir spēkā tikai pirmais un ceturtais ierobežojums.
Iziesim cauri ierobežojumiem no apakšas uz augšu un paskatīsimies, kā varam tos rakstīt scipy valodā.
Ierobežojumi и definēsim to, izmantojot objektu Robežas.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Ierobežojumi и Rakstīsim to lineārā formā:
Definēsim šos ierobežojumus kā LinearConstraint objektu:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Un visbeidzot nelineārais ierobežojums matricas formā:
Mēs definējam Jakoba matricu šim ierobežojumam un Hesenes matricas lineāru kombināciju ar patvaļīgu vektoru :
Tagad mēs varam definēt nelineāru ierobežojumu kā objektu 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)Ja izmērs ir liels, matricas var norādīt arī retā formā:
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)vai kā objektu 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)Aprēķinot Hesenes matricu prasa daudz pūļu, jūs varat izmantot klasi . Ir pieejamas šādas stratēģijas: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hesenes vērtību var aprēķināt arī, izmantojot ierobežotas atšķirības:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Jakoba matricu ierobežojumiem var arī aprēķināt, izmantojot ierobežotas atšķirības. Tomēr šajā gadījumā Hesenes matricu nevar aprēķināt, izmantojot ierobežotas atšķirības. Hessian ir jādefinē kā funkcija vai jāizmanto HessianUpdateStrategy klase.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Optimizācijas problēmas risinājums izskatās šādi:
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]Ja nepieciešams, funkciju Hessian aprēķināšanai var definēt, izmantojot LinearOperator klasi
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)vai Hesenes un patvaļīga vektora reizinājums caur parametru 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)Alternatīvi, optimizējamās funkcijas pirmo un otro atvasinājumu var tuvināt. Piemēram, Hesenes vērtību var tuvināt, izmantojot funkciju SR1 (kvaziņūtona tuvinājums). Gradientu var tuvināt ar ierobežotām atšķirībām.
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)Nosacītā optimizācijas metode = SLSQP
SLSQP metode ir paredzēta, lai atrisinātu problēmas, kas saistītas ar funkcijas minimizēšanu šādā formā:
Kur и — izteiksmju indeksu kopas, kas apraksta ierobežojumus vienādību vai nevienlīdzību veidā. — apakšējo un augšējo robežu kopas funkcijas definīcijas jomā.
Lineārie un nelineārie ierobežojumi ir aprakstīti vārdnīcu veidā ar taustiņiem 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])
}Minimuma meklēšana tiek veikta šādi:
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 ]Optimizācijas piemērs
Saistībā ar pāreju uz piekto tehnoloģisko struktūru, aplūkosim ražošanas optimizāciju, izmantojot tīmekļa studijas piemēru, kas mums nes nelielus, bet stabilus ienākumus. Iedomāsimies sevi kā kambīzes direktoru, kas ražo trīs veidu produktus:
- x0 - izvietošanas lapu pārdošana, no 10 tr.
- x1 - korporatīvās mājas lapas, no 20 tr.
- x2 - interneta veikali, no 30 tr.
Mūsu draudzīgajā komandā ir četri juniori, divi vidējie un viens vecākais. Viņu ikmēneša darba laika fonds:
- jūnijā:
4 * 150 = 600 чел * час, - vidus:
2 * 150 = 300 чел * час, - Senors:
150 чел * час.
Ļaujiet pirmajam pieejamajam junioram pavadīt (0, 1, 2) stundas vienas vietnes (x10, x20, x30) izstrādei un izvietošanai, vidējais - (7, 15, 20), vecākais - (5, 10, 15). ) savas dzīves labākā laika stundas.
Tāpat kā jebkurš parasts direktors, mēs vēlamies maksimāli palielināt ikmēneša peļņu. Pirmais solis uz panākumiem ir mērķa funkcijas pierakstīšana value kā ienākumu summa no saražotās produkcijas mēnesī:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Tā nav kļūda; meklējot maksimumu, mērķa funkcija tiek minimizēta ar pretēju zīmi.
Nākamais solis ir aizliegt mūsu darbiniekiem pārmērīgi strādāt un ieviest darba laika ierobežojumus:
Kas ir līdzvērtīgs:
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]])
}Formāls ierobežojums ir tāds, ka produkta izlaidei jābūt tikai pozitīvai:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Un visbeidzot, pats rožainākais pieņēmums ir tas, ka zemās cenas un augstās kvalitātes dēļ pie mums nepārtraukti stāv rinda ar apmierinātiem klientiem. Mēneša ražošanas apjomus varam izvēlēties paši, pamatojoties uz ierobežotās optimizācijas problēmas risināšanu ar 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]Noapaļosim brīvi līdz veseliem skaitļiem un aprēķināsim airētāju mēneša slodzi ar optimālu produktu sadalījumu x = (8, 6, 3) :
- jūnijā:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - vidus:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - Senors:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Secinājums: lai režisors saņemtu savu pelnīto maksimumu, ir optimāli mēnesī izveidot 8 galvenās lapas, 6 vidēja lieluma vietnes un 3 veikalus. Šajā gadījumā senioram jāar, nepaskatoties no mašīnas, vidus slodze būs aptuveni 2/3, junioriem mazāka par pusi.
Secinājums
Rakstā ir izklāstīti pamata paņēmieni darbam ar paketi scipy.optimize, ko izmanto, lai atrisinātu nosacītās minimizēšanas problēmas. Personīgi es lietoju scipy tīri akadēmiskiem nolūkiem, tāpēc minētajam piemēram ir tik komisks raksturs.
Daudz teoriju un virtuālu piemēru var atrast, piemēram, I.L.Akuļiha grāmatā “Matemātiskā programmēšana piemēros un problēmās”. Vairāk hardcore pieteikumu scipy.optimize lai izveidotu 3D struktūru no attēlu kopas () var apskatīties .
Galvenais informācijas avots ir tiem, kas vēlas piedalīties šīs un citu sadaļu tulkošanā scipy Laipni lūdzam .
Paldies par dalību izdevuma sagatavošanā.
Avots: www.habr.com