|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ
On some stochastic mirror descent methods for constrained online optimization problems
[О некоторых стохастических методах зеркального спуска для условных задач онлайн-оптимизации]
M. S. Alkousa Moscow Institute of Physics and Technology,
9 Institutskiy per., Dolgoprudny, Moscow Region, 141701, Russia
Аннотация:
Задача выпуклой онлайн-оптимизации естественно возникают в случаях, когда имеет место обновления статистической информации. Для задач негладкой оптимизации хорошо известен метод зеркального спуска. Зеркальный спуск — это расширение субградиентного метода для решения негладких выпуклых задач оптимизации на случай неевклидова расстояния. Работа посвящена стохастическим аналогам недавно предложенных методов зеркального спуска для задач выпуклой онлайн-оптимизации с выпуклыми липшицевыми (вообще говоря, негладкими) функциональными ограничениями. Это означает, что вместо(суб)градиента целевого функционала и функционального ограничения мы используем их стохастические (суб)градиенты. Точнее говоря, допустим, что на замкнутом подмножестве $n$-мерного векторного пространства задано N выпуклых липшицевых негладких функционалов. Рассматривается задача минимизации среднего арифметического этих функционалов с выпуклым липшицевым ограничением. Предложены два метода для решения этой задачи с использованием стохастических (суб)градиентов: адаптивный (не требует знания констант Липшица ни для целевого функционала, ни для ограничения), а также неадаптивный (требует знания константы Липшица для целевого функционала и ограничения). Отметим, что разрешено вычислять стохастический (суб)градиент каждого целевого функционала только один раз. В случае неотрицательного регрета мы находим, что количество непродуктивных шагов равно $O(N)$, что указывает на оптимальность предложенных методов. Мы рассматриваем произвольную прокс-структуру, что существенно для задач принятия решений. Приведены результаты численных экспериментов, позволяющие сравнить работу адаптивного и неадаптивного методов для некоторых примеров. Показано, что адаптивный метод может позволить существенно улучшить количество найденного решения.
Ключевые слова:
задача выпуклой онлайн-оптимизации, негладкая задача условной оптимизации, адаптивный зеркальный спуск, липшицев функционал, стохастический (суб)градиент.
Поступила в редакцию: 18.11.2018 Исправленный вариант: 05.03.2019 Принята в печать: 06.03.2019
Образец цитирования:
M. S. Alkousa, “On some stochastic mirror descent methods for constrained online optimization problems”, Компьютерные исследования и моделирование, 11:2 (2019), 205–217
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm706 https://www.mathnet.ru/rus/crm/v11/i2/p205
|
|