Все выпуски

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

The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a variety of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are usually used to solve such problems. We propose to use the ellipsoid method with mini-batching, which converges linearly and can be more efficient than SGD for a class of problems. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of the objective to achieve linear convergence. Thus, its complexity does not depend on the conditional number of the problem. We prove that the method arrives at an approximate solution with given probability when using mini-batches of size proportional to the desired accuracy to the power −2. This enables efficient parallel execution of the algorithm, whereas possibilities for batch parallelization of SGD are rather limited. Despite fast convergence, ellipsoid method can result in a greater total number of calls to oracle than SGD, which works decently with small batches. Complexity is quadratic in dimension of the problem, hence the method is suitable for relatively small dimensionalities.

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

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

Gradient-free optimization methods or zeroth-order methods are widely used in training neural networks, reinforcement learning, as well as in industrial tasks where only the values of a function at a point are available (working with non-analytical functions). In particular, the method of error back propagation in PyTorch works exactly on this principle. There is a well-known fact that computer calculations use heuristics of floating-point numbers, and because of this, the problem of finiteness of the mantissa arises.

In this paper, firstly, we reviewed the most popular methods of gradient approximation: Finite forward/central difference (FFD/FCD), Forward/Central wise component (FWC/CWC), Forward/Central randomization on $l_2$ sphere (FSSG2/CFFG2); secondly, we described current theoretical representations of the noise introduced by the inaccuracy of calculating the function at a point: adversarial noise, random noise; thirdly, we conducted a series of experiments on frequently encountered classes of problems, such as quadratic problem, logistic regression, SVM, to try to determine whether the real nature of machine noise corresponds to the existing theory. It turned out that in reality (at least for those classes of problems that were considered in this paper), machine noise turned out to be something between adversarial noise and random, and therefore the current theory about the influence of the mantissa limb on the search for the optimum in gradient-free optimization problems requires some adjustment.

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

The paper deals with a heat wave motion problem for a degenerate second-order nonlinear parabolic equation with power nonlinearity. The considered boundary condition specifies in a plane the motion equation of the circular zero front of the heat wave. A new numerical-analytical algorithm for solving the problem is proposed. A solution is constructed stepby- step in time using difference time discretization. At each time step, a boundary value problem for the Poisson equation corresponding to the original equation at a fixed time is considered. This problem is, in fact, an inverse Cauchy problem in the domain whose initial boundary is free of boundary conditions and two boundary conditions (Neumann and Dirichlet) are specified on a current boundary (heat wave). A solution of this problem is constructed as the sum of a particular solution to the nonhomogeneous Poisson equation and a solution to the corresponding Laplace equation satisfying the boundary conditions. Since the inhomogeneity depends on the desired function and its derivatives, an iterative solution procedure is used. The particular solution is sought by the collocation method using inhomogeneity expansion in radial basis functions. The inverse Cauchy problem for the Laplace equation is solved by the null field method as applied to a circular domain with a circular hole. This method is used for the first time to solve such problem. The calculation algorithm is optimized by parallelizing the computations. The parallelization of the computations allows us to realize effectively the algorithm on high performance computing servers. The algorithm is implemented as a program, which is parallelized by using the OpenMP standard for the C++ language, suitable for calculations with parallel cycles. The effectiveness of the algorithm and the robustness of the program are tested by the comparison of the calculation results with the known exact solution as well as with the numerical solution obtained earlier by the authors with the use of the boundary element method. The implemented computational experiment shows good convergence of the iteration processes and higher calculation accuracy of the proposed new algorithm than of the previously developed one. The solution analysis allows us to select the radial basis functions which are most suitable for the proposed algorithm.

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

The work investigates the search for inefficient edges in the model of stable dynamics by Nestrov – de Palma (2003). For this purpose, we prove several general theorems about equilibrium properties, including the condition of equal costs for all used routes that can be extended to all paths involving edges from equilibrium routes. The study demonstrates that the standard problem formulation of finding edges whose removal reduces the cost of travel for all participants has no practical significance because the same edge can be both efficient and inefficient depending on the network’s load. In the work, we introduce the concept of an inefficient edge based on the sensitivity of total driver costs to the costs on the edge. The paper provides an algorithm for finding inefficient edges and presents the results of numerical experiments for the transportation network of the city of Anaheim.

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

