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  pentru o mulțime  de numere reale
Se cere: un element  pentru care  ("minimizare"), sau  ("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,  este o submulțime a spațiului Euclidian , des specificat ca un set de limitări de posibilități, egalități sau inegalități pe care membrii lui  trebuie să le satisfacă. Elementele lui  se numesc soluții admisibile. Funcția  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  este definit ca fiind un punct pentru care câțiva  și toți x astfel încât

 

formula

 
se verifică; aceasta înseamnă că, în anumite bile ale lui  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:

 

Această problemă cere minimul expresiei . În acest caz, valoarea minimului este 1, pentru .

Aici se cere maximul pentru . În acest caz nu există un maxim deoarece funcția  este nemărginită, soluția problemei fiind "infinit" sau "nedefinită".

Aici se cere valoarea (sau valorile) lui  pentru care se minimizează expresia . (Valoarea minimul nu contează.) În acest caz, soluția este .

Aici se cer perechile de forma  care maximizează valoarea expresiei , cu condiția că . (Aici iarăși, valoarea maximă nu contează.) În acest caz soluțiile sunt perechi de forma  și , unde .

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:

 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ă

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ă". De asemenea, 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.

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 

 argmax
 teoria jocurilor
 cercetări operaționale
 logica fuzzy
 optimizare aleatoare
 inegalități variaționale
 algoritmul simplex
 metoda punctelor interioare
 problema comis-voiajorului
 publicații importante în optimizare

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ă 
 Metoda simplex 
 NEOS Guide 
 Online curve and surface fitting
 Xpress-MP - Optimization software free to students 

Optimizare
Cercetări operaționale