Отделение ИВМ РАН в Московском центре фундаментальной и прикладной математике проводит цикл лекций
Классическая и неклассическая оптимизация
Лектор: д.ф.-м.н. Роланд Хильдебранд (МФТИ, Иннополис)
Во вторник, 10 марта 2026 в 10:30 в ауд. 727 ИВМ РАН состоится первая лекция мини-курса
Программа мини-курса:
В предыдущем цикле лекций были освещены алгоритмы выпуклой и гладкой оптимизации, предметом которых является минимизация функции от вещественных переменных, а также методы решения задач дискретной оптимизации, основанные на выпуклых релаксациях. В данном цикле будут освещены алгоритмы дискретной оптимизации, опирающиеся на дискретную структуру допустимого множества задачи, и смежные темы, в частности, связанные с квантовыми вычислениями.
Среди задач дискретной оптимизации можно выделить некоторые стандартные классы, для которых существуют специализированные алгоритмы решения. На лекциях мы рассмотрим задачу о выполнимости булевых формул, задачу покрытия множества подмножествами, задачу упаковки в контейнеры, задачу рюкзака, задачу о сумме подмножества. Большое внимание будет уделено задачам над графами, таким как задача о наибольшем паросочетании, задача о наименьшем вершинном покрытии, задаче о покраске графа, задача о наибольшей клике и наибольшем независимом множестве, задача о покрытии кликами. Особое внимание мы уделим хордальным графам и их приложениям в численной линейной алгебре, являющейся одной из ключевых низкоуровневых компонент многих методов оптимизации. Большинство задач дискретной оптимизации имеют формулировку в виде целочисленной линейной программы. Особенности этих формулировок также будут рассмотрены.
В дополнение к специализированным методам будут освещены алгоритмы общего профиля, т.н. метаэвристики. Мы рассмотрим локальный спуск, поиск с запретами, поиск в больших окрестностях, генетические алгоритмы, метод имитации отжига, рой частиц, муравьиные колонии.
Отдельной темой будет связь задачи квадратичной бинарной безусловной оптимизации с квантовыми вычислениями посредством модели Изинга.