Все выпуски

Методы оптимизации первого порядка являются важным рабочим инструментов для широкого спектра современных приложений в разных областях, среди которых можно выделить экономику, физику, биологию, машинное обучение и управление. Среди методов первого порядка особого внимания заслуживают ускоренные (моментные) методы в силу их практической эффективности. Метод тяжелого шарика (heavy-ball method — HB) — один из первых ускоренных методов. Данный метод был разработан в 1964 г., и для него был проведен анализ сходимости для квадратичных сильно выпуклых функций. С тех пор были предложены и проанализированы разные варианты HB. В частности, HB известен своей простотой реализации и эффективностью при решении невыпуклых задач. Однако, как и другие моментные методы, он имеет немонотонное поведение; более того, при сходимости HB с оптимальными параметрами наблюдается нежелательное явление, называемое пик-эффектом. Чтобы решить эту проблему, в этой статье мы рассматриваем усредненную версию метода тяжелого шарика (averaged heavy-ball method — AHB). Мы показываем, что для квадратичных задач AHB имеет меньшее максимальное отклонение от решения, чем HB. Кроме того, для общих выпуклых и сильно выпуклых функций доказаны неускоренные скорости глобальной сходимости AHB, его версии WAHB cо взвешенным усреднением, а также для AHB с рестартами R-AHB. Насколько нам известно, такие гарантии для HB с усреднением не были явно доказаны для сильно выпуклых задач в существующих работах. Наконец, мы проводим несколько численных экспериментов для минимизации квадратичных и неквадратичных функций, чтобы продемонстрировать преимущества использования усреднения для HB. Кроме того, мы также протестировали еще одну модификацию AHB, называемую методом tail-averaged heavy-ball (TAHB). В экспериментах мы наблюдали, что HB с правильно настроенной схемой усреднения сходится быстрее, чем HB без усреднения, и имеет меньшие осцилляции.

First-order optimization methods are workhorses in a wide range of modern applications in economics, physics, biology, machine learning, control, and other fields. Among other first-order methods accelerated and momentum ones obtain special attention because of their practical efficiency. The heavy-ball method (HB) is one of the first momentum methods. The method was proposed in 1964 and the first analysis was conducted for quadratic strongly convex functions. Since then a number of variations of HB have been proposed and analyzed. In particular, HB is known for its simplicity in implementation and its performance on nonconvex problems. However, as other momentum methods, it has nonmonotone behavior, and for optimal parameters, the method suffers from the so-called peak effect. To address this issue, in this paper, we consider an averaged version of the heavy-ball method (AHB). We show that for quadratic problems AHB has a smaller maximal deviation from the solution than HB. Moreover, for general convex and strongly convex functions, we prove non-accelerated rates of global convergence of AHB, its weighted version WAHB, and for AHB with restarts R-AHB. To the best of our knowledge, such guarantees for HB with averaging were not explicitly proven for strongly convex problems in the existing works. Finally, we conduct several numerical experiments on minimizing quadratic and nonquadratic functions to demonstrate the advantages of using averaging for HB. Moreover, we also tested one more modification of AHB called the tail-averaged heavy-ball method (TAHB). In the experiments, we observed that HB with a properly adjusted averaging scheme converges faster than HB without averaging and has smaller oscillations.

Предложен алгоритм идентификации параметров плоской вихревой структуры по информации о скорости теченияв конечном (малом) наборе опорных точек. Алгоритм основан на использовании модельной системы точечных вихрей и минимизации в пространстве ее параметров целевого функционала, оценивающего близость модельного и известного наборов векторов скорости. Для численной реализации используются модифицированный метод градиентного спуска с управлением шагом, аппроксимации производных конечными разностями, аналитическое выражение для поля скорости, индуцируемое модельной системой. Проведен численный экспериментальный анализ работы алгоритма на тестовых течениях: одного и системы нескольких точечных вихрей, вихря Рэнкина и диполя Ламба. Используемые дляид ентификации векторы скорости задавались в случайно распределенных наборах опорных точек (от 3 до 200) согласно известным аналитическим выражениям для тестовых полей скорости. В результате вычислений показано: алгоритм сходится к искомому минимуму из широкой области начальных приближений; алгоритм сходится во всех случаях когда опорные точки лежат в областях, где линии тока тестовой и модельной систем топологически эквивалентны; если системы топологически не эквивалентны, то доля удачных расчетов снижается, но сходимость алгоритма также может иметь место; координаты найденных в результате сходимости алгоритма вихрей модельной системы близки к центрам вихрей тестовых конфигураций, а во многих случаях и значения их интенсивностей; сходимость алгоритма в большей степени зависит от расположения, чем от количества используемых при идентификации векторов. Результаты исследования позволяют рекомендовать предложенный алгоритм для анализа плоских вихревых структур, у которых линии тока топологически близки траекториям частиц в поле скорости систем точечных вихрей.

