
SciPy (izgovara se kao saj paj) je paket primijenjenih matematičkih procedura koji se temelji na proširenju Numpy Python. Sa SciPy, interaktivna sesija Pythona postaje puna sredina za obradu podataka i prototipiranje složenih sustava, poput MATLAB-a, IDL-a, Octave-a, R-Lab-a i SciLab-a. Danas ću ukratko pričati o tome kako treba primijeniti neke poznate algoritme optimizacije u paketu scipy.optimize. Detaljne i aktuelne informacije o upotrebi funkcija uvijek se mogu dobiti pomoću komande help() ili pritiskom na Shift+Tab.
Uvod
Da bih sebi i čitateljima olakšao pretraživanje i čitanje izvora, linkovi do opisa metoda biće uglavnom na Wikipediji. Obično su te informacije dovoljne za opšte razumevanje metoda i uslova njihove primene. Za razumijevanje suštine matematičkih metoda, idemo putem ka tako autoritativnijim publikacijama, koje se mogu pronaći na kraju svake članka ili u omiljenoj pretraživačkoj mašini.
Dakle, modul scipy.optimize uključuje implementaciju sljedećih procedura:
- Uslovne i bezuslovne minimizacije skalarnih funkcija više varijabli (minim) pomoću raznih algoritama (Nelder-Meadovsimpleks, BFGS, Newtonovi sopruženi gradijenti, i )
- Globalne optimizacije (npr: , )
- Minimizacija ostataka (least_squares) i algoritmi za prilagođavanje krivulja nelinearnim MNLK (curve_fit)
- Minimizacija skalarne funkcije jedne varijable (minim_scalar) i pretraga korijena (root_scalar)
- Višedimenzionalni rješavači sistema jednadzbi (root) uz korištenje raznih algoritama (Hibridni Powellov, ili velike metode poput ).
U ovom članku razmatraćemo samo prvu tačku iz cijele ove liste.
Bezuvjetna minimizacija skalarne funkcije više varijabli
Funkcija minim iz paketa scipy.optimize pruža opći interfejs za rješavanje problema uslovne i bezuslovne minimizacije skalarnih funkcija više varijabli. Da bismo demonstrirali njen rad, potrebna nam je odgovarajuća funkcija više varijabli koju ćemo različito minimizirati.
Za te svrhe, funkcija Rosenbrock od N varijabli odgovara:

