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

Многокритериальная оптимизация (также многокритериальное программирование, англ. 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$. Этот метод способен находить решения на невыпуклых участках фронта.

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

См. также

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