Все выпуски

Задача выпуклой онлайн-оптимизации естественно возникают в случаях, когда имеет место обновления статистической информации. Для задач негладкой оптимизации хорошо известен метод зеркального спуска. Зеркальный спуск — это расширение субградиентного метода для решения негладких выпуклых задач оптимизации на случай неевкидова расстояния. Работа посвящена стохастическим аналогам недавно предложенных методов зеркального спуска для задач выпуклой онлайн-оптимизации с выпуклыми липшицевыми (вообще говоря, негладкими) функциональными ограничениями. Это означает, что вместо (суб)градиента целевого функционала и функционального ограничения мы используем их стохастические (суб)градиенты. Точнее говоря, допустим, что на замкнутом подмножестве $n$-мерного векторного пространства задано $N$ выпуклых липшицевых негладких функционалов. Рассматривается задача минимизации среднего арифметического этих функционалов с выпуклым липшицевым ограничением. Предложены два метода для решения этой задачи с использованием стохастических (суб)градиентов: адаптивный (не требует знания констант Липшица ни для целевого функционала, ни для ограничения), а также неадаптивный (требует знания константы Липшица для целевого функционала и ограничения). Отметим, что разрешено вычислять стохастический (суб)градиент каждого целевого функционала только один раз. В случае неотрицательного регрета мы находим, что количество непродуктивных шагов равно $O$($N$), что указывает на оптимальность предложенных методов. Мы рассматриваем произвольную прокс-структуру, что существенно для задач принятия решений. Приведены результаты численных экспериментов, позволяющие сравнить работу адаптивного и неадаптивного методов для некоторых примеров. Показано, что адаптивный метод может позволить существенно улучшить количество найденного решения.

В данной работе рассматривается возможность применения концепции $(\delta, L)$-модели функции для оптимизационных задач, в которых посредством решения прямой задачи имеется необходимость восстанавливать решение двойственной задачи. Концепция $(\delta, L)$-модели основана на концепции $(\delta, L)$-оракула, предложенной Деволдером–Глинером–Нестеровым, при этом данные авторы предложили фукнционалы в оптимизационных задачах аппроксимировать сверху выпуклой параболой с некоторым аддитивным шумом $\delta$; таким образом, им удалось получить квадратичные верхние оценки с шумом даже для негладких функционалов. Концепция $(\delta, L)$-модели продолжает эту идею за счет того, что аппроксимация сверху делается не выпуклой параболой, а некоторым более сложным выпуклым функционалом. Возможность восстанавливать решение двойственной задачи хорошо зарекомендовала себя, так как во многих случаях в прямой задаче можно значительно быстрее находить решение, чем в двойственной. Отметим, что прямо-двойственные методы хорошо изучены, но при этом, как правило, каждый метод предлагается под конкретный класс задач. Наша же цель — предложить метод, который бы включал в себя сразу различные методы. Это реализуется за счет использования концепции $(\delta, L)$-модели и адаптивной структуры наших методов. Таким образом, нам удалось получить прямо-двойственный адаптивный градиентный метод и быстрый градиентный метод с $(\delta, L)$-моделью и доказать оценки сходимости для них, причем для некоторых классов задач данные оценки являются оптимальными. Основная идея заключается в том, что нахождение двойственных решений происходит относительно оптимизационной задачи, которая аппроксимируют прямую с помощью концепции $(\delta, L)$-модели и имеет более простую структуру, поэтому находить двойственное решение у нее проще. Стоит отметить, что это происходит на каждом шаге работы оптимизационного метода; таким образом, реализуется принцип «разделяй и властвуй».

Cтроится семейство явных разностных схем на пятиточечном шаблоне для численного решения линейного уравнения переноса. Анализ свойств разностных схем проводится в пространстве неопределенных коэффициентов. Такие пространства впервые были введены в рассмотрение А. С. Холодовым. Для исследования свойств разностных схем ставилась задача линейного программирования. В качестве целевой функции обычно рассматривался коэффициент при главном члене невязки. Для построения монотонных разностных схем ставилась задача оптимизации с ограничениями типа неравенств. Ограниченность такого подхода становится ясной с учетом того, что аппроксимация разностной схемы определяется лишь на классических (гладких) решениях дифференциальной задачи.

В соответствие разностной схеме ставится некоторый функционал, определяющий свойства разностной схемы. Функционал должен быть линейным по коэффициентам схемы. Возможно, что функционал зависит от сеточной функции — решения разностной задачи или проекции на сетку решения дифференциальной задачи. Если первые члены разложения в ряд Тейлора этого функционала по сеточным параметрам совпадут с условиями классической аппроксимации, такой функционал будем называть обобщенным условием аппроксимации. В статье показано, что такие функционалы существуют. Для линейного уравнения с постоянными коэффициентами построение такого функционала возможно и для обобщенного (негладкого) решения дифференциальной задачи.

Построение разностной схемы с заданными свойствами тогда опирается на решение задачи поиска минимума функционала.

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

Приводится пример численной реализации простейшей разностной схемы с обобщенной аппроксимацией.