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

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

История

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

Пример 1

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

{displaystyle max _ {x, y} {3x + 2y} mathrm {при условии} x, ygeq 0; cx + dyleq 10, forall (c, d) in P}

куда ${displaystyle P}$ данное подмножество ${displaystyle mathbb {R} ^ {2}}$ .

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

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

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

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

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

Местная устойчивость

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

{displaystyle {hat {ho}} (x, {hat {u}}): = max _ {ho geq 0} {ho: uin S (x), forall uin B (ho, {hat {u}})} }

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

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

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

Глобальная надежность

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

{displaystyle max _ {xin X} {f (x): g (x, u) leq b, forall uin U}}

куда ${displaystyle U}$ обозначает множество всех возможный ценности ${displaystyle u}$ на рассмотрении.

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

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

Пример 2

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

{displaystyle ho (x): = max _ {Ysubseteq U} {size (Y): g (x, u) leq b, forall uin Y}, xin X}

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

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

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

{displaystyle max _ {xin X, Ysubseteq U} {size (Y): g (x, u) leq b, forall uin Y}}

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

Пример 3

Рассмотрим проблему робастной оптимизации

{displaystyle z (U): = max _ {xin X} {f (x): g (x, u) leq b, forall uin U}}

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

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

{displaystyle z ({mathcal {N}}): = max _ {xin X} {f (x): g (x, u) leq b, forall uin {mathcal {N}}}}

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

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

{displaystyle g (x, u) leq b + eta cdot dist (u, {mathcal {N}}), forall uin U}

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

{displaystyle z ({mathcal {N}}, U): = max _ {xin X} {f (x): g (x, u) leq b + eta cdot dist (u, {mathcal {N}}), forall uin U}}

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

{displaystyle dist (u, {mathcal {N}}) geq 0, forall uin U}

и

{displaystyle dist (u, {mathcal {N}}) = 0, forall uin {mathcal {N}}}

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

{displaystyle g (x, u) leq b + eta cdot dist (u, {mathcal {N}})}

за пределами ${displaystyle {mathcal {N}}}$ .

Невероятностные робастные модели оптимизации

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

{displaystyle max _ {xin X} min _ {uin U (x)} f (x, u)}

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

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

{displaystyle max _ {xin X, vin mathbb {R}} {v: vleq f (x, u), forall uin U (x)}}

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

{displaystyle max _ {xin X} min _ {uin U (x)} {f (x, u): g (x, u) leq b, forall uin U (x)}}

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

{displaystyle max _ {xin X, vin mathbb {R}} {v: vleq f (x, u), g (x, u) leq b, forall uin U (x)}}

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

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

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

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

Смотрите также

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

