Надежная оптимизация

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

История

Истоки робастной оптимизации восходят к созданию современной теории принятия решений в 1950-х годах и использованию анализа наихудшего случая и максиминной модели Уолда в качестве инструмента для обработки серьезной неопределенности. В 1970-е годы она стала отдельной дисциплиной, параллельно развиваясь в нескольких научных и технологических областях. На протяжении многих лет он применялся в статистике , а также в исследованиях операций . электротехника , теория управления , финансы , управление портфелем логистика , машиностроение , химическая инженерия , лекарство , и информатика . В инженерных задачах эти формулировки часто называют «оптимизацией надежного проектирования», RDO или «оптимизацией проектирования, основанной на надежности», RBDO.

Пример 1

Рассмотрим следующую линейного программирования задачу

$\max _{x,y}\ \{3x+2y\}\ \ \mathrm {subject\ to} \ \ x,y\geq 0;cx+dy\leq 10,\forall (c,d)\in P$

где $P$ представляет собой заданное подмножество $\mathbb {R} ^{2}$.

Что делает эту задачу «робастной оптимизации» так это $\forall (c,d)\in P$ пункт в ограничениях. Отсюда следует, что для пары $(x,y)$ чтобы быть допустимым, ограничение $cx+dy\leq 10$ должен довольствоваться худшим $(c,d)\in P$ относящийся к $(x,y)$, а именно пара $(c,d)\in P$ что максимизирует ценность $cx+dy$ за заданное значение $(x,y)$.

Если пространство параметров $P$ конечна (состоит из конечного числа элементов), то эта робастная задача оптимизации сама по себе является задачей линейного программирования : для каждого $(c,d)\in P$ существует линейное ограничение $cx+dy\leq 10$.

Если $P$ не является конечным множеством, то эта проблема представляет собой задачу линейного полубесконечного программирования , а именно задачу линейного программирования с конечным числом (2) переменных решения и бесконечным числом ограничений.

Классификация

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

Локальная устойчивость

Есть случаи, когда требуется устойчивость к небольшим изменениям номинального значения параметра. Очень популярной моделью локальной устойчивости является модель радиуса устойчивости :

${\hat {\rho }}(x,{\hat {u}}):=\max _{\rho \geq 0}\ \{\rho :u\in S(x),\forall u\in B(\rho ,{\hat {u}})\}$

где ${\hat {u}}$ обозначает номинальное значение параметра, $B(\rho ,{\hat {u}})$ обозначает шар радиуса $\rho$ сосредоточено в ${\hat {u}}$ и $S(x)$ обозначает набор значений $u$ которые удовлетворяют заданным условиям стабильности/производительности, связанным с решением $x$.

Другими словами, робастность (радиус устойчивости) решения $x$ - радиус наибольшего шара с центром в ${\hat {u}}$ все элементы которого удовлетворяют требованиям устойчивости, предъявляемым к $x$. Картина такая:

где прямоугольник $U(x)$ представляет собой набор всех значений $u$ связанный с решением $x$.

Глобальная

Рассмотрим простую абстрактную задачу устойчивой оптимизации.

$\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}$

где $U$ обозначает набор всех возможных значений $u$ на рассмотрении.

Это глобальная задача робастной оптимизации в том смысле, что ограничение устойчивости $g(x,u)\leq b,\forall u\in U$ представляет все возможные значения $u$.

Трудность состоит в том, что такое «глобальное» ограничение может быть слишком жестким, поскольку не существует никаких ограничений. $x\in X$ который удовлетворяет этому ограничению. Но даже если такое $x\in X$ существует, ограничение может быть слишком «консервативным» в том смысле, что оно дает решение $x\in X$ это приносит очень небольшой выигрыш $f(x)$ это не отражает эффективность других решений в $X$. Например, может существовать $x'\in X$ это лишь незначительно нарушает ограничение устойчивости, но дает очень большой выигрыш $f(x')$. В таких случаях может потребоваться немного ослабить ограничение устойчивости и/или изменить постановку задачи.

Пример 2

Рассмотрим случай, когда целью является удовлетворение ограничения $g(x,u)\leq b,$. где $x\in X$ обозначает переменную решения и $u$ параметр, набор возможных значений которого в $U$. Если нет $x\in X$ такой, что $g(x,u)\leq b,\forall u\in U$, то напрашивается следующая интуитивная мера устойчивости:

$\rho (x):=\max _{Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in Y\}\ ,\ x\in X$

где $size(Y)$ обозначает подходящую меру «размера» множества $Y$. Например, если $U$ конечное множество, то $size(Y)$ можно определить как мощность множества $Y$.

Другими словами, надежность решения — это размер наибольшего подмножества $U$ для которого ограничение $g(x,u)\leq b$ удовлетворен для каждого $u$ в этом наборе. Оптимальным решением является тогда решение, устойчивость которого является наибольшей.

Это дает следующую робастную задачу оптимизации:

$\max _{x\in X,Y\subseteq U}\ \{size(Y):g(x,u)\leq b,\forall u\in Y\}$

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

Пример 3

Рассмотрим задачу устойчивой оптимизации

$z(U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}$