An algorithm is proposed to identify parameters of a 2D vortex structure used on information about the flow velocity at a finite (small) set of reference points. The approach is based on using a set of point vortices as a model system and minimizing a functional that compares the model and known sets of velocity vectors in the space of model parameters. For numerical implementation, the method of gradient descent with step size control, approximation of derivatives by finite differences, and the analytical expression of the velocity field induced by the point vortex model are used. An experimental analysis of the operation of the algorithm on test flows is carried out: one and a system of several point vortices, a Rankine vortex, and a Lamb dipole. According to the velocity fields of test flows, the velocity vectors utilized for identification were arranged in a randomly distributed set of reference points (from 3 to 200 pieces). Using the computations, it was determined that: the algorithm converges to the minimum from a wide range of initial approximations; the algorithm converges in all cases when the reference points are located in areas where the streamlines of the test and model systems are topologically equivalent; if the streamlines of the systems are not topologically equivalent, then the percentage of successful calculations decreases, but convergence can also take place; when the method converges, the coordinates of the vortices of the model system are close to the centers of the vortices of the test configurations, and in many cases, the values of their circulations also; con-vergence depends more on location than on the number of vectors used for identification. The results of the study allow us to recommend the proposed algorithm for identifying 2D vortex structures whose streamlines are topologically close to systems of point vortices.

Статья посвящена моделированию гидродинамических процессов мелководных водоемов на примере Азовского моря. В статье приведена математическая модель гидродинамики мелководного водоема, позволяющая вычислить трехмерные поля вектора скорости движения водной среды. Применение регуляризаторов по Б.Н. Четверушкину в уравнении неразрывности привело к изменению способа расчета поля давления, базирующегося на решении волнового уравнения. Построена дискретная конечно-разностная схема для расчета давления в области, линейные размеры которой по вертикали существенно меньше размеров по горизонтальным координатным направлениям, что является характерным для геометрии мелководных водоемов. Описаны метод и алгоритм решения сеточных уравнений с предобуславливателем трехдиагонального вида. Предложенный метод применен для решения сеточных уравнений, возникающих при расчете давления для трехмерной задачи гидродинамики Азовского моря. Показано, что предложенный метод сходится быстрее модифицированного попеременно-треугольного метода. Представлена параллельная реализация предложенного метода решения сеточных уравнений и проведены теоретические и практические оценки ускорения алгоритма с учетом времени латентности вычислительной системы. Приведены результаты вычислительных экспериментов для решения задач гидродинамики Азовского моря с использованием гибридной технологии MPI + OpenMP. Разработанные модели и алгоритмы применялись для реконструкции произошедшей в 2001 году в Азовском море экологической катастрофы и решения задачи движения водной среды в устьевых районах. Численные эксперименты проводились на гибридном вычислительном кластере К-60 ИПМ им. М.В. Келдыша РАН.

The article is devoted to modeling the shallow water hydrodynamic processes using the example of the Azov Sea. The article presents a mathematical model of the hydrodynamics of a shallow water body, which allows one to calculate three-dimensional fields of the velocity vector of movement of the aquatic environment. Application of regularizers according to B.N.Chetverushkin in the continuity equation led to a change in the method of calculating the pressure field, based on solving the wave equation. A discrete finite-difference scheme has been constructed for calculating pressure in an area whose linear vertical dimensions are significantly smaller than those in horizontal coordinate directions, which is typical for the geometry of shallow water bodies. The method and algorithm for solving grid equations with a tridiagonal preconditioner are described. The proposed method is used to solve grid equations that arise when calculating pressure for the three-dimensional problem of hydrodynamics of the Azov Sea. It is shown that the proposed method converges faster than the modified alternating triangular method. A parallel implementation of the proposed method for solving grid equations is presented and theoretical and practical estimates of the acceleration of the algorithm are carried out taking into account the latency time of the computing system. The results of computational experiments for solving problems of hydrodynamics of the Sea of Azov using the hybrid MPI + OpenMP technology are presented. The developed models and algorithms were used to reconstruct the environmental disaster that occurred in the Sea of Azov in 2001 and to solve the problem of the movement of the aquatic environment in estuary areas. Numerical experiments were carried out on the K-60 hybrid computing cluster of the Keldysh Institute of Applied Mathematics of Russian Academy of Sciences.

Представлена программа NINE (Newtonian Iteration for Nonlinear Equation) численного решения граничных задач для нелинейных дифференциальных уравнений второго порядка на основе непрерывного аналога метода Ньютона (НАМН) с использованием нумеровской конечно-разностной аппроксимации четвертого порядка относительно шага дискретизации по пространственной переменной. Обсуждаются алгоритмы вычисления ньютоновского итерационного параметра. Выполнены методические расчеты, демонстрирующие влияние выбора итерационного параметра на сходимость итерационного процесса. Представлены результаты проведенного с помощью программы NINE численного исследования положительных частицеподобных решений уравнения скалярного поля.