Х. Дж. Гринберг. Глоссарий математического программирования. Всемирная паутина, http://glossary.computing.society.informs.org/, 1996-2006. Под редакцией INFORMS Computing Society.
Бен-Тал, А .; Немировский, А. (1998). «Робастная выпуклая оптимизация». Математика исследования операций. 23 (4): 769–805. CiteSeerX 10.1.1.135.798. Дои:10.1287 / moor.23.4.769.
Бен-Тал, А .; Немировский, А. (1999). «Надежные решения неопределенных линейных программ». Письма об исследованиях операций. 25: 1–13. CiteSeerX 10.1.1.424.861. Дои:10.1016 / s0167-6377 (99) 00016-4.
Бен-Тал, А .; Аркадий Немировский, А. (2002). «Надежная оптимизация - методология и приложения». Математическое программирование, серия B. 92 (3): 453–480. CiteSeerX 10.1.1.298.7965. Дои:10.1007 / с101070100286.
Бен-Тал А., Эль-Гауи, Л. и Немировски, А. (2006). Математическое программирование, специальный выпуск по робастной оптимизации, Том 107 (1-2).
Бен-Тал А., Эль-Гауи, Л. и Немировски, А. (2009). Надежная оптимизация. Принстонская серия по прикладной математике, Издательство Принстонского университета.
Берцимас, Д .; Сим, М. (2003). «Робастная дискретная оптимизация и сетевые потоки». Математическое программирование. 98 (1–3): 49–71. CiteSeerX 10.1.1.392.4470. Дои:10.1007 / s10107-003-0396-4.
Берцимас, Д .; Сим, М. (2006). "Подходящие аппроксимации к задачам робастной конической оптимизации Димитрис Берцимас". Математическое программирование. 107 (1): 5–36. CiteSeerX 10.1.1.207.8378. Дои:10.1007 / s10107-005-0677-1.
Chen, W .; Сим, М. (2009). «Оптимизация на основе цели». Исследование операций. 57 (2): 342–357. Дои:10.1287 / opre.1080.0570.
Чен, X .; Sim, M .; Sun, P .; Чжан, Дж. (2008). «Приближение на основе линейного решения к стохастическому программированию». Исследование операций. 56 (2): 344–357. Дои:10.1287 / opre.1070.0457.
Чен, X .; Sim, M .; Солнце, П. (2007). «Робастная перспектива оптимизации стохастического программирования». Исследование операций. 55 (6): 1058–1071. Дои:10.1287 / opre.1070.0441.
Дембо, Р. (1991). «Оптимизация сценария». Анналы исследований операций. 30 (1): 63–80. Дои:10.1007 / bf02204809.
Додсон, Б., Хэммет, П., и Клеркс, Р. (2014) Вероятностный дизайн для оптимизации и надежности для инженеров John Wiley & Sons, Inc. ISBN 978-1-118-79619-1
Gupta, S.K .; Розенхед Дж. (1968). «Устойчивость в последовательных инвестиционных решениях». Наука управления. 15 (2): 18–29. Дои:10.1287 / mnsc.15.2.B18.
Кувелис П., Ю. Г. (1997). Робастная дискретная оптимизация и ее приложения, Kluwer.
Мутапчич, Альмир; Бойд, Стивен (2009). «Методы вырезания множества для надежной выпуклой оптимизации с пессимизирующими оракулами». Методы оптимизации и программное обеспечение. 24 (3): 381–406. CiteSeerX 10.1.1.416.4912. Дои:10.1080/10556780802712889.
Mulvey, J.M .; Vanderbei, R.J .; Зениос, С.А. (1995). «Робастная оптимизация крупномасштабных систем». Исследование операций. 43 (2): 264–281. Дои:10.1287 / opre.43.2.264.
Розенблат, M.J. (1987). «Надежный подход к проектированию объектов». Международный журнал производственных исследований. 25 (4): 479–486. Дои:10.1080/00207548708919855.
Розенхед, М.Дж .; Элтон, М; Гупта, С. (1972). «Устойчивость и оптимальность как критерии стратегических решений». Ежеквартальное оперативное исследование. 23 (4): 413–430. Дои:10.2307/3007957. JSTOR 3007957.
Рустем Б. и Хау М. (2002). Алгоритмы для наихудшего сценария и приложения к управлению рисками, Издательство Принстонского университета.
Сниедович, М (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. Дои:10.1109 / ИранскийCEE.2015.7146458. ISBN 978-1-4799-1972-7.

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

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

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

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

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

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

[6] Мадам Асадуджаман и Кайс Заман, «Надежная оптимизация портфеля в условиях неопределенности данных» 15-я Национальная статистическая конференция, декабрь 2014 г., Дакка, Бангладеш.

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

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

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

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

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

[12] Kassam, S.A .; Бедный, Х.В. (1985). «Надежные методы обработки сигналов: обзор». Труды IEEE. 73 (3): 433–481. Дои:10.1109 / proc.1985.13167. HDL:2142/74118.

[13] М. Датский Нисар. «Минимаксная надежность в обработке сигналов для связи», Шейкер Верлаг, ISBN 978-3-8440-0332-1, Август 2011 г.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]