
SciPy (izgovara se kao saj paj) je paket aplikativnih matematičkih procedura, baziran na proširenju Numpy Python-a. Sa SciPy, interaktivna Python sesija postaje potpuno funkcionalno okruženje za obradu podataka i prototipiziranje složenih sistema, kao što su MATLAB, IDL, Octave, R-Lab i SciLab. Danas ću kratko govoriti o tome kako primeniti neke poznate algoritme optimizacije iz paketa scipy.optimize. Detaljnije i ažurirane informacije o korišćenju funkcija uvek možete dobiti pomoću komande help() ili pomoću Shift+Tab.
Uvod
Da bih sebe i čitaoce oslobodio od traženja i čitanja prvobitnih izvora, linkovi na opise metoda biće uglavnom usmereni ka Vikipediji. Uglavnom, ovih informacija je dovoljno za razumevanje metoda u opštem smislu i uslova njihove primene. Za razumevanje suštine matematičkih metoda idemo na linkove ka autoritativnijim publikacijama, koje možete pronaći na kraju svake članka ili u omiljenoj pretraživačkoj mašini.
Dakle, modul scipy.optimize uključuje implementaciju sledećih procedura:
- Usmerene i neusmerene minimizacije skalara funkcija više promenljivih (minim) uz pomoć različitih algoritama (Nelder-Mead simplex, BFGS, Newtonove konjugovane gradijente, i )
- Globalne optimizacije (na primer: , )
- Minimizacija ostataka (least_squares) i algoritmi prilagođavanja krivulja nelinearnim MNLK (curve_fit)
- Minimizacije skalara funkcija jedne promenljive (minim_scalar) i pronalaženje korena (root_scalar)
- Višedimenzionalni rešavači sistema jednačina (root) koristeći različite algoritme (hidridni Powell, ili velike metode kao što su ).
U ovom članku ćemo razmotriti samo prvu tačku sa liste.
Neusmerena minimizacija skalarne funkcije više promenljivih
Funkcija minim iz paketa scipy.optimize pruža opšti interfejs za rešavanje problema usmerene i neusmerene minimizacije skalarnih funkcija više promenljivih. Da bismo ilustrovali njeno delovanje, biće nam potrebna odgovarajuća funkcija više promenljivih koju ćemo različito minimizovati.
Za te svrhe, funkcija Rosenbrock od N promenljivih, koja ima oblik:

Iako je funkcija Rosenbrock i njenih Jacobijevih i Hessovih matrica (prva i druga derivacija) već definisana u paketu scipy.optimize, definišemo je sami.
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 ćemo prikazati 3D vrednosti funkcije Rosenbrock u odnosu na dve promenljive.
Kod za prikazivanje
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Podešavanje 3D grafika
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Podešavanje ugla 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]))
# Crtanje površine
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()

Znajući unapred da minimum iznosi 0 kada
, razmotrićemo primere kako odrediti minimalnu vrednost funkcije Rosenbrock koristeći različite procedure iz scipy.optimize.
Nelder-Mead Simplex metoda
Neka imamo početnu tačku x0 u 5-dimenzionalnom prostoru. Pronađimo najbližu tačku minimuma funkcije Rosenbrock koristeći algoritam (algoritam se navodi kao vrednost 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 uspešno završena.
Trenutna vrednost funkcije: 0.000000
Iteracije: 339
Evaluacije funkcije: 571
[1. 1. 1. 1. 1.]Nelder-Mead simplex metoda je najjednostavniji način za minimizaciju jasno definisane i relativno glatke funkcije. Ne zahteva izračunavanje derivata funkcije, dovoljno je dati samo njene vrednosti. Metoda Nelder-Mead je dobar izbor za jednostavne probleme minimizacije. Međutim, budući da ne koristi procene gradijenta, može biti potrebno više vremena za pronalaženje minimuma.
Powellova metoda
Drugi algoritam optimizacije koji koristi samo vrednosti 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 uspešno završena.
Trenutna vrednost funkcije: 0.000000
Iteracije: 19
Evaluacije funkcije: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) algoritam
Za bržu konvergenciju ka rešenju, procedura koristi gradijent ciljne funkcije. Gradijent može biti definisan kao funkcija ili se može izračunati pomoću prvih razlika. U svakom slučaju, obično metoda BFGS zahteva manje poziva funkcija nego simplex metoda.
Pronađimo derivaciju funkcije Rosenbrok u analitičkom obliku:


Ova izraz važi za derivacije svih varijabli, osim prve i poslednje, koje se definišu kao:


Pogledajmo funkciju u Pythonu 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čunavanje gradijenta se navodi kao vrednost parametra jac funkcije minim, kao što je prikazano ispod.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimizacija je uspešno završena.
Trenutna vrednost funkcije: 0.000000
Iteracije: 25
Evaluacije funkcije: 30
Evaluacije gradijenta: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Algoritam konjugovanih gradijenata (Newton)
Algoritam je modifikovana Newtonova metoda.
Newtonova metoda se zasniva na aproksimaciji funkcije u lokalnoj oblasti polinomom drugog stepena:

gde
je matrica drugih derivacija (Hesova matrica, hesi).
Ako je hesi pozitivno definitan, tada se lokalni minimum ove funkcije može naći postavljanjem nultog gradijenta kvadratne forme na nulu. U rezultat će proizaći izraz:

Obrnuti hesi se izračunava pomoću metode konjugovanih gradijenata. Primer korišćenja ove metode za minimizaciju funkcije Rosenbrok je prikazan ispod. Da biste koristili Newton-CG metodu, potrebno je navesti funkciju koja izračunava hesi.
Hesi funkcije Rosenbrok u analitičkom obliku jednak je:


