RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Стохастический анализ в задачах
19 марта 2016 г. 13:00–15:00, г. Москва, Занятие будет на территории НИУ ВШЭ (Мясницкая, 20, ауд. 101, для прохода необходимо один раз заранее (до 12 февраля) написать письмо (тема письма “курс Гасникова”) Инне Юрьевне Корольковой ikorolkova@hse.ru)
 


Лекция 3 (часть 4). Базисные численные методы на множествах простой структуры

А. В. Гасниковab

a Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва
b Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.

Количество просмотров:
Эта страница:91
Youtube Video:





Аннотация: 1. Прямой градиентный метод Канторовича–Поляка (ПГМ). Прямой-прокс градиентный метод. Прямой-прокс градиентный метод с неточным оракулом и метод зеркального спуска. Равномерная ограниченность последовательностей, генерируемых методами (особенности ПГМ в случае выбора не евклидовой нормы).
2. Метод зеркального спуска Немировского–Юдина (МЗС) и метод двойственных усреднений Ю.Е. Нестерова (МДУ) (второй метод Ляпунова).
3. Игра на выборе прокс-структуры, исходя из множества (простой структуры). Примеры (шары, симплекс, прямое произведение симплексов).
4. Метод сопряженных градиентов и метод тяжелого шарика (первый метод Ляпунова).
5. Быстрый градиентный метод (БГМ) Ю.Е. Нестерова (в форме Allen-Zhu–Oreсchia: выпуклая комбинация ПГМ и МЗС, в геометрической форме S. Bubeck’a). Равномерная ограниченность последовательности, генерируемой методом.
6. Метод регуляризации А.Н. Тихонова (приведение выпуклой задачи к сильно выпуклой). Выбор параметра регуляризации. Техника рестарта по параметру. Оптимальный выбор параметра рестарта. Получение оценок в сильно выпуклом случае с помощью рестарт техники по расстоянию от текущего положения до решения из методов, не настроенных на сильную выпуклость. Непрерывность ПГМ по параметру сильной выпуклости.
7. Непрерывные аналоги численных методов. Интерпретация методов.
8. Структурная оптимизация. Концепция заглядывания в “черный ящик”. Композитная оптимизация. Пример LASSO. Метод двойственного сглаживания Ю.Е. Нестерова для задач с простым лежандровым представлением.
Литература:
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
- Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
- Boyd S., Vandenberghe L. Convex optimization. Cambridge University Press, 2004. http://stanford.edu/~boyd/cvxbook/
- Nesterov Y. Smooth minimization of non-smooth function // Math. Program. Ser. A. 2005. V. 103. № 1. P. 127–152. http://luthuli.cs.uiuc.edu/~daf/courses/Optimization/MRFpapers/nesterov05.pdf
- Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013. http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf
- Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. CORE UCL, PhD thesis, March 2013. http://www.ucllouvain.be/cps/ucl/doc/core/documents/coredp2011_70web.pdf
- Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent // e-print, 2014. arXiv:1407.1537
- Bubeck S. Convex optimization: algorithms and complexity // In Foundations and Trends in Machine Learning. 2015. V. 8. no. 3-4. P. 231–357. arXiv:1405.4980
- Гасников А.В., Лагуновская А.А., Морозова Л.Э. О связи имитационной логит динамики в популяционной теории игр и метода зеркального спуска в онлайн оптимизации на примере задачи выбора кратчайшего маршрута // Труды МФТИ. 2015. Т. 7. № 4. С. 104–113. arXiv:1511.02398 Wibisono A., Wilson A.C. On accelerated methods in optimization // e-print, 2015. arXiv:1509.03616
- Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. 2016. Т. 8. arxiv:1411.4218

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018