Optimizare multicriterială

Optimizare multicriterială (de asemenea programare multicriterială, engl. multi-objective optimization, multi-criteria optimization) — este o ramură a optimizării matematice care studiază problemele de optimizare simultană după două sau mai multe funcții obiectiv (criterii), care, de regulă, intră în conflict unele cu altele. Formal, problema se notează ca minimizarea unei funcții obiectiv vectoriale pe mulțimea soluțiilor admisibile.

Definiție și terminologie

Problema optimizării multicriteriale în formă generală se notează astfel: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ unde $S\subseteq {\mathbb{ℝ}}^n$ — mulțimea nevidă a soluțiilor admisibile, iar $f_i:S\to \mathbb{ℝ}$ — funcțiile obiectiv ($k\ge 2$). Vectorul $f(x)=(f_1(x),\dots ,f_k(x))$ se numește vector obiectiv.

Spre deosebire de optimizarea scalară, în formularea multicriterială de obicei nu există o soluție unică care să îmbunătățească valorile tuturor criteriilor simultan. De aceea, noțiunea clasică de optim se generalizează folosind conceptul de optimalitate Pareto.

• Soluție Pareto (soluție Pareto-optimală sau eficientă): o soluție admisibilă $x^{*}\in S$, pentru care nu există o altă soluție $x\in S$ astfel încât $f_i(x)\le f_i(x^{*})$ pentru toți $i=1,\dots ,k$, și totodată $f_j(x)<f_j(x^{*})$ cel puțin pentru un indice $j$. Cu alte cuvinte, o soluție este Pareto-optimală dacă nicio valoare a unui criteriu nu poate fi îmbunătățită fără a înrăutăți cel puțin un alt criteriu.
• Frontul Pareto (sau mulțimea Pareto): mulțimea tuturor vectorilor obiectiv corespunzători soluțiilor Pareto-optimale.
• Soluție slab Pareto-optimală: o soluție $x^{*}\in S$, pentru care nu există o altă soluție $x\in S$ astfel încât $f_i(x)<f_i(x^{*})$ pentru toți $i$.

Proprietăți și teoreme esențiale

• Teorema sumei ponderate: În problemele convexe (unde toate funcțiile $f_i(x)$ și mulțimea $S$ sunt convexe), orice soluție Pareto-optimală $x^{*}$ este soluția problemei scalare de minimizare a sumei ponderate a criteriilor $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ pentru un anumit set de ponderi nenegative $w_i\ge 0$. Totuși, în problemele neconvexe, această metodă poate să nu găsească anumite porțiuni ale frontului Pareto.

• Condițiile de optimalitate Karush-Kuhn-Tucker (KKT): Condițiile necesare de optimalitate pentru problemele netede se generalizează la cazul multicriterial. Într-un punct de optim Pareto există un set nenul de multiplicatori (ponderi) nenegativi pentru care gradienții funcțiilor obiectiv și ai restricțiilor active sunt liniar dependenți.

• Proprietățile mulțimii soluțiilor: Frontul Pareto posedă o serie de caracteristici calitative importante. Frontiera sa este delimitată de punctul ideal (alcătuit din minimele element cu element ale tuturor criteriilor) și punctul nadir (din maximele element cu element pe front).

Exemple

• Problemă liniară: Minimizați $f_1(x)=-x_1$ și $f_2(x)=-x_2$ sub restricția $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Aici, îmbunătățirea unui criteriu (de exemplu, creșterea $x_1$) conduce inevitabil la înrăutățirea celuilalt (scăderea $x_2$). Mulțimea soluțiilor Pareto-optimale este segmentul de dreaptă $x_1+x_2=1$.
• Problemă neconvexă: Minimizați $f_1(x)=x^2$ și $f_2(x)=(x-2{)}^2$ pe segmentul $[0,2]$. Frontul Pareto este neconvex. Metoda sumelor ponderate cu ponderi pozitive nu va putea găsi soluții în interiorul acestui segment (de exemplu, în punctul $x=1$), deoarece combinația liniară a criteriilor va atinge minimul doar în punctele extreme $x=0$ sau $x=2$.

Noțiuni conexe și aplicații

Optimizarea multicriterială este strâns legată de luarea deciziilor multicriteriale (MCDM), care studiază alegerea celei mai bune alternative ținând cont de preferințele factorului de decizie. Principalele metode de transformare a problemei multicriteriale într-una scalară (scalarizare) includ:

• Metoda sumelor ponderate.
• Metoda restricțiilor $\epsilon$: Se optimizează un singur criteriu, iar celelalte sunt transformate în restricții de tipul $f_i(x)\le {\epsilon }_i$. Această metodă este capabilă să găsească soluții pe porțiunile neconvexe ale frontului.

Optimizarea multicriterială găsește aplicații largi în proiectarea inginerească, economie (de exemplu, optimizarea portofoliului), management și ecologie.

Vezi și

• Optimalitate Pareto
• Optimizare vectorială
• Teoria deciziei
• Sisteme de suport al deciziei
• Cercetare operațională