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

Надежная оптимизация — это область математической теории оптимизации, которая занимается проблемами оптимизации, в которых определенная мера надежности ищется по отношению к неопределенности , которая может быть представлена ​​как детерминированная изменчивость в значении параметров самой проблемы и/или ее решения. Она связана с вероятностными методами оптимизации, такими как оптимизация с ограничениями по шансам, но часто отличается от них. ^{[1] [2]}

История

Истоки надежной оптимизации восходят к созданию современной теории принятия решений в 1950-х годах и использованию анализа наихудшего случая и максиминной модели Вальда в качестве инструмента для обработки серьезной неопределенности. Она стала самостоятельной дисциплиной в 1970-х годах с параллельными разработками в нескольких научных и технологических областях. На протяжении многих лет она применялась в статистике , а также в исследовании операций , ^[3] электротехнике , ^{[4] [5] [6]} теории управления , ^[7] финансах , ^[8] управлении портфелем , ^[9] логистике , ^[10] машиностроении , ^[11] химической инженерии , ^[12] медицине , ^[13] и информатике . В инженерных задачах эти формулировки часто называют «надежной оптимизацией проектирования», 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 (x,y)}$ ${\displaystyle cx+dy\leq 10}$ ${\displaystyle (c,d)\in P}$ ${\displaystyle (x,y)}$ ${\displaystyle (c,d)\in P}$ ${\displaystyle cx+dy}$ ${\displaystyle (x,y)}$

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

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

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

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

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

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

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

где обозначает номинальное значение параметра, обозначает шар радиуса с центром в точке и обозначает набор значений, которые удовлетворяют заданным условиям устойчивости/производительности, связанным с решением . ${\displaystyle {\hat {u}}}$ ${\displaystyle B(\rho ,{\hat {u}})}$ ${\displaystyle \rho }$ ${\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 _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}}$

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

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

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

Пример 2

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

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

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

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

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

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

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

Пример 3

Рассмотрим задачу надежной оптимизации

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

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

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

