Двухуровневая оптимизация

Двухуровневая оптимизация — это особый вид оптимизации, при котором одна проблема встроена (вложена) в другую. Задачу внешней оптимизации обычно называют задачей оптимизации верхнего уровня, а задачу внутренней оптимизации обычно называют задачей оптимизации нижнего уровня. Эти проблемы связаны с двумя типами переменных, называемыми переменными верхнего уровня и переменными нижнего уровня.

Математическая постановка задачи

Общую формулировку задачи двухуровневой оптимизации можно записать следующим образом:

$\min \limits _{x\in X,y\in Y}\;\;F(x,y)$

подлежит:

$G_{i}(x,y)\leq 0$, для $i\in \{1,2,\ldots ,I\}$

$y\in \arg \min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}$

где

$F,f:R^{n_{x}}\times R^{n_{y}}\to R$

$G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R$

$X\subseteq R^{n_{x}}$

$Y\subseteq R^{n_{y}}.$

В приведенной выше формулировке $F$ представляет целевую функцию верхнего уровня и $f$ представляет собой целевую функцию нижнего уровня. Сходным образом $x$ представляет вектор решения верхнего уровня и $y$ представляет вектор решения нижнего уровня. $G_{i}$ и $g_{j}$ представляют функции ограничения неравенства на верхнем и нижнем уровнях соответственно.Если какую-то целевую функцию необходимо максимизировать, это эквивалентно минимизации ее отрицательной.Приведенная выше формулировка также способна представлять ограничения равенства, поскольку их можно легко переписать в терминах ограничений неравенства: например, $h(x)=0$ можно перевести как $\{h(x)\leq 0,\ -h(x)\leq 0\}$.Однако обычно стоит рассматривать ограничения равенства отдельно, чтобы более эффективно решать их специальным образом;в представлении выше они для краткости опущены.

конкурс Штакельберга

Основная статья: Конкурс Штакельберга

Двухуровневая оптимизация была впервые реализована в области теории игр немецким экономистом Генрихом Фрайхером фон Штакельбергом , который в 1934 году опубликовал «Структуру рынка и равновесие» (Marktform und Gleichgewicht), в которой описал эту иерархическую проблему. Стратегическая игра, описанная в его книге, стала известна как игра Штакельберга, состоящая из лидера и последователя. Лидера обычно называют лидером Штакельберга, а последователя обычно называют последователем Штакельберга. В игре Штакельберга игроки соревнуются друг с другом, так что лидер делает первый ход, а затем ведомый оптимально реагирует на действия лидера. Такая иерархическая игра имеет асимметричный характер, в которой лидер и ведомый не могут быть заменены местами. Лидер заранее знает, что ведомый наблюдает за его действиями, прежде чем отреагировать оптимальным образом. Следовательно, если лидер хочет оптимизировать свою цель, ему необходимо предвидеть оптимальную реакцию последователя. В этом случае задача оптимизации лидера содержит вложенную задачу оптимизации, соответствующую задаче оптимизации ведомого. В играх Штакельберга задачу оптимизации верхнего уровня обычно называют проблемой лидера, а задачу оптимизации нижнего уровня обычно называют проблемой ведомого.

Если у ведомого имеется более одного оптимального ответа на определенный выбор лидера, то возможны два варианта: предполагается либо лучшее, либо худшее решение ведомого относительно целевой функции лидера, т.е. предполагается, что ведомый действует либо в кооперативным или агрессивным способом. Полученная двухуровневая задача называется задачей оптимистического двухуровневого программирования или задачей пессимистического двухуровневого программирования соответственно.

Приложения

Проблемы двухуровневой оптимизации обычно встречаются в ряде реальных задач. Сюда входят проблемы в области транспорта , экономики , науки о принятии решений , бизнеса , техники , экономики окружающей среды и т. д. Кратко обсуждаются некоторые практические двухуровневые проблемы, изучаемые в литературе.

Проблема с установкой платных дорог

В сфере транспорта двухуровневая оптимизация обычно возникает при решении проблемы установления платы за проезд. Рассмотрим сеть автомагистралей, которой управляет правительство. Правительство хочет максимизировать свои доходы за счет выбора оптимального размера платы за проезд по автомагистралям. Однако правительство может максимизировать свои доходы, только принимая во внимание проблемы пользователей автомагистралей. Для любой данной структуры налогообложения пользователи автомагистралей решают свою собственную задачу оптимизации, при которой они минимизируют свои транспортные расходы, выбирая между использованием автомагистралей или альтернативным маршрутом. В этих условиях задачу правительства необходимо сформулировать как задачу двухуровневой оптимизации. Верхний уровень состоит из целей и ограничений правительства, а нижний уровень состоит из целей и ограничений пользователей автомагистралей для данной налоговой структуры. Примечательно, что правительство сможет определить доходы, генерируемые той или иной налоговой структурой, только решив задачу нижнего уровня, определяющую степень использования автомагистралей.

Структурная оптимизация

Задачи структурной оптимизации состоят из двух уровней задач оптимизации и обычно называются задачами математического программирования с равновесными ограничениями ( MPEC ). Цель верхнего уровня в таких задачах может включать минимизацию затрат или минимизацию веса с учетом ограничений на перемещения, напряжения и контактные силы. Переменными решения на верхнем уровне обычно являются форма конструкции, выбор материалов, количество материала и т. д. Однако для любого заданного набора переменных верхнего уровня переменные состояния (перемещение, напряжения и контактные силы) можно определить только путем решения задачи минимизации потенциальной энергии, которая появляется как ограничение удовлетворения равновесия или задачи минимизации нижнего уровня для проблемы верхнего уровня.

