Алгоритмическая выпуклая оптимизация

Юрий Евгеньевич Нестеров

Серия: Учебник Школы прикладной математики и информатики МФТИ

За последние десятилетия теория оптимизации развивалась гораздо быстрее, чем любое другое направление численного анализа. Фундаментальной причиной этой перестройки являлся переход от методов, базирующихся на модели черного ящика, в которых была недоступна информация о внутренней структуре функциональных компонент, к полностью открытой модели, когда разработчику алгоритмов разрешалось даже менять внутреннее представление данных с целью облегчить работу специализированного метода оптимизации. В результате удавалось построить гораздо более эффективные алгоритмы, которые по эффективности превосходили даже верхние границы теории сложности, разработанные для черно-ящичных методов. К настоящему моменту основные достижения этого этапа еще не отражены в монографической литературе.

Эта книга является, по-видимому, первой попыткой восполнить возникший пробел, изложив основные концепции в форме, доступной для студентов старших курсов. Среди основных тем в ней можно найти современную теорию субградиентных методов, включая разные аспекты двойственности, быстрые градиентные методы, эффективные методы решения вариационных неравенств и современные методы второго порядка. Специальные главы посвящены технике сглаживания недифференцируемых функций и построению оптимизационных алгоритмов для нахождения решений с относительной точностью. Уровень изложения соответствует старшим курсам технических университетов. Содержание глав достаточно независимо. Каждая из них может быть включена в различные курсы по теории оптимизации.