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

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

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

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

${displaystyle min limits _{xin X,yin Y};;F(x,y)}$

при условии:${displaystyle G_{i}(x,y)leq 0}$, за ${displaystyle iin {1,2,ldots ,I}}$;

${displaystyle yin arg min limits _{zin Y}{f(x,z):g_{j}(x,z)leq 0,jin {1,2,ldots ,J}}}$

куда

${displaystyle F,f:R^{n_{x}} imes R^{n_{y}} o R}$

${displaystyle G_{i},g_{j}:R^{n_{x}} imes R^{n_{y}} o R}$

${displaystyle Xsubseteq R^{n_{x}}}$

${displaystyle Ysubseteq R^{n_{y}}.}$

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

Соревнование Штакельберга

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

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

Приложения

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

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

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

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

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

Защитные приложения

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

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

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

Эволюционная двухуровневая оптимизация

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

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

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

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

при условии:${displaystyle G_{i}(x,y)leq 0}$, за ${displaystyle iin {1,2,ldots ,I}}$;

${displaystyle yin arg min limits _{zin Y}{f(x,z)=(f_{1}(x,z),f_{2}(x,z),ldots ,f_{q}(x,z)):g_{j}(x,z)leq 0,jin {1,2,ldots ,J}}}$ В играх Штакельберга: проблема со спутником

куда

${displaystyle F:R^{n_{x}} imes R^{n_{y}} o R^{p}}$

${displaystyle f:R^{n_{x}} imes R^{n_{y}} o R^{q}}$

${displaystyle G_{i},g_{j}:R^{n_{x}} imes R^{n_{y}} o R}$

${displaystyle Xsubseteq R^{n_{x}}}$

${displaystyle Ysubseteq R^{n_{y}}.}$

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

Рекомендации

1. «Объем: эволюционная двухуровневая оптимизация». www.bilevel.org. Получено 6 октября 2013.

внешняя ссылка

• Метаэвристика для двухуровневой оптимизации
• Эволюционная двухуровневая оптимизация
• Глоссарий математического программирования