SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy (izgovara se kao saj paj) je matematički paket temeljen na numpy, koji uključuje i biblioteke napisane u C i Fortran. Sa SciPy, interaktivna Python sesija postaje jednako snažno okruženje za obradu podataka kao Ŕto su MATLAB, IDL, Octave, R ili SciLab.

U ovom članku ćemo razmotriti osnovne tehnike matematičkog programiranja — rjeÅ”enja zadataka uvjetne optimizacije za skalarne funkcije viÅ”e varijabli koriÅ”tenjem paketa scipy.optimize. Algoritmi bezuvjetne optimizacije već su razmatrani u proÅ”lom članku. Detaljnije i ažurnije informacije o funkcijama scipy uvijek možete dobiti putem komande help(), Shift+Tab ili na službenoj dokumentaciji.

Uvod

Opći интерфейс za rjeÅ”avanje zadataka, kako uvjetne, tako i bezuvjetne optimizacije u paketu scipy.optimize, osigurava funkcija minimize(). Međutim, poznato je da ne postoji univerzalni način za rjeÅ”avanje svih zadataka, stoga izbor odgovarajuće metode uvijek pada na ramena istraživača.
Odgovarajući algoritam optimizacije postavlja se putem argumenta funkcije minimize(..., method="").
Za uvjetnu optimizaciju funkcija viÅ”e varijabli dostupne su implementacije sljedećih metoda:

  • trust-constr — pronalaženje lokalnog minimuma u povjereničkom području. Članak na wiki, članak na habre;
  • SLSQP — sekvencijalno kvadratno programiranje s ograničenjima, Newtonova metoda rjeÅ”avanja Lagrangeovog sustava. Članak na viki.
  • TNC — Truncated Newton Constrained, ograničen broj iteracija, dobar za nelinearne funkcije s velikim brojem neovisnih varijabli. Članak na wiki.
  • L-BFGS-B — metoda četvorke Broyden–Fletcher–Goldfarb–Shanno, implementirana s smanjenom potroÅ”njom memorije zahvaljujući djelomičnom učitavanju vektora iz Hessove matrice. Članak na wiki, članak na habre.
  • COBYLA — KOBYLA Constrained Optimization By Linear Approximation, ograničena optimizacija s linearnom aproksimacijom (bez izračunavanja gradijenta). Članak na wiki.

Ovisno o odabranoj metodi, uvjeti i ograničenja za rjeŔavanje zadatka postavljaju se na različite načine:

  • objektom klase Bounds za metode L-BFGS-B, TNC, SLSQP, trust-constr;
  • popisom (min, max) za iste metode L-BFGS-B, TNC, SLSQP, trust-constr;
  • objektom ili popisom objekata LinearConstraint, NonlinearConstraint za metode COBYLA, SLSQP, trust-constr;
  • riječnikom ili popisom rječnika {'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt} za metode COBYLA, SLSQP.

Plan članka:
1) Razmotriti primjenu algoritma uvjetne optimizacije u povjerenju (method=Ā»trust-constrĀ») s ograničenjima koja su definirana kao objekti Bounds, LinearConstraint, NonlinearConstraint ;
2) Razmotriti sekvencijsko programiranje metodom najmanjih kvadrata (method=Ā»SLSQPĀ») s ograničenjima koja su definirana kao rječnik {'type', 'fun', 'jac', 'args'};
3) Razraditi primjer optimizacije proizvodnje na primjeru web studija.

Uvjetna optimizacija method=»trust-constr»

Implementacija metode trust-constr se temelji na EQSQP za zadatke s ograničenjima tipa jednakosti i na TRIP za zadatke s ograničenjima u obliku nejednakosti. Obje metode su implementirane algoritmima za pretraživanje lokalnog minimuma u povjerenju i dobro su prilagođene za velike zadatke.

Matematička formulacija problema pronalaska minimuma u općem obliku:

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

Za ograničenja stroge jednakosti donja granica se postavlja jednaka gornjoj SciPy, optimizacija s uvjetima.
Za jednostrano ograničenje gornja ili donja granica se postavlja np.inf s odgovarajućim znakom.
Pretpostavimo da je potrebno pronaći minimum poznate Rosenbrockove funkcije od dvije varijable:

SciPy, optimizacija s uvjetima

Pri tome su zadana sljedeća ograničenja na njeno područje definicije:

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

U naÅ”em slučaju postoji jedino rjeÅ”enje u tački SciPy, optimizacija s uvjetima, za koju su važeća samo prvo i četvrto ograničenje.
Proći ćemo kroz ograničenja odozdo prema gore i razmotriti kako ih možemo zapisati u scipy.
Ograničenja SciPy, optimizacija s uvjetima i SciPy, optimizacija s uvjetima odrediti pomoću objekta Bounds.

from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])

Ograničenja SciPy, optimizacija s uvjetima i SciPy, optimizacija s uvjetima zapisati u linearnoj formi:

SciPy, optimizacija s uvjetima

Definiraćemo ta ograničenja u obliku objekta LinearConstraint:

import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])

I konačno, nekonzistentno ograničenje u matričnom obliku:

SciPy, optimizacija s uvjetima

Odredite Jacobijevu matricu za to ograničenje i linearne kombinacije Hessove matrice s proizvoljnim vektorom SciPy, optimizacija s uvjetima:

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

Sada nekonzistentno ograničenje možemo definirati kao objekat NonlinearConstraint:

from scipy.optimize import NonlinearConstraint

def cons_f(x):
     return [x[0]**2 + x[1], x[0]**2 - x[1]]

def cons_J(x):
     return [[2*x[0], 1], [2*x[0], -1]]

def cons_H(x, v):
     return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]])

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H)

Ako je dimenzija velika, matrice se mogu zadavati i u rijetkom obliku:

from scipy.sparse import csc_matrix

def cons_H_sparse(x, v):
     return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]])

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
                                            jac=cons_J, hess=cons_H_sparse)

ili kao objekat LinearOperator:

iz scipy.sparse.linalg uvozi LinearOperator

def cons_H_linear_operator(x, v):
    def matvec(p):
        return np.array([p[0]*2*(v[0]+v[1]), 0])
    return LinearOperator((2, 2), matvec=matvec)

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
                                jac=cons_J, hess=cons_H_linear_operator)

Kada izračunavanje Hesijanove matrice SciPy, optimizacija s uvjetima zahteva velika sredstva, može se koristiti klasa HessianUpdateStrategy. Dostupne su sledeće strategije: BFGS i SR1.

iz scipy.optimize uvozi BFGS

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())

Hesijan se takođe može izračunati pomoću konačnih razlika:

nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')

Jakobijeva matrica za ograničenja takođe se može izračunati pomoću konačnih razlika. Međutim, u ovom slučaju, Hesijan se već ne može izračunati pomoću konačnih razlika. Hesijan mora biti definisan u obliku funkcije ili pomoću klase HessianUpdateStrategy.

nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())

ReŔenje optimizacijskog problema izgleda ovako:

iz scipy.optimize uvozi minimize
iz scipy.optimize uvozi rosen, rosen_der, rosen_hess, rosen_hess_prod

x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess,
                constraints=[linear_constraint, nonlinear_constraint],
                options={'verbose': 1}, bounds=bounds)
print(res.x)

`gtol` uslov prekidanja je zadovoljen.
Broj iteracija: 12, evaluacija funkcije: 8, CG iteracije: 7, optimalnost: 2.99e-09, krŔenje ograničenja: 1.11e-16, vreme izvrŔavanja: 0.033 s.
[0.41494531 0.17010937]

Ako je potrebno, funkciju za izračunavanje hesijana može se definisati pomoću klase LinearOperator

def rosen_hess_linop(x):
    def matvec(p):
        return rosen_hess_prod(x, p)
    return LinearOperator((2, 2), matvec=matvec)

res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop,
                 constraints=[linear_constraint, nonlinear_constraint],
                 options={'verbose': 1}, bounds=bounds)

print(res.x)

ili proizvod hesijana i proizvoljnog vektora kroz parametar hessp:

res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod,
                constraints=[linear_constraint, nonlinear_constraint],
                options={'verbose': 1}, bounds=bounds)
print(res.x)

Alternativno, prva i druga derivacije optimizovane funkcije mogu se približno izračunati. Na primer, hesijan se može aproksimirati pomoću funkcije SR1 (kvazi-Njutnovskog približavanja). Gradient se može približiti konačnim razlikama.

iz scipy.optimize uvozi SR1
res = minimize(rosen, x0, method='trust-constr',  jac="2-point", hess=SR1(),
               constraints=[linear_constraint, nonlinear_constraint],
               options={'verbose': 1}, bounds=bounds)
print(res.x)

Uslovna optimizacija method=»SLSQP»

Metod SLSQP je dizajniran za reŔavanje problema minimizacije funkcije u obliku:

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

SciPy, optimizacija s uvjetima

Gde SciPy, optimizacija s uvjetima i SciPy, optimizacija s uvjetima — množine indeksa izraza koji opisuju ograničenja u obliku jednakosti ili nejednakosti. SciPy, optimizacija s uvjetima — mnoÅ”tvo donjih i gornjih granica za domenu funkcije.

Linijska i nelinijska ograničenja opisuju se u obliku rečnika sa ključevima tip, fun i jac.

ineq_cons = {'type': 'ineq',
             'fun': lambda x: np.array ([1 - x [0] - 2 * x [1],
                                          1 - x [0] ** 2 - x [1],
                                          1 - x [0] ** 2 + x [1]]),
             'jac': lambda x: np.array ([[- 1.0, -2.0],
                                          [-2 * x [0], -1.0],
                                          [-2 * x [0], 1.0]])
            }