Оборонные приложения

Двухуровневая оптимизация имеет ряд применений в обороне, например, проектирование структуры стратегических наступательных и оборонительных сил, структуру сил стратегических бомбардировщиков и распределение тактических самолетов для выполнения миссий. Наступательная сущность в этом случае может считаться лидером, а защищающаяся сущность в этом случае может считаться последователем. Если лидер хочет максимизировать ущерб, причиняемый противнику, то этого можно достичь только в том случае, если лидер примет во внимание реакцию ведомого. Рациональный последователь всегда оптимально отреагирует на наступление лидера. Таким образом, проблема лидера предстает как оптимизационная задача верхнего уровня, а оптимальная реакция ведомого на действия лидера определяется решением оптимизационной задачи нижнего уровня.

Приложения для управления персоналом и персоналом

Двухуровневая оптимизация может служить инструментом поддержки принятия решений для фирм в реальных условиях, чтобы улучшить рабочую силу и человеческие ресурсы.решения. Первый уровень отражает цель компании по максимизации прибыльности. Второй уровень отражает цель сотрудников минимизировать разрыв между желаемой зарплатой и предпочтительным планом работы. Двухуровневая модель обеспечивает точное решение, основанноена смешанной целочисленной формулировке и представить вычислительный анализ, основанный на изменении поведения сотрудников вответ на стратегию фирмы, тем самым продемонстрировав, как параметры проблемы влияют на политику принятия решений.

Методологии решения

Задачи двухуровневой оптимизации решить трудно. Одним из методов решения является переформулирование задач двухуровневой оптимизации в задачи оптимизации, для которых доступны надежные алгоритмы решения. Расширенное математическое программирование (EMP) — это расширение языков математического программирования, которое предоставляет несколько ключевых слов для задач двухуровневой оптимизации. Эти аннотации облегчают автоматическое переформулирование математических программ с равновесными ограничениями (MPEC), для которых существует зрелая технология решения. EMP доступен в GAMS .

переформулировка ККТ

Некоторые двухуровневые программы, особенно те, которые имеют выпуклый нижний уровень и удовлетворяют условию регулярности (например, условию Слейтера ), могут быть переформулированы в одноуровневую путем замены задачи нижнего уровня ее условиями Каруша-Куна-Такера . В результате получается одноуровневая математическая программа с ограничениями дополнительности, т. е. MPEC. Если задача нижнего уровня не является выпуклой, то при таком подходе допустимое множество задачи двухуровневой оптимизации расширяется за счет локальных оптимальных решений и стационарных точек нижнего уровня, а это означает, что полученная одноуровневая задача является релаксацией исходной двухуровневой задачи. проблема.

Переформулировка оптимального значения

Обозначая

$\phi (x)=\min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}$

так называемая функция оптимального значения , возможная одноуровневая переформулировка двухуровневой задачи:

$\min \limits _{x\in X,y\in Y}\;\;F(x,y)$

подлежит:

$G_{i}(x,y)\leq 0$, для $i\in \{1,2,\ldots ,I\}$

$g_{j}(x,y)\leq 0,j\in \{1,2,\ldots ,J\}$

$f(x,y)\leq \phi (x).$

Это негладкая задача оптимизации, поскольку функция оптимального значения, как правило, не дифференцируема, даже если все функции ограничений и целевая функция в задаче нижнего уровня гладкие.

Эвристические методы

Для сложных двухуровневых задач классические методы могут оказаться неэффективными из-за таких трудностей, как нелинейность , дискретность , недифференцируемость , невыпуклость и т. д. В таких ситуациях можно использовать эвристические методы. Среди них эволюционные методы, хотя и требуют больших вычислительных ресурсов, часто представляют собой альтернативный инструмент для компенсации некоторых из этих трудностей, с которыми сталкиваются точные методы, хотя и не предлагают никаких гарантий оптимальности решений, которые они дают.

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

Задачу двухуровневой оптимизации можно обобщить до многокритериальной задачи двухуровневой оптимизации с множеством целей на одном или обоих уровнях. Общую задачу многокритериальной двухуровневой оптимизации можно сформулировать следующим образом:

$\min \limits _{x\in X,y\in Y}\;\;F(x,y)=(F_{1}(x,y),F_{2}(x,y),\ldots ,F_{p}(x,y))$ В играх Штакельберга: проблема лидера

подлежит:

$G_{i}(x,y)\leq 0$, для $i\in \{1,2,\ldots ,I\}$;

$y\in \arg \min \limits _{z\in Y}\{f(x,z)=(f_{1}(x,z),f_{2}(x,z),\ldots ,f_{q}(x,z)):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}$ В играх Штакельберга: проблема последователя

где

$F:R^{n_{x}}\times R^{n_{y}}\to R^{p}$

$f:R^{n_{x}}\times R^{n_{y}}\to R^{q}$

$G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R$

$X\subseteq R^{n_{x}}$

$Y\subseteq R^{n_{y}}.$

В приведенной выше формулировке $F$ представляет целевой вектор верхнего уровня с $p$ цели и $f$ представляет целевой вектор нижнего уровня с $q$ цели. Сходным образом, $x$ представляет вектор решения верхнего уровня и $y$ представляет вектор решения нижнего уровня. $G_{i}$ и $g_{j}$ представляют функции ограничения неравенства на верхнем и нижнем уровнях соответственно. Ограничения равенства также могут присутствовать в двухуровневой программе, но для краткости они опущены.

Внешние ссылки

• Глоссарий по математическому программированию