SciPy (borið fram sai pie) er stærðfræðilegur forritapakki byggður á Numpy Python viðbótinni. Með SciPy verður gagnvirka Python lotan þín sama fullkomna gagnavísinda- og flóknu frumgerðaumhverfi kerfisins og MATLAB, IDL, Octave, R-Lab og SciLab. Í dag vil ég tala stuttlega um hvernig á að nota nokkur vel þekkt hagræðingaralgrím í scipy.optimize pakkanum. Ítarlegri og uppfærðari hjálp við notkun aðgerða er alltaf hægt að fá með help() skipuninni eða með Shift+Tab.
Inngangur
Til að bjarga sjálfum þér og lesendum frá leit og lestri frumheimilda verða tenglar á lýsingar á aðferðum aðallega á Wikipedia. Að jafnaði nægja þessar upplýsingar til að skilja aðferðirnar almennt og skilyrði fyrir beitingu þeirra. Til að skilja kjarna stærðfræðilegra aðferða skaltu fylgja krækjunum á viðurkenndari rit, sem er að finna í lok hverrar greinar eða í uppáhalds leitarvélinni þinni.
Svo, scipy.optimize einingin felur í sér útfærslu á eftirfarandi aðferðum:
- Skilyrt og skilyrðislaus lágmörkun á kvarðaföllum nokkurra breyta (lágmark) með því að nota ýmsar reiknirit (Nelder-Mead simplex, BFGS, Newton samtengda halla, и )
- Alþjóðleg hagræðing (til dæmis: , )
- Lágmarka leifar (minnstu_ferninga) og ferilpassunar reiknirit sem nota ólínulega minnstu ferninga (curve_fit)
- Lágmarka skalaraðgerðir einnar breytu (minim_scalar) og leita að rótum (root_scalar)
- Fjölvíða leysir jöfnukerfis (rót) með ýmsum reikniritum (blendingur Powell, eða stórum stílaðferðum eins og ).
Í þessari grein munum við aðeins fjalla um fyrsta atriðið af öllum þessum lista.
Skilyrðislaus lágmörkun á kvarðafalli nokkurra breyta
Lágmarksaðgerðin úr scipy.optimize pakkanum veitir almennt viðmót til að leysa skilyrt og skilyrðislaus lágmarksvandamál stigstærðaraðgerða af nokkrum breytum. Til að sýna fram á hvernig það virkar, þurfum við viðeigandi fall af nokkrum breytum, sem við munum lágmarka á mismunandi hátt.
Í þessum tilgangi er Rosenbrock fall N breyta fullkomið, sem hefur formið:
Þrátt fyrir þá staðreynd að Rosenbrock fallið og Jacobi og Hessian fylki þess (fyrsta og önnur afleiða, í sömu röð) séu þegar skilgreind í scipy.optimize pakkanum, munum við skilgreina það sjálf.
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)Til glöggvunar skulum við teikna í þrívídd gildi Rosenbrock fallsins af tveimur breytum.
Teikningarkóði
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()
Að vita fyrirfram að lágmarkið er 0 kl , við skulum skoða dæmi um hvernig á að ákvarða lágmarksgildi Rosenbrock fallsins með því að nota ýmsar scipy.optimize aðferðir.
Nelder-Mead simplex aðferð
Látum það vera upphafspunkt x0 í 5-víddarrými. Við skulum finna lágmarkspunkt Rosenbrock fallsins sem er næst henni með því að nota reikniritið (algrímið er tilgreint sem gildi aðferðarfæribreytunnar):
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.]Simplex aðferðin er einfaldasta leiðin til að lágmarka skýrt skilgreinda og nokkuð slétta virkni. Það þarf ekki að reikna út afleiður falls, það er nóg að tilgreina aðeins gildi þess. Nelder-Mead aðferðin er góður kostur fyrir einföld lágmarksvandamál. Hins vegar, þar sem það notar ekki hallamat, getur það tekið lengri tíma að finna lágmarkið.
Powell aðferð
Annað hagræðingaralgrím þar sem aðeins fallgildin eru reiknuð er . Til að nota það þarftu að stilla method = 'powell' í lágmarksaðgerðinni.
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) reiknirit
Til að fá hraðari samleitni að lausn, aðferðin notar halla hlutfallsins. Hægt er að tilgreina hallann sem fall eða reikna út með fyrstu röð mismun. Í öllum tilvikum, BFGS aðferðin krefst venjulega færri aðgerðakalla en simplex aðferðin.
Við skulum finna afleiðu Rosenbrock fallsins í greiningarformi:
Þessi tjáning gildir fyrir afleiður allra breyta nema fyrstu og síðustu, sem eru skilgreindar sem:
Við skulum skoða Python fallið sem reiknar þennan halla:
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 derHallaútreikningsfallið er tilgreint sem gildi jac breytu lágmarksfallsins, eins og sýnt er hér að neðan.
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]Samtengdur halli reiknirit (Newton)
Reikniritið er breytt aðferð Newtons.
Aðferð Newtons byggir á því að nálgast fall í staðbundnu svæði með margliðu af annarri gráðu:
þar sem er fylki annars afleiða (hessísk fylki, hessíska).
Ef Hessian er jákvætt ákveðið, þá er hægt að finna staðbundið lágmark þessarar falls með því að jafna núllhalla ferningsformsins við núll. Útkoman verður orðatiltækið:
Andhverfur Hessian er reiknaður út með samtengdu hallaferli. Dæmi um að nota þessa aðferð til að lágmarka Rosenbrock aðgerðina er gefið hér að neðan. Til að nota Newton-CG aðferðina verður þú að tilgreina fall sem reiknar hessíuna.
Hessian of the Rosenbrock fall í greiningarformi er jafnt og:
þar sem и , skilgreinið fylkið .
Eftirstandandi frumefni fylkisins sem ekki eru núll eru jöfn:
Til dæmis, í fimmvíðu rými N = 5, er hessíska fylkið fyrir Rosenbrock fallið í formi bands:
Kóði sem reiknar þetta hessian ásamt kóða til að lágmarka Rosenbrock fallið með því að nota samtengda halla (Newton) aðferðina:
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]Dæmi með skilgreiningu á afurðarfalli Hessíunnar og handahófskenndum vektor
Í raunveruleikavandamálum getur það að reikna út og geymt allt Hessian fylkið krefst verulegs tíma og minnisauðlinda. Í þessu tilviki er í raun engin þörf á að tilgreina Hessian fylkið sjálft, vegna þess að lágmarksaðferðin krefst aðeins vigurs sem jafngildir margfeldi Hessíunnar með öðrum handahófskenndum vektor. Þannig, frá reiknisjónarmiði, er miklu æskilegra að skilgreina strax fall sem skilar niðurstöðu af margfeldi Hessíunnar með handahófskenndum vektor.
Lítum á hess fallið, sem tekur lágmörkunarvigurinn sem fyrstu röksemd, og handahófskenndan vektor sem seinni röksemdina (ásamt öðrum rökum fallsins sem á að lágmarka). Í okkar tilviki er ekki mjög erfitt að reikna út margfeldi Hessian af Rosenbrock fallinu með handahófskenndum vektor. Ef p er handahófskenndur vektor, þá afurðin lítur út eins og:
Fallið sem reiknar út margfeldi hessíunnar og handahófskenndra vigurs er sent sem gildi hessp röksemdarinnar til lágmarksfallsins:
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: 66Conjugate gradient trust region algorithm (Newton)
Léleg skilyrðing á Hessian fylkinu og rangar leitarleiðbeiningar geta valdið því að samtengda halla reiknirit Newtons sé óvirkt. Í slíkum tilfellum er valið (traust-svæði) samtengdu Newton halla.
Dæmi með skilgreiningu á hessíska fylkinu:
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.]Dæmi með afurðarfalli Hessian og handahófskenndan vektor:
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 gerð aðferðir
Eins og trust-ncg aðferðin henta Krylov-gerð aðferðir vel til að leysa stór vandamál vegna þess að þær nota aðeins fylkisvektorvörur. Kjarni þeirra er að leysa vandamál á sjálfstraustssvæði sem takmarkast af styttu Krylov undirrými. Fyrir óviss vandamál er betra að nota þessa aðferð, þar sem hún notar minni fjölda ólínulegra endurtekninga vegna minni fjölda fylkisvektorafurða á undirvandamáli, samanborið við trust-ncg aðferðina. Að auki er lausnin á fjórðungs undirvandamálinu fundin nákvæmari en að nota trust-ncg aðferðina.
Dæmi með skilgreiningu á hessíska fylkinu:
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.]
Dæmi með afurðarfalli Hessian og handahófskenndan vektor:
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.]
Reiknirit fyrir áætlaða lausn á öryggissvæðinu
Allar aðferðir (Newton-CG, trust-ncg og trust-krylov) henta vel til að leysa stór vandamál (með þúsundum breyta). Þetta er vegna þess að undirliggjandi samtengda halla reiknirit felur í sér áætlaða ákvörðun á andhverfu Hessian fylki. Lausnin er fundin ítrekað, án skýrrar útvíkkunar á Hessian. Þar sem þú þarft aðeins að skilgreina fall fyrir margfeldi hessíu og handahófsvigurs, er þetta reiknirit sérstaklega gott til að vinna með dreifðar (band ská) fylki. Þetta veitir lágan minniskostnað og verulegan tímasparnað.
Fyrir meðalstór vandamál er kostnaður við að geyma og þátta Hessian ekki mikilvægur. Þetta þýðir að hægt er að fá lausn í færri endurtekningum og leysa undirvandamál traustsvæðisins nánast nákvæmlega. Til að gera þetta eru nokkrar ólínulegar jöfnur leystar ítrekað fyrir hvert annars stigs undirdæmi. Slík lausn krefst venjulega 3 eða 4 Cholesky niðurbrot á Hessian fylkinu. Fyrir vikið rennur aðferðin saman í færri endurtekningar og krefst færri hlutlægra fallútreikninga en aðrar útfærðar öryggissvæðisaðferðir. Þetta reiknirit felur aðeins í sér að ákvarða heildarhessíska fylkið og styður ekki getu til að nota afurðarfall hessans og handahófskenndan vektor.
Dæmi um lágmörkun á Rosenbrock fallinu:
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.])Við stoppum líklega þar. Í næstu grein mun ég reyna að segja það áhugaverðasta um skilyrta lágmörkun, beitingu lágmarks við að leysa nálgunarvandamál, lágmarka fall af einni breytu, handahófskenndar lágmörk og finna rætur jöfnukerfis með því að nota scipy.optimize pakka.
Heimild:
Heimild: www.habr.com