Многокритериална оптимизация

Многокритериална оптимизация (също многокритериално програмиране, англ. multi-objective optimization, multi-criteria optimization) — това е раздел на математическата оптимизация, изучаващ задачи за едновременна оптимизация по две или повече целеви функции (критерии), които, като правило, си противоречат помежду си. Формално задачата се записва като минимизация на векторна целева функция върху множеството от допустими решения.

Определение и терминология

Задачата за многокритериална оптимизация в общ вид се записва по следния начин: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ където $S\subseteq {\mathbb{ℝ}}^n$ — непразно множество от допустими решения, а $f_i:S\to \mathbb{ℝ}$ — целеви функции ($k\ge 2$). Векторът $f(x)=(f_1(x),\dots ,f_k(x))$ се нарича целеви вектор.

За разлика от скаларната оптимизация, в многокритериалната постановка обикновено не съществува единствено решение, което едновременно подобрява стойностите на всички критерии. Затова класическото понятие за оптимум се обобщава чрез концепцията за оптималност по Парето.

• Решение на Парето (Парето-оптимално или ефективно решение): допустимо решение $x^{*}\in S$, за което не съществува друго решение $x\in S$, такова че $f_i(x)\le f_i(x^{*})$ за всички $i=1,\dots ,k$, и при това $f_j(x)<f_j(x^{*})$ поне за един индекс $j$. С други думи, решението е Парето-оптимално, ако стойността на нито един критерий не може да бъде подобрена, без да се влоши поне един друг критерий.
• Фронт на Парето (или множество на Парето): множеството от всички целеви вектори, съответстващи на Парето-оптимални решения.
• Слабо Парето-оптимално решение: решение $x^{*}\in S$, за което не съществува друго решение $x\in S$, такова че $f_i(x)<f_i(x^{*})$ за всички $i$.

Ключови свойства и теореми

• Теорема за претеглената сума: В изпъкнали задачи (където всички функции $f_i(x)$ и множеството $S$ са изпъкнали) всяко Парето-оптимално решение $x^{*}$ е решение на скаларна задача за минимизация на претеглена сума от критерии $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ за някакъв набор от неотрицателни тегла $w_i\ge 0$. Въпреки това, в неизпъкнали задачи този метод може да не намери някои части на фронта на Парето.

• Условия за оптималност на Каруш-Кун-Тъкър (ККТ): Необходимите условия за оптималност за гладки задачи се обобщават за многокритериалния случай. В точката на Парето-оптимума съществува ненулев набор от неотрицателни множители (тегла), при които градиентите на целевите функции и активните ограничения са линейно зависими.

• Свойства на множеството от решения: Парето-фронтът притежава редица важни качествени характеристики. Границата му е определена от идеалната точка (съставена от поелементните минимуми на всички критерии) и точката надир (от поелементните максимуми върху фронта).

Примери

• Линейна задача: Минимизиране на $f_1(x)=-x_1$ и $f_2(x)=-x_2$ при ограничение $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Тук подобряването на един критерий (например увеличаването на $x_1$) неизбежно води до влошаване на друг (намаляване на $x_2$). Множеството от Парето-оптимални решения е отсечка от правата $x_1+x_2=1$.
• Неизпъкнала задача: Минимизиране на $f_1(x)=x^2$ и $f_2(x)=(x-2{)}^2$ върху отсечката $[0,2]$. Парето-фронтът е неизпъкнал. Методът на претеглените суми с положителни тегла няма да може да намери решения вътре в тази отсечка (например в точката $x=1$), тъй като линейната комбинация от критерии ще достига минимум само в крайните точки $x=0$ или $x=2$.

Свързани понятия и приложения

Многокритериалната оптимизация е тясно свързана с многокритериалното вземане на решения (MCDM), което изучава избора на най-добра алтернатива, отчитайки предпочитанията на лицето, вземащо решения. Основните методи за преобразуване на многокритериалната задача в скаларна (скаларизация) включват:

• Метод на претеглените суми.
• Метод на $\epsilon$-ограниченията: Оптимизира се един критерий, а останалите се превръщат в ограничения от вид $f_i(x)\le {\epsilon }_i$. Този метод е в състояние да намира решения върху неизпъкнали участъци на фронта.

Многокритериалната оптимизация намира широко приложение в инженерното проектиране, икономиката (например оптимизация на портфейл), управлението и екологията.

Вижте също

• Оптималност по Парето
• Векторна оптимизация
• Теория на вземането на решения
• Системи за подпомагане вземането на решения
• Изследване на операциите