SciPy, optimizacija

SciPy, optimizacija

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:

  1. Uslovne i bezuslovne minimizacije skalarnih funkcija više varijabli (minim) pomoću raznih algoritama (Nelder-Meadovsimpleks, BFGS, Newtonovi sopruženi gradijenti, COBYLA i SLSQP)
  2. Globalne optimizacije (npr: basinhopping, diff_evolution)
  3. Minimizacija ostataka MNLK (least_squares) i algoritmi za prilagođavanje krivulja nelinearnim MNLK (curve_fit)
  4. Minimizacija skalarne funkcije jedne varijable (minim_scalar) i pretraga korijena (root_scalar)
  5. Višedimenzionalni rješavači sistema jednadzbi (root) uz korištenje raznih algoritama (Hibridni Powellov, Levenberg-Marquardt ili velike metode poput Newton-Krylovih).

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:

SciPy, optimizacija

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

SciPy, optimizacija

Znajući unaprijed da je minimum jednak 0 pri SciPy, optimizacija, 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 Nelder-Mead simplex (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 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 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 BFGS 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:

SciPy, optimizacija

SciPy, optimizacija

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

SciPy, optimizacija

SciPy, optimizacija

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 der

Funkcija 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 konjugiranih gradijenata Newton je modificirana Newtonova metoda.
Newtonova metoda se temelji na aproksimaciji funkcije u lokalnom području pomoću polinoma drugog reda:

SciPy, optimizacija

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

SciPy, optimizacija

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:

SciPy, optimizacija

SciPy, optimizacija

gdje SciPy, optimizacija i SciPy, optimizacija, definiraju matricu SciPy, optimizacija.

Ostali nenulti elementi matrice su jednaki:

SciPy, optimizacija

SciPy, optimizacija

SciPy, optimizacija

SciPy, optimizacija

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

SciPy, optimizacija

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

SciPy, optimizacija

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

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

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

Izvor: habr.com

Kupite pouzdan hosting za web stranice s DDoS zaštitom, VPS VDS servere 🔥 Kupite pouzdan hosting za web stranice s DDoS zaštitom, VPS VDS servere | ProHoster