Первая лекция в ИВМ РАН мини-курса по оптимизации, докладчик в.н.с. МФТИ Роланд Хильдебранд

В рамках серии лекции отделения Московского центра фундаментальной и прикладной математики в ИВМ РАН Программа мини-курса по оптимизации: 1. Общие сведения. Примеры проблем. Мультикритериальная оптимизация, множество Парето. Эвристики и оптимальные решения. Формализация проблемы в виде задачи оптимизации. Форма записи задач оптимизации. Классификация задач оптимизации. Классы задач. Оракулы. Сложность классов задач. Критерии сходимости. Пример: одномерный поиск, дихотомия. Решатели. Форматы для ЭВМ. 2. Неструктурированная оптимизация. Безусловные задачи. Градиентный спуск. Метод Ньютона. Автоматическое дифференцирование. Метод сопряжённых градиентов. Блочный координатный спуск. Задачи с ограничениями. Метод множителей Лагранжа. Метод проектированного градиента. Метод Франк-Вульфа. Барьеры и штрафные функции. Приложения. Машинное обучение. Декомпозиция сложных задач. 3. Структурированная оптимизация. Линейное программирование. Условия оптимальности, сильная двойственность. Симплекс-метод. Метод внутренней точки. Разреженность. Полуопределённое программирование. Приложения. 4. Дискретная и смешанно-целочисленная оптимизация. Примеры задач: рюкзак, упаковка, раскраска, паросочетания. Эвристики. Релаксации. Метод ветвей и границ. Рандомизированный метод Гёманса-Виллиамсона. Пи/2 теорема Нестерова.