The computer code NINE (Newtonian Iteration for Nonlinear Equation) for numerical solution of the boundary problems for nonlinear differential equations on the basis of continuous analogue of the Newton method (CANM) is presented. Numerov’s finite-difference appproximation is applied to provide the fourth accuracy order with respect to the discretization stepsize. Algorithms of calculating the Newtonian iterative parameter are discussed. A convergence of iteration process in dependence on choice of the iteration parameter has been studied. Results of numerical investigation of the particle-like solutions of the scalar field equation are given.

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

The paper presents a new dense material modeling method based on spherepolyhedra packing algorithm, describes mathematical model of spherepolyhedra and discuss the results of computation experiments on different spherepolyhedra packs. The results of experiments show convergence of proposed method. Experiments include investigations of spherepolyhedra packs with different shapes, polydisperse and oriented structures. Presented method would be applied to virtual design of dense materials composed of non-spherical particles.

В работе рассматриваются интегро-дифференциальные уравнения влагопереноса дробного порядка с оператором Бесселя. Изучаемые уравнения содержат оператор Бесселя, два оператора дробного дифференцирования Герасимова – Капуто с разными порядками $\alpha$ и $\beta$. Рассмотрены два вида интегро-дифференциальных уравнений: в первом случае уравнение содержит нелокальный источник, т.е. интеграл от неизвестной функции по переменной интегрирования $x$, а во втором — случае интеграл по временной переменной $\tau$, обозначающий эффект памяти. Подобные задачи возникают при изучении процессов с предысторией. Для решения дифференциальных задач при различных соотношениях $\alpha$ и $\beta$ получены априорные оценки в дифференциальной форме, откуда следуют единственность и устойчивость решения по правой части и начальным данным. Для приближенного решения поставленных задач построены разностные схемы с порядком аппроксимации $O(h^2+\tau^2)$ при $\alpha=\beta$ и $O(h^2+\tau^{2-\max\{\alpha,\beta\}})$ при $\alpha\neq\beta$. Исследование единственности, устойчивости и сходимости решения проводится с помощью метода энергетических неравенств. Получены априорные оценки решений разностных задач при различных соотношениях $\alpha$ и $\beta$, откуда следуют единственность и устойчивость, а также сходимость решения разностной схемы к решению исходной дифференциальной задачи со скоростью равной порядку аппроксимации разностной схемы.

The paper considers integro-differential equations of fractional order moisture transfer with the Bessel operator. The studied equations contain the Bessel operator, two Gerasimov – Caputo fractional differentiation operators with different orders $\alpha$ and $\beta$. Two types of integro-differential equations are considered: in the first case, the equation contains a non-local source, i.e. the integral of the unknown function over the integration variable $x$, and in the second case, the integral over the time variable τ, denoting the memory effect. Similar problems arise in the study of processes with prehistory. To solve differential problems for different ratios of $\alpha$ and $\beta$, a priori estimates in differential form are obtained, from which the uniqueness and stability of the solution with respect to the right-hand side and initial data follow. For the approximate solution of the problems posed, difference schemes are constructed with the order of approximation $O(h^2+\tau^2)$ for $\alpha=\beta$ and $O(h^2+\tau^{2-\max\{\alpha,\beta\}})$ for $\alpha\neq\beta$. The study of the uniqueness, stability and convergence of the solution is carried out using the method of energy inequalities. A priori estimates for solutions of difference problems are obtained for different ratios of $\alpha$ and $\beta$, from which the uniqueness and stability follow, as well as the convergence of the solution of the difference scheme to the solution of the original differential problem at a rate equal to the order of approximation of the difference scheme.

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

The possibility to simplify the integration of Langevin equation using the variation of correlation between augmentation was researched. The analytical expression for a set of numerical schemes is presented. It’s shown that asymptotic limits for squared velocity depend on step size. The region of convergence and the convergence orders were estimated. It turned out that the incorrect correlation between increments decrease the accuracy down to the level of first-order methods for schemes based on precise solution.

