Диссертации, представленные на защиту и подготовленные в НИУ ВШЭ

Численные методы оптимизации играют важнейшую роль в решении многих прикладных задач различных областей науки, прежде всего, машинного обучения и анализа данных. Наибольшие трудности в использовании известных алгоритмов оптимизации возникают из-за негладкости целевой функции, невозможности точного вычисления ее значения и значения ее субградиентов в заданной точке, а также большой размерности задачи. В данной диссертации предлагаются различные модификации алгоритма зеркального спуска с переключениями для минимизации негладких выпуклых функций. При этом данные модификации применимы для разнообразных вариантов постановки задачи оптимизации с ограничениями типа неравенств, в том числе, для невыпуклых (квазивыпуклых) функций и ограничений, неточно заданных функций, допускающих представление в виде абстрактной модели, а также случаев онлайн и стохастической постановок задачи. Далее в диссертации предлагаются численные методы решения вариационных неравенств с монотонным оператором и обосновывается возможность применения техники рестартов адаптивного проксимального зеркального метода в случае, если оператор является сильно монотонным и удовлетворяет условию Гельдера. Также в работе впервые предлагается ускоренный метод решения седловой задачи с пониженным уровнем гладкости.

На практике оптимизационные задачи обладают некоторой структурой, что позволяет под каждую конкретную задачу разрабатывать более эффективные методы оптимизации, чем классические методы. Используя структуру, можно получить более оптимистичные оценки скорости сходимости для следующих задач: минимизация функции с гёльдеровым градиентом, минимизация суперпозиции функций (min-max задача), композитная оптимизация. В данной диссертации предлагается унификация методов в один, используя концепцию неточной модели функции. На базе предложенной концепции разработаны методы оптимизации, позволяющие эффективно решать большое количество задач со структурой. Для данных методов были получены теоретические гарантии. Предложенные идеи были расширены на прямодвойственность, стохастичность и задачи с относительной гладкостью, что дает возможность применять концепцию неточной модели функции на более широком круге задач из структурной оптимизации.