Все выпуски

В статье рассматривается задача минимизации математического ожидания выпуклой функции. Задачи такого вида повсеместны в машинном обучении, а также часто возникают в ряде других приложений. На практике для их решения обычно используются процедуры типа стохастического градиентного спуска (SGD). В нашей работе предлагается решать такие задачи с использованием метода эллипсоидов с мини-батчингом. Алгоритм имеет линейную скорость сходимости и может оказаться эффективнее SGD в ряде задач. Это подтверждается в наших экспериментах, исходный код которых находится в открытом доступе. Для получения линейной скорости сходимости метода не требуется ни гладкость, ни сильная выпуклость целевой функции. Таким образом, сложность алгоритма не зависит от обусловленности задачи. В работе доказывается, что метод эллипсоидов с наперед заданной вероятностью находит решение с желаемой точностью при использовании мини-батчей, размер которых пропорционален точности в степени -2. Это позволяет выполнять алгоритм параллельно на большом числе процессоров, тогда как возможности для батчараллелизации процедур типа стохастического градиентного спуска весьма ограничены. Несмотря на быструю сходимость, общее количество вычислений градиента для метода эллипсоидов может получиться больше, чем для SGD, который неплохо сходится и при маленьком размере батча. Количество итераций метода эллипсоидов квадратично зависит от размерности задачи, поэтому метод подойдет для относительно небольших размерностей.

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

В этой работе мы, во-первых, сделали обзор наиболее популярных методов аппроксимации градиента: конечная прямая/центральная разность (FFD/FCD), покомпонентная прямая/центральная разность (FWC/CWC), прямая/центральная рандомизация на $l_2$ сфере (FSSG2/CFFG2); во-вторых, мы описали текущие теоретические представления шума, вносимого неточностью вычисления функции в точке: враждебный шум, случайный шум; в-третьих, мы провели серию экспериментов на часто встречающихся классах задач, таких как квадратичная задача, логистическая регрессия, SVM, чтобы попытаться определить, соответствует ли реальная природа машинного шума существующей теории. Оказалось, что в реальности (по крайней мере на тех классах задач, которые были рассмотрены в данной работе) машинный шум оказался чем-то средним между враждебным шумом и случайным, в связи с чем текущая теория о влиянии конечности мантиссы на поиск оптимума в задачах безградиентной оптимизации требует некоторой корректировки.

В работе рассмотрена краевая задача о движении тепловой волны для вырождающегося уравнения второго порядка параболического типа со степенной нелинейностью. Краевое условие задает уравнение движения на плоскости нулевого фронта тепловой волны, имеющего форму окружности. Предложен новый численно-аналитический алгоритм, в соответствии с которым решение строится по шагам по времени при разностной схеме дискретизации времени. На каждом шаге рассматривается краевая задача для уравнения Пуассона, к которому сводится исходное уравнение. Фактически она является обратной задачей Коши, в которой исходная граница области решения свободна от граничных условий, а на текущей границе (фронте волны) заданы два условия (Неймана и Дирихле). Решение этой задачи ищется в виде суммы частного решения уравнения Пуассона и решения соответствующего уравнения Лапласа, удовлетворяющего граничным условиям. Поскольку неоднородность зависит от искомой функции и ее производных, решение строится итерационно. Частное решение ищется методом коллокаций с помощью разложения неоднородности по радиальным базисным функциям. Обратная задача Коши для уравнения Лапласа решается методом нулевого поля применительно к круговым областям с круговыми отверстиями. Для таких задач этот метод применяется впервые. Вычислительный алгоритм оптимизирован за счет распараллеливания вычислений. Распараллеливание вычислений позволило эффективно реализовать алгоритм на высокопроизводительных вычислительных системах. На базе алгоритма была создана компьютерная программа. В качестве средства распараллеливания был выбран стандарт параллельного программирования OpenMP для языка программирования C++ как наиболее подходящий для вычислительных программ с параллельными циклами. Эффективность алгоритма и работоспособность программы были проверены сравнением результатов расчетов с известным точным решением, а также с численным решением, полученным авторами ранее с помощью метода граничных элементов. Проведенный вычислительный эксперимент показал хорошую сходимость итерационных процессов и более высокую точность нового алгоритма по сравнению с разработанным ранее. Анализ решений позволил определить наиболее подходящую систему радиальных базисных функций.

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

В работе с помощью аналитических и численных методов рассматривается задача о структуре и динамике связанных локализованных нелинейных волн в модели синус-Гордона с тремя одинаковыми притягивающими протяженными примесями, которые моделируются пространственной неоднородностью периодического потенциала. Найдены два возможных типа связанных нелинейных локализованных волн — бризерного и солитонного. Проведен анализ влияния параметров системы и начальных условий на структуру локализованных волн, их амплитуду и частоту. Связанные колебания локализованных волн бризерного типа, как и для случая точечных примесей, представляет собой сумму трех гармонических колебаний: синфазного, синфазно-антифазного и антифазного типа. Частотный анализ локализованных на примесях волн, которые были получены в ходе численного эксперимента, выполнялся с помощью дискретного преобразования Фурье. Для анализа локализованных волн бризерного типа применялся численный метод конечных разностей. Для проведения качественно анализа полученных численных результатов задача решалась аналитически для случая малых амплитуд локализованных на примесях колебаний. Показано, что при определенных параметрах примеси (глубина, ширина) можно получить локализованные волны солитонного типа. Найдены области значений параметров системы, в которых существуют локализованные волны определенного типа, а также область перехода от бризерных к солитонным типам колебаний. Были определены значения глубины и ширины примеси, при которых наблюдается переход от бризерного к солитонному типу локализованных колебаний. Были получены и рассмотрены различные сценарии колебаний солитонного типа с отрицательными и положительными значениями амплитуд на всех трех примесях, а также и смешанные случаи. Показано, что в случае расстояния между примесями много меньше единицы отсутствует переходная область, в которой зарождающийся бризер после потери энергии на излучение переходит в солитон. Показано, что рассмотренная модель может быть использована, например, для описания динамики волн намагниченности в мультислойных магнетиках.

