На главную страницу НМУ

Ю.Е. Нестеров

Алгоритмические основы современной Теории Оптимизации

Интенсивный миникурс лекций
Курс поддержан Лабораторией структурных методов анализа данных в предсказательном моделировании (ПреМоЛаб http://www.premolab.ru/), ФУПМ МФТИ, грант правительства РФ дог. 11.G34.31.0073.

Курс будет читаться:
лекция 1: вторник 4 сентября в 19:20 конф-зал (401),
лекция 2: четверг 6 сентября в 19:20 конф-зал (401),
лекция 3: суббота 8 сентября в 16:00 конф-зал (401),
лекция 4: понедельник 10 сентября в 19:20 ауд.310,
лекция 5: среда 12 сентября в 19:20 ауд.310,
лекция 6: пятница 14 сентября в 19:20 ауд.310.

Экзамен

Экзамен будет устроен экзамен в виде решения задач.pdf.
Каждой задаче присваиваются баллы (в фигурных скобках).

Оценки будут проставляться по следующей шкале (примерно): 3: 6-9 баллов,
4: 10-12 баллов,
5: 13-15 баллов.

Решенные задачи присылать Шпирко Сергею по адресу shpirko@yahoo.com (в формате pdf).

Срок приема - 3 дня: с 9:00 понедельник, 1 октября по 24:00 четверг, 4 октября.

Материалы к лекциям:

ВИДЕО

к лекции 1: Слайды 1.pdf
к лекции 2: Слайды 2.pdf, скачать аудио-запись лекции
к лекции 3: Слайды 3.pdf
к лекции 4: Слайды 4.pdf
к лекции 5: Слайды 5.pdf
к лекции 6: Слайды 6.pdf

Программа курса

В курсе излагаются основные принципы разработки и применения современных методов оптимизации. Во вводной лекции обсуждаются приоритеты алгоритмической Теории Оптимизации, учитывая ее связующее положение между математикой и инженерными науками. Далее мы подробно останавливаемся на нижних оценках сложности и оптимальных методах в модели "черный ящик". В то же время приводятся примеры преодоления теоретических пределов эффективности этой теории за счет использования структуры оптимизационных задач (методы внутренней точки, сглаживание, минимизация составных функций). Затем мы обсудим специальные подходы к решению задач очень больших размеров. Завершается курс двумя нестандартными разделами: применение выпуклой оптимизации для решения комбинаторных задач и алгоритмическими моделями, объясняющих возможность рационального поведения в живой и неживой природе.

Список лекций:

  1. Простота и сложность задач оптимизации

  2. Нижние оценки сложности и оптимальные алгоритмы

  3. Заглядывая в Черный Ящик (Структурная Оптимизация)

  4. Задачи оптимизации огромных размеров

  5. Нелинейный анализ комбинаторных задач

  6. Алгоритмические модели человеческого поведения.

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

  1. Нестеров Ю. Е. Введение в выпуклую оптимизацию. Изд. МЦНМО, Москва, 2010. 

  2. Yu. Nesterov, A. Nemirovskii. Interior point polynomial methods in convex programming: Theory and Applications. SIAM, Philadelphia, 1994.

  3. Nesterov Yu. Smooth minimization of non-smooth functions,  Mathematical Programming, 103(1), 127 ? 152 (2005). 

  4. Nesterov Yu. Primal-dual subgradient methods for convex problems.  Mathematical Programming, 120(1), 261 ? 283 (2009). 

  5. Nesterov Yu. Minimization methods for composite functions. Accepted  by Mathematical Programming.

  6. Yu.Nesterov. Semidefinite relaxation and nonconvex quadratic optimization. Optimization Methods and Software, 9, 141-160 (1998)
Rambler's Top100