Оптимизация в анализе данных: дополнительные главы, весна 2025

О курсе

Курс разработан для студентов, имеющих базовые знания математического анализа и методов оптимизации. Большая часть запланированных тем подробно не рассматривается в основных курсах по оптимизации. Слушатели смогут углубить свои знания, а также расширить границы применения навыков в области использования оптимизационных алгоритмов. В учебные планы на ФПМИ курс включён как альтернативный для студентов 4 курса бакалавриата и 5 курса магистратуры.

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

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

Вторая (основная) часть курса посвящена методам первого порядка для вариационных неравенств и седловых задач. Будут рассмотрены понятие вариационного неравенства, результаты о разрешимости и примеры задач (задачи дополнительности, отыскание седловых точек с разными приложениями в игровых задачах), сводящихся к вариационным неравенствам. Далее, будут описаны методы для вариационных неравенств: проекционный и экстраградиентный методы, проксимальный зеркальный метод и его адаптивный вариант, а также ускоренные методы для седловых задач.

Третья часть курса нацелена на изложение наиболее известных подходов и теоретических результатов о численных методах для задач невыпуклой оптимизации. Намечено детальное рассмотрение теоретических результатов для задач с аналогами выпуклости (квазивыпуклость, слабая выпуклость), а также сильной выпуклости (условие градиентного доминирования, квадратичного роста и их аналоги) и соответствующие примеры прикладных задач (восстановление малоранговых матриц, перепараметризованные системы в глyбоком обyчении). Поговорим о стохастических методах (в т.ч. с редyкцией дисперсии) для задач с ycловием градиентного доминированиям. Затронем темy стохастических методов для задач с ограничениями. Поговорим о некоторых методах, применимых для отдельных классов невыпyклых задач с приемлемыми оценками скорости сходимости. Наконец, рассмотрим приложения методов для задач с ограничениями к распределённой децентрализованной оптимизации: децентрализованный градиентный метод, консенсусное проектирование, а также сведение к двойственной задаче.