А.В. Гасников (МФТИ). Мини-курс. Лекция 2. Введение в теорию сложности задач выпуклой оптимизации.

Лекция 2. Введение в теорию сложности задач выпуклой оптимизации. - Точные оценки сложности класса задач гладкой, негладкой, выпуклой, сильно выпуклой оптимизации. - Примеры универсально плохих функций (для гладких и негладких задач выпуклой оптимизации). - Задачи малой размерности. - Метод центров тяжести, эллипсоидов, Вайды, Lee-Sidford-Wong. - Субградиентный и быстрый градиентный методы. - Сведение класса выпуклых задач к классу сильно выпуклых задач с помощью регуляризации. - Распространение методов, решающих задачи выпуклой оптимизации, на задачи сильно выпуклой оптимизации с помощью техники рестартов. - Адаптивные методы. 1 лекция - https://youtu.be/ObqoK2J_db4 3 лекция - https://youtu.be/sgoxQrJvZTY 4 лекция - https://youtu.be/7XIRfV7CG8U 5 лекция - https://youtu.be/1OHxD-lG_jE 6 лекция - https://youtu.be/uTvErcqG7V4 7 лекция - https://youtu.be/JhWMjF2Sor8 8 лекция - https://youtu.be/uZmYqjwdZ9w 9 лекция - https://youtu.be/_dfW1FzUb4I Литература: 1. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. – М.: Наука, 1979. – 384 с. - URL: http://cmcagu.ru/docs/books/Nemirovskii-effektivnost_metodov_optimizatsii.pdf 2. Nesterov Yu. Primal-dual subgradient methods for convex problems // Math. Program. Ser. B. – 2009. – V. 120(1). – P. 261–283. – URL: http://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2005_67.pdf 3. Нестеров Ю.Е. Введение в выпуклую оптимизацию. – М.: МЦНМО, 2010. – 262 с. – URL: http://premolab.ru/pub_files/pub5/MnexoB89z7.pdf (основной источник) Главы 2, 3 4. Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. – 2015. – V. 152. – P. 381–404. 5. Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. – Philadelphia: SIAM, 2015. – URL: http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf 6. Bubeck S. Convex optimization: algorithms and complexity Trends in Machine Learning. – 2015. – V. 8, N 3–4. – P. 231–357. – URL: https://arxiv.org/pdf/1405.4980.pdf Chapter 2-4 (основной источник) 7. Гасников А.В. Современные численные методы оптимизации. Универсальный градиентный спуск. – М.: МФТИ, 2018. – 166 с. – URL: https://arxiv.org/pdf/1711.00394.pdf Много интересного можно найти в нашей группе ВК: Последние события в нашем аккаунте Инстаграм: #гасников #майкоп #кмцагу