А.В. Гасников (МФТИ). Мини-курс. Лекция 7. Каталист и оптимальные методы высокого порядка

Лекция 7. Каталист. Проксимальный быстрый градиентный метод Monteiro-Svaiter. Имплементируемые методы высокого порядка. Построение оптимальных методов высокого порядка. Проксимальный ускоренный градиентный спуск и построение на его основе универсальной процедуры ускорения не ускоренных методов первого порядка (градиентного типа) и их рандомизированных вариантов Lin-Marial-Harchoui. Получение конструкции каталист с помощью ускоренного градиентного метода, работающего в концепции модели функции с неточным оракулом и Moreau envelope. Тонкий вариант проксимального ускоренного градиентного спуска Monteiro-Svaiter'а. Решение вспомогательной задачи в концепции относительной точности (возможность неточного решения вспомогательной задачи). Методы высокого порядка. Метод Ньютона с кубической регуляризацией и имплементируемый метод третьего порядка. Построение оптимальных методов высокого порядка на базе проксимального ускоренного градиентного спуска Monteiro-Svaiter'а и неускоренных методов высокого порядка Ю.Е. Нестерова. Построение примера функции, который обосновывает неулучшаемость (с точностью до числового множителя) полученных оценок скорости сходимости. Перенесение оптимальных методов высокого порядка на сильно выпуклые задачи с помощью рестартов на базе идеи попадания в окрестность квадратичной сходимости метода Ньютона. 1 лекция - https://www.youtube.com/watch?v=ObqoK2J_db4 2 лекция - https://www.youtube.com/watch?v=wsq74WZvdDA 3 лекция - https://www.youtube.com/watch?v=sgoxQrJvZTY 4 лекция - https://www.youtube.com/watch?v=7XIRfV7CG8U 5 лекция - https://www.youtube.com/watch?v=1OHxD-lG_jE 6 лекция - https://www.youtube.com/watch?v=uTvErcqG7V4 8 лекция - https://www.youtube.com/watch?v=uZmYqjwdZ9w 9 лекция - https://www.youtube.com/watch?v=_dfW1FzUb4I Литература: 1. Мonteiro R., Svaiter B. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods // SIAM Journa on Optimization. – 2013. – V. 23(2). – P. 1092–1125. – URL: https://www2.isye.gatech.edu/~monteiro/publications/tech_reports/prox-accel7.pdf (основной источник) 2. Lin H., Mairal J., Harchaoui Z. Catalyst acceleration for first-order convex optimization: from theory to practice // arXiv.org e-Print archive. 2017. – URL: https://arxiv.org/pdf/1712.05654.pdf 3. Гасников А.В. и др. Обоснование гипотезы об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков // Компьютерные исследования и моделирование. – 2018. – Т. 10:6 (в печати). – URL: https://arxiv.org/ftp/arxiv/papers/1809/1809.00382.pdf (основной источник) 4. Nesterov Yu. Lecture on convex optimization. – Springer, 2018. Chapter 5. 5. Nesterov Yu. Implementable tensor methods in unconstrained convex optimization // CORE Discussion Papers. 2018/5. – 2018. – 22 p. – URL: https://alfresco.uclouvain.be/alfresco/service/guest/streamDownload/workspace/SpacesStore/aabc2323-0bc1-40d4-9653-1c29971e7bd8/coredp2018_05web.pdf?guest=true 6. Гасников А.В. Современные численные методы оптимизации. Универсальный градиентный спуск. – М.: МФТИ, 2018. – 166 с. – URL: https://arxiv.org/pdf/1711.00394.pdf Приложение Много интересного можно найти в нашей группе ВК: Последние события в нашем аккаунте Инстаграм: #гасников #майкоп #кмцагу