где $g$ является вещественной функцией на $X\times U$и предположим, что не существует допустимого решения этой проблемы, поскольку ограничение устойчивости $g(x,u)\leq b,\forall u\in U$ слишком требовательна.

Чтобы преодолеть эту трудность, позвольте ${\mathcal {N}}$ быть относительно небольшим подмножеством $U$ представляющие «нормальные» значения $u$ и рассмотрим следующую робастную задачу оптимизации:

$z({\mathcal {N}}):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in {\mathcal {N}}\}$

С ${\mathcal {N}}$ намного меньше, чем $U$, его оптимальное решение может не работать хорошо на большой части $U$ и, следовательно, не может быть устойчивым к изменчивости $u$ над $U$.

Один из способов решить эту трудность — ослабить ограничение $g(x,u)\leq b$ для значений $u$ вне съемочной площадки ${\mathcal {N}}$ контролируемым образом, чтобы допускать более крупные нарушения по мере того, как расстояние $u$ от ${\mathcal {N}}$ увеличивается. Например, рассмотрим ослабленное ограничение устойчивости

$g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \forall u\in U$

где $\beta \geq 0$ является управляющим параметром и $dist(u,{\mathcal {N}})$ обозначает расстояние $u$ от ${\mathcal {N}}$. Таким образом, для $\beta =0$ ослабленное ограничение устойчивости возвращается к исходному ограничению устойчивости.Это дает следующую (расслабленную) робастную задачу оптимизации:

$z({\mathcal {N}},U):=\max _{x\in X}\ \{f(x):g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \forall u\in U\}$

Функция $dist$ определяется таким образом, что

$dist(u,{\mathcal {N}})\geq 0,\forall u\in U$

и

$dist(u,{\mathcal {N}})=0,\forall u\in {\mathcal {N}}$

и, следовательно, оптимальное решение ослабленной задачи удовлетворяет исходному ограничению $g(x,u)\leq b$ для всех значений $u$ в ${\mathcal {N}}$. Он также удовлетворяет ослабленному ограничению

$g(x,u)\leq b+\beta \cdot dist(u,{\mathcal {N}})$

снаружи ${\mathcal {N}}$.

Невероятностные

Доминирующей парадигмой в этой области робастной оптимизации является максиминная модель Уолда , а именно:

$\max _{x\in X}\min _{u\in U(x)}f(x,u)$

где $\max$ представляет лицо, принимающее решения, $\min$ представляет Природу, а именно неопределенность , $X$ представляет собой пространство решений и $U(x)$ обозначает набор возможных значений $u$ связанный с решением $x$. Это классический формат общей модели, который часто называют минимаксной или максиминной задачей оптимизации. Невероятностная ( детерминированная ) модель широко использовалась и используется для надежной оптимизации, особенно в области обработки сигналов.

Эквивалентное математическое программирование (МП) классического формата, описанного выше:

$\max _{x\in X,v\in \mathbb {R} }\ \{v:v\leq f(x,u),\forall u\in U(x)\}$

Ограничения могут быть явно включены в эти модели. Общий ограниченный классический формат:

$\max _{x\in X}\min _{u\in U(x)}\ \{f(x,u):g(x,u)\leq b,\forall u\in U(x)\}$

Эквивалентный ограниченный формат MP определяется как:

$\max _{x\in X,v\in \mathbb {R} }\ \{v:v\leq f(x,u),g(x,u)\leq b,\forall u\in U(x)\}$

устойчивые модели

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

Надежный аналог

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

См. также

• Радиус устойчивости
• Минимакс
• Минимаксная оценка
• Минимаксное сожаление
• Надежная статистика
• Надежное принятие решений
• Стохастическое программирование
• Стохастическая оптимизация
• Теория принятия решений при информационном дефиците
• Методы Тагучи

Дальнейшее чтение