In this work, we use analytical and numerical methods to consider the problem of the structure and dynamics of coupled localized nonlinear waves in the sine-Gordon model with three identical attractive extended “impurities”, which are modeled by spatial inhomogeneity of the periodic potential. Two possible types of coupled nonlinear localized waves are found: breather and soliton. The influence of system parameters and initial conditions on the structure, amplitude, and frequency of localized waves was analyzed. Associated oscillations of localized waves of the breather type as in the case of point impurities, are the sum of three harmonic oscillations: in-phase, in-phase-antiphase and antiphase type. Frequency analysis of impurity-localized waves that were obtained during a numerical experiment was performed using discrete Fourier transform. To analyze localized breather-type waves, the numerical finite difference method was used. To carry out a qualitative analysis of the obtained numerical results, the problem was solved analytically for the case of small amplitudes of oscillations localized on impurities. It is shown that, for certain impurity parameters (depth and width), it is possible to obtain localized solitontype waves. The ranges of values of the system parameters in which localized waves of a certain type exist, as well as the region of transition from breather to soliton types of oscillations, have been found. The values of the depth and width of the impurity at which a transition from the breather to the soliton type of localized oscillations is observed were determined. Various scenarios of soliton-type oscillations with negative and positive amplitude values for all three impurities, as well as mixed cases, were obtained and considered. It is shown that in the case when the distance between impurities much less than one, there is no transition region where which the nascent breather, after losing energy through radiation, transforms into a soliton. It is shown that the considered model can be used, for example, to describe the dynamics of magnetization waves in multilayer magnets.

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

The article presents an analytical-numerical method to simulate $p$-dimentional heat transfer processes on complex geometry domains when conventional methods are not applicable. The model is converted by the proposed method so that conventional numerical analysis methods is applied to the numerical research. The results of numerical experiments are given to demonstrate the effectiveness of the proposed method. The obtained results, other authors’ numerical results and exact analytical solutions, known for a class of problems, is compared.

