Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
ENG
Логин:
Пароль:

Лекция Современные эффективные методы выпуклой оптимизации

Преподаватели:
Nesterov Yurii
Должность: Ведущий научный сотрудник
Shpirko Sergei
Должность: Ведущий научный сотрудник

Описание курса

Часть I.
1.    Глобальная оптимизация. Понятие общей итеративной схемы метода. Метод равномерного перебора. Теорема об оценке сложности метода равномерного перебора;
2.    Глобальная оптимизация.Сопротивляющийся оракул. Теорема о нижней оценке сложности класса задач с липшицевой целевой функцией.
3.    Нелинейная оптимизация. Принципы аппроксимации и релаксации. Необходимые условия оптимальности первого и второго порядков. Общая схема градиентного метода и оценки его эффективности. Пример несходимости метода к точке локального минимума.
4.    Нелинейная оптимизация. Теорема о локальной сходимости градиентного метода.
5.    Гладкая выпуклая оптимизация. Выпуклые функции. Эквивалентные условия первого и второго порядков. Теорема о нижней оценке сложности класса выпуклых задач с липшицевым градиентом.
6.    Гладкая выпуклая оптимизация. Сильно выпуклые функции. Эквивалентные условия первого и второго порядков. Теорема о нижней оценке сложности класса сильно выпуклых задач с липшицевым градиентом.
7.    Гладкая выпуклая оптимизация. Градиентный метод. Теоремы сходимости метода на классах выпуклых и сильно выпуклых функций с липшицевым градиентом, оценки скорости сходимости.
8.    Гладкая выпуклая оптимизация. Принцип оценивающих последовательностей. Общая схема оптимального метода. Теорема сходимости метода на классах выпуклых и сильно выпуклых функций с липшицевым градиентом, оценки скорости сходимости (общая идея). 
9.    Гладкая выпуклая оптимизация. Условная задача. Градиентное отображение. Теорема сходимости градиентного метода на простых множествах, оценка скорости сходимости.’
10.    Гладкая выпуклая оптимизация. Минимаксная задача. Градиентное отображение. Градиентный метод для минимаксной задачи. Теорема об оценках сходимости градиентного метода для минимаксной задачи. Оценка скорости сходимости оптимального метода для минимаксной задачи (без доказательства).
Часть II.
11.    Негладкая выпуклая оптимизация. Производная по направлению. Лемма о связи нижней аппроксимации выпуклой функции и производной по направлению.
12.    Негладкая выпуклая оптимизация. Первая и вторая теоремы отделимости.
13.    Негладкая выпуклая оптимизация. Субградиент и субдифференциал функции. Теорема о связи субдифференциала и производной по направлению. Примеры вычисления субградиентов.
14.    Методы негладкой оптимизации. Теорема о нижней оценке сложности в безусловном случае (равномерно по размерности).
15.    Методы негладкой оптимизации. Принцип локализации решения. Субградиентный метод. Теорема сходимости субградиентного метода, оценка скорости сходимости.
16.    Методы негладкой оптимизации. Субградиентный метод для условной задачи с функциональными ограничениями. Теорема сходимости, оценка скорости сходимости.
17. Методы негладкой оптимизации. Задача разрешимости. Теорема о нижней оценке сложности в конечномерном случае. 
18.    Методы негладкой оптимизации. Метод отсекающей гиперплоскости. Основное свойство конечномерных множеств локализации. 
19.    Методы негладкой оптимизации. Обобщенный метод отсекающей гиперплоскости. Метод центров тяжести. Терема сходимости метода центров тяжести, оценка скорости сходимости. Метод эллипсоидов (общая идея).
Часть III.
20. Гладкая аппроксимация недифференцируемых функций. Оптимальная схема для гладкой оптимизации. Примеры применения техники сглаживания (основан на: Yu. Nesterov. Smooth minimization of non-smooth functions).
21. Пример задач сверхбольшого размера с разреженными субградиентами. Техника рекурсивного пересчета матричного-векторного произведения (разреженный случай). Техника пересчета значения функции с помощью бинарного дерева. Субградиентный метод и его сходимость. Применение субградиентного метода для решения разреженных задач сверхбольших размеров (факультативно).(основан на: Nesterov Yu. Subgradient Methods for Huge-Scale Optimization Problems )

 

Даты проведения и расписание:
Дата Расписание

05.09.2014
-
26.12.2014
МФТИ

ауд. 535 ГК
каждую пятницу с 9:00.

Экзамены 26.12 и 29.12 в 9:00