• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Convex Programming and Approximation Algorithms

2021/2022
Academic Year
RUS
Instruction in Russian
6
ECTS credits
Course type:
Elective course
When:
1 year, 3 module

Instructors


Milovanov, Alexey

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

Аннотация

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

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

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

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

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

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

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

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

  • неблокирующий Домашнее задание
  • неблокирующий Устный экзамен
Промежуточная аттестация

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

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

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

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

  • Комбинаторная оптимизация : теория и алгоритмы, Корте, Б., 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