Целью данной работы является обобщение макроскопических гидродинамических моделей второго порядка, описывающих автомобильное движение, с помощью алгоритма построения адекватного реальным измерениям уравнения состояния — зависимости давления от плотности транспортного потока, получаемого эмпирическим образом для каждого отдельного участка транспортной сети с использованием данных транспортных детекторов. Доказано, что именно вид уравнения состояния, замыкающего систему модельных уравнений и полученного из экспериментально наблюдаемого вида фундаментальной диаграммы — зависимости интенсивности транспортного потока от его плотности, полностью определяет все свойства любой феноменологической модели. Проверка работоспособности предложенного подхода проводилась с использованием численных расчетов, путем проведения вычисленных экспериментов на типичных данных, предоставляемых системой PeMS (http://pems.dot.ca.gov/), таких как моделирование движения трафика на заданном участке транспортной сети автострады I-580 в Калифорнии.

The goal of this work is to generalize second order mathematical models for automotive flow using algorithm for building state equation — the dependency of pressure on traffic density — which is adequate with regard to real world data. The form of state equation, which closes the system of model equations, is obtained from experimental form of fundamental diagram — the dependency of traffic flow intensity on its density, and completely defines all properties of any phenomenological model. The proposed approach was verified using numerical experiments on typical traffic data, obtained from PeMS system (http://pems.dot.ca.gov/), using segment of I-507 highway in California, USA as model system.

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

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

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

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

The results of verification carried out for investigations of hydrodynamic effect on reentry conicalsegmental space vehicle are presented in the paper. The program complex Flow Vision is used for this analysis. The purpose of the study is verification of using Flow Vision program complex for problem solving mentioned above on the base of comparison between calculated and experimental data, obtained on the Apollo landing models and new development reentry spacecraft of manned transporting spaceship designed by RSC Energia. The comparison was carried out through the data of pressure values on spacecraft model surfaces during its water landing and inertia center motion parameters.

The results of study show good agreement between experimental and calculated data of force effects on vehicle construction during water landing and its motion parameters in the water medium. Computer simulation sufficiently well reproduces influence of initial velocities & water entry angles variations on water landing process.

Using of computer simulation provides simultaneous acquisition of all data information needed for investigation of water landing peculiarities during construction design, notably, hydrodynamic effects for structural strength calculations, parameters and dynamics of center mass motion and vehicle revolution around center mass for estimation water landing conditions, as well as vehicle stability after landing.

Obtained results confirm suitability of using Flow Vision program complex for water landing vehicle investigations and investigations of influence of different landing regimes through wide initial condition change range, that permits considerably decrease extent of expensive experimental tests and realize landing conditions which are sufficiently complicated for realizing in model physical experiments.

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

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

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

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

In the last decades, the development of methods for increasing the efficiency of hydrocarbon extraction in fields with unconventional reserves containing large amounts of gas condensate is of great importance. This makes important the development of methods of mathematical modeling that realistically describe physical processes in a gas-condensate mixture in a porous medium.

In the paper, a mathematical model which describes the dynamics of the pressure, velocity and concentration of the components of a two-component two-phase mixture entering a laboratory model of plast filled with a porous substance with known physicochemical properties is considered. The mathematical model is based on a system of nonlinear spatially one-dimensional partial differential equations with the corresponding initial and boundary conditions. Laboratory experiments show that during a finite time the system stabilizes, what gives a basis to proceed to the stationary formulation of the problem.

The numerical solution of the formulated system of ordinary differential equations is realized in the Maple environment on the basis of the Runge–Kutta procedure. It is shown that the physical parameters of the gascondensate mixture, which characterize the modeled system in the stabilization regime, obtained on this basis, are in good agreement with the available experimental data. This confirms the correctness of the chosen approach and the validity of its further application and development for computer modeling of physical processes in gas-condensate mixtures in a porous medium. The paper presents a mathematical formulation of the system of partial differential equations and of respective system stationary equations, describes the numerical approach, and discusses the numerical results obtained in comparison with experimental data.

В настоящей работе предложен вариант импорта в систему ANSYS Mechanical APDL модели поведения гибких тканых композиционных материалов с армирующей тканью полотняного переплетения при статическом растяжении вдоль нитей армирования. Импорт осуществлен при помощи использования, разработанного авторами и представленного в текущей работе модуля интеграции, основанного на использовании аналитической модели деформирования исследуемого материала, представленной в опубликованных ранее статьях и учитывающей изменения геометрической структуры, происходящие в армирующем слое материала в процессе деформирования, образование необратимых деформаций и взаимодействие накрест лежащих нитей армирующей ткани. Во введении кратко описаны основные вводимые характеристики полотняного переплетения армирующей ткани и аналитической модели, импортируемой в ANSYS. Аналитическая модель основана на описании процессов деформирования элементарной периодической ячейки исследуемого класса материалов. Входными параметрами модуля являются механические характеристики материалов, входящих в состав композита (связующее и материал нитей армирования), геометрические характеристики переплетения армирующей ткани. Алгоритм импорта модели основан на вычислении и передачи в ANSYS расчетных точек диаграммы деформирования материала при одноосном растяжения вдоль направления армирования и использовании вложенных в систему ANSYS пользовательской моделей материала Multilinear Kinematich Hardening. Аналитическая модель, импортируемая при помощи представленного модуля, позволяет моделировать композиционный материал с армирующей тканью без детального описания геометрии переплетения нитей при моделировании материала в целом. Выполнена верификация импортированной модели. Для верификации были проведены натурные экспериментальные исследования и численное моделирование растяжения образцов из гибких тканых композитов. В экспериментах принимали участие образцы трех марок: VP4126, VP6131 и VP6545. Погрешность импортированной в ANSYS модели составила менее 10 % относительно экспериментальных исследований для всех марок материала. Анализ полученных результатов показал хорошее качественное и количественное согласование расчетов в системе ANSYS с применением импортированной модели и натурных испытаний до величин предельных деформаций, соответствующих разрушению образцов материала для всех исследуемых марок гибких тканых композитов, что позволяет сделать вывод о возможности применения предложенного модуля при моделировании процессов деформирования гибких тканых композитов и конструкций, созданных из таких материалов при статическом одноосном растяжении вдоль нитей армирования.

A variant of import into ANSYS Mechanical APDL system of the model of behavior of flexible woven composite materials with reinforcing weaving cloth of linen at static stretching along the reinforcement yarns is offered. The import was carried out using an integration module based on the use of an analytical model of deformation of the material under study. The model is presented in the articles published earlier and takes into account the changes in the geometric structure occurring in the reinforcing layer of the material during the deformation process, the formation of irreversible deformations and the interaction of cross-lying reinforcing fabric threads. In the introduction input characteristics of the plain weave of the reinforcing fabric and the analytical model imported into ANSYS are briefly described. The input parameters of the module are the mechanical characteristics of the materials that make up the composite (binder and material of reinforcement yarns), the geometric characteristics of the interlacing of the reinforcing fabric. The algorithm for importing the model is based on the calculation and transfer in ANSYS of the calculated points of the material stress-strain diagram for uniaxial stretching along the reinforcement direction and using the Multilinear Kinematich Hardening model material embedded in the ANSYS. The analytical model imported with the help of the presented module allows to model a composite material with reinforcing fabric without a detailed description of the geometry of the interlacing of threads during modeling of the material as a whole. The imported model was verified. For verification full-scale experimental studies and numerical simulation of the stretching of samples from flexible woven composites were carried out. The analysis of the obtained results showed good qualitative and quantitative agreement of calculations.