Все выпуски

В работе предложен новый класс безитерационных схем (явно-неявных), который позволяет получать методы, повторяющие на линейных неавтономных задачах свойства лучших неявных жестко-точных методов Рунге–Кутты [Хайрер, Ваннер,1999] – RadauIIA и LobattoIIIC. Для этого используется понятие LN-эквивалентности методов [Ширков, 2012]. С использованием среды аналитических вычислений получены уравнения порядка и затухания таких методов и найдены коэффициенты некоторых схем до 3-го порядка включительно. Проводится численное исследование новых методов на классических тестах, применяемых для проверки схем, разрабатываемых для жестких систем.

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

Многомерные данные, при использовании значительно большего количества признаков относительно меньшего числа наблюдений, порождают хорошо известную проблему переопределённой задачи. В связи с этим, представляется целесообразным описание данных в терминах меньшего числа мета-признаков, которые вычисляются при помощи так называемых матричных факторизаций. Такие факторизации способствуют уменьшению случайного шума при сохранении наиболее существенной информации. Три новых и взаимосвязанных метода предложены в этой статье: 1) факторизационный механизм градиентного спуска с двумя (согласно размерности микрочипа) гибкими и адаптируемыми параметрами обучения, включая явные формулы их автоматического пересчета, 2) непараметрический критерий для отбора количества факторов, и 3) неотрицательная модификация градиентной факторизации, которая не требует дополнительных вычислительных затрат в сравнении с базовой моделью. Мы иллюстрируем эффективность предложенных методов в приложении к задаче направляемой классификации данных в области биоинформатики.

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

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

В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближенного решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро – Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счет замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю. Е. Нестерова (2018 г.), а также за счет специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю. Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка $p \geqslant 3$.

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

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

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