Разработана численная 2D-модель погружения холодной океанической плиты в толщу верхней мантии Земли, где этапу начального погружения плиты предшествует установление режима термогравитационной конвекции мантийного вещества. Модельным приближением мантии выступает двумерный образ несжимаемой ньютоновской квазижидкости в декартовой системе координат, где вследствие высокой вязкости среды уравнения мантийной конвекции принимаются в стоксовском приближении. Полагается, что вместе с плитой в верхние слои мантии поступает просочившаяся сюда морская вода. С глубиной рост давления и температуры приводит к определенным потерям ее легких фракций и флюидов, потерям воды и газов водосодержащих минералов плиты, перестройке их кристаллической решетки и, как следствие, фазовым превращениям. Эти потери обусловливают рост плотности плиты и неравномерность распределения вдоль плиты напряжений (начальные участки плиты оказываются менее плотными), что в последствии вместе с воздействием на плиту мантийных течений вызывает ее фрагментацию. Рассматривается состояние мантийной конвекции, когда плита и ее отдельные фрагменты опустились на подошву верхней мантии. Разработаны вычислительные схемы решения уравнений модели. Расчеты мантийной конвекции выполнены в терминах приближения Стокса для завихренности и функции тока, а для расчетов состояния и погружения плиты использован SPH. Выполнен ряд вычислительных экспериментов. Показано, что вследствие воздействия на плиту мантийной конвекции и с развитием вдоль плиты неоднородного поля напряжений происходит ее фрагментация. Следуя уравнениям модели, оценивается время финальной стадии субдукции, т. е. времени выхода всей океанической плиты на дно верхней мантии. В геодинамике этот процесс определяется коллизией плит, следует непосредственно за субдукцией и рассматривается обычно в качестве конечного этапа цикла Уилсона (т. е. цикла развития складчатых поясов).

Традиционные методы решения задачи коммивояжера не являются эффективными для задач высокой размерности из-за их высокой вычислительной сложности. Одним из эффективных способов решения этой проблемы является декомпозиционный подход, который включает в себя три основных этапа: кластеризацию вершин, решение подзадач внутри каждого кластера и последующее объединение полученных решений в итоговое. В данной статье основное внимание уделяется третьему этапу — объединению циклов решений подзадач, поскольку этому этапу не всегда уделяется должное внимание, что приводит к менее точному итоговому решению. В статье предлагается новый модифицированный алгоритм Сигала для объединения циклов. Для оценки его эффективности проводится сравнение с двумя алгоритмами объединения циклов: метод соединения средних точек ребер и алгоритм на основе близости центроидов кластеров. Исследуется зависимость качества решения подзадач на алгоритмы объединения циклов. Модифицированный алгоритм Сигала выполняет попарное объединение кластеров, минимизируя количество пересечений и общее расстояние. Метод центроидов ориентирован на соединение кластеров на основе близости центроидов, а алгоритм с использованием средних точек оценивает расстояние между средними точками ребер. Также были рассмотрены два типа кластеризации: алгоритмы k-means и affinity propagation. Для проверки эффективности предложенного алгоритма были проведены численные эксперименты на наборе данных TSPLIB с различным количеством городов. В исследовании анализируются ошибки, вызванные порядком объединения кластеров, качеством решения подзадач и количеством кластеров. Эксперименты показали, что модифицированный алгоритм Сигала демонстрирует наименьшую медиану итогового расстояния и наиболее устойчивые результаты по сравнению с другими методами. Результаты указывают на большую устойчивость качества конечного решения, полученным модифицированным алгоритмом Сигала, от последовательности объединения кластеров. Повышение качества решения подзадачи обычно приводит к линейному улучшению конечного решения, но используемый алгоритм объединения редко влияет на степень этого улучшения.

Разработан и протестирован новый метод формирования тестовых сигналов для корреляционной идентификации нелинейных динамических систем методом Ли–Шетцена. Для коррекции моментных функций тестовых сигналов применен численный алгоритм оптимизации Гаусса–Ньютона. В экспериментах получены тестовые воздействия длиной до 40 000 точек, позволяющие определять ядра Винера 2-го порядка с линейным разрешением до 32 точек, ядра Винера 3-го порядка с линейным разрешением до 12 точек, ядра Винера 4-го порядка с линейным разрешением до 8 точек.

Рассматривается проблема применимости микроскопического моделирования транспортных потоков к анализу достаточно больших фрагментов сетей на примере модели дискретного потока с безопасной дистанцией. Вводится понятие интегральных характеристик перекрестков и предлагается методика получения интегральных характеристик на основе данных численных экспериментов по моделированию потоков на заданном перекрестке. Методика применяется к кольцевому коммутатору с Т-образными перекрестками, анализируются полученные характеристики.

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