Teorie TO Flashcards
Problema optimizare stationara
O problema de optimizare stationara impune determinarea minimului dupa x a unei functii (fx), une f este functie scalara iar x e R un vector.
Minimizarea functiei trebuie facuta in conditiile in care x satisface h(x) = 0, g(x) < 0
Interpretarea geometrica a pasului optim
Pasul optim este lungimea pasului pentru care functia capata valoarea minima pe directia de deplasarea aleasa
Clasificarea generala a metodelor de optimizare stationara
Metode:
- directe
- indirecte
Dupa principiul metodelor avem:
- de explorare
- de eliminarea
- analitice
- de cautare
Teorema de baza la metode analitice pt problemele de optimizare stationara cu restrictii inegalitate
Kuhn Tucker
conditii necesare de extrem:
-se impune ca f ,gi sa aiba derivata de ord 1 continue intr-o vecinatate a lui x care e presupus pct de minim pe domeniul definit de restrictie
- restrictiile satisfac in x conditiile de regularitate
Dgi(x) sa fie liniar independenti
* toti vectorii care patrund in S indeplinesc : <D gi(x*), z <= 0
* X=convexa, g(x) = convexa pe X a.i g(x) < 0
Esenta metodelor bazate pe directii conjugate
X* = x0 + xS = x0 + suma de la 0 la n-1 OiPi
din x0 se poate ajunge in x* daca se adauga un vector potrivit xS
pi = vectorul bazei
0i = lungimea directiilor de deplasare coresc fiecarei baze
Este posibil sa ajungem prin deplasari succesive pe directiile axelor pana la minim daca avem o regula potrivita pt lungimile pasilor pe aceste directii ( se foloseste deplasarea cu pasi optimi. Aceasta metoda are vit de convergenta relativ mare si este mai avantajoasa decat metoda gradientului
Ce reprezinta pasul optim
Pasul optim este lungimea pasului de deplasare pentru care functia ia valoarea minima pe directia de deplasare aleasa
Clasificare metodelor de cautare
Metode:
orind 1 (se utilizeaza functia obiectiv
ordin 2 (se utilizeaza derivata 1 a lui f(x)
ordin 3 (se utilizeaza derivate de ordin 2 a lui f(x)
D.p.d.v al pasului: -metode cu pas constant -cu pas variabil -cu pas optim
Precizati in cati pasi este atins minimul unei functii patratice in cazul metodelor: gradient optimal, gradient conjugat, directii conjugate, Newton-Raphson, DFP
gradient optimal: numar infinit de pasi ----------------------------------------- gradient conjugat: n pasi ----------------------------------------- directii conjugate: numar infinit de pasi ----------------------------------------- Newton-Raphson: un singur pas ----------------------------------------- DFP: n + 1 pasi -----------------------------------------
Ameliorari ale criteriului Newton-Raphson:
->nr de aproximare a functiei
-> aproximare de ordinul 2, se considera ca aceeasi aproximare e valabila intr-o regiune de incredere. Se foloseste pasul newton pana la limita regiunii de increde, in nou pct, se reface aproximarea functiei
-> se foloseste pasul optim in locul pasului unitar, s-a modificat h pt asigurarea convergentei,
-> se aprox matrx H sau inversa acesteia (fara a folosi derivate de ordin 2) -> combinarea cu metoda gradientului
Metode de eliminare
- este dificla pentru n>=3
Sunt folosite pt stabilirea grosiera a domeniului in cazul n=1 sunt cele mai folosite
Se bazeaza pe ipoteza de unimodalitate (adica existenta unui singur ectrem in domeniul ales
Domeniul se impare in 2 printr-un plan de separare si printr-o procedura specifica se det in care semiplan se afla minimul. se elimina cealalta parte si procedura continua pana se ajunge la un domeniu de incertitudine prestabilit prin precizia impusa
Metode de cautare
- cele mai des folosite
Se porneste de la un pct initial x0 ales fie cu ajutorul unei proceduri fie prin intamplare
Se cauta iterativ x1, x2, xk care tind la x*. Aceasta iteratie inceteaza cand este indeplinit un criteriu de stop
Forma generala principiului de optimizare stationara
Se cere aflarea min f(x) respectand restrictiile
Metode de explorare
In domeniul considerat se stabilesc niste puncte de explorare in care se calculeaza valoarea functiei si in urma comparatiei se precizeaza intervalul de incertitudine in care este minimul
Avantaj: localizarea se face in jurul punctului de minim global
Exista 2 categorii de metode de explorare -> explorare exhaustiva: intregul domeniu se partitioneaza dupa fiecare axa la intervale echidistante si stabilesc noduri -> explorare aleatoare: se aleg un nr de puncte stabilite printr-o regula bazata pe numere aleatoare.
Metoda gradientului optimal:
Se foloseste formula iterativa
xk+1 = xk - 0kRk, rk = gradient f(xK)
Directiile de deplasare sunt ortogonale, acest tip de deplasare nu este favorabil, cu cat ne apropiem de minim, pasul devine mai mic, viteza de convergenta mica
Avantaje + Dezavantaje la metoda Newton-Raphson
(A) La functii patratice minimul se obtine intr-un singur pas
(D) la functii generale minimul se obtine intr-un nr inifinti de pasi (dar are convergenta rapida (A) )
(D) trebuie calculate dervivatele de ordin 2
(D) nu are garantata convergenta globala
