Optimizare

Optimizarea reprezintă activitatea de selectare, din mulțimea soluțiilor posibile unei probleme, a acelei soluții care este cea mai avantajoasă în raport cu un criteriu predefinit. Această definiție implică existența următoarelor componente:

O problemă constând în găsirea unei soluții printr-un procedeu matematic;
Existența mai multor soluții pentru aceeași problemă;
Un criteriu de selectare a soluției optime.

Funcția obiectiv reprezintă expresia matematică a criteriului de optimizare. Aceasta trebuie să reflecte eficiența economică a procesului și în același timp să răspundă obiectivelor funcționării oricărui proces industrial: siguranța în exploatare și respectarea condițiilor de calitate.

Problema de optimizare reprezintă o aplicație matematică de selectare a unei soluții, dintr-o mulțime posibilă, pe baza evaluării funcției obiectiv. Foarte multe probleme din domeniile matematicii, statisticii, ingineriei, economiei și științelor aplicate se pot formula ca probleme de optimizare.
Î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})\leq f(x),\forall x\in A

("minimizare"), sau

f(x_{0})\geq 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.

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 algebrice $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}$ .

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.

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:

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:

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 neliniare 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ă". De asemenea, la calculul 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 proiectare 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, deși sunt folositoare în multe probleme simple, au fost aplicate și în problemele de inginerie aerospațială.

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

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.

Vezi și

Referințe

Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization, Cambridge University Press. ISBN 0-521-83378-7.

Legături externe

Inițiere în programarea matematică Arhivat în 6 noiembrie 2011, la Wayback Machine.
Metoda simplex Arhivat în 6 noiembrie 2011, la Wayback Machine.
NEOS Guide Arhivat în 22 august 2002, la Wayback Machine.
Online curve and surface fitting
Xpress-MP - Optimization software free to students Arhivat în 29 martie 2008, la Wayback Machine.