RUS  ENG
Полная версия
ЖУРНАЛЫ // Компьютерные исследования и моделирование // Архив

Компьютерные исследования и моделирование, 2019, том 11, выпуск 2, страницы 205–217 (Mi crm706)

Эта публикация цитируется в 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)$, что указывает на оптимальность предложенных методов. Мы рассматриваем произвольную прокс-структуру, что существенно для задач принятия решений. Приведены результаты численных экспериментов, позволяющие сравнить работу адаптивного и неадаптивного методов для некоторых примеров. Показано, что адаптивный метод может позволить существенно улучшить количество найденного решения.

Ключевые слова: задача выпуклой онлайн-оптимизации, негладкая задача условной оптимизации, адаптивный зеркальный спуск, липшицев функционал, стохастический (суб)градиент.

УДК: 519.85

Поступила в редакцию: 18.11.2018
Исправленный вариант: 05.03.2019
Принята в печать: 06.03.2019

Язык публикации: английский

DOI: 10.20537/2076-7633-2019-11-2-205-217



© МИАН, 2024