Optimizare

De la Wikipedia, enciclopedia liberă

În matematică, termenul de optimizare se referă la studiul problemelor care sunt de forma

Se dă: o funcţie $f : A \to R$ pentru o mulţime $A \!$ de numere reale

Se cere: un element $x_0 \in A$ pentru care $f(x_0) \le f(x), \forall x \in A$ ("minimizare"), sau $f(x_0) \ge f(x), \forall x \in A$ ("maximizare").

O asemenea formulare este câteodată numită program matematic (un termen care nu are legătură directă cu programarea calculatoarelor, dar încă se mai foloseşte în programarea liniară). Multe probleme din lumea reală cât şi probleme teoretice, pot fi modele pentru această ramură a matematicii.

Tipic, $A \!$ este o submulţime a spaţiului Euclidian $\mathbb{R}^n$ , des specificat ca un set de limitări de posibilităţi, egalităţi sau inegalităţi pe care membrii lui $A \!$ trebuie să le satisfacă. Elementele lui $A \!$ se numesc soluţii admisibile. Funcţia $f \!$ se numeşte funcţie obiectiv, sau funcţie cost. O soluţie admisibilă care minimizează (sau maximizează, dacă acesta este scopul) funcţia obiectiv se numeşte soluţie optimă.

În general, există mai multe puncte de minim sau maxim local, unde minimul local $x^* \!$ este definit ca fiind un punct pentru care câţiva $\delta > 0 \!$ şi toţi x astfel încât

$\|\mathbf{x}-\mathbf{x}^*\|\leq\delta$

formula

$f(\mathbf{x}^*)\leq f(\mathbf{x})$

se verifică; aceasta înseamnă că, în anumite bile ale lui $x^* \!$ toate valorile funcţiilor sunt mai mari sau egale decât valoarea în acel punct. Maximul local se defineşte similar. În general, minimul local este simplu de găsit — informaţii adiţionale despre problemă (spre exemplu, funcţia este convexă) sunt necesare pentru a fi siguri că soluţia problemei este minimul global.

[modifică] Notaţii

Problemele de optimizare sunt deseori exprimate prin notaţii speciale. Iată câteva exemple:

$\min_{x\in\mathbb R}\; x^2 + 1$

Această problemă cere minimul expresiei $x^2 + 1 , x \in \mathbb{R}$ . În acest caz, valoarea minimului este 1, pentru $x = 0 \!$ .

$\max_{x\in\mathbb R}\; 2x$

Aici se cere maximul pentru $2x , x \in \mathbb{R}$ . În acest caz nu există un maxim deoarece funcţia $2x \!$ este nemărginită, soluţia problemei fiind "infinit" sau "nedefinită".

$\operatorname{argmin}_{x\in[-\infty,-1]}\; x^2 + 1$

Aici se cere valoarea (sau valorile) lui $x \in [-\infty,-1]$ pentru care se minimizează expresia $x^2 + 1 \!$ . (Valoarea minimul nu contează.) În acest caz, soluţia este $x = -1 \!$ .

$\operatorname{argmax}_{x\in[-5,5],\;y\in\mathbb R}\; x\cdot\cos(y)$

Aici se cer perechile de forma $(x,y) \!$ care maximizează valoarea expresiei $x\cdot cos(y) \!$ , cu condiţia că $x \in [-5,5]$ . (Aici iarăşi, valoarea maximă nu contează.) În acest caz soluţiile sunt perechi de forma $(5,2\pi k) \!$ şi $(-5,2(k+1)\pi ) \!$ , unde $k \in \mathbb{Z}$ .

[modifică] Subcategorii majore

