Спецкурс «Алгоритмы выпуклой оптимизации»
О чем этот курс
Об алгоритмах выпуклой оптимизации. Предполагается дать слушателям представление об алгоритмах оптимизации в целом, выделить среди них выпуклые алгоритмы и объяснить их значимость и практическую применимость.
Для кого этот курс
Спецкурс рассчитан главным образом на студентов 3-4 курсов и магистратуры, но может быть понятен и младшекурсникам, обладающим некоторыми знаниями по функциональному анализу и линейной алгебре.
Кто читает
Асс. (кафедра Анализа Данных ФИВТ).
Продолжительность и форма отчетности
Спецкурс рассчитан на один семестр, по окончании желающие могут сдать экзамен.
Время и место проведения
Понедельник, 17:05 - 18:30, аудитория 419 Главного корпуса.
Первое занятие состоится 12 сентября.
Примерный список тем
1. Введение в оптимизацию. (Основные классы задач оптимизации, примеры задач оптимизации в физике, экономике, теории распознавания. )
2.Сведения из функционального анализа и линейной алгебры. (Выпуклые множества и выпуклые функции. Операции, сохраняющие выпуклость. Теорема Банаха обо открытом отображении и теоремы об отделимости выпуклых множеств. Нормированные пространства. Классы функций. Дифференциальное исчисление в нормированных пространствах. )
3. Необходимые условия экстремума. Принцип Лагранжа. (Принцип Лагранжа для гладких задач с равенствами и неравенствами. Принцип Лагранжа для выпуклых задач. Теорема Каруша-Куна-Таккера. )
4. Нелинейная минимизация. (Формулировка задачи нелинейной минимизации. Ограничения сложности для глобальной минимизации. Алгоритмы безусловной локальной минимизации. Метод градиента и метод Ньютона, сравнение методов. Другие методы. Негладкая безусловная минимизация Субградиент. Минимизация с ограничениями типа равенств.)
5. Методы внутренней точки. (Минимизация с ограничениями типа неравенств. Метод Левина-Ньюмена центрированных сечений. Метод эллипсоидов. Метод симплексов. Логарифмическая барьерная функция. Барьерный метод. Анализ сложности методов.)
