Все выпуски

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

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

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

$$ \text{Argmin}_{x\in X}{\langle p,\,x \rangle} $$

для заданного вектора $p \in \mathbb{R}^n$. Существует целый ряд методов условного градиента, имеющих линейную скорость сходимости в сильно выпуклом случае. Однако во всех этих методах в оценку скорости сходимости входит размерность задачи, которая в современных приложениях может быть очень большой. В данной работе доказывается, что в сильно выпуклом случае скорость сходимости методов условного градиента в лучшем случае зависит от размерности задачи $n$ как $\widetilde{\Omega}\left(\!\sqrt{n}\right)$. Таким образом, методы условного градиента могут оказаться неэффективными для решения сильно выпуклых оптимизационных задач больших размерностей.

Отдельно рассматривается приложение методов условного градиента к задачам минимизации квадратичной формы. Уже была доказана эффективность метода Франк – Вульфа для решения задачи квадратичной оптимизации в выпуклом случае на симплексе (PageRank). Данная работа показывает, что использование методов условного градиента для минимизации квадратичной формы в сильно выпуклом случае малоэффективно из-за наличия размерности в оценке скорости сходимости этих методов. Поэтому рассматривается метод рестартов условного градиента (Shrinking Conditional Gradient). Его отличие от методов условного градиента заключается в том, что в нем используется модифицированный линейный минимизационный оракул, который для заданного вектора $p \in \mathbb{R}^n$ вычисляет решение задачи $$ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. $$ В оценку скорости сходимости такого алгоритма размерность уже не входит. С помощью рестартов метода условного градиента получена сложность (число арифметических операций) минимизации квадратичной формы на $\infty$-шаре. Полученная оценка работы метода сравнима со сложностью градиентного метода.

Модели многозначной классификации возникают в различных сферах современной жизни, что объясняется всё большим количеством информации, требующей оперативного анализа. Одним из математических методов решения этой задачи является модульный метод, на первом этапе которого для каждого класса строится некоторая ранжирующая функция, упорядочивающая некоторым образом все объекты, а на втором этапе для каждого класса выбирается оптимальное значение порога, объекты с одной стороны которого относят к текущему классу, а с другой — нет. Пороги подбираются так, чтобы максимизировать целевую метрику качества. Алгоритмы, свойства которых изучаются в настоящей статье, посвящены второму этапу модульного подхода — выбору оптимального вектора порогов. Этот этап становится нетривиальным в случае использования в качестве целевой метрики качества $F$-меры от средней точности и полноты, так как она не допускает независимую оптимизацию порога в каждом классе. В задачах экстремальной многозначной классификации число классов может достигать сотен тысяч, поэтому исходная оптимизационная задача сводится к задаче поиска неподвижной точки специальным образом введенного отображения $\boldsymbol V$, определенного на единичном квадрате на плоскости средней точности $P$ и полноты $R$. Используя это отображение, для оптимизации предлагаются два алгоритма: метод линеаризации $F$-меры и метод анализа области определения отображения $\boldsymbol V$. На наборах данных многозначной классификации разного размера и природы исследуются свойства алгоритмов, в частности зависимость погрешности от числа классов, от параметра $F$-меры и от внутренних параметров методов. Обнаружена особенность работы обоих алгоритмов для задач с областью определения отображения $\boldsymbol V$, содержащей протяженные линейные участки границ. В случае когда оптимальная точка расположена в окрестности этих участков, погрешности обоих методов не уменьшаются с увеличением количества классов. При этом метод линеаризации достаточно точно определяет аргумент оптимальной точки, а метод анализа области определения отображения $\boldsymbol V$ — полярный радиус.

При моделировании методами классической молекулярной динамики поведения системы частиц используются уравнения движения в ньютоновской и гамильтоновой формулировке. При использовании уравнений Ньютона для получения координат и скоростей частиц системы, состоящей из $N$ частиц, требуется на каждом временном шаге в трехмерном случае решить $3N$ обыкновенных дифференциальных уравнений второго порядка. Традиционно для решения уравнений движения молекулярной динамики в ньютоновской формулировке используются численные схемы метода Верле. Для сохранения устойчивости численных схем Верле на достаточно больших интервалах времени приходится уменьшать шаг интегрирования. Это приводит к существенному увеличению объема вычислений. В большинстве современных пакетов программ молекулярной динамики для численного интегрирования уравнений движения используют схемы метода Верле с контролем сохранения гамильтониана (энергии системы) по времени. Для уменьшения времени вычислений при молекулярно-динамических расчетах можно использовать два дополняющих друг друга подхода. Первый основан на совершенствовании и программной оптимизации существующих пакетов программ молекулярной динамики с использованием векторизации, распараллеливания, спецпроцессоров. Второй подход основан на разработке эффективных методов численного интегрирования уравнений движения. В работе предложена процедура построения явных, неявных и симметричных симплектических численных схем с заданной точностью аппроксимации относительно шага интегрирования для решения уравнений движения молекулярной динамики в гамильтоновой форме. В основе подхода для построения предложенной в работе процедуры лежат следующие положения: гамильтонова формулировка уравнений движения, использование разложения точного решения в ряд Тейлора, использование для вывода численных схем аппарата производящих функций для сохранения геометрических свойств точного решения. Численные эксперименты показали, что полученная в работе симметричная симплектическая схема третьего порядка точности сохраняет в приближенном решении основные свойства точного решения, является более устойчивой по шагу аппроксимации и более точно сохраняет гамильтониан системы на большом интервале интегрирования, чем численные схемы метода Верле второго порядка.

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

