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