• Х. Дж. Гринберг. Словарь математического программирования. Всемирная паутина, http://glossary.computing.society.informs.org/ , 1996–2006 гг. Под редакцией Вычислительного общества ИНФОРМС.
• Бен-Тал, А.; Немировский, А. (1998). «Надежная выпуклая оптимизация». Математика исследования операций . 23 (4): 769–805. CiteSeerX   10.1.1.135.798 . дои : 10.1287/moor.23.4.769 . S2CID   15905691 .
• Бен-Тал, А.; Немировский, А. (1999). «Надежные решения неопределенных линейных программ». Письма об исследованиях операций . 25 : 1–13. CiteSeerX   10.1.1.424.861 . дои : 10.1016/s0167-6377(99)00016-4 .
• Бен-Тал, А.; Аркадий Немировский, А. (2002). «Надежная оптимизация - методология и приложения». Математическое программирование, серия Б. 92 (3): 453–480. CiteSeerX   10.1.1.298.7965 . дои : 10.1007/s101070100286 . S2CID   1429482 .
• Бен-Тал А., Эль Гауи Л. и Немировский А. (2006). Математическое программирование, специальный выпуск по робастной оптимизации, том 107 (1-2).
• Бен-Тал А., Эль Гауи Л. и Немировский А. (2009). Надежная оптимизация. Принстонская серия по прикладной математике, Princeton University Press.
• Берцимас, Д.; Сим, М. (2003). «Надежная дискретная оптимизация и сетевые потоки». Математическое программирование . 98 (1–3): 49–71. CiteSeerX   10.1.1.392.4470 . дои : 10.1007/s10107-003-0396-4 . S2CID   1279073 .
• Берцимас, Д.; Сим, М. (2006). «Разрешимые аппроксимации к робастным задачам конической оптимизации Димитрис Берцимас». Математическое программирование . 107 (1): 5–36. CiteSeerX   10.1.1.207.8378 . дои : 10.1007/s10107-005-0677-1 . S2CID   900938 .
• Чен, В.; Сим, М. (2009). «Оптимизация, основанная на цели». Исследование операций . 57 (2): 342–357. дои : 10.1287/опре.1080.0570 .
• Чен, X.; Сим, М.; Сан, П.; Чжан, Дж. (2008). «Подход к стохастическому программированию на основе линейного решения». Исследование операций . 56 (2): 344–357. дои : 10.1287/opre.1070.0457 .
• Чен, X.; Сим, М.; Сан, П. (2007). «Надежная перспектива оптимизации стохастического программирования». Исследование операций . 55 (6): 1058–1071. дои : 10.1287/opre.1070.0441 .
• Дембо, Р. (1991). «Оптимизация сценария». Анналы исследования операций . 30 (1): 63–80. дои : 10.1007/bf02204809 . S2CID   44126126 .
• Додсон Б., Хэмметт П. и Клеркс Р. (2014) Вероятностное проектирование для оптимизации и надежности для инженеров John Wiley & Sons, Inc. ISBN   978-1-118-79619-1
• Гупта, Словакия; Розенхед, Дж. (1968). «Надежность в последовательных инвестиционных решениях». Наука управления . 15 (2): 18–29. дои : 10.1287/mnsc.15.2.B18 .
• Кувелис П. и Ю Г. (1997). Робастная дискретная оптимизация и ее приложения, Клювер.
• Мутапчич, Альмир; Бойд, Стивен (2009). «Методы вырезания для надежной выпуклой оптимизации с пессимистическими оракулами». Методы оптимизации и программное обеспечение . 24 (3): 381–406. CiteSeerX   10.1.1.416.4912 . дои : 10.1080/10556780802712889 . S2CID   16443437 .
• Малви, Дж. М.; Вандербей, Р.Дж.; Зениос, SA (1995). «Надежная оптимизация крупномасштабных систем». Исследование операций . 43 (2): 264–281. дои : 10.1287/опре.43.2.264 .
• Неядсейфи О., Гейселерс HJM, ван ден Бугаард А.Х. (2018). «Надежная оптимизация, основанная на аналитической оценке распространения неопределенности». Инженерная оптимизация 51 (9): 1581-1603. дои:10.1080/0305215X.2018.1536752 .
• Розенблат, MJ (1987). «Надежный подход к проектированию объектов». Международный журнал производственных исследований . 25 (4): 479–486. дои : 10.1080/00207548708919855 .
• Розенхед, MJ; Элтон, М; Гупта, СК (1972). «Надежность и оптимальность как критерии стратегических решений». Ежеквартальный журнал операционных исследований . 23 (4): 413–430. дои : 10.2307/3007957 . JSTOR   3007957 .
• Рустем Б. и Хоу М. (2002). Алгоритмы проектирования наихудшего случая и приложения к управлению рисками, Princeton University Press.
• Снедович, М (2007). «Искусство и наука моделирования принятия решений в условиях жесткой неопределенности» . Принятие решений в производстве и сфере услуг . 1 (1–2): 111–136. дои : 10.7494/dmms.2007.1.2.111 .
• Снедович, М (2008). «Максиминовая модель Уолда: замаскированное сокровище!». Журнал рискового финансирования . 9 (3): 287–291. дои : 10.1108/15265940810875603 .
• Снедович, М (2010). «Теория принятия решений при информационном дефиците с высоты птичьего полета». Журнал рискового финансирования . 11 (3): 268–283. дои : 10.1108/15265941011043648 .
• Вальд, А. (1939). «Вклад в теорию статистических оценок и проверки гипотез» . Анналы математики . 10 (4): 299–326. дои : 10.1214/aoms/1177732144 .
• Вальд, А. (1945). «Функции статистического принятия решений, минимизирующие максимальный риск». Анналы математики . 46 (2): 265–280. дои : 10.2307/1969022 . JSTOR   1969022 .
• Уолд, А. (1950). Статистические функции принятия решений, Джон Уайли, Нью-Йорк.
• Шабанзаде, Мортеза; Фаттахи, Мохаммед (2015). «Планирование технического обслуживания генерации посредством надежной оптимизации». 2015 23-я Иранская конференция по электротехнике . стр. 1504–1509. doi : 10.1109/IranianCEE.2015.7146458 . ISBN  978-1-4799-1972-7 . S2CID   8774918 .

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

• РИМ: надежная оптимизация стала проще
• Надежное принятие решений в условиях серьезной неопределенности
• Robustimizer: надежное программное обеспечение для оптимизации