SciPy, optimizacija

SciPy, optimizacija

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:

  1. Usmerene i neusmerene minimizacije skalara funkcija više promenljivih (minim) uz pomoć različitih algoritama (Nelder-Mead simplex, BFGS, Newtonove konjugovane gradijente, COBYLA i SLSQP)
  2. Globalne optimizacije (na primer: basinhopping, diff_evolution)
  3. Minimizacija ostataka MNL (least_squares) i algoritmi prilagođavanja krivulja nelinearnim MNLK (curve_fit)
  4. Minimizacije skalara funkcija jedne promenljive (minim_scalar) i pronalaženje korena (root_scalar)
  5. Višedimenzionalni rešavači sistema jednačina (root) koristeći različite algoritme (hidridni Powell, Levenberg-Marquardt ili velike metode kao što su Newton-Krylov).

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:

SciPy, optimizacija

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()

SciPy, optimizacija

Znajući unapred da minimum iznosi 0 kada SciPy, optimizacija, 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 Nelder-Mead simpleksa (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 Powellova metoda. 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 BFGS 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:

SciPy, optimizacija

SciPy, optimizacija

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

SciPy, optimizacija

SciPy, optimizacija

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 der

Funkcija 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 konjugovanih gradijenata Newton je modifikovana Newtonova metoda.
Newtonova metoda se zasniva na aproksimaciji funkcije u lokalnoj oblasti polinomom drugog stepena:

SciPy, optimizacija

gde SciPy, optimizacija 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:

SciPy, optimizacija

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:

SciPy, optimizacija

SciPy, optimizacija

gde SciPy, optimizacija i SciPy, optimizacija, definišu matricu SciPy, optimizacija.

Ostali nenulti elementi matrice su jednaki:

SciPy, optimizacija

SciPy, optimizacija

SciPy, optimizacija

SciPy, optimizacija

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

SciPy, optimizacija

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 SciPy, optimizacija ima oblik:

SciPy, optimizacija

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: 66

Algoritam 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 metoda povjerenja (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.x

Optimizacija 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: https://docs.scipy.org/doc/scipy/reference/

Izvor: habr.com

Kupite pouzdan hosting za sajtove uz zaštitu od DDoS, VPS VDS servere 🔥 Kupite pouzdan hosting za sajtove uz zaštitu od DDoS, VPS VDS servere | ProHoster