eq_cons = {'type': 'eq',
           'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]),
           'jac': lambda x: np.array ([2.0, 1.0])
          }

Pretraživanje minimuma vrÅ”i se na sledeći način:

x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='SLSQP', jac=rosen_der,
               constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True},
               bounds=bounds)

print(res.x)

Optimizacija je uspeŔno zavrŔena.    (Izlazni režim 0)
            Trenutna vrednost funkcije: 0.34271757499419825
            Iteracije: 4
            Evaluacije funkcije: 5
            Evaluacije gradijenta: 4
[0.41494475 0.1701105 ]

Primer optimizacije

S obzirom na prelazak na petu tehnoloŔku fazu, razmatramo optimizaciju proizvodnje na primeru veb studija, koja nam donosi mali, ali stabilan prihod. Pretpostavljamo da smo direktori galerije, na kojoj se proizvode tri vrste proizvoda:

  • x0 — prodajni landing page-evi, od 10.000 RSD.
  • x1 — korporativni sajtovi, od 20.000 RSD.
  • x2 — internet prodavnice, od 30.000 RSD.

NaŔ pravi radni kolektiv uključuje četiri juniora, dva mid-level i jednog seniora. Fond njihovog radnog vremena za mesec:

  • juniori: 4 * 150 = 600 čovek-sati,
  • mid-level: 2 * 150 = 300 čovek-sati,
  • senior: 150 čovek-sati.

Pretpostavimo da na razvoj i deploy jednog sajta tipa (x0, x1, x2) prvi naiÅ”ao junior mora potroÅ”iti (10, 20, 30) sati, mid-level — (7, 15, 20), senior — (5, 10, 15) sati najboljeg vremena svog života.

Kao bilo kojem normalnom direktoru, želimo da maksimiziramo mesečni profit. Prvi korak ka uspehu — zapiÅ”emo ciljnu funkciju value kao sumu prihoda od proizvedenih proizvoda tokom meseca:

def value(x):
    return - 10*x[0] - 20*x[1] - 30*x[2]

To nije greŔka, kada se traži maksimum, ciljna funkcija se minimizira sa obrnutim znakom.

Sledeći korak — zabranjujemo prekovremeni rad naÅ”im zaposlenima i uvodimo ograničenja na fond radnog vremena:

SciPy, optimizacija s uvjetima

Å to ekvivalentno ispoljava:

SciPy, optimizacija s uvjetima

ineq_cons = {'type': 'ineq',
             'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2],
                                         300 - 7  * x [0] - 15 * x [1] - 20 * x[2],
                                         150 - 5  * x [0] - 10 * x [1] - 15 * x[2]])
            }

Formalna ograničenja — proizvodnja treba biti isključivo pozitivna:

bnds = Granice ([0, 0, 0], [np.inf, np.inf, np.inf])

I konačno, najoptimističnija pretpostavka — zbog niske cijene i visoke kvalitete, stalno se formira red zadovoljnih klijenata. Možemo sami birati mjesečne obime proizvodnje proizvoda, u skladu sa rjeÅ”enjem problema uslovne optimizacije sa scipy.optimize:

x0 = np.array([10, 10, 10])
res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds)
print(res.x)

[7.85714286 5.71428571 3.57142857]

Nestriktno zaokružimo na cijele brojeve i izračunajmo mjesečno opterećenje čamaca prema optimalnoj raspodjeli proizvoda x = (8, 6, 3) :

  • juniori: 8 * 10 + 6 * 20 + 3 * 30 = 290 ljudi * sati;
  • mid-level: 8 * 7 + 6 * 15 + 3 * 20 = 206 ljudi * sati;
  • senior: 8 * 5 + 6 * 10 + 3 * 15 = 145 ljudi * sati.

Zaključak: da bi direktor dobio svoj zasluženi maksimum, optimalno je raditi 8 odrediÅ”nih stranica, 6 srednjih web stranica i 3 prodavnice mjesečno. Senior bi pritom trebao raditi bez odmora, opterećenje midlevel-a će iznositi otprilike 2/3, a junior manje od polovine.

Zaključak

U članku su izložene osnovne tehnike rada sa paketom scipy.optimize, koriŔtene za rjeŔavanje problema uslovne minimizacije. Ja lično koristim scipy isključivo u akademske svrhe, pa je dati primjer viŔe Ŕale.

Mnogo teorije i primjera u WinRAR-u možete pronaći, primjerice, u knjizi I.L.Akulicha ā€žMatematičko programiranje kroz primjere i zadatkeā€œ. O ozbiljnijoj primjeni scipy.optimize za izradu 3D struktura na osnovu skupa slika (članak na habre) možete pogledati u scipy-cookbook.

Glavni izvor informacija — docs.scipy.org, oni koji žele doprinijeti prijevodu ovog i drugih odjeljaka scipy dobrodoÅ”li na GitHub.

Hvala mephistopheies za učeŔće u pripremi publikacije.

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