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

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

История [ править ]

Истоки надежной оптимизации восходят к созданию современной теории принятия решений в 1950-х годах и использованию анализа наихудшего случая и модели максимина Вальда в качестве инструмента для обработки серьезной неопределенности. Это стало самостоятельной дисциплиной в 1970-х годах с параллельным развитием в нескольких научных и технологических областях. На протяжении многих лет он применялся в статистике , а также в исследованиях операций , ^[1] электротехнике , ^[2]^[3] теории управления , ^[4] финансах , ^[5] управлении портфелем ^[6] логистике ,^[7] Технология машиностроения ,^[8] химического машиностроения ,^[9] препарат ,^[10] и информатика . В инженерных задачах эти формулировки часто называют «оптимизацией надежной конструкции», RDO или «оптимизацией конструкции на основе надежности», RBDO.

Пример 1 [ править ]

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

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

где заданное подмножество . ${\ displaystyle P}$ ${\ Displaystyle \ mathbb {R} ^ {2}}$

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

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

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

Классификация [ править ]

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

Локальная устойчивость [ править ]

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

{\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}}\}

Так как он намного меньше чем , его оптимальное решение может не работать хорошо на большой части и, следовательно, не может быть устойчивым к изменчивости over . ${\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}}

и поэтому оптимальное решение ослабленной задачи удовлетворяет исходному ограничению для всех значений in . Он также удовлетворяет ослабленному ограничению $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)

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

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

\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)\}

Вероятностно устойчивые модели оптимизации [ править ]

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