Iako je funkcija Rosenbrock i njene Jacobi i Hess (prva i druga derivacija) već definirana u paketu scipy.optimize, definirajmo je samostalno.
import numpy as np
def rosen(x):
"""Funkcija Rosenbrock"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Za vizualizaciju, prikazat ćemo u 3D vrijednosti funkcije Rosenbrock od dvije varijable.
Kod za prikazivanje
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Postavke 3D grafika
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Postavljanje kuta gledanja
ax.view_init(45, 30)
# Kreiranje podataka za graf
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]))
# Oslikavanje površine
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()

Znajući unaprijed da je minimum jednak 0 pri
, razmotrit ćemo primjere kako odrediti minimalnu vrijednost funkcije Rosenbrock uz pomoć raznih procedura scipy.optimize.
Nelder-Mead simplex metoda
Pretpostavimo da imamo početnu točku x0 u 5-dimenzionalnom prostoru. Pronađimo najbližu točku minimuma funkcije Rosenbrock koristeći algoritam (algoritam je naveden kao vrijednost parametra method):
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)Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 339
Evaluacije funkcije: 571
[1. 1. 1. 1. 1.]Nelder-Mead metoda je najjednostavniji način minimiziranja eksplicitno definirane i relativno glatke funkcije. Ne zahtijeva izračunavanje derivata funkcije, dovoljne su samo njene vrijednosti. Ova metoda je dobar izbor za jednostavne probleme minimizacije. Međutim, budući da ne koristi procjene gradijenata, može biti potrebno više vremena za pronalaženje minimuma.
Powellova metoda
Drugi algoritam optimizacije koji koristi samo vrijednosti funkcija je . Da bismo je koristili, potrebno je postaviti method = ‘powell’ u funkciji minim.
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)Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 19
Evaluacije funkcije: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) algoritam
Za brže konvergenciju prema rješenju, procedura koristi gradijent ciljne funkcije. Gradijent može biti definiran kao funkcija ili izračunat korištenjem prvog reda razlika. U svakom slučaju, metoda BFGS obično zahtijeva manje poziva funkcija od simplex metode.
Izračunajmo derivaciju Rosenbrockove funkcije u analitičkom obliku:


Ova formulacija vrijedi za derivacije svih varijabli, osim prve i posljednje, koje se definiraju kao:


Pogledajmo Python funkciju koja izračunava ovaj gradijent:
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 derFunkcija za izračun gradijenta se specificira kao vrijednost parametra jac funkcije minim, kao što je prikazano u nastavku.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 25
Evaluacija funkcije: 30
Evaluacija gradijenta: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Algoritam konjugiranih gradijenata (Newton)
Algoritam je modificirana Newtonova metoda.
Newtonova metoda se temelji na aproksimaciji funkcije u lokalnom području pomoću polinoma drugog reda:

gdje
je matrica drugih derivacija (Hessianova matrica, hessian).
Ako je hessian pozitivno definitivan, lokalni minimum ove funkcije se može naći postavljanjem nula gradijenta kvadratnog oblika na nulu. Kao rezultat dobijamo izraz:

Obrnut hessian se izračunava metodom konjugiranih gradijenata. Primjer korištenja ove metode za minimizaciju Rosenbrockove funkcije prikazan je u nastavku. Da biste koristili Newton-CG metodu, potrebno je definirati funkciju koja izračunava hessian.
Hessian Rosenbrockove funkcije u analitičkom obliku je jednak:


gdje
i
, definiraju matricu
.
Ostali nenulti elementi matrice su jednaki:




Na primjer, u petodimenzionalnom prostoru N = 5, Hessianova matrica za Rosenbrockovu funkciju ima trakom oblik:

Kod koji izračunava ovaj hessian zajedno s kodom za minimizaciju Rosenbrockove funkcije koristeći metodu konjugiranih gradijenata (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)Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 24
Evaluacije funkcije: 33
Evaluacije gradijenta: 56
Evaluacije Hessian: 24
[1. 1. 1. 0.99999999 0.99999999]Primjer definicije funkcije proizvoda Hessiana i proizvoljnog vektora
U stvarnim zadacima, izračunavanje i pohrana cijele Hessian matrice može zahtijevati značajne resurse vremena i memorije. Međutim, zapravo nije potrebno definirati samu Hessian matricu jer je za postupak minimizacije samo potreban vektor koji je rezultat proizvoda Hessiana s drugim proizvoljnim vektorom. Stoga je s računarske točke gledišta mnogo prikladnije odmah definirati funkciju koja vraća rezultat proizvoda Hessiana s proizvoljnim vektorom.
Razmotrimo funkciju hess, koja prima vektor minimizacije kao prvi argument, a proizvoljni vektor kao drugi argument (uz ostale argumente minimizirane funkcije). U našem slučaju, izračunavanje proizvoda Hessiana Rosenbrockove funkcije s proizvoljnim vektorom nije previše složeno. Ako p — proizvoljni vektor, tada proizvod
ima oblik:

Funkcija koja izračunava proizvod Hessiana i proizvoljnog vektora prosljeđuje se kao vrijednost argumenta hessp funkciji 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})
Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 24
Evaluacije funkcije: 33
Evaluacije gradijenta: 56
Evaluacije Hessian: 66Algoritam povjerenja (trust region) gradijenata (Newton) povezanih s parovima
Loša uvjetovanost Hessian matrice i netočne smjerove pretraživanja mogu rezultirati time da algoritam gradijenata u Newtonovu metodu može biti neučinkovit. U takvim slučajevima daje se prednost (trust-region) gradijenata u Newtonovu metodu.
Primjer definicije Hessian matrice:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 20
Evaluacije funkcije: 21
Evaluacije gradijenta: 20
Evaluacije hesijana: 19
[1. 1. 1. 1. 1.]Primjer s proizvodom hesijana i proizvoljnog vektora:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 20
Evaluacije funkcije: 21
Evaluacije gradijenta: 20
Evaluacije hesijana: 0
[1. 1. 1. 1. 1.]Krilove metode
Slično metodi trust-ncg, Krilove metode su posebno pogodne za rješavanje velikih problema jer koriste samo matricno-vektorske proizvode. Suština im je rješavanje problema u povjereničkom području, ograničenom skraćenim Krilovim podprostorom. Za probleme s nesigurnostima je bolje koristiti ovu metodu, budući da zahtijeva manje nelinearnih iteracija zbog manjeg broja matricno-vektorskih proizvoda po podzadatku, u usporedbi s metodom trust-ncg. Osim toga, rješenje kvadratnog podzadataka se pronalazi preciznije nego metodom trust-ncg.
Primjer definicije Hessian matrice:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 19
Evaluacije funkcije: 20
Evaluacije gradijenta: 20
Evaluacije hesijana: 18
print(res.x)
[1. 1. 1. 1. 1.]
Primjer s proizvodom hesijana i proizvoljnog vektora:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 19
Evaluacije funkcije: 20
Evaluacije gradijenta: 20
Evaluacije hesijana: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algoritam približnog rješenja u povjereničkom području
Sve metode (Newton-CG, trust-ncg i trust-krylov) su vrlo pogodne za rješavanje velikih problema (s tisućama varijabli). To je zbog toga što temeljni algoritam konjugiranih gradijenata podrazumijeva približno pronalaženje obrnute hesijanske matrice. Rješenje se nalazi iterativno, bez eksplicitnog dekomponiranja hesijana. Budući da je potrebno odrediti samo funkciju za proizvod hesijana i proizvoljnog vektora, ovaj algoritam je posebno dobar za rad s rijetkim (trakastim dijagonalnim) matricama. To osigurava niske troškove memorije i značajne uštede vremena.
U zadacima srednje veličine, troškovi pohrane i faktoriranje Hessianove matrice nisu odlučujući. To znači da se rješenje može dobiti s manjim brojem iteracija, rješavajući podzadatke područja povjerenja gotovo točno. Za to se neka nelinearna jednadžbe rješavaju iterativno za svaku kvadratnu podzadatak. Takvo rješenje obično zahtijeva 3 ili 4 Choleskyjeve dekompozicije Hessianove matrice. Kao rezultat, metoda konvergira s manjim brojem iteracija i zahtijeva manje izračuna ciljne funkcije nego druge provedene metode područja povjerenja. Ovaj algoritam podrazumijeva samo određivanje pune Hessianove matrice i ne podržava mogućnost korištenja funkcije proizvoda Hessiana i proizvoljnog vektora.
Primjer minimizacije Rosenbrockove funkcije:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimizacija je uspješno završena.
Trenutna vrijednost funkcije: 0.000000
Iteracije: 13
Evaluacije funkcije: 14
Evaluacije gradienta: 13
Evaluacije Hessiana: 14
array([1., 1., 1., 1., 1.])Na tome, mislim da možemo stati. U sljedećem članku ću pokušati ispričati najzanimljivije o uvjetnoj minimizaciji, aplikacijama minimizacije u rješavanju problema aproksimacije, minimizaciji funkcije jedne varijable, proizvoljnim minimizatorima i pronalaženju korijena sustava jednadžbi pomoću paketa scipy.optimize.
Izvor:
Izvor: habr.com
