Все выпуски

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

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка AGMsDR на классе задач минимизации, вообще говоря, невыпуклых функций с $M$-липшицевым градиентом и удовлетворяющих условию Поляка – Лоясиевича. При реализации метода не требуется знать параметр $\mu^{PL}>0$ из условия Поляка – Лоясиевича, при этом метод демонстрирует линейную скорость сходимости (сходимость со скоростью геометрической прогрессии со знаменателем $\left.\left(1 - \frac{\mu^{PL}}{M}\right)\right)$. Ранее для метода была доказана сходимость со скоростью $O\left(\frac1{k^2}\right)$ на классе выпуклых задач с $M$-липшицевым градиентом. А также сходимость со скоростью геометрической прогрессии, знаменатель которой $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$, но только если алгоритму известно значение параметра сильной выпуклости $\mu^{SC}>0$. Новизна результата заключается в том, что удается отказаться от использования методом значения параметра $\mu^{SC}>0$ и при этом сохранить линейную скорость сходимости, но уже без корня в знаменателе прогрессии.

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

Таким образом, представлены адаптивные ускоренные методы с оценкой сходимости $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ на классе выпуклых функций с $M$-липшицевым градиентом, которые удовлетворяют условию Поляка – Лоясиевича. При этом для работы метода не требуются значения параметров $M$ и $\mu^{PL}$. Если же условие Поляка – Лоясиевича не выполняется, то можно утверждать, что скорость сходимости равна $O\left(\frac1{k^2}\right)$, но при этом методы не требуют никаких изменений.

Также рассматривается адаптивная каталист-оболочка неускоренного градиентного метода, которая позволяет доказать оценку скорости сходимости $O\left(\frac1{k^2}\right)$. Проведено экспериментальное сравнение неускоренного градиентного метода с адаптивным выбором шага, ускоренного с помощью адаптивной каталист-оболочки с методами AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) и алгоритмом Синхорна для задачи, двойственной к задаче оптимального транспорта.

Проведенные вычислительные эксперименты показали более быструю работу метода Alternating AGMsDR по сравнению как с неускоренным градиентным методом, ускоренным с помощью адаптивной каталист-оболочки, так и с методом AGMsDR, несмотря на асимптотически одинаковые гарантии скорости сходимости $O\left(\frac1{k^2}\right)$. Это может быть объяснено результатом о линейной скорости сходимости метода Alternating AGMsDR на классе задач, удовлетворяющих условию Поляка – Лоясиевича. Гипотеза была проверена на квадратичных задачах. Метод Alternating AGMsDR показал более быструю сходимость по сравнению с методом AGMsDR.

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

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

Предлагается семейство методов Гаусса – Ньютона для решения оптимизационных задачи систем нелинейных уравнений, основанное на идеях использования верхней оценки нормы невязки системы уравнений и квадратичной регуляризации. В работе представлено развитие схемы метода трех квадратов с добавлением моментного члена к правилу обновления искомых параметров в решаемой задаче. Получившаяся схема обладает несколькими замечательными свойствами. Во-первых, в работе алгоритмически описано целое параметрическое семейство методов, минимизирующих функционалы специального вида: композиции невязки нелинейного уравнения и унимодального функционала. Такой функционал, целиком согласующийся с парадигмой «серого ящика» в описании задачи, объединяет в себе большое количество решаемых задач, связанных с приложениями в машинном обучении, с задачами восстановления регрессионной зависимости. Во-вторых, полученное семейство методов описывается как обобщение нескольких форм алгоритма Левенберга – Марквардта, допускающих реализацию в том числе и в неевклидовых пространствах. В алгоритме, описывающем параметрическое семейство методов Гаусса – Ньютона, используется итеративная процедура, осуществляющая неточное параметризованное проксимальное отображение и сдвиг с помощью моментного члена. Работа содержит детальный анализ эффективности предложенного семейства методов Гаусса – Ньютона, выведенные оценки учитывают количество внешних итераций алгоритма решения основной задачи, точность и вычислительную сложность представления локальной модели и вычисления оракула. Для семейства методов выведены условия сублинейной и линейной сходимости, основанные на неравенстве Поляка – Лоясиевича. В обоих наблюдаемых режимах сходимости локально предполагается наличие свойства Липшица у невязки нелинейной системы уравнений. Кроме теоретического анализа схемы, в работе изучаются вопросы ее практической реализации. В частности, в проведенных экспериментах для субоптимального шага приводятся схемы эффективного вычисления аппроксимации наилучшего шага, что позволяет на практике улучшить сходимость метода по сравнению с оригинальным методом трех квадратов. Предложенная схема объединяет в себе несколько существующих и часто используемых на практике модификаций метода Гаусса – Ньютона, в добавок к этому в работе предложена монотонная моментная модификация семейства разработанных методов, не замедляющая поиск решения в худшем случае и демонстрирующая на практике улучшение сходимости метода.

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

Молекулярно-динамические методы, использующие силовое поле ReaxFF, позволяют получать достаточно хорошие результаты при моделировании больших многокомпонентных химически-реактивных систем. Здесь представлены алгоритм поиска оптимальных параметров силового поля ReaxFF для произвольных химических систем, а также его реализация. Метод основан на способе многомерного поиска глобального минимума, предложенном Р. Г. Стронгиным. Алгоритм хорошо масштабируемый и хорошо подходит для работы на параллельных вычислительных кластерах.

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

Курс «Естественные модели параллельных вычислений», читаемый студентам старших курсов факультета ВМК МГУ, посвящен рассмотрению вопросов суперкомпьютерной реализации естественных вычислительных моделей и является, по сути, введением в теорию естественных вычислений (natural computing) относительно нового раздела науки, образовавшегося на стыке математики, информатики и естественных наук (прежде всего биологии). Тематика естественных вычислений включает в себя как классические разделы, например клеточные автоматы, так и относительно новые, появившиеся в последние 10–20 лет, например методы роевого интеллекта. Несмотря на свое биологическое «происхождение», все эти модели находят широчайшее применение в областях, связанных с компьютерной обработкой данных. Исследования в области естественных вычислений также тесно связаны с вопросами и технологиями параллельных вычислений. Изложение теоретического материала курса сопровождается рассмотрением возможных схем распараллеливания вычислений, а в практической части курса предполагается выполнение студентами программной реализации рассматриваемых моделей с использованием технологии MPI и проведение численных экспериментов по исследованию эффективности выбранных схем распараллеливания вычислений.