Надежный аналог [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

^ Берцимас, Димитрис; Сим, Мелвин (2004). «Цена надежности». Исследование операций . 52 (1): 35–53. DOI : 10.1287 / opre.1030.0065 .
^ Шабанзаде М; Шейх-Эль-Эслами, МК; Haghifam, P; MR (октябрь 2015 г.). «Разработка инструмента хеджирования рисков для виртуальных электростанций с помощью надежного подхода к оптимизации». Прикладная энергия . 155 : 766–777. DOI : 10.1016 / j.apenergy.2015.06.059 .
^ Шабанзаде М; Фаттахи, М. (июль 2015 г.). Планирование технического обслуживания поколения с помощью надежной оптимизации . 23-я Иранская конференция по электротехнике (ICEE) . С. 1504–1509. DOI : 10.1109 / IranianCEE.2015.7146458 . ISBN 978-1-4799-1972-7.
^ Харгонекар, ПП; Petersen, IR; Чжоу, К. (1990). «Робастная стабилизация неопределенных линейных систем: квадратичная стабилизируемость и H / sup infinity / теория управления». IEEE Transactions по автоматическому контролю . 35 (3): 356–361. DOI : 10.1109 / 9.50357 .
^ Надежная оптимизация портфеля
^ Md. Asadujjaman и Kais Заман «Robust Оптимизация портфеля при данных неопределенности» пятнадцатый Национальная конференциястатистическим, декабрь 2014, Дакка, Бангладеш.
^ Ю, Чиан-Сон; Ли, Хан-Линь (2000). «Робастная модель оптимизации для стохастических логистических задач». Международный журнал экономики производства . 64 (1–3): 385–397. DOI : 10.1016 / S0925-5273 (99) 00074-2 .
^ Strano, M (2006). «Оптимизация в условиях неопределенности процессов обработки листового металла методом конечных элементов». Труды Института инженеров-механиков, Часть B: Журнал машиностроения . 220 (8): 1305–1315. DOI : 10.1243 / 09544054JEM480 .
^ Бернардо, Фернандо П .; Сараива, Педро М. (1998). «Надежная система оптимизации параметров процесса и проектирования допусков». Журнал Айше . 44 (9): 2007–2017. DOI : 10.1002 / aic.690440908 . hdl : 10316/8195 .
^ Чу, Милли; Зинченко, Юрий; Хендерсон, Шейн Дж. Шарп, Майкл Б. (2005). «Надежная оптимизация планирования лечения лучевой терапией с модуляцией интенсивности в условиях неопределенности». Физика в медицине и биологии . 50 (23): 5463–5477. DOI : 10.1088 / 0031-9155 / 50/23/003 . PMID 16306645 .
^ Verdu, S .; Бедный, HV (1984). «О минимаксной устойчивости: общий подход и приложения». IEEE Transactions по теории информации . 30 (2): 328–340. CiteSeerX 10.1.1.132.837 . DOI : 10,1109 / tit.1984.1056876 .
^ Кассам, SA; Бедный, HV (1985). «Надежные методы обработки сигналов: обзор». Труды IEEE . 73 (3): 433–481. DOI : 10,1109 / proc.1985.13167 . ЛВП : 2142/74118 .
^ М. Датский Нисар. "Minimax Robustness in Signal Processing for Communications" , Shaker Verlag, ISBN 978-3-8440-0332-1 , август 2011 г.
^ Бен-Таль А., Эль Ghaoui, Л. и Немировский, А. (2009). Надежная оптимизация. Принстонская серия по прикладной математике, Princeton University Press, 9-16.
^ Лейффер С., Меникелли М., Мансон Т., Ванарет С. и Уайлд С. М. (2020). Обзор нелинейной робастной оптимизации. ИНФОР: информационные системы и операционные исследования, Тейлор и Фрэнсис.

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

РИМ: надежная оптимизация стала проще
Надежное принятие решений в условиях крайней неопределенности

[1] Берцимас, Димитрис; Сим, Мелвин (2004). «Цена надежности». Исследование операций . 52 (1): 35–53. DOI : 10.1287 / opre.1030.0065 .

[VPP_Robust_2015-2] Шабанзаде М; Шейх-Эль-Эслами, МК; Haghifam, P; MR (октябрь 2015 г.). «Разработка инструмента хеджирования рисков для виртуальных электростанций с помощью надежного подхода к оптимизации». Прикладная энергия . 155 : 766–777. DOI : 10.1016 / j.apenergy.2015.06.059 .

[RO2015-3] Шабанзаде М; Фаттахи, М. (июль 2015 г.). Планирование технического обслуживания поколения с помощью надежной оптимизации . 23-я Иранская конференция по электротехнике (ICEE) . С. 1504–1509. DOI : 10.1109 / IranianCEE.2015.7146458 . ISBN 978-1-4799-1972-7.

[4] Харгонекар, ПП; Petersen, IR; Чжоу, К. (1990). «Робастная стабилизация неопределенных линейных систем: квадратичная стабилизируемость и H / sup infinity / теория управления». IEEE Transactions по автоматическому контролю . 35 (3): 356–361. DOI : 10.1109 / 9.50357 .

[5] Надежная оптимизация портфеля

[6] Md. Asadujjaman и Kais Заман «Robust Оптимизация портфеля при данных неопределенности» пятнадцатый Национальная конференциястатистическим, декабрь 2014, Дакка, Бангладеш.

[7] Ю, Чиан-Сон; Ли, Хан-Линь (2000). «Робастная модель оптимизации для стохастических логистических задач». Международный журнал экономики производства . 64 (1–3): 385–397. DOI : 10.1016 / S0925-5273 (99) 00074-2 .

[8] Strano, M (2006). «Оптимизация в условиях неопределенности процессов обработки листового металла методом конечных элементов». Труды Института инженеров-механиков, Часть B: Журнал машиностроения . 220 (8): 1305–1315. DOI : 10.1243 / 09544054JEM480 .

[9] Бернардо, Фернандо П .; Сараива, Педро М. (1998). «Надежная система оптимизации параметров процесса и проектирования допусков». Журнал Айше . 44 (9): 2007–2017. DOI : 10.1002 / aic.690440908 . hdl : 10316/8195 .

[10] Чу, Милли; Зинченко, Юрий; Хендерсон, Шейн Дж. Шарп, Майкл Б. (2005). «Надежная оптимизация планирования лечения лучевой терапией с модуляцией интенсивности в условиях неопределенности». Физика в медицине и биологии . 50 (23): 5463–5477. DOI : 10.1088 / 0031-9155 / 50/23/003 . PMID 16306645 .

[11] Verdu, S .; Бедный, HV (1984). «О минимаксной устойчивости: общий подход и приложения». IEEE Transactions по теории информации . 30 (2): 328–340. CiteSeerX 10.1.1.132.837 . DOI : 10,1109 / tit.1984.1056876 .

[12] Кассам, SA; Бедный, HV (1985). «Надежные методы обработки сигналов: обзор». Труды IEEE . 73 (3): 433–481. DOI : 10,1109 / proc.1985.13167 . ЛВП : 2142/74118 .

[13] М. Датский Нисар. "Minimax Robustness in Signal Processing for Communications" , Shaker Verlag, ISBN 978-3-8440-0332-1 , август 2011 г.

[14] Бен-Таль А., Эль Ghaoui, Л. и Немировский, А. (2009). Надежная оптимизация. Принстонская серия по прикладной математике, Princeton University Press, 9-16.

[15] Лейффер С., Меникелли М., Мансон Т., Ванарет С. и Уайлд С. М. (2020). Обзор нелинейной робастной оптимизации. ИНФОР: информационные системы и операционные исследования, Тейлор и Фрэнсис.

[1]