В статье изложены основные положения методики расчета отделения полезной нагрузки (объектов различного назначения с собственным движительным комплексом) от подводного носителя методом самовыхода с использованием современных методов численной гидродинамики (CFD-технологий). Приводится описание метода отделения самовыходом, его достоинства и недостатки. Приводятся результаты исследования сходимости по сетке конечно-объемной модели по критерию «точность–время», а также результаты сопоставления расчета с экспериментом (валидации модели). Валидация модели проводилась по имеющимся данным экспериментального определения тяговых характеристик водометного движительного комплекса натурного образца в опытовом бассейне. Расчеты тяговых характеристик водометного движительного комплекса проводились с применением программного комплекса FlowVision версии 3.10. На основании сопоставления результатов расчетов для условий проведения экспериментов была определена погрешность расчетной модели водометного движительного комплекса, которая составила не более 5 % в диапазоне поступей работы водометного движительного комплекса, реализуемых в процессе отделения методом самовыхода. Полученное значение погрешности расчета тяговых характеристик используется для определения предельных расчетных значений скорости отделения объекта от носителя (минимальные и максимальные значения). Рассмотренная задача является значимой с научной точки зрения благодаря особенностям подхода к моделированию водометного движительного комплекса совместно с движением отделяемого объекта, а также с практической точки зрения благодаря возможности получения с высокой степенью достоверности параметров отделения объектов от подводных аппаратов методом самовыхода, условия работы которых предполагают движение в замкнутых объемах, уже на стадии проектирования.

The article describes the basic approaches of the calculation procedure of payload swim-out (objects of different function with own propulsor) from the underwater carrier a method of a self-exit using modern CFD technologies. It contains the description of swim-out by a self-exit method, its advantages and disadvantages. Also it contains results of research of convergence on a grid of a final-volume model with accuracy-time criterion, and results of comparison of calculation with experiment (validation of models). Validation of models was carried out using the available data of experimental definition of traction characteristics of water-jet propulsor of the natural sample in the development pool. Calculations of traction characteristics of water-jet propulsor were carried out via software package FlowVision ver. 3.10. On the basis of comparison of results of calculations for conditions of carrying out of experiments the error of water-jet propulsor calculated model which has made no more than 5% in a range of advance coefficient water-jet propulsor, realised in the process of swim-out by a selfexit method has been defined. The received value of an error of calculation of traction characteristics is used for definition of limiting settlement values of speed of branch of object from the carrier (the minimum and maximum values). The considered problem is significant from the scientific point of view thanks to features of the approach to modelling hydrojet moving system together with movement of separated object, and also from the practical point of view, thanks to possibility of reception with high degree of reliability of parametres swim-out of objects from sea bed vehicles a method of the self-exit which working conditions are assumed by movement in the closed volumes, already on a design stage.

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

In this paper, we develop a new first-order method for composite nonconvex minimization problems with simple constraints and inexact oracle. The objective function is given as a sum of «hard», possibly nonconvex part, and «simple» convex part. Informally speaking, oracle inexactness means that, for the «hard» part, at any point we can approximately calculate the value of the function and construct a quadratic function, which approximately bounds this function from above. We give several examples of such inexactness: smooth nonconvex functions with inexact H¨older-continuous gradient, functions given by the auxiliary uniformly concave maximization problem, which can be solved only approximately. For the introduced class of problems, we propose a gradient-type method, which allows one to use a different proximal setup to adapt to the geometry of the feasible set, adaptively chooses controlled oracle error, allows for inexact proximal mapping. We provide a convergence rate for our method in terms of the norm of generalized gradient mapping and show that, in the case of an inexact Hölder-continuous gradient, our method is universal with respect to Hölder parameters of the problem. Finally, in a particular case, we show that the small value of the norm of generalized gradient mapping at a point means that a necessary condition of local minimum approximately holds at that point.

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

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

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

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

The paper contains numerical simulation of nonisothermal nonlinear flow in a porous medium. Twodimensional unsteady problem of heavy oil, water and steam flow is considered. Oil phase consists of two pseudocomponents: light and heavy fractions, which like the water component, can vaporize. Oil exhibits viscoplastic rheology, its filtration does not obey Darcy's classical linear law. Simulation considers not only the dependence of fluids density and viscosity on temperature, but also improvement of oil rheological properties with temperature increasing.

To solve this problem numerically we use streamline method with splitting by physical processes, which consists in separating the convective heat transfer directed along filtration from thermal conductivity and gravitation. The article proposes a new approach to streamline methods application, which allows correctly simulate nonlinear flow problems with temperature-dependent rheology. The core of this algorithm is to consider the integration process as a set of quasi-equilibrium states that are results of solving system on a global grid. Between these states system solved on a streamline grid. Usage of the streamline method allows not only to accelerate calculations, but also to obtain a physically reliable solution, since integration takes place on a grid that coincides with the fluid flow direction.

In addition to the streamline method, the paper presents an algorithm for nonsmooth coefficients accounting, which arise during simulation of viscoplastic oil flow. Applying this algorithm allows keeping sufficiently large time steps and does not change the physical structure of the solution.

Obtained results are compared with known analytical solutions, as well as with the results of commercial package simulation. The analysis of convergence tests on the number of streamlines, as well as on different streamlines grids, justifies the applicability of the proposed algorithm. In addition, the reduction of calculation time in comparison with traditional methods demonstrates practical significance of the approach.