Skip to content
Назад к результатам поиска

Робастная оптимизация — математическое программирование в наихудшем случае

Автор метода
Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
Год
1970s theoretical roots; modern tractable form from late 1990s–2004
Тип
Mathematical programming framework

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Робастная оптимизация — это фреймворк математического программирования, формализованный Бен-Талом и Немировским в конце 1990-х годов и сделанный широко решаемым Бертимасом и Симом (2004), который находит решения, гарантированно работающие приемлемо при любом сценарии в пределах предопределенного множества неопределенности — вместо предположения, что значения параметров известны точно.

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

Интуиция метода

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

История

Теоретические корни робастной оптимизации восходят к Сойстеру (1971) и теории принятия решений по критерию мини-макса Вальда (1945). Современный, решаемый фундамент был заложен Аркадием Немировским и Ахароном Бен-Талом в серии статей начиная с 1997 года, кульминацией которых стала их монография 2009 года с Эль Гауи. Димитрис Бертимас и Мелвин Сим (2004) ввели формулировку с бюджетной неопределенностью (полиэдральной), которая сохраняет линейность номинальной задачи и сделала робастное линейное программирование широко доступным. С тех пор робастная оптимизация расширилась, охватив целочисленные программы, двухэтапные формулировки и множества неопределенности, основанные на данных, полученные из исторических наблюдений.

Когда применять

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

Ограничения и замечания

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

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

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

Применение

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

Как это работает

Как это работает

1

Аналитик определяет множество неопределенности — область правдоподобных возмущений вокруг номинальных значений параметров. Распространенные формы включают: ящик (каждый параметр изменяется независимо в пределах интервала), эллипсоид (возмущения ограничены в евклидовой норме), полиэдр и бюджетные ограничения (Бертимас-Сим). Выбор кодирует предположение о том, насколько коррелированной и серьезной может быть неопределенность, и напрямую контролирует консервативность получаемого решения.

2

Задача оптимизации формулируется в форме мини-макс: минимизировать по решениям максимальную стоимость, которую может наложить враждебная неопределенность. Формально, целевая функция становится min_x max_{u in U} f(x, u) при ограничениях, которые должны выполняться для всех u в множестве неопределенности U. Эта внутренняя максимизация моделирует выбор природой наихудшей реализации неопределенных параметров.

3

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

4

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

5

Аналитик изучает цену робастности: разрыв между номинальным оптимальным значением целевой функции (без неопределенности) и робастным оптимальным значением. Тесное множество неопределенности дает небольшой разрыв, но более слабые гарантии; большое множество дает сильную защиту в наихудшем случае при более высокой стоимости производительности в типичных сценариях. Анализ чувствительности к размеру множества неопределенности направляет окончательный выбор уровня консервативности.

Частые ошибки

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

Часто задаваемые вопросы

Чем робастная оптимизация отличается от стохастического программирования?

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

Что такое цена робастности?

Цена робастности — это увеличение целевой функции (для задачи минимизации) по сравнению с номинальным оптимальным решением, полученным без учета неопределенности. Бертимас и Сим (2004) показали, что для их формулировки с бюджетной неопределенностью эта цена растет только как квадратный корень из числа неопределенных параметров, что делает ее скромной на практике. Изучение этого разрыва после решения является существенным: если он очень велик, то множество неопределенности, вероятно, слишком консервативно.

Какую форму множества неопределенности следует выбрать?

Ящичные множества являются самыми простыми и наиболее консервативными — каждый параметр изменяется независимо. Эллипсоидальные множества (Бен-Тал и Немировский) моделируют коррелированные возмущения, ограниченные в евклидовой норме, и приводят к программам второго порядка. Полиэдральные / бюджетные множества (Бертимас и Сим) контролируют количество параметров, которые могут одновременно отклоняться, сохраняя линейность и уменьшая консервативность. Выбор зависит от знаний в предметной области о том, как возмущения сочетаются, и от доступного класса решателей.

Может ли робастная оптимизация обрабатывать целочисленные переменные решения?

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

Похожие методы

Источники

  1. Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.

    ISBN: 9780691143682
    Скопировано.
  2. Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.

    Открыть ссылку DOI
    Скопировано.