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

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