${\displaystyle z({\mathcal {N}}):=\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in {\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+\beta \cdot dist(u,{\mathcal {N}})\ ,\ \forall u\in U}$

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вероятностно надежные модели оптимизации

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

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

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

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

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

Ссылки

1. Риаз, Мухаммад; Ахмад, Садик; Хуссейн, Иршад; Наим, Мухаммад; Михет-Попа, Лучиан (2022). «Вероятностные методы оптимизации в интеллектуальной энергосистеме». Energies . 15 (3): 825. doi : 10.3390/en15030825 . hdl : 11250/2988376 .
2. https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture24.pdf ^{[ пустой URL-адрес PDF ]}
3. Бертсимас, Димитрис; Сим, Мелвин (2004). «Цена надежности». Исследование операций . 52 (1): 35–53. doi :10.1287/opre.1030.0065. hdl : 2268/253225 . S2CID  8946639.
4. Хиральдо, Хуан С.; Кастрильон, Джон А.; Лопес, Хуан Камило; Райдер, Маркос Х.; Кастро, Карлос А. (июль 2019 г.). «Управление энергоснабжением микросетей с использованием надежного выпуклого программирования». IEEE Transactions on Smart Grid . 10 (4): 4520–4530. doi :10.1109/TSG.2018.2863049. ISSN  1949-3053. S2CID  115674048.
5. Шабанзаде М.; Шейх-Эль-Эслами, МК; Хагифам, П.; МР (октябрь 2015 г.). «Разработка инструмента хеджирования рисков для виртуальных электростанций с помощью надежного подхода к оптимизации». Applied Energy . 155 : 766–777. Bibcode : 2015ApEn..155..766S. doi : 10.1016/j.apenergy.2015.06.059.
6. Шабанзаде М.; Фаттахи, М. (июль 2015 г.). «Планирование технического обслуживания генераторов с помощью надежной оптимизации». 2015 г. 23-я Иранская конференция по электротехнике . С. 1504–1509. doi :10.1109/IranianCEE.2015.7146458. ISBN 978-1-4799-1972-7. S2CID  8774918.
7. Khargonekar, PP; Petersen, IR; Zhou, K. (1990). «Надежная стабилизация неопределенных линейных систем: квадратичная стабилизируемость и H/sup бесконечность / теория управления». IEEE Transactions on Automatic Control . 35 (3): 356–361. doi :10.1109/9.50357.
8. Надежная оптимизация портфеля
9. Мд. Асадуджаман и Кайс Заман, «Надежная оптимизация портфеля в условиях неопределенности данных», 15-я Национальная статистическая конференция, декабрь 2014 г., Дакка, Бангладеш.
10. Ю, Чиан-Сон; Ли, Хан-Лин (2000). «Надежная модель оптимизации для стохастических логистических задач». Международный журнал экономики производства . 64 (1–3): 385–397. doi :10.1016/S0925-5273(99)00074-2.
11. Strano, M (2006). «Оптимизация в условиях неопределенности процессов формовки листового металла методом конечных элементов». Труды Института инженеров-механиков, часть B: Журнал инженерного производства . 220 (8): 1305–1315. doi :10.1243/09544054JEM480. S2CID  108843522.
12. Бернардо, Фернандо П.; Сарайва, Педро М. (1998). «Надежная структура оптимизации для проектирования параметров процесса и допусков». Журнал AIChE . 44 (9): 2007–2017. Bibcode : 1998AIChE..44.2007B. doi : 10.1002/aic.690440908. hdl : 10316/8195 .
13. Чу, Милли; Зинченко, Юрий; Хендерсон, Шейн Г; Шарп, Майкл Б (2005). «Надежная оптимизация для планирования лечения лучевой терапией с модуляцией интенсивности в условиях неопределенности». Физика в медицине и биологии . 50 (23): 5463–5477. Bibcode : 2005PMB....50.5463C. doi : 10.1088/0031-9155/50/23/003. PMID  16306645. S2CID  15713904.
14. Verdu, S.; Poor, HV (1984). «О надежности минимакса: общий подход и приложения». Труды IEEE по теории информации . 30 (2): 328–340. CiteSeerX 10.1.1.132.837 . doi :10.1109/tit.1984.1056876. 
15. Кассам, С.А.; Пур, Х.В. (1985). «Надежные методы обработки сигналов: обзор». Труды IEEE . 73 (3): 433–481. doi : 10.1109/proc.1985.13167. hdl : 2142/74118 . S2CID  30443041.
16. М. Даниш Нисар. «Минимаксная надежность в обработке сигналов для связи», Shaker Verlag, ISBN 978-3-8440-0332-1 , август 2011 г. 
17. Бен-Тал А., Эль Гауи, Л. и Немировски, А. (2009). Надежная оптимизация. Принстонская серия по прикладной математике, Princeton University Press, 9-16.
18. Лейффер С. , Меникелли М., Мансон Т., Ванарет К. и Уайлд С. М. (2020). Обзор нелинейной надежной оптимизации. INFOR: Информационные системы и операционные исследования, Тейлор и Фрэнсис.

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

• HJ Greenberg. Глоссарий математического программирования. World Wide Web, 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. S2CID  15905691.
• Бен-Тал, А.; Немировски, А. (1999). «Надежные решения неопределенных линейных программ». Operations Research Letters . 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. S2CID  1429482.
• Бен-Тал А., Эль Гауи Л. и Немировски А. (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. S2CID  1279073.
• Бертсимас, Д.; Сим, М. (2006). «Удобные аппроксимации для надежных задач конической оптимизации Димитриса Бертсимаса». Математическое программирование . 107 (1): 5–36. CiteSeerX  10.1.1.207.8378 . doi :10.1007/s10107-005-0677-1. S2CID  900938.
• Чен, В.; Сим, М. (2009). «Оптимизация, ориентированная на цели». Исследование операций . 57 (2): 342–357. doi :10.1287/opre.1080.0570.
• Chen, X.; Sim, M.; Sun, P.; Zhang, J. (2008). «Подход к стохастическому программированию на основе линейных решений». Operations Research . 56 (2): 344–357. doi :10.1287/opre.1070.0457.
• Чен, X.; Сим, М.; Сан, П. (2007). «Надежная оптимизационная перспектива стохастического программирования». Исследование операций . 55 (6): 1058–1071. doi :10.1287/opre.1070.0441.
• Дембо, Р. (1991). «Оптимизация сценария». Annals of Operations Research . 30 (1): 63–80. doi :10.1007/bf02204809. S2CID  44126126.
• Додсон, Б., Хэмметт, П. и Клеркс, Р. (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.
• Mutapcic, Almir; Boyd, Stephen (2009). «Методы разрезания для надежной выпуклой оптимизации с пессимизирующими оракулами». Методы оптимизации и программное обеспечение . 24 (3): 381–406. CiteSeerX  10.1.1.416.4912 . doi :10.1080/10556780802712889. S2CID  16443437.
• Mulvey, JM; Vanderbei, RJ; Zenios, SA (1995). «Надежная оптимизация крупномасштабных систем». Исследование операций . 43 (2): 264–281. doi :10.1287/opre.43.2.264.
• Nejadseyfi, O., Geijselaers HJM, van den Boogaard AH (2018). "Надежная оптимизация на основе аналитической оценки распространения неопределенности". Engineering Optimization 51 (9): 1581-1603. doi:10.1080/0305215X.2018.1536752.
• Розенблат, М. Дж. (1987). «Надежный подход к проектированию объектов». Международный журнал исследований производства . 25 (4): 479–486. doi :10.1080/00207548708919855.
• Розенхед, М.Дж.; Элтон, М.; Гупта, СК (1972). «Надежность и оптимальность как критерии стратегических решений». Operational Research Quarterly . 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). «Максиминовая модель Вальда: скрытое сокровище!». Журнал Risk Finance . 9 (3): 287–291. doi :10.1108/15265940810875603.
• Снедович, М. (2010). «Взгляд с высоты птичьего полета на теорию принятия решений об информационном разрыве». Журнал Risk Finance . 11 (3): 268–283. doi :10.1108/15265941011043648.
• Вальд, А. (1939). «Вклад в теорию статистической оценки и проверки гипотез». Анналы математики . 10 (4): 299–326. doi : 10.1214/aoms/1177732144 .
• Вальд, А. (1945). «Статистические функции принятия решений, минимизирующие максимальный риск». Анналы математики . 46 (2): 265–280. doi :10.2307/1969022. JSTOR  1969022.
• Уолд, А. (1950). Статистические функции принятия решений, John Wiley, Нью-Йорк.
• Шабанзаде, Мортеза; Фаттахи, Мохаммад (2015). «Планирование технического обслуживания генераторов с помощью надежной оптимизации». 2015 23-я Иранская конференция по электротехнике . С. 1504–1509. doi :10.1109/IranianCEE.2015.7146458. ISBN 978-1-4799-1972-7. S2CID  8774918.

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

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