Metode de optimizare parametrica

METODE DE OPTIMIZARE PARAMETRICA

NOTIUNI TEORETICE

Problemele de optimizare presupun extremizarea (maximizarea/minimizarea) unui criteriu de performanta, care poate fi functionala sau functie. In cele ce urmeaza se considera numai cazul cand criteriul de performanta este o functie, (optimizare parametrica), numita functie obiectiv sau functie scop, functie criteriu, fara impuneri de legaturi si/sau restrictii.

Extremizarea unei functii-obiectiv f(x₁, x₂, .,x_n) consta in gasirea unui vector , corespunzator unui punct din spatiu n-dimensional, pentru care functia este minima sau maxima (adica optima). Formal, intre maximizarea si minimizarea functiei nu exista deosebire, deoarece minimul lui f(x₁, x₂, .,x_n) are loc pentru maximul lui - f(x₁, x₂, .,x_n).

Natura geometrica a functiei-obiectiv depinde de relatiile dintre variabilele fata de care aceasta este definita.

De exemplu, daca se noteaza cu f valoarea unei functii de o variabila, f(x₁), intre f si x₁exista corespondenta biunivoca ce are o corespondenta geometrica reprezentata printr-o curba in planul x₁ - f (figura 1).

In cazul a doua variabile independente, , reprezentarea geometrica a acestei relatii necesita un sistem de trei axe de coordonate , figura 2, unde este data reprezentarea izometrica a unui punct din spatiul tridimensional. Locul geometric al punctelor din sistemul de coordonate x₁-x₂-f care verifica relatia este o suprafata denumita suprafata de raspuns, (figura 3).

Intersectia suprafetei de raspuns cu planuri avand ecuatiile , si proiectia ortogonala in planul a curbelor de intersectie rezultante, duce la obtinerea asa numitelor curbe de contur, similare curbelor de izoproprietate, (figura 4)

Generalizarea acestor reprezentari in cazul unei functii obiectiv de n variabile independente necesita un sistem de (n+1) axe independente, perpendiculare intr-un sistem cartezian (imposibil de realizat fizic in spatiul tridimensional) si introducerea notiunilor de hiperspatiu, hipersuprafata, hiperplan, hipercontur.

METODE DE CALCUL PENTRU OPTIMIZAREA PARAMETRICA

(fara restrictii)

Principalele categorii de metode pentru optimizarea functiilor obiectiv de variabila vectoriala, sunt:

a)    Metode indirecte - Acestea sunt denumite astfel intrucat nu se bazeaza pe calculul functiei obiectiv pentru determinarea coordonatelor optimului; mai poarta si numele de metode de urcare (coborare).

Metode de gradient ce apeleaza la primele derivate ale functiei scalare continue si derivabile de variabila vectoriala.

Pentru functia , gradientul intr-un punct i, notat se defineste ca vectorul derivatelor partiale de ordinul unu in raport cu , evaluate in

(1)

Directia gradientului indica intotdeauna spre maximul al unei functii concave, punct in care gradientul este nul , dupa cum antigradientul indica minimul unei functii convexe. Metoda gradientului (Chauchy) se bazeaza pe aproximarea liniara de ordinul I, a dezvoltarii in serie Taylor pentru functia obiectiv in jurul punctului de maxim :

(2)

unde este gradientul ce arata directia ratei maxime de crestere a functiei si metoda se numeste metoda celei mai mari pante, iar - arata directia celei mai mari descresteri, metoda numindu-se metoda celei mai abrupte coborari.

Metode Newton sau metode de gradient de ordinul II, intrucat apeleaza la derivatele de ordinul unu si doi, adica foloseste o aproximare patratica, a dezvoltarii in serie Taylor a functiei obiectiv in jurul punctului de extrem . La aceste metode se foloseste faptul ca in apropierea unui maxim valorile proprii ale hessianului sunt negative, iar in cazul unui minim sunt pozitive. Metodele Newton au dezavantajul ca necesita calcularea hessianului la fiecare iteratie ( timp mare de calcul si volum mare de memorie la calculator).

Metode ale directiilor conjugate, care converg mult mai rapid decat metodele de gradient, aproape ca metodele Newton, dar care nu necesita numarul mare de operatii aritmetice cerute de matricea la fiecare iteratie. Notiunea de directii conjugate este analoaga cu directiile ortogonale, acestea din urma fiind un tip particular de directii conjugate.

b)    Metode de cautare directa - La aceste metode, problema de optimizare este atacata "direct", localizarea extremului facandu-se pe baza informatiilor obtinute in urma determinarii valorilor functiei obiectiv pentru diverse combinatii de valori ale variabilelor independente si nu prin intermediul derivatelor functiei.

Metoda explorarii exhaustive (complete), care este cea mai simpla metoda imaginabila pentru aflarea optimului pe cale directa, consta in calcularea valorilor functiei obiectiv intr-un numar oarecare K de puncte, de coordonate , k=1,2,.,k; dupa ce se analizeaza valorile obtinute, se alege apoi ca optim punctul de coordonate pentru care functia obiectiv este minima sau maxima. Metoda prezinta dezavantajul ca desi numarul de evaluari este foarte mare, uneori se poate intampla ca cel mai bun punct gasit sa fie departe de adevaratul optim din spatiul n-dimensional;

Metode de eliminare se folosesc atunci cand functia obiectiv prezinta un singur punct de extrem. Comparandu-se doua sau mai multe valori ale functiei obiectiv se poate elimina o regiune a domeniului de variatie a variabilelor independente x ca nefiind interesanta deoarece nu contine optimul.

Metode de cautare pe baza de hiperpoliedre (simplexuri) care nu apeleaza la explorari locale pe cele n directii posibile, ci utilizeaza un set de (n+1) puncte exploratoare ce pot fi considerate "varfuri" ale unui hiperpoliedru pe suprafata de raspuns.

Metode de cautare aleatoare (Monte Carlo) care se bazeaza pe generarea unui grup de numere aleatoare intr-un domeniu prestabilit, pentru determinarea minimului global al functiei de n variabile. Algoritmii de cautare aleatoare sunt mai putin performante decat ceilalti, in schimb sunt foarte simpli.

Metoda relaxarii sau a cautarii unidimensionale transforma cautarea multidimensionala intr-o succesiune de cautari unidimensionale, fara nici un fel de prospectari in scopul alegerii directiei acestor inaintari, ci doar prin trierea (relaxarea) rand pe rand a tuturor directiilor axelor de coordonate.