Programarea liniară studiază cazurile în care funcţia obiectiv f este liniară şi mulţimea A este specificată folosind doar egalităţi sau inegalităţi liniare.
Programarea quadrică permite funcţiei obiectiv să aibă termeni quadrici, iar mulţimea A trebuie să fie specificată doar prin egalităţi sau inegalităţi liniare.
Programarea neliniară studiază cazurile când funcţia obiectiv sau condiţiile impuse de problemă sunt specificate prin egalităţi sau inegalităţi neliniare
Teoria stocurilor studiază cazurile în care condiţiile impuse de problemă depind de variabile aleatoare.
Programarea dinamică studiază cazurile în care strategia de optimizare se bazează pe împărţirea problemei în probleme mai simple.
Optimizarea combinatorică se ocupă cu problemele ale căror soluţii admisibile sunt discrete sau pot fi reduse la soluţii discrete.
Optimizarea infinit-dimensională studiază cazurile în care o mulţime de soluţii admisibile este o submulţime a unui spaţiu infinit dimensional, precum un spaţiu de funcţii.

[modifică] Tehnici

Pentru funcţiile dublu diferenţiabile, problemele fără limitări de posibilităţi se pot rezolva găsind punctele în care panta funcţiei obiectiv este 0 (acestea sunt punctele staţionare) şi folosind matricea Hessiană pentru a clasifica tipul fiecărui punct. Dacă este pozitiv definită, punctul este un minim local, dacă este negativă, un maxim local, iar dacă este nedefinită, un punct de şa.

Se poate găsi acel punct staţionar pornind de la o bănuială despre el, apoi ajungând la el printr-una din metodele:

descreşterea pantei
metoda lui Newton
conjugatul pantei
căutarea liniară

Dacă funcţia este convexă în regiunea de interes, atunci orice minim local este şi global. Există metode rapide pentru optmizarea funcţiilor dublu diferenţiabile convexe.

Problemele cu limitări de situaţii pot fi transformate în probleme fără limitări cu ajutorul multiplicatorilor lui Lagrange.

Iată câteva metode populare:

algoritmi genetici
strategie de evoluţie
evoluţie diferenţială

[modifică] Utilizări

Problemele de dinamică a corpurilor rigide (în particular cele articulate) necesită de multe ori tehnici matematice de programare, din moment ce un dinamica corpurile rigide poate fi văzută ca o rezolvare a unei ecuaţii diferenţiale simple cu multiple limitări de situaţii; constrângerile sunt constrângeri geometrice non-liniare precum "aceste două puncte trebuie să coincidă", "această suprafaţă nu trebuie să se interpenetreze cu alta", sau "acest punct trebuie să se plimbe pe o curbă". Deasemenea, computaţiei forţelor de contact se poate rezolva numai rezolvând o problemă de complementaritate liniară, care poate fi văzută ca o QP (problemă "quadratic programming").

Multe probleme de design pot fi exprimate ca programe de optimizare. Aceste probleme se numesc probleme de optimizare a designului. O dezvoltare recentă a unei categorii a acesteia sunt problemele de optimizare a designului multidisciplinar, care, desi sunt folositoare in multe probleme simple, au fost aplicate si in problemele de inginerie aerospaţială.

Altă categorie care foloseşte foarte mult optimizarea este reprezentată de cercetările operaţionale.

[modifică] Istoric

Istoric vorbind, primul termen introdus a fost programarea liniară, care a fost inventat de George Dantzig în anii 1940. În acest context, termenul de programare nu se referă la programarea calculatoarelor (deşi astăzi calculatoarele sunt folosind în multe cazuri pentru a rezolva probleme matematice). Termenul vine de la folosirea cuvântului program de către armata S.U.A. pentru a face referire la orarul de pregătire şi logistică, exact ceea ce Dantzig studia la acea vreme. Mai târziu, termenu de "programare" a devenit important, primind fonduri guvernamentale, fiind asociat cu ariile de înaltă tehnologie, care erau foarte importante.

[modifică] Vezi şi

argmax
teoria jocurilor
cercetări operaţionale
logica fuzzy
optimizare aleatoare
inegalităţi variaţionale
algoritmul simplex
metoda punctelor interioare
Publicaţii importante în optimizare

[modifică] Referinţe

Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization, Cambridge University Press. ISBN 0521833787.

[modifică] Linkuri externe

Adus de la "http://ro.wikipedia.org../../../o/p/t/Optimizare.html"

Categorii: Optimizare | Cercetări operaţionale

We provide Linux to the World