gde
i
, definišu matricu
.
Ostali nenulti elementi matrice su jednaki:




Na primer, u petodimenzionalnom prostoru N = 5, matrica Hese za funkciju Rosenbrok ima traku oblik:

Kod koji izračunava ovu hesi zajedno sa kodom za minimizaciju funkcije Rosenbrok pomoću metode konjugovanih 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 uspješno završena.
Trenutna funkcijska vrijednost: 0.000000
Iteracije: 24
Evaluacije funkcije: 33
Evaluacije gradijenta: 56
Evaluacije Hesseovih matrica: 24
[1. 1. 1. 0.99999999 0.99999999]Primjer s definicijom funkcije proizvoda Hesseove matrice i proizvoljnog vektora
U stvarnim zadacima, izračun i pohrana cijele Hesseove matrice može zahtijevati značajne resurse vremena i memorije. U suštini, nije potrebno definirati samu Hesseovu matricu, jer za postupak minimizacije samo je potreban vektor koji je rezultat proizvodnje Hesseove matrice s drugim proizvoljnim vektorom. Stoga je s računalnog aspekta mnogo bolje odmah definirati funkciju koja vraća rezultat proizvodnje Hesseove matrice s proizvoljnim vektorom.
Razmotrimo funkciju hess, koja kao prvi argument uzima vektor minimizacije, a kao drugi argument — proizvoljni vektor (uz ostale argumente minimizirane funkcije). U našem slučaju, izračunati proizvod Hesseove matrice funkcije Rosenbrock s proizvoljnim vektorom nije previše složeno. Ako p — proizvoljni vektor, tada proizvod
ima oblik:

Funkcija koja izračunava proizvod Hesseove matrice i proizvoljnog vektora proslijeđ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 uspješno završena.
Trenutna funkcijska vrijednost: 0.000000
Iteracije: 24
Evaluacije funkcije: 33
Evaluacije gradijenta: 56
Evaluacije Hesseovih matrica: 66Algoritam povjerenja (trust region) usklađenih gradijenata (Newtonov)
Loša uvjetovanost Hesseove matrice i pogrešni smjerovi traženja mogu dovesti do toga da algoritham usklađenih gradijenata Newtona može biti neučinkovit. U takvim slučajevima, preferira se (trust-region) usklađenih gradijenata Newtona.
Primjer s definicijom Hesseove 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 Hesseove matrice: 19
[1. 1. 1. 1. 1.]Primjer s funkcijom proizvoda Hesseove matrice 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 Hesseove matrice: 0
[1. 1. 1. 1. 1.]Krilovljeve metode
Slično metodi trust-ncg, Krilovljeve metode su vrlo prikladne za rješavanje velikih problema jer koriste samo proizvode matrica i vektora. Suština ovih metoda je rješavanje problema u povjerljivom području ograničenom sjeckanim Krilovljevim podprostorom. Za nedefinirane probleme bolje je koristiti ovu metodu, jer koristi manje nelinearnih iteracija zahvaljujući manjem broju proizvoda matrica i vektora po podzadatku u odnosu na metodu trust-ncg. Osim toga, rješenje kvadratnog podzadatka se pronalazi preciznije nego metodom trust-ncg.
Primjer s definicijom Hesseove 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 Hesseove matrice: 18
print(res.x)
[1. 1. 1. 1. 1.]
Primjer s funkcijom proizvoda Hesseove matrice 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 Hesseove matrice: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algoritam približnog rješenja u povjerljivom području
Sve metode (Newton-CG, trust-ncg i trust-krylov) su vrlo prikladne za rješavanje velikih problema (s tisućama varijabli). To je zbog toga što algoritam konjugiranih gradijenata, koji leži u njihovoj srži, implicira približno određivanje inverzne Hesseove matrice. Rješenje se pronalazi iterativno, bez eksplicitnog razlaganja Hesseove matrice. Budući da treba odrediti samo funkciju za proizvod Hesseove matrice i proizvoljnog vektora, ovaj algoritam je posebno dobar za rad s rijetkim (trakastim dijagonalnim) matricama. Ovo osigurava nizke troškove memorije i značajne uštede vremena.
U zadacima srednje veličine, troškovi skladištenja i faktorizacije Hesian matrice nisu presudni. To znači da se rešenje može dobiti za manje iteracija tako što se podzadaci povjerenosti rešavaju gotovo tačno. Za to se neka nelinearna jednadžba rešava iterativno za svaku kvadratnu podzadacu. Takvo rešenje obično zahteva 3 ili 4 Cholesky razlaganja Hesian matrice. Kao rezultat, metoda konvergira za manje iteracija i zahteva manje izračunavanja ciljne funkcije u poređenju s drugim implementiranim metodama povjerenosti. Oalgoritam podrazumeva samo određivanje pune Hesian matrice i ne podržava mogućnost korišćenja funkcije produkta Hesian i proizvoljnog vektora.
Primer sa minimizacijom Rosenbrokovih funkcija:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimizacija je uspešno završena.
Trenutna vrednost funkcije: 0.000000
Iteracije: 13
Evaluacije funkcije: 14
Evaluacije gradijenta: 13
Evaluacije Hesian: 14
array([1., 1., 1., 1., 1.])Na ovome ćemo se, verovatno, zaustaviti. U sledećem članku ću pokušati da podelim zanimljivosti o uslovnoj minimizaciji, primeni minimizacije u rešavanju problema aproksimacije, minimizaciji funkcije jedne varijable, proizvoljnim minimizatorima i traženju korena sistema jednadžbi pomoću paketa scipy.optimize.
Izvor:
Izvor: habr.com
