SciPy (hääldatakse sai pie) on Numpy Pythoni laiendil põhinev matemaatiline rakenduspakett. SciPy abil muutub teie interaktiivne Pythoni seanss samasuguseks täielikuks andmeteaduseks ja keerukaks süsteemi prototüüpimiskeskkonnaks nagu MATLAB, IDL, Octave, R-Lab ja SciLab. Täna tahan lühidalt rääkida, kuidas kasutada mõnda tuntud optimeerimisalgoritmi paketis scipy.optimize. Üksikasjalikumat ja ajakohasemat abi funktsioonide kasutamise kohta saab alati käsu help() või Shift+Tab abil.
Sissejuhatus
Et säästa ennast ja lugejaid esmaste allikate otsimisest ja lugemisest, on meetodite kirjelduste lingid peamiselt Vikipeedias. Reeglina on see teave piisav, et mõista meetodeid üldiselt ja nende rakendamise tingimusi. Matemaatiliste meetodite olemuse mõistmiseks järgi linke autoriteetsematele väljaannetele, mille leiate iga artikli lõpust või oma lemmikotsingumootorist.
Seega sisaldab moodul scipy.optimize järgmiste protseduuride rakendamist:
- Mitme muutuja skalaarfunktsioonide tingimuslik ja tingimusteta minimeerimine (minimaalne), kasutades erinevaid algoritme (Nelder-Mead simplex, BFGS, Newtoni konjugaadi gradiendid, и )
- Globaalne optimeerimine (näiteks: , )
- Jääkide minimeerimine (least_quares) ja kõvera sobitusalgoritmid, mis kasutavad mittelineaarseid vähimruutusid (curve_fit)
- Ühe muutuja skalaarfunktsioonide minimeerimine (minim_scalar) ja juurte otsimine (root_scalar)
- Võrrandisüsteemi (juur) mitmemõõtmelised lahendajad, kasutades erinevaid algoritme (hübriid Powell, või suuremahulisi meetodeid nagu ).
Selles artiklis käsitleme ainult esimest üksust kogu loendist.
Mitme muutuja skalaarfunktsiooni tingimusteta minimeerimine
Minimeerimisfunktsioon paketist scipy.optimize pakub üldist liidest mitme muutuja skalaarfunktsioonide tingimusliku ja tingimusteta minimeerimise probleemide lahendamiseks. Selle toimimise demonstreerimiseks vajame mitme muutuja sobivat funktsiooni, mida me erinevatel viisidel minimeerime.
Nendel eesmärkidel on täiuslik N muutuja Rosenbrocki funktsioon, mille vorm on:
Vaatamata sellele, et Rosenbrocki funktsioon ja selle Jacobi ja Hessi maatriksid (vastavalt esimene ja teine tuletis) on juba scipy.optimize paketis defineeritud, defineerime selle ise.
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)Selguse huvides joonistame 3D-s kahe muutuja Rosenbrocki funktsiooni väärtused.
Joonistuskood
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()
Teades ette, et miinimum on 0 at , vaatame näiteid, kuidas määrata Rosenbrocki funktsiooni miinimumväärtust erinevate scipy.optimize protseduuride abil.
Nelder-Meadi simpleksmeetod
Olgu 0-mõõtmelises ruumis algpunkt x5. Leiame algoritmi abil Rosenbrocki funktsiooni miinimumpunkti, mis on talle kõige lähemal (algoritm on määratud meetodi parameetri väärtusena):
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.]Simpleksmeetod on lihtsaim viis selgelt määratletud ja üsna sujuva funktsiooni minimeerimiseks. See ei nõua funktsiooni tuletisi arvutamist, piisab ainult selle väärtuste määramisest. Nelder-Meadi meetod on hea valik lihtsate minimeerimisprobleemide lahendamiseks. Kuna see aga ei kasuta gradiendi hinnanguid, võib miinimumi leidmine võtta kauem aega.
Powelli meetod
Teine optimeerimisalgoritm, milles arvutatakse ainult funktsiooni väärtused, on . Selle kasutamiseks tuleb minim-funktsioonis määrata method = 'powell'.
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) algoritm
Lahendusele kiirema lähenemise saavutamiseks protseduur kasutab sihtfunktsiooni gradienti. Gradiendi saab määrata funktsioonina või arvutada esimest järku erinevuste abil. Igal juhul nõuab BFGS-meetod tavaliselt vähem funktsioonikutseid kui simpleksmeetod.
Leiame Rosenbrocki funktsiooni tuletise analüütilisel kujul:
See avaldis kehtib kõigi muutujate tuletistele, välja arvatud esimene ja viimane, mis on määratletud järgmiselt:
Vaatame Pythoni funktsiooni, mis arvutab selle gradiendi:
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 derGradiendi arvutamise funktsioon on määratud minimeerimisfunktsiooni jac parameetri väärtusena, nagu allpool näidatud.
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]Konjugeeritud gradiendi algoritm (Newton)
Algoritm on modifitseeritud Newtoni meetod.
Newtoni meetod põhineb kohaliku piirkonna funktsiooni lähendamisel teise astme polünoomiga:
kus on teise tuletise maatriks (Hessi maatriks, Hessi maatriks).
Kui Hesse on positiivne kindel, siis selle funktsiooni lokaalse miinimumi saab leida ruutvormi nullgradiendi võrdsustamise teel nulliga. Tulemuseks on väljend:
Hessi pöördväärtus arvutatakse konjugeeritud gradiendi meetodil. Allpool on toodud näide selle meetodi kasutamisest Rosenbrocki funktsiooni minimeerimiseks. Newtoni-CG meetodi kasutamiseks peate määrama funktsiooni, mis arvutab Hessi.
Rosenbrocki funktsiooni Hessian analüütilisel kujul on võrdne:
kus и , defineerige maatriks .
Maatriksi ülejäänud nullist erinevad elemendid on võrdsed:
Näiteks viiemõõtmelises ruumis N = 5 on Rosenbrocki funktsiooni Hesse maatriksil riba kuju:
Kood, mis arvutab selle Hesseni koos koodiga Rosenbrocki funktsiooni minimeerimiseks, kasutades konjugeeritud gradiendi (Newtoni) meetodit:
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]Näide Hessi ja suvalise vektori korrutisfunktsiooni definitsiooniga
Reaalsete probleemide korral võib kogu Hesse maatriksi arvutamine ja salvestamine nõuda märkimisväärseid aja- ja mäluressursse. Sel juhul pole tegelikult vaja Hesse maatriksit ennast täpsustada, sest minimeerimisprotseduur nõuab ainult vektorit, mis on võrdne Hessi korrutisega teise suvalise vektoriga. Seega on arvutuslikust seisukohast palju eelistatum kohe defineerida funktsioon, mis tagastab Hessi korrutise tulemuse suvalise vektoriga.
Vaatleme funktsiooni Hess, mis võtab esimese argumendina minimeerimisvektori ja teiseks argumendiks suvalise vektori (koos muude minimeeritava funktsiooni argumentidega). Meie puhul ei ole Rosenbrocki funktsiooni Hessi korrutise arvutamine suvalise vektoriga kuigi keeruline. Kui p on suvaline vektor, siis korrutis tundub, et:
Funktsioon, mis arvutab Hessi ja suvalise vektori korrutise, edastatakse minimeerimisfunktsiooni argumendi hessp väärtusena:
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: 66Konjugeeritud gradiendi usalduspiirkonna algoritm (Newton)
Hesse maatriksi kehv konditsioneerimine ja valed otsingusuunad võivad põhjustada Newtoni konjugeeritud gradiendi algoritmi ebatõhususe. Sellistel juhtudel eelistatakse (usalduspiirkonna) konjugaadi Newtoni gradiendid.
Näide Hesse maatriksi määratlusega:
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.]Näide Hessi ja suvalise vektori korrutisfunktsiooniga:
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.]Krylovi tüüpi meetodid
Sarnaselt usaldus-ncg meetodile sobivad Krylovi tüüpi meetodid hästi suuremahuliste ülesannete lahendamiseks, kuna nendes kasutatakse ainult maatriks-vektorprodukte. Nende olemus on lahendada probleem usalduspiirkonnas, mida piirab kärbitud Krylovi alamruum. Ebakindlate probleemide korral on parem kasutada seda meetodit, kuna see kasutab usaldus-ncg meetodiga võrreldes väiksemat arvu mittelineaarseid iteratsioone, kuna alamprobleemi kohta on väiksem arv maatriks-vektori korruseid. Lisaks leitakse ruutarvulise alamprobleemi lahendus täpsemalt kui usaldus-ncg meetodit kasutades.
Näide Hesse maatriksi määratlusega:
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.]
Näide Hessi ja suvalise vektori korrutisfunktsiooniga:
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.]
Usalduspiirkonna ligikaudse lahenduse algoritm
Kõik meetodid (Newton-CG, trust-ncg ja trust-krylov) sobivad hästi suuremahuliste (tuhandete muutujatega) probleemide lahendamiseks. See on tingitud asjaolust, et aluseks olev konjugeeritud gradiendi algoritm eeldab Hessi pöördmaatriksi ligikaudset määramist. Lahendus leitakse iteratiivselt, ilma Hessi keele selgesõnalise laiendamiseta. Kuna funktsioon tuleb defineerida ainult Hessi ja suvalise vektori korrutisele, on see algoritm eriti hea hõredate (riba diagonaalsete) maatriksitega töötamiseks. See tagab madalad mälukulud ja märkimisväärse aja kokkuhoiu.
Keskmise suurusega probleemide puhul ei ole Hesseni hoiuse- ja faktooringukulud kriitilised. See tähendab, et lahendust on võimalik saada vähemate iteratsioonidega, lahendades usalduspiirkonna alamprobleemid peaaegu täpselt. Selleks lahendatakse mõned mittelineaarsed võrrandid iteratiivselt iga ruutsuuruse alamülesande jaoks. Selline lahendus nõuab tavaliselt 3 või 4 Hessi maatriksi Cholesky dekompositsiooni. Selle tulemusena läheneb meetod vähemate iteratsioonidega ja nõuab vähem eesmärgifunktsiooni arvutusi kui teised rakendatud usalduspiirkonna meetodid. See algoritm hõlmab ainult täieliku Hessi maatriksi määramist ja ei toeta võimalust kasutada Hessi ja suvalise vektori korrutisfunktsiooni.
Näide Rosenbrocki funktsiooni minimeerimise kohta:
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.])Tõenäoliselt lõpetame sellega. Järgmises artiklis püüan rääkida kõige huvitavamast tingimuslikust minimeerimisest, minimeerimise rakendamisest lähendusülesannete lahendamisel, ühe muutuja funktsiooni minimeerimisest, suvalistest minimeerijatest ja võrrandisüsteemi juurte leidmisest scipy.optimize abil. pakett.
Allikas:
Allikas: www.habr.com