SciPy (pronunciatu sai pie) hè un pacchettu di applicazione matematica basatu annantu à l'estensione Numpy Python. Cù SciPy, a vostra sessione interattiva di Python diventa a stessa scienza di dati cumpleta è un ambiente cumplessu di prototipu di sistema cum'è MATLAB, IDL, Octave, R-Lab è SciLab. Oghje vogliu parlà brevemente di cumu utilizà qualchi algoritmi di ottimisazione cunnisciuti in u pacchettu scipy.optimize. L'aiutu più detallatu è aghjurnatu nantu à l'usu di e funzioni pò sempre esse ottenutu cù u cumandimu help() o usendu Shift+Tab.
Introduzione
Per salvà sè stessu è i lettori da a ricerca è a lettura di e fonti primarie, i ligami à e descrizzioni di i metudi seranu principalmente in Wikipedia. Comu regula, sta infurmazione hè abbastanza per capiscenu i metudi in termini generale è e cundizioni per a so applicazione. Per capiscenu l'essenza di i metudi matematichi, seguitate i ligami per publicazioni più autoritarii, chì ponu esse truvati à a fine di ogni articulu o in u vostru mutore di ricerca favuritu.
Dunque, u modulu scipy.optimize include l'implementazione di e seguenti prucedure:
- Minimizazione condicionale è incondizionata di funzioni scalari di parechje variabili (minimu) cù vari algoritmi (Nelder-Mead simplex, BFGS, gradienti conjugate Newton, и )
- Ottimisazione globale (per esempiu: , )
- Minimizà i residuali (least_squares) è algoritmi di adattazione di curve chì utilizanu minimi quadrati non lineari (curve_fit)
- Minimizazione di e funzioni scalari di una variabile (minim_scalar) è ricerca di radici (root_scalar)
- Risolutori multidimensionali di sistema di equazioni (radice) chì utilizanu diversi algoritmi (Powell ibridu, o metudi à grande scala cum'è ).
In questu articulu avemu da cunsiderà solu u primu articulu di sta lista sana.
Minimizazione incondizionata di una funzione scalare di parechje variabili
A funzione minim da u pacchettu scipy.optimize furnisce una interfaccia generale per risolve i prublemi di minimizazione cundizionale è incondizionale di funzioni scalari di parechje variàbili. Per dimustrà cumu funziona, avemu bisognu di una funzione adattata di parechje variàbili, chì minimizeremu in modi diffirenti.
Per questi scopi, a funzione Rosenbrock di N variàbili hè perfetta, chì hà a forma:
Malgradu u fattu chì a funzione Rosenbrock è e so matrici Jacobi è Hessian (a prima è a seconda derivativa, rispettivamente) sò digià definite in u pacchettu scipy.optimize, avemu da definisce noi stessi.
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)Per a chiarezza, disegnu in 3D i valori di a funzione Rosenbrock di duie variàbili.
Codice di disegnu
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()
Sapendu in anticipu chì u minimu hè 0 at , Fighjemu l'esempii di cumu per determinà u valore minimu di a funzione Rosenbrock usendu diverse prucedure scipy.optimize.
Metudu Nelder-Mead simplex
Chì ci sia un puntu iniziale x0 in u spaziu di 5 dimensioni. Truvemu u puntu minimu di a funzione Rosenbrock più vicinu à questu utilizendu l'algoritmu (l'algoritmu hè specificatu cum'è u valore di u paràmetru di u metudu):
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.]U metudu simplex hè u modu più simplice per minimizzà una funzione esplicitamente definita è abbastanza liscia. Ùn hè micca bisognu di calculà i derivati di una funzione; hè abbastanza per specificà solu i so valori. U metudu Nelder-Mead hè una bona scelta per i prublemi di minimizazione simplici. In ogni casu, postu chì ùn usa micca stima di gradiente, pò piglià più tempu per truvà u minimu.
Metudu Powell
Un altru algoritmu di ottimisazione in quale sò calculati solu i valori di a funzione hè . Per aduprà, avete bisognu di mette u metudu = 'powell' in a funzione minima.
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.]Algoritmu Broyden-Fletcher-Goldfarb-Shanno (BFGS).
Per ottene una cunvergenza più veloce à una suluzione, a prucedura usa u gradiente di a funzione objetiva. U gradiente pò esse specificatu cum'è una funzione o calculatu utilizendu differenze di primu ordine. In ogni casu, u metudu BFGS tipicamente richiede menu chjama di funzione cà u metudu simplex.
Truvemu a derivativa di a funzione di Rosenbrock in forma analitica:
Questa espressione hè valida per i derivati di tutte e variàbili eccettu u primu è l'ultimu, chì sò definiti cum'è:
Fighjemu a funzione Python chì calcula stu gradiente:
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 derA funzione di calculu gradiente hè specificatu cum'è u valore di u paràmetru jac di a funzione minima, cum'è mostra sottu.
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]Algoritmu di gradiente cunjugatu (Newton)
Algoritmu hè un metudu di Newton mudificatu.
U metudu di Newton hè basatu annantu à l'approssimazione di una funzione in una zona lucale da un polinomiu di u sicondu gradu:
induve hè a matrice di derivati secondari (matrice Hessian, Hessian).
Sè u Hessian hè definitu pusitivu, allura u minimu lucale di sta funzione pò esse truvata da equating u gradiente zero di a forma quadratica à zero. U risultatu serà l'espressione:
U Hessian inversu hè calculatu utilizendu u metudu di gradiente cunjugatu. Un esempiu di usu di stu mètudu per minimizzà a funzione Rosenbrock hè datu quì sottu. Per utilizà u metudu Newton-CG, deve specificà una funzione chì calcula l'Hessian.
L'Hessian di a funzione di Rosenbrock in forma analitica hè uguale à:
induve и , definisce a matrice .
L'elementi rimanenti non zero di a matrice sò uguali à:
Per esempiu, in un spaziu di cinque dimensioni N = 5, a matrice Hessian per a funzione Rosenbrock hà a forma di una banda:
Codice chì calcula stu Hessian cù u codice per minimizzà a funzione Rosenbrock utilizendu u metudu di gradiente conjugate (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]Un esempiu cù a definizione di a funzione di u produttu di Hessian è un vettore arbitrariu
In i prublemi di u mondu reale, l'informatica è l'almacenamiento di tutta a matrice Hessiana pò esse bisognu di risorse di tempu è memoria significativa. In questu casu, ùn ci hè micca bisognu di specificà a matrice Hessian stessu, perchè a prucedura di minimizazione richiede solu un vettore uguale à u pruduttu di l'hessianu cù un altru vettore arbitrariu. Cusì, da un puntu di vista computazionale, hè assai preferibile di definisce immediatamente una funzione chì torna u risultatu di u pruduttu di l'hessianu cù un vettore arbitrariu.
Cunsiderate a funzione hess, chì piglia u vettore di minimizazione cum'è u primu argumentu, è un vettore arbitrariu cum'è u sicondu argumentu (inseme cù l'altri argumenti di a funzione per esse minimizatu). In u nostru casu, calculà u pruduttu di u Hessian di a funzione Rosenbrock cù un vettore arbitrariu ùn hè micca assai difficiule. Se p hè un vettore arbitrariu, allora u pruduttu pari cum'è:
A funzione chì calcula u pruduttu di u Hessian è un vettore arbitrariu hè passatu cum'è u valore di l'argumentu hessp à a funzione di 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: 66Conjugate l'algoritmu di regione di fiducia di gradiente (Newton)
Cundizionamentu poveru di a matrice Hessian è direzzione di ricerca incorrecta pò causà l'algoritmu di gradiente conjugate di Newton per esse inefficace. In tali casi, a preferenza hè data (regione di fiducia) cunjuga i gradienti di Newton.
Esempiu cù a definizione di a matrice 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.]Esempiu cù a funzione di produttu di Hessian è un vettore arbitrariu:
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.]metudi di tipu Krylov
Cum'è u metudu trust-ncg, i metudi di tipu Krylov sò adattati per risolve i prublemi à grande scala perchè usanu solu prudutti di vettori di matrice. A so essenza hè di risolve un prublema in una regione di cunfidenza limitata da un subspazio truncatu di Krylov. Per i prublemi incerti, hè megliu aduprà stu metudu, postu chì usa un numeru più chjucu di iterazioni non lineari per via di u numeru più chjucu di prudutti di matrix-vector per subproblem, cumparatu cù u metudu trust-ncg. Inoltre, a suluzione à u subproblema quadratu hè truvatu più precisamente chì l'usu di u metu trust-ncg.
Esempiu cù a definizione di a matrice 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.]
Esempiu cù a funzione di produttu di Hessian è un vettore arbitrariu:
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.]
Algoritmu per a suluzione apprussimata in a regione di cunfidenza
Tutti i metudi (Newton-CG, trust-ncg è trust-krylov) sò bè adattati per risolve prublemi à grande scala (cù millaie di variàbili). Questu hè duvuta à u fattu chì l'algoritmu di gradiente cunjugatu sottumessu implica una determinazione apprussimata di a matrice Hessian inversa. A suluzione si trova in modu iterativu, senza espansione esplicita di u Hessian. Siccomu solu bisognu di definisce una funzione per u pruduttu di un Hessian è un vettore arbitrariu, questu algoritmu hè soprattuttu bonu per travaglià cù matrici sparse (banda diagonale). Questu furnisce bassi costi di memoria è risparmiu di tempu significativu.
Per i prublemi di medie dimensioni, u costu di almacenà è factoring l'Hessian ùn hè micca criticu. Questu significa chì hè pussibule di ottene una suluzione in menu iterazioni, risolvendu i subproblemi di a regione di fiducia quasi esattamente. Per fà questu, alcune equazioni non lineari sò risolte in modu iterativu per ogni subproblema quadraticu. Una tale suluzione generalmente richiede 3 o 4 decomposizioni Cholesky di a matrice Hessian. In u risultatu, u metudu cunverge in menu iterazioni è esige menu calculi di funzione obiettivu cà altri metudi di regione di fiducia implementati. Stu algoritmu implica solu a determinazione di a matrice Hessian cumpleta è ùn sustene micca a capacità di utilizà a funzione di u produttu di Hessian è un vettore arbitrariu.
Esempiu cù minimizazione di a funzione 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.])Probabilmente ci fermemu quì. In u prossimu articulu, pruvaraghju à dì à e cose più interessanti nantu à a minimizazione cundizionale, l'applicazione di a minimizazione in a risoluzione di prublemi di approssimazione, minimizendu una funzione di una variabile, minimizers arbitrarie, è truvà e radiche di un sistema di equazioni utilizendu scipy.optimize. pacchettu.
Source:
Source: www.habr.com