SciPy (lausutaan sai pie) on numpy-pohjainen matematiikkapaketti, joka sisältää myös C- ja Fortran-kirjastot. SciPy muuttaa interaktiivisen Python-istunnon täydelliseksi datatieteen ympäristöksi, kuten MATLAB, IDL, Octave, R tai SciLab.
Tässä artikkelissa tarkastellaan matemaattisen ohjelmoinnin perustekniikoita - useiden muuttujien skalaarifunktion ehdollisten optimointiongelmien ratkaisemista scipy.optimize-paketin avulla. Rajoittamattomista optimointialgoritmeista on jo keskusteltu . Tarkempia ja ajantasaisia ohjeita scipy-funktioista saat aina help()-komennolla, Shift+Tab tai .
Esittely
Toiminto tarjoaa yhteisen käyttöliittymän sekä ehdollisten että rajoittamattomien optimointiongelmien ratkaisemiseen scipy.optimize-paketissa minimize(). Tiedetään kuitenkin, että kaikkien ongelmien ratkaisemiseen ei ole olemassa universaalia menetelmää, joten sopivan menetelmän valinta on, kuten aina, tutkijan harteilla.
Sopiva optimointialgoritmi määritetään käyttämällä funktioargumenttia minimize(..., method="").
Useiden muuttujien funktion ehdolliseen optimointiin on käytettävissä seuraavat menetelmät:
trust-constr— Etsi paikallinen minimi luottamusalueelta. , ;SLSQP— peräkkäinen neliöllinen ohjelmointi rajoituksilla, Newtonin menetelmä Lagrange-järjestelmän ratkaisemiseksi. .TNC- Typistetty Newton Rajoitettu, rajoitettu määrä iteraatioita, hyvä epälineaarisille funktioille, joissa on suuri määrä riippumattomia muuttujia. .L-BFGS-B— Broyden–Fletcher–Goldfarb–Shanno-tiimin menetelmä, joka on toteutettu pienemmällä muistinkulutuksella, koska vektorit on ladattu osittain Hessenin matriisista. , .COBYLA— MARE rajoitettu optimointi lineaarisella approksimaatiolla, rajoitettu optimointi lineaarisella approksimaatiolla (ilman gradienttilaskentaa). .
Valitusta menetelmästä riippuen ongelman ratkaisemisen ehdot ja rajoitukset asetetaan eri tavalla:
- luokan objekti
Boundsmenetelmille L-BFGS-B, TNC, SLSQP, trust-constr; - lista
(min, max)samoilla menetelmillä L-BFGS-B, TNC, SLSQP, trust-constr; - objekti tai objektiluettelo
LinearConstraint,NonlinearConstraintCOBYLA-, SLSQP-, trust-constr-menetelmille; - sanakirja tai sanakirjaluettelo
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA-, SLSQP-menetelmille.
Artikkelin pääpiirteet:
1) Harkitse ehdollisen optimointialgoritmin käyttöä luottamusalueella (method=”trust-constr”) objekteiksi määritettyjen rajoitusten kanssa Bounds, LinearConstraint, NonlinearConstraint ;
2) Harkitse peräkkäistä ohjelmointia pienimmän neliösumman menetelmällä (method = "SLSQP") rajoituksin, jotka on määritelty sanakirjan muodossa {'type', 'fun', 'jac', 'args'};
3) Analysoi esimerkki valmistettujen tuotteiden optimoinnista web-studion esimerkillä.
Ehdollinen optimointimenetelmä="trust-constr"
Menetelmän toteutus trust-constr perustuen tasa-arvon muotoon liittyviin ongelmiin ja muihin ongelmiin, jotka liittyvät eriarvoisuuden muodossa oleviin rajoituksiin. Molemmat menetelmät on toteutettu algoritmeilla paikallisen minimin löytämiseksi luottamusalueelta ja ne sopivat hyvin suuriin ongelmiin.
Matemaattinen muotoilu minimin löytämisen ongelmasta yleisessä muodossa:
Tiukkoja tasa-arvorajoituksia varten alaraja asetetaan yhtä suureksi kuin yläraja .
Yksisuuntaiselle rajoitukselle asetetaan ylä- tai alaraja np.inf vastaavalla merkillä.
Olkoon tarpeen löytää tunnetun Rosenbrock-funktion minimi kahdesta muuttujasta:
Tässä tapauksessa sen määritelmäalueelle asetetaan seuraavat rajoitukset:
Meidän tapauksessamme on olemassa ainutlaatuinen ratkaisu , joille vain ensimmäinen ja neljäs rajoitus ovat voimassa.
Käydään rajoitukset läpi alhaalta ylös ja katsotaan kuinka voimme kirjoittaa ne scipy-kielellä.
Rajoitukset и määritellään se käyttämällä Bounds-objektia.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Rajoitukset и Kirjoitetaan se lineaarisessa muodossa:
Määritellään nämä rajoitukset LinearConstraint-objektiksi:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])Ja lopuksi epälineaarinen rajoite matriisimuodossa:
Määrittelemme tälle rajoitukselle Jacobi-matriisin ja Hessin matriisin lineaarisen yhdistelmän mielivaltaisen vektorin kanssa :
Nyt voimme määritellä epälineaarisen rajoitteen objektiksi 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)Jos koko on suuri, matriisit voidaan määrittää myös harvassa muodossa:
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)tai esineenä 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)Hessenin matriisia laskettaessa vaatii paljon vaivaa, voit käyttää luokkaa . Seuraavat strategiat ovat käytettävissä: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())Hessian voidaan laskea myös äärellisillä eroilla:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')Jakobilainen matriisi rajoituksille voidaan myös laskea käyttämällä äärellisiä eroja. Tässä tapauksessa Hessen-matriisia ei kuitenkaan voida laskea äärellisillä eroilla. Hessian on määritettävä funktiona tai käyttämällä HessianUpdateStrategy-luokkaa.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Ratkaisu optimointiongelmaan näyttää tältä:
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]Tarvittaessa Hessenin laskentafunktio voidaan määritellä LinearOperator-luokalla
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)tai Hessenin ja mielivaltaisen vektorin tulo parametrin kautta 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)Vaihtoehtoisesti optimoitavan funktion ensimmäinen ja toinen derivaatta voidaan approksimoida. Esimerkiksi Hessian voidaan approksimoida funktiolla SR1 (quasi-Newtonin approksimaatio). Gradientti voidaan arvioida äärellisillä eroilla.
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)Ehdollinen optimointimenetelmä="SLSQP"
SLSQP-menetelmä on suunniteltu ratkaisemaan funktion minimointiongelmia muodossa:
jossa и — lausekkeiden indeksit, jotka kuvaavat rajoituksia yhtäläisyyksien tai eriarvoisuuksien muodossa. — funktion määrittelyalueen ala- ja ylärajojen joukot.
Lineaariset ja epälineaariset rajoitukset on kuvattu avaimilla varustettujen sanakirjojen muodossa 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])
}Minimihaku suoritetaan seuraavasti:
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 ]Esimerkki optimoinnista
Viidenteen teknologiseen rakenteeseen siirtymisen yhteydessä tarkastellaan tuotannon optimointia web-studion esimerkillä, joka tuo meille pienen mutta vakaan tulon. Kuvittelemme itseämme keittiön johtajana, joka tuottaa kolmenlaisia tuotteita:
- x0 - aloitussivujen myynti, alkaen 10 tr.
- x1 - yritysten verkkosivut, alkaen 20 tr.
- x2 - verkkokaupat, alkaen 30 tr.
Ystävälliseen työporukkaamme kuuluu neljä junioria, kaksi keskimmäistä ja yksi seniori. Heidän kuukausittainen työaikarahastonsa:
- Kesäkuu:
4 * 150 = 600 чел * час, - keskikohdat:
2 * 150 = 300 чел * час, - senor:
150 чел * час.
Anna ensimmäisen käytettävissä olevan juniorin käyttää (0, 1, 2) tuntia yhden tyypin (x10, x20, x30), keskitason (7, 15, 20), senior - (5, 10, 15) sivuston kehittämiseen ja käyttöönottoon. ) tuntia elämäsi parasta aikaa.
Kuten kaikki normaalit johtajat, haluamme maksimoida kuukausittaiset voitot. Ensimmäinen askel menestykseen on tavoitefunktion kirjoittaminen value tuotettujen tuotteiden tulona kuukaudessa:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Tämä ei ole virhe, vaan maksimia haettaessa tavoitefunktio minimoidaan päinvastaisella etumerkillä.
Seuraava askel on kieltää työntekijöitämme ylityöstä ja ottaa käyttöön työaikarajoituksia:
Mikä on vastaava:
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]])
}Muodollinen rajoitus on, että tuotteen tuotos saa olla vain positiivinen:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])Ja lopuksi, ruusuisin oletus on, että alhaisen hinnan ja korkean laadun vuoksi jono tyytyväisiä asiakkaita odottaa jatkuvasti meitä. Voimme valita itse kuukausittaiset tuotantomäärät, perustuen rajoittuneen optimointiongelman ratkaisuun 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]Pyöristetään löyhästi kokonaislukuihin ja lasketaan soutajien kuukausikuorma optimaalisella tuotejakaumalla x = (8, 6, 3) :
- Kesäkuu:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - keskikohdat:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Johtopäätös: jotta ohjaaja saisi ansaitun maksiminsa, on optimaalista luoda 8 aloitussivua, 6 keskikokoista sivustoa ja 3 kauppaa kuukaudessa. Tällöin seniorin tulee kyntää koneesta katsomatta, keskiosien kuormitus on noin 2/3, juniorien alle puolet.
Johtopäätös
Artikkelissa kuvataan perustekniikat paketin kanssa työskentelyyn scipy.optimize, jota käytetään ratkaisemaan ehdollisia minimointiongelmia. Henkilökohtaisesti käytän scipy puhtaasti akateemisiin tarkoituksiin, minkä vuoksi annettu esimerkki on luonteeltaan niin koominen.
Paljon teoriaa ja virtuaalisia esimerkkejä löytyy esimerkiksi I.L. Akulichin kirjasta "Mathematical programming in examples and problems". Lisää hardcore-sovelluksia scipy.optimize rakentaa 3D-rakenne joukosta kuvia () voi katsoa .
Pääasiallinen tiedonlähde on jotka haluavat osallistua tämän ja muiden osien kääntämiseen scipy Tervetuloa .
Kiitos osallistumisesta julkaisun valmisteluun.
Lähde: will.com