SciPy (tariama sai pie) yra matematinės programos paketas, pagrįstas Numpy Python plėtiniu. Su „SciPy“ jūsų interaktyvioji „Python“ sesija tampa tokia pačia išsamia duomenų mokslo ir sudėtingų sistemų prototipų kūrimo aplinka kaip MATLAB, IDL, Octave, R-Lab ir SciLab. Šiandien noriu trumpai pakalbėti apie kai kuriuos gerai žinomus optimizavimo algoritmus scipy.optimize pakete. Išsamesnę ir atnaujintą funkcijų naudojimo pagalbą visada galite gauti naudodami komandą help() arba Shift+Tab.
įvedimas
Siekiant apsaugoti save ir skaitytojus nuo pirminių šaltinių paieškos ir skaitymo, nuorodos į metodų aprašymus daugiausia bus Vikipedijoje. Paprastai šios informacijos pakanka, kad būtų galima suprasti metodus ir jų taikymo sąlygas. Norėdami suprasti matematinių metodų esmę, vadovaukitės nuorodomis į autoritetingesnius leidinius, kuriuos rasite kiekvieno straipsnio pabaigoje arba savo mėgstamoje paieškos sistemoje.
Taigi, modulis scipy.optimize apima šių procedūrų įgyvendinimą:
- Sąlyginis ir besąlyginis kelių kintamųjų skaliarinių funkcijų sumažinimas (minimumas), naudojant įvairius algoritmus (Nelder-Mead simplex, BFGS, Newton konjugato gradientai, и )
- Visuotinis optimizavimas (pvz.: , )
- Likučių mažinimas (mažiausi_kvadratai) ir kreivės pritaikymo algoritmai, naudojant netiesinius mažiausius kvadratus (curve_fit)
- Vieno kintamojo skaliarinių funkcijų sumažinimas (minim_scalar) ir šaknų paieška (root_scalar)
- Daugiamačiai lygčių sistemos sprendėjai (šaknis), naudojant įvairius algoritmus (hibridinis Powell, arba didelio masto metodai, pvz ).
Šiame straipsnyje mes apsvarstysime tik pirmąjį elementą iš viso sąrašo.
Besąlyginis kelių kintamųjų skaliarinės funkcijos sumažinimas
Minimumo funkcija iš scipy.optimize paketo suteikia bendrąją sąsają kelių kintamųjų skaliarinių funkcijų sąlyginio ir besąlyginio minimizavimo problemoms spręsti. Norėdami parodyti, kaip tai veikia, mums reikės tinkamos kelių kintamųjų funkcijos, kurias įvairiais būdais sumažinsime.
Šiems tikslams puikiai tinka N kintamųjų Rosenbrock funkcija, kuri turi tokią formą:
Nepaisant to, kad Rosenbrock funkcija ir jos Jacobi bei Hessian matricos (atitinkamai pirmoji ir antroji išvestinės) jau yra apibrėžtos scipy.optimize pakete, mes ją apibrėžsime patys.
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)Aiškumo dėlei nubrėžkime 3D dviejų kintamųjų Rosenbrock funkcijos reikšmes.
Piešimo kodas
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()
Iš anksto žinant, kad minimumas yra 0 at , pažvelkime į pavyzdžius, kaip nustatyti mažiausią Rosenbrock funkcijos reikšmę naudojant įvairias scipy.optimize procedūras.
Nelder-Mead simplex metodas
Tegul 0-matėje erdvėje yra pradinis taškas x5. Naudodami algoritmą suraskime arčiausiai jai esantį mažiausią Rosenbrock funkcijos tašką (algoritmas nurodytas kaip metodo parametro reikšmė):
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.]Simpleksinis metodas yra paprasčiausias būdas sumažinti aiškiai apibrėžtą ir gana sklandžią funkciją. Tam nereikia skaičiuoti funkcijos išvestinių, pakanka nurodyti tik jos reikšmes. Nelder-Mead metodas yra geras pasirinkimas paprastoms mažinimo problemoms spręsti. Tačiau, kadangi jame nenaudojami gradiento įverčiai, minimumo nustatymas gali užtrukti ilgiau.
Powell metodas
Kitas optimizavimo algoritmas, kuriame apskaičiuojamos tik funkcijų reikšmės, yra . Norėdami jį naudoti, minimalioje funkcijoje turite nustatyti metodą = '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) algoritmas
Kad greičiau priartėtų prie sprendimo, procedūra naudoja tikslo funkcijos gradientą. Gradientas gali būti nurodytas kaip funkcija arba apskaičiuotas naudojant pirmos eilės skirtumus. Bet kuriuo atveju BFGS metodui paprastai reikia mažiau funkcijų iškvietimų nei vienpusio metodo.
Raskime Rosenbrock funkcijos išvestinę analitine forma:
Ši išraiška galioja visų kintamųjų, išskyrus pirmąjį ir paskutinįjį, išvestiniams, kurie apibrėžiami taip:
Pažvelkime į Python funkciją, kuri apskaičiuoja šį gradientą:
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 derGradiento skaičiavimo funkcija nurodoma kaip minimalios funkcijos jac parametro reikšmė, kaip parodyta toliau.
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]Konjuguoto gradiento algoritmas (niutonas)
Algoritmas yra modifikuotas Niutono metodas.
Niutono metodas pagrįstas funkcijos vietinėje srityje aproksimavimu antrojo laipsnio polinomu:
kur yra antrųjų darinių matrica (Heso matrica, Heso matrica).
Jei Hesenas yra teigiamas apibrėžtasis, tai šios funkcijos lokalinį minimumą galima rasti kvadratinės formos nulinį gradientą prilyginus nuliui. Rezultatas bus išraiška:
Atvirkštinis Hesenas apskaičiuojamas naudojant konjuguoto gradiento metodą. Žemiau pateikiamas šio metodo naudojimo, siekiant sumažinti Rosenbrock funkciją, pavyzdys. Norėdami naudoti Newton-CG metodą, turite nurodyti funkciją, kuri apskaičiuoja Heseno koeficientą.
Rosenbrock funkcijos Hesenas analitine forma yra lygus:
kur и , apibrėžkite matricą .
Likę nuliniai matricos elementai yra lygūs:
Pavyzdžiui, penkiamatėje erdvėje N = 5 Rosenbrock funkcijos Heseno matrica turi juostos formą:
Kodas, apskaičiuojantis šį Heseno kodą kartu su Rosenbrock funkcijos sumažinimo kodu, naudojant konjuguoto gradiento (niutono) metodą:
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]Pavyzdys su Heseno sandaugos funkcijos ir savavališko vektoriaus apibrėžimu
Esant realioms problemoms, visos Heseno matricos skaičiavimas ir saugojimas gali pareikalauti daug laiko ir atminties išteklių. Šiuo atveju iš tikrųjų nereikia nurodyti pačios Heseno matricos, nes minimizavimo procedūrai reikalingas tik vektorius, lygus Heseno sandaugai su kitu savavališku vektoriumi. Taigi, skaičiavimo požiūriu, daug geriau iš karto apibrėžti funkciją, kuri grąžina Heseno sandaugos rezultatą su savavališku vektoriumi.
Apsvarstykite Heso funkciją, kuri kaip pirmąjį argumentą laiko sumažinimo vektorių, o antruoju argumentu – savavališką vektorių (kartu su kitais sumažintinos funkcijos argumentais). Mūsų atveju Rosenbrock funkcijos Heseno sandaugą su savavališku vektoriumi apskaičiuoti nėra labai sunku. Jeigu p yra savavališkas vektorius, tada sandauga atrodo kaip:
Funkcija, apskaičiuojanti Heso ir savavališko vektoriaus sandaugą, perduodama kaip hessp argumento reikšmė minimizavimo funkcijai:
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: 66Konjuguoto gradiento pasitikėjimo regiono algoritmas (niutonas)
Dėl blogo Heseno matricos sąlygų ir neteisingų paieškos krypčių Niutono konjuguoto gradiento algoritmas gali būti neveiksmingas. Tokiais atvejais pirmenybė teikiama (pasitikėjimo regionas) konjugato Niutono gradientai.
Heseno matricos apibrėžimo pavyzdys:
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.]Pavyzdys su Heseno sandaugos funkcija ir savavališku vektoriumi:
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.]Krylovo tipo metodai
Kaip ir pasitikėjimo-ncg metodas, Krylovo tipo metodai puikiai tinka didelės apimties problemoms spręsti, nes juose naudojami tik matricos-vektoriaus sandaugai. Jų esmė yra išspręsti problemą pasitikėjimo regione, kurį riboja sutrumpinta Krylovo poerdvė. Neaiškioms problemoms geriau naudoti šį metodą, nes jis naudoja mažesnį netiesinių iteracijų skaičių dėl mažesnio matricos-vektoriaus sandaugų skaičiaus vienoje subproblemoje, palyginti su pasitikėjimo-ncg metodu. Be to, kvadratinės subproblemos sprendimas randamas tiksliau nei naudojant pasitikėjimo-ncg metodą.
Heseno matricos apibrėžimo pavyzdys:
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.]
Pavyzdys su Heseno sandaugos funkcija ir savavališku vektoriumi:
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.]
Apytikslio sprendimo patikimumo srityje algoritmas
Visi metodai (Newton-CG, trust-ncg ir trust-krylov) puikiai tinka didelės apimties problemoms (su tūkstančiais kintamųjų) spręsti. Taip yra dėl to, kad pagrindinis konjuguoto gradiento algoritmas reiškia apytikslį atvirkštinės Heseno matricos nustatymą. Sprendimas randamas iteratyviai, aiškiai neišplečiant Heseno kalbos. Kadangi jums tereikia apibrėžti funkciją Heseno ir savavališko vektoriaus sandaugai, šis algoritmas ypač tinka dirbant su retomis (juostos įstrižainės) matricomis. Tai sumažina atminties sąnaudas ir sutaupo daug laiko.
Kalbant apie vidutinio dydžio problemas, Hessian saugojimo ir faktoringo kaina nėra kritinė. Tai reiškia, kad sprendimą galima gauti atliekant mažiau iteracijų, beveik tiksliai išsprendžiant pasitikėjimo regiono subproblemas. Norėdami tai padaryti, kai kurios netiesinės lygtys išsprendžiamos iteratyviai kiekvienai kvadratinei daliai. Tokiam sprendimui paprastai reikia 3 arba 4 Heseno matricos Cholesky skaidymų. Dėl to metodas konverguoja atliekant mažiau iteracijų ir reikalauja mažiau objektyvių funkcijų skaičiavimų nei kiti įgyvendinti pasitikėjimo srities metodai. Šis algoritmas apima tik visos Heseno matricos nustatymą ir nepalaiko galimybės naudoti Heseno ir savavališko vektoriaus sandaugos funkciją.
Pavyzdys su Rosenbrock funkcijos sumažinimu:
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.])Tikriausiai tuo ir sustosime. Kitame straipsnyje pabandysiu papasakoti įdomiausius dalykus apie sąlyginį minimizavimą, minimizavimo taikymą sprendžiant aproksimacijos uždavinius, vieno kintamojo funkcijos minimizavimą, savavališkus minimizatorius ir lygčių sistemos šaknų suradimą naudojant scipy.optimize. paketą.
Šaltinis:
Šaltinis: www.habr.com