SciPy (lausutaan sai pie) on Numpy Python -laajennukseen perustuva matemaattinen sovelluspaketti. SciPyn avulla interaktiivisesta Python-istunnostasi tulee sama täydellinen datatiede ja monimutkainen järjestelmäprototyyppiympäristö kuin MATLAB, IDL, Octave, R-Lab ja SciLab. Tänään haluan puhua lyhyesti siitä, kuinka käyttää joitain tunnettuja optimointialgoritmeja scipy.optimize-paketissa. Tarkempia ja ajantasaisia ohjeita funktioiden käyttöön saa aina help()-komennolla tai Shift+Tab-näppäimillä.
Esittely
Voit säästää itseäsi ja lukijoita ensisijaisten lähteiden etsinnästä ja lukemisesta, linkit menetelmien kuvauksiin ovat pääasiassa Wikipediassa. Yleensä nämä tiedot riittävät menetelmien yleiseen ymmärtämiseen ja niiden soveltamisehtoihin. Ymmärtääksesi matemaattisten menetelmien olemuksen, seuraa linkkejä arvokkaampiin julkaisuihin, jotka löytyvät jokaisen artikkelin lopusta tai suosikkihakukoneestasi.
Joten scipy.optimize-moduuli sisältää seuraavat toimenpiteet:
- Useiden muuttujien skalaarifunktioiden ehdollinen ja ehdoton minimointi (minimi) käyttämällä erilaisia algoritmeja (Nelder-Mead simplex, BFGS, Newtonin konjugaattigradientit, и )
- Globaali optimointi (esim. , )
- Jäännösten minimoiminen (pienimmän neliösumman) ja käyrän sovitusalgoritmit käyttäen epälineaarisia pienimmän neliösumman (curve_fit) avulla
- Yhden muuttujan skalaarifunktioiden minimointi (minim_scalar) ja juurien etsiminen (root_scalar)
- Yhtälöjärjestelmän (juuren) moniulotteiset ratkaisijat eri algoritmeilla (hybridi Powell, tai suuren mittakaavan menetelmiä, kuten ).
Tässä artikkelissa tarkastelemme vain ensimmäistä kohtaa koko luettelosta.
Useiden muuttujien skalaarifunktion ehdoton minimointi
Scipy.optimize-paketin minimifunktio tarjoaa yleisen käyttöliittymän useiden muuttujien skalaarifunktioiden ehdollisten ja ehdottomien minimointiongelmien ratkaisemiseen. Sen toiminnan osoittamiseksi tarvitsemme sopivan funktion useista muuttujista, jotka minimoidaan eri tavoin.
Näihin tarkoituksiin N muuttujan Rosenbrock-funktio on täydellinen, jonka muoto on:
Huolimatta siitä, että Rosenbrock-funktio ja sen Jacobi- ja Hessian-matriisit (ensimmäinen ja toinen derivaatta) on jo määritelty scipy.optimize-paketissa, määrittelemme sen itse.
import numpy as np
def rosen(x):
"""The Rosenbrock function"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Selvyyden vuoksi piirretään 3D:ssä kahden muuttujan Rosenbrock-funktion arvot.
Piirustuskoodi
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Настраиваем 3D график
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Задаем угол обзора
ax.view_init(45, 30)
# Создаем данные для графика
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))
# Рисуем поверхность
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Tietäen etukäteen, että minimi on 0 at , katsotaanpa esimerkkejä siitä, kuinka määrittää Rosenbrock-funktion vähimmäisarvo käyttämällä erilaisia scipy.optimize-toimenpiteitä.
Nelder-Mead simplex -menetelmä
Olkoon 0-ulotteisessa avaruudessa alkupiste x5. Etsitään algoritmin avulla sitä lähinnä oleva Rosenbrock-funktion minimipiste (algoritmi on määritetty menetelmäparametrin arvoksi):
from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 339
Function evaluations: 571
[1. 1. 1. 1. 1.]Simpleksimenetelmä on yksinkertaisin tapa minimoida selkeästi määritelty ja melko tasainen funktio. Se ei edellytä funktion derivaattojen laskemista, riittää, että määritetään vain sen arvot. Nelder-Mead-menetelmä on hyvä valinta yksinkertaisiin minimointiongelmiin. Koska se ei kuitenkaan käytä gradienttiestimaatteja, minimin löytäminen voi kestää kauemmin.
Powellin menetelmä
Toinen optimointialgoritmi, jossa vain funktioarvot lasketaan, on . Käyttääksesi sitä, sinun on asetettava menetelmä = 'powell' minimifunktiossa.
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) -algoritmi
Saadaksesi nopeamman konvergenssin ratkaisuun, menettely käyttää tavoitefunktion gradienttia. Gradientti voidaan määrittää funktiona tai laskea käyttämällä ensimmäisen asteen eroja. Joka tapauksessa BFGS-menetelmä vaatii tyypillisesti vähemmän funktiokutsuja kuin simpleksimenetelmä.
Etsitään Rosenbrock-funktion derivaatta analyyttisessä muodossa:
Tämä lauseke pätee kaikkien muuttujien johdannaisiin paitsi ensimmäistä ja viimeistä, jotka määritellään seuraavasti:
Katsotaan Python-funktiota, joka laskee tämän gradientin:
def rosen_der (x):
xm = x [1: -1]
xm_m1 = x [: - 2]
xm_p1 = x [2:]
der = np.zeros_like (x)
der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
der [-1] = 200 * (x [-1] -x [-2] ** 2)
return derGradientin laskentafunktio on määritetty minimifunktion jac-parametrin arvoksi alla olevan kuvan mukaisesti.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 25
Function evaluations: 30
Gradient evaluations: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Konjugoitu gradienttialgoritmi (Newton)
Algoritmi on modifioitu Newtonin menetelmä.
Newtonin menetelmä perustuu funktion approksimoimiseen paikallisella alueella toisen asteen polynomilla:
missä on toisten derivaattojen matriisi (Hessian matriisi, Hessian).
Jos Hessian on positiivinen definiitti, niin tämän funktion paikallinen minimi voidaan löytää vertaamalla toisen asteen muodon nollagradientti nollaan. Tuloksena on lauseke:
Käänteis-Hessian lasketaan käyttämällä konjugaattigradienttimenetelmää. Alla on esimerkki tämän menetelmän käytöstä Rosenbrock-funktion minimoimiseksi. Jotta voit käyttää Newton-CG-menetelmää, sinun on määritettävä funktio, joka laskee Hessenin.
Rosenbrock-funktion Hessen-funktio analyyttisessä muodossa on yhtä suuri kuin:
missä и , määrittele matriisi .
Matriisin loput nollasta poikkeavat elementit ovat yhtä suuria kuin:
Esimerkiksi viisiulotteisessa avaruudessa N = 5 Rosenbrock-funktion Hessen-matriisi on nauhan muotoinen:
Koodi, joka laskee tämän Hessenin ja koodin Rosenbrock-funktion minimoimiseksi käyttämällä konjugaattigradientti (Newton) menetelmää:
def rosen_hess(x):
x = np.asarray(x)
H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
diagonal = np.zeros_like(x)
diagonal[0] = 1200*x[0]**2-400*x[1]+2
diagonal[-1] = 200
diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
H = H + np.diag(diagonal)
return H
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hess=rosen_hess,
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 24
[1. 1. 1. 0.99999999 0.99999999]Esimerkki Hessenin tulofunktion ja mielivaltaisen vektorin määritelmästä
Reaalimaailman ongelmissa koko Hessenin matriisin laskeminen ja tallentaminen voi vaatia huomattavia aika- ja muistiresursseja. Tässä tapauksessa itse Hessen-matriisia ei tarvitse määrittää, koska minimointimenettely vaatii vain vektorin, joka on yhtä suuri kuin Hessenin tulo toisen mielivaltaisen vektorin kanssa. Laskennallisesti katsottuna on siis paljon parempi määrittää välittömästi funktio, joka palauttaa Hessenin tulon tuloksen mielivaltaisella vektorilla.
Tarkastellaan hess-funktiota, joka ottaa minimointivektorin ensimmäiseksi argumentiksi ja mielivaltaisen vektorin toiseksi argumentiksi (sekä muiden minimoitavan funktion argumenttien kanssa). Meidän tapauksessamme Rosenbrock-funktion Hessenin tulon laskeminen mielivaltaisella vektorilla ei ole kovin vaikeaa. Jos p on mielivaltainen vektori, sitten tulo on muoto:
Funktio, joka laskee Hessenin ja mielivaltaisen vektorin tulon, välitetään hessp-argumentin arvoksi minimointifunktiolle:
def rosen_hess_p(x, p):
x = np.asarray(x)
Hp = np.zeros_like(x)
Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1]
-400*x[1:-1]*p[2:]
Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
return Hp
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hessp=rosen_hess_p,
options={'xtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 66Konjugoidun gradientin luottamusalueen algoritmi (Newton)
Hessin matriisin huono ehdollisuus ja väärät hakusuunnat voivat aiheuttaa Newtonin konjugaattigradienttialgoritmin tehottomuuden. Tällaisissa tapauksissa etusija annetaan (luottamusalue) konjugaatti Newtonin gradientit.
Esimerkki Hessenin matriisin määritelmästä:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 19
[1. 1. 1. 1. 1.]Esimerkki Hessenin tulofunktiosta ja mielivaltaisesta vektorista:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 0
[1. 1. 1. 1. 1.]Krylov-tyyppiset menetelmät
Trust-ncg-menetelmän tavoin Krylov-tyyppiset menetelmät sopivat hyvin suurten ongelmien ratkaisemiseen, koska niissä käytetään vain matriisivektorituloja. Niiden ydin on ratkaista ongelma luottamusalueella, jota rajoittaa katkaistu Krylov-aliavaruus. Epävarmoihin ongelmiin on parempi käyttää tätä menetelmää, koska se käyttää vähemmän epälineaarisia iteraatioita, koska matriisivektorituloja on pienempi määrä aliongelmaa kohti verrattuna luottamus-ncg-menetelmään. Lisäksi neliöllisen aliongelman ratkaisu löydetään tarkemmin kuin käyttämällä trust-ncg-menetelmää.
Esimerkki Hessenin matriisin määritelmästä:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 18
print(res.x)
[1. 1. 1. 1. 1.]
Esimerkki Hessenin tulofunktiosta ja mielivaltaisesta vektorista:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algoritmi likimääräiselle ratkaisulle luottamusalueella
Kaikki menetelmät (Newton-CG, trust-ncg ja trust-krylov) soveltuvat hyvin suurten (tuhansien muuttujien) ongelmien ratkaisemiseen. Tämä johtuu siitä, että taustalla oleva konjugaattigradienttialgoritmi edellyttää käänteisen Hessin matriisin likimääräistä määritystä. Ratkaisu löydetään iteratiivisesti ilman Hessenin nimenomaista laajentamista. Koska sinun on määritettävä funktio vain Hessenin ja mielivaltaisen vektorin tulolle, tämä algoritmi on erityisen hyvä harvoille (kaistalävistäjä) matriiseille. Tämä tarjoaa alhaiset muistikustannukset ja huomattavat ajansäästöt.
Keskikokoisissa ongelmissa Hessianin varastointi- ja suhdekustannukset eivät ole kriittisiä. Tämä tarkoittaa, että on mahdollista saada ratkaisu harvemmalla iteraatiolla, mikä ratkaisee luottamusalueen aliongelmat lähes tarkasti. Tätä varten jotkin epälineaariset yhtälöt ratkaistaan iteratiivisesti jokaiselle toisen asteen alitehtävälle. Tällainen ratkaisu vaatii yleensä 3 tai 4 Cholesky-hajotelmaa Hessen-matriisista. Tämän seurauksena menetelmä konvergoi harvemmissa iteraatioissa ja vaatii vähemmän tavoitefunktiolaskelmia kuin muut toteutetut luottamusalueen menetelmät. Tämä algoritmi sisältää vain täydellisen Hessin matriisin määrittämisen, eikä se tue mahdollisuutta käyttää Hessenin ja mielivaltaisen vektorin tulofunktiota.
Esimerkki Rosenbrock-toiminnon minimoinnista:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization terminated successfully.
Current function value: 0.000000
Iterations: 13
Function evaluations: 14
Gradient evaluations: 13
Hessian evaluations: 14
array([1., 1., 1., 1., 1.])Todennäköisesti lopetamme siihen. Seuraavassa artikkelissa yritän kertoa mielenkiintoisimmista asioista ehdollisen minimoinnin, minimoinnin soveltamisesta approksimaatioongelmien ratkaisemiseen, yhden muuttujan funktion minimoimisesta, mielivaltaisista minimointityökaluista ja yhtälöjärjestelmän juurien löytämisestä scipy.optimize-tiedoston avulla. paketti.
Lähde:
Lähde: will.com