В данной работе этот алгоритм лежит в основе решения следующих задач.

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

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

Задача 3. Построение непрерывного аналога задачи минимизации вещественного квадратичного многочлена от булевых переменных и новой формы задания необходимых и достаточных условий оптимальности для разработки методов их решения за полиномиальное время. В результате исходная задача сводится к задаче поиска минимального расстояния между началом координат и угловой точкой выпуклого многогранника (полиэдра), который является возмущением $n$-мерного куба и описывается системой двойных линейных неравенств с верхней треугольной матрицей коэффициентов с единицами на главной диагонали. Исследованию подлежат только две грани, одна из которых или обе содержат вершины, ближайшие к началу координат. Для их вычисления достаточно решить $4n – 4$ систем линейных уравнений и выбрать среди них все ближайшие равноудаленные вершины за полиномиальное время. Задача минимизации квадратичного полинома является $NP$-трудной, поскольку к ней сводится $NP$-трудная задача о вершинном покрытии для произвольного графа. Отсюда следует вывод, что $P = NP$, в основе построения которого лежит выход за пределы целочисленных методов оптимизации.

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

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

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

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

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

Работа посвящена исследованию возможности повышения эффективности решения задач внешней аэродинамики. Изучаются методические аспекты применения локально-адаптивных неструктурированных расчетных сеток и пристеночных функций для численного моделирования турбулентных течений около летательных аппаратов. Интегрируются осредненные по Рейнольдсу уравнения Навье–Стокса, которые замыкаются стандартной моделью турбулентности $k–\varepsilon$. Рассматривается обтекание крылового профиля RAE 2822 турбулентным дозвуковым потоком вязкого сжимаемого газа. Расчеты проводятся в программном ВГД-комплексе FlowVision. Анализируется эффективность применения технологии сглаживания диффузионных потоков и формулы Брэдшоу для турбулентной вязкости в качестве мер, повышающих точность решения аэродинамических задач на локально-адаптивных сетках. Результаты исследования показывают, что использование технологии сглаживания диффузионных потоков приводит к существенному уменьшению расхождений в величине коэффициента лобового сопротивления между результатами расчетов и экспериментальными данными. Кроме того, обеспечивается регуляризация распределения коэффициента поверхностного трения на криволинейной поверхности профиля. Эти результаты позволяют сделать вывод о том, что данная технология является эффективным способом повышения точности расчетов на локально-адаптивных сетках. Формула Брэдшоу для динамического коэффициента турбулентной вязкости традиционно используется в модели SST $k–\omega$. В настоящей работе исследуется возможность ее применения в стандартной $k–\varepsilon$-модели турбулентности. Результаты расчетов показывают, что, с одной стороны, данная формула обеспечивает хорошее согласование суммарных аэродинамических характеристик и распределения коэффициента давления по поверхности профиля с экспериментом. Помимо этого, она значительно повышает точность моделирования течения в пограничном слое и в следе. С другой стороны, использование формулы Брэдшоу при моделировании обтекания профиля RAE 2822 приводит к занижению коэффициента поверхностного трения. Поэтому в работе делается вывод о том, что практическое применение формулы Брэдшоу требует ее предварительной валидации и калибровки на надежных экспериментальных данных для рассматриваемого класса задач. Результаты работы в целом показывают, что при использовании рассмотренных технологий численное решение задач внешнего обтекания на локально-адаптивных сетках с применением пристеночных функций обеспечивает точность, приемлемую для оперативной оценки аэродинамических характеристик, а ПК FlowVision является эффективным инструментом решения задач предварительного аэродинамического проектирования, концептуального проектирования и оптимизации аэродинамических форм.

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