Задачи комбинаторной оптимизации с вероятностными ограничениями

В данной работе рассмотрено применение подхода Distributionally Robust Optimization к задачам линейной комбинаторной оптимизации на основе конечного неполного набора данных. Целью данной работы является отыскание процедуры, позволяющей преобразовать конечный набор данных в наименее консервативную оценку минимизируемой функции, удовлетворяющую определенным асимптотическим свойствам. Особенностью данной работы по сравнению с другими, представленными в литературе, является рассмотрение задачи на неполном наборе данных, т. е. на таком, что количества наблюдений над каждой компонентой случайного вектора весов могут отличаться. Данная постановка задачи представляется более приближенной к реальным условиям. Предъявляется алгоритм решения указанной задачи с помощью сведения к задаче distributionally robust optimization. Более конкретно, ЛПР оптимизирует наихудшую оценку минимизируемой функции по всем распределениям, каждая компонента которых лежит в шаре фиксированного радиуса с центром в эмпирическом распределении. Доказывается слабая оптимальность данного метода и свойство экспоненциального спадания вероятности ошибки при увеличении размера датасета. Проводятся численные эксперименты, сравнивающие эффективность представленного метода с аналогичными, описанными в литературе.