RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

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

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

DOI: https://doi.org/10.20537/2076-7633-2019-11-2-205-217

Полный текст: PDF файл (152 kB)
Полный текст: http://crm.ics.org.ru/.../2775
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.85
Поступила в редакцию: 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

Цитирование в формате AMSBIB
\RBibitem{Alk19}
\by M.~S.~Alkousa
\paper On some stochastic mirror descent methods for constrained online optimization problems
\jour Компьютерные исследования и моделирование
\yr 2019
\vol 11
\issue 2
\pages 205--217
\mathnet{http://mi.mathnet.ru/crm706}
\crossref{https://doi.org/10.20537/2076-7633-2019-11-2-205-217}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/crm706
  • http://mi.mathnet.ru/rus/crm/v11/i2/p205

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Компьютерные исследования и моделирование
    Просмотров:
    Эта страница:50
    Полный текст:18
    Литература:6
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019