SciPy (pwononse sai pie) se yon pake aplikasyon matematik ki baze sou ekstansyon Numpy Python. Avèk SciPy, sesyon entèaktif Python ou a vin menm syans done konplè ak anviwònman pwototip sistèm konplèks kòm MATLAB, IDL, Octave, R-Lab, ak SciLab. Jodi a mwen vle pale yon ti tan sou fason yo sèvi ak kèk algoritm optimize byen li te ye nan pake a scipy.optimize. Ou ka toujou jwenn èd ki pi detaye ak ajou sou itilizasyon fonksyon lè l sèvi avèk èd () kòmand la oswa lè l sèvi avèk Shift + Tab.
Entwodiksyon
Pou sove tèt ou ak lektè yo nan rechèch ak li sous prensipal yo, lyen ki mennen nan deskripsyon metòd yo pral sitou sou Wikipedya. Kòm yon règ, enfòmasyon sa a se ase yo konprann metòd yo an tèm jeneral ak kondisyon yo pou aplikasyon yo. Pou konprann sans metòd matematik, swiv lyen ki mennen nan piblikasyon ki gen plis otorite, ki ka jwenn nan fen chak atik oswa nan motè rechèch ou pi renmen.
Se konsa, modil la scipy.optimize gen ladan aplikasyon an nan pwosedi sa yo:
- Minimize kondisyonèl ak enkondisyonèl nan fonksyon eskalè plizyè varyab (minimòm) lè l sèvi avèk divès algoritm (Nelder-Mead senp, BFGS, gradyan konjige Newton, и )
- Optimize mondyal (pa egzanp: , )
- Minimize rezidyèl yo (least_squares) ak algorithm adapte koub lè l sèvi avèk pi piti kare ki pa lineyè (curve_fit)
- Minimize fonksyon eskalar yon varyab (minim_scalar) ak rechèch pou rasin (root_scalar)
- Solveur miltidimansyonèl nan sistèm ekwasyon (rasin) lè l sèvi avèk divès algoritm (ibrid Powell, oswa metòd gwo echèl tankou ).
Nan atik sa a nou pral konsidere sèlman premye atik la nan tout lis sa a.
Minimize san kondisyon yon fonksyon eskalè plizyè varyab
Fonksyon minim ki soti nan pake scipy.optimize bay yon koòdone jeneral pou rezoud pwoblèm minimize kondisyonèl ak enkondisyonèl nan fonksyon eskalè plizyè varyab. Pou demontre kijan li fonksyone, nou pral bezwen yon fonksyon apwopriye nan plizyè varyab, ke nou pral minimize nan diferan fason.
Pou rezon sa yo, fonksyon Rosenbrock N varyab yo pafè, ki gen fòm sa a:
Malgre lefèt ke fonksyon Rosenbrock la ak matris Jacobi ak Hessian li yo (premye ak dezyèm dérivés, respektivman) deja defini nan pake scipy.optimize, nou pral defini li tèt nou.
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)Pou klè, ann desine an 3D valè fonksyon Rosenbrock de varyab yo.
Kòd desen
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()
Konnen davans ke minimòm lan se 0 at , ann gade egzanp sou fason pou detèmine valè minimòm fonksyon Rosenbrock lè l sèvi avèk plizyè pwosedi scipy.optimize.
Metòd senp Nelder-Mead
Se pou gen yon pwen inisyal x0 nan espas 5 dimansyon. Ann jwenn pwen minimòm fonksyon Rosenbrock ki pi pre li a lè l sèvi avèk algorithm la (se algorithm la espesifye kòm valè a nan paramèt metòd la):
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.]Metòd senp la se fason ki pi senp pou minimize yon fonksyon ki defini klèman e ki san patipri. Li pa mande pou kalkile dérivés yon fonksyon; li ase pou presize sèlman valè li yo. Metòd Nelder-Mead la se yon bon chwa pou pwoblèm minimize senp. Sepandan, piske li pa sèvi ak estimasyon gradyan, li ka pran plis tan pou jwenn minimòm la.
Metòd Powell
Yon lòt algorithm optimize nan ki sèlman valè fonksyon yo kalkile se . Pou itilize li, ou bezwen mete metòd = 'powell' nan fonksyon minim la.
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.]Algorithm Broyden-Fletcher-Goldfarb-Shanno (BFGS).
Pou jwenn pi vit dirèksyon nan yon solisyon, pwosedi a sèvi ak gradyan fonksyon objektif la. Ka gradyan an dwe espesifye kòm yon fonksyon oswa kalkile lè l sèvi avèk diferans premye lòd. Nan nenpòt ka, metòd BFGS tipikman mande pou mwens apèl fonksyon pase metòd la senp.
Ann jwenn dérivés fonksyon Rosenbrock nan fòm analyse:
Ekspresyon sa a valab pou dérivés tout varyab eksepte premye ak dènye a, ki defini kòm:
Ann gade fonksyon Python ki kalkile gradyan sa a:
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 derFonksyon kalkil gradyan an espesifye kòm valè paramèt jac nan fonksyon minim la, jan yo montre anba a.
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]Algorithm gradyan konjige (Newton)
Algorithm la se yon metòd Newton modifye.
Metòd Newton a baze sou apwoksimasyon yon fonksyon nan yon zòn lokal pa yon polinòm dezyèm degre:
kote se matris dezyèm dérivés (Matrice Hessian, Hessian).
Si Hessian an se defini pozitif, lè sa a ou ka jwenn minimòm lokal fonksyon sa a lè w egalize gradyan zewo fòm kwadratik la ak zewo. Rezilta a pral ekspresyon:
Hessian envès la kalkile lè l sèvi avèk metòd gradyan konjige. Yo bay yon egzanp sou itilizasyon metòd sa a pou minimize fonksyon Rosenbrock la anba a. Pou itilize metòd Newton-CG, ou dwe presize yon fonksyon ki kalkile Hessian la.
Hessian nan fonksyon Rosenbrock nan fòm analyse egal a:
kote и , defini matris la .
Eleman ki pa zewo ki rete nan matris la egal a:
Pou egzanp, nan yon espas senk dimansyon N = 5, matris Hessian pou fonksyon Rosenbrock la gen fòm yon bann:
Kòd ki kalkile Hessian sa a ansanm ak kòd pou minimize fonksyon Rosenbrock lè l sèvi avèk metòd gradyan konjige (Newton):
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]Yon egzanp ak definisyon an nan fonksyon an pwodwi nan Hessian a ak yon vektè abitrè
Nan pwoblèm nan mond reyèl la, enfòmatik ak estoke tout matris Hessian ka mande anpil tan ak resous memwa. Nan ka sa a, gen aktyèlman pa bezwen presize matris Hessian tèt li, paske pwosedi minimize a mande sèlman yon vektè ki egal a pwodwi Hessian a ak yon lòt vektè abitrè. Kidonk, nan yon pwen de vi enfòmatik, li pi preferab pou defini imedyatman yon fonksyon ki retounen rezilta pwodwi Hessian a ak yon vektè abitrè.
Konsidere fonksyon hess la, ki pran vektè minimize a kòm premye agiman, ak yon vektè abitrè kòm dezyèm agiman (ansanm ak lòt agiman nan fonksyon yo dwe minimize). Nan ka nou an, kalkile pwodwi Hessian nan fonksyon Rosenbrock ak yon vektè abitrè pa trè difisil. Si p se yon vektè abitrè, Lè sa a, pwodwi a sanble ak:
Fonksyon ki kalkile pwodwi Hessian a ak yon vektè abitrè yo pase kòm valè agiman hessp nan fonksyon minimize:
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: 66Konjige algorithm rejyon konfyans gradyan (Newton)
Move kondisyone nan matris Hessian ak direksyon rechèch kòrèk ka lakòz algorithm gradyan konjige Newton a pa efikas. Nan ka sa yo, yo bay preferans (trust-region) konjige gradyan Newton.
Egzanp ak definisyon matris Hessian:
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.]Egzanp ak fonksyon pwodwi Hessian a ak yon vektè abitrè:
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.]Metòd kalite Krylov
Menm jan ak metòd konfyans-ncg, metòd Krylov-kalite yo byen adapte pou rezoud pwoblèm gwo echèl paske yo itilize sèlman pwodwi matris-vektè. Sans yo se rezoud yon pwoblèm nan yon rejyon konfyans limite pa yon sousespas Krylov twonke. Pou pwoblèm ensèten, li pi bon pou itilize metòd sa a, paske li itilize yon pi piti kantite iterasyon ki pa lineyè akòz pi piti kantite pwodwi matris-vektè pou chak subproblem, konpare ak metòd konfyans-ncg. Anplis de sa, yo jwenn solisyon pou subpwoblèm kwadratik la pi byen pase lè l sèvi avèk metòd trust-ncg la.
Egzanp ak definisyon matris Hessian:
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.]
Egzanp ak fonksyon pwodwi Hessian a ak yon vektè abitrè:
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.]
Algorithm pou solisyon apwoksimatif nan rejyon an konfyans
Tout metòd (Newton-CG, trust-ncg ak trust-krylov) yo byen adapte pou rezoud pwoblèm gwo echèl (ak dè milye de varyab). Sa a se akòz lefèt ke algorithm gradyan konjige ki kache a enplike yon detèminasyon apwoksimatif nan matris Hessian envès la. Yo jwenn solisyon an iteratif, san ekspansyon eksplisit nan Hessian la. Piske ou sèlman bezwen defini yon fonksyon pou pwodwi yon Hessian ak yon vektè abitrè, algorithm sa a se espesyalman bon pou travay ak matris sparse (band dyagonal). Sa a bay depans memwa ki ba ak ekonomi tan enpòtan.
Pou pwoblèm mwayen gwosè, pri pou estoke ak faktè Hessian a pa kritik. Sa vle di ke li posib jwenn yon solisyon nan mwens iterasyon, rezoud pwoblèm yo nan rejyon an konfyans prèske egzakteman. Pou fè sa, yo rezoud kèk ekwasyon ki pa lineyè yon fason iterativ pou chak pwoblèm kwadratik. Yon solisyon konsa anjeneral mande pou 3 oswa 4 dekonpozisyon Cholesky nan matris Hessian la. Kòm yon rezilta, metòd la konvèje nan mwens iterasyon epi li mande mwens kalkil fonksyon objektif pase lòt metòd rejyon konfyans yo aplike. Algorithm sa a sèlman enplike detèmine matris Hessian konplè a epi li pa sipòte kapasite nan sèvi ak fonksyon an pwodwi nan Hessian a ak yon vektè abitrè.
Egzanp ak minimize fonksyon Rosenbrock:
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.])Nou pwal pwobableman kanpe la. Nan pwochen atik la mwen pral eseye di bagay ki pi enteresan sou minimize kondisyonèl, aplikasyon pou minimize nan rezoud pwoblèm apwoksimasyon, minimize yon fonksyon yon varyab, minimize abitrè, ak jwenn rasin yo nan yon sistèm ekwasyon lè l sèvi avèk scipy.optimize la. pake.
Sous:
Sous: www.habr.com