Выпуклое программирование и аппроксимационные алгоритмы

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

4-й курс, 3 модуль

Преподаватель

Вялый Михаил Николаевич

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• Освоить общие приемы построения приближенных алгоритмов: метод усреднения, ЛП релаксации, SDP релаксации.
• Изучить классические примеры использования метода усреднения, ЛП релаксаций и SDP релаксаций.
• Научиться анализировать сложность приближенных алгоритмов и их точность.

Планируемые результаты обучения

• Воспроизводит доказательства основных результатов о точности приближенных алгоритмов
• Оценивает точность приближения SDP релаксации
• Оценивает точность приближения в методе усреднения
• Оценивает точность приближения ЛП релаксации

Содержание учебной дисциплины

• Средние оценки и дерандомизация
• ЛП релаксации задач комбинаторной оптимизации
• SDP релаксации
• Знакомство с иерархией Лассера

Элементы контроля

• Устный экзамен
• Домашнее задание

Промежуточная аттестация

• 2023/2024 учебный год 3 модуль
  0.4 * Домашнее задание + 0.6 * Устный экзамен

Список литературы

Рекомендуемая основная литература

• Комбинаторная оптимизация : теория и алгоритмы, Корте, Б., 2015

Рекомендуемая дополнительная литература

• A mathematical view of interior-point methods in convex optimization, Renegar, J., 2001
• Lectures on modern convex optimization : analysis, algorithms, and engineering applications, Ben-Tal, A., 2001
• Эффективные методы в нелинейном программировании, Нестеров, Ю. Е., 1989