All issues

В работе рассматриваются интегро-дифференциальные уравнения влагопереноса дробного порядка с оператором Бесселя. Изучаемые уравнения содержат оператор Бесселя, два оператора дробного дифференцирования Герасимова – Капуто с разными порядками $\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.

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

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

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

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

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

This paper analyzes some issues in developing numerical methods for solving problems with a Boltzmann-type linear kinetic transport equation. Existing applications of this type of equation are listed. The focus is on the problem of radiative transfer in a flat layer, which are important for experimental research practice. Key definitions and traditional limitations applied to radiative transfer problems are presented. Some features of formulating radiative transfer problems for flat layers of irregular heterogeneous composite materials that are partially transparent to electromagnetic radiation are considered. The main approaches to the numerical and numerical-analytical solution of the linear kinetic transport equation are outlined.

Some variants of the simplest grid numerical methods for solving of nonstationary kinetic problems of transport a flat layer of a medium with strong attenuation are considered. Problems with one- and two-step variants of these iterative methods are analyzed, for some of them the causes of instability and convergence absence in some of them are investigated and established. It is shown that in the explicit conservative one-step method for a layer of a homogeneous absorbing, but neither radiating nor scattering, medium, unstable modes always exist in the spectrum of harmonic solutions. These modes arise in the region of radiation propagating almost parallel to the layer boundaries, and their instability increases with increasing attenuation effects and is caused by the presence of a small coefficient before the spatial derivative in the transport equation. To limit the undesirable influence of this component, various variants of splitting the equation into two and three fractional steps are considered.

It is shown that the most preferable options are those with explicitly organized fractional steps, for which a proof of their stability and convergence, that based on the Lax’s equivalence theorem is presented. It is demonstrated that the correct building of the fractional step sequence in explicit schemes for numerical solving of the nonstationary linear kinetic transport problems can provide additional stabilization, with the scattering integral plays an important role in stabilizing them. So, when solving kinetic transport problems in media with high scattering albedo, the explicit grid method of settling with splitting the iterations into three fractional steps, that were based on physical processes proved to be the simplest and most effective. The method is implemented as Matlab code, which performs quality control during the generation of the numerical solution process. The most significant modeling results are presented, confirming that the three-step method imposes relatively moderate requirements on resources and numerical integration accuracy, and ensures conditional convergence of iterations. Its mathematical correctness is confirmed by the behavior of the equation residuals and direct control of the convergence of numerical solutions. Its physical correctness is confirmed by ensuring, for ergodic systems, the property of convergence to an invariant steady state independent of the initial conditions. Some discovered and possible limitations of the method are listed.

The work will be useful to specialists in the field of mathematical modeling, numerical methods, kinetic theory, combined heat and mass transfer, dealing with issues of interpretation of experimental data, graduate students and senior students specializing in the indicated areas.

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

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.

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

In this paper, we consider two variants of the concept of sharp minimum for mathematical programming problems with quasiconvex objective function and inequality constraints. It investigated the problem of describing a variant of a simple subgradient method with switching along productive and non-productive steps, for which, on a class of problems with Lipschitz functions, it would be possible to guarantee convergence with the rate of geometric progression to the set of exact solutions or its vicinity. It is important that to implement the proposed method there is no need to know the sharp minimum parameter, which is usually difficult to estimate in practice. To overcome this problem, the authors propose to use a step adjustment procedure similar to that previously proposed by B. T. Polyak. However, in this case, in comparison with the class of problems without constraints, it arises the problem of knowing the exact minimal value of the objective function. The paper describes the conditions for the inexactness of this information, which make it possible to preserve convergence with the rate of geometric progression in the vicinity of the set of minimum points of the problem. Two analogs of the concept of a sharp minimum for problems with inequality constraints are considered. In the first one, the problem of approximation to the exact solution arises only to a pre-selected level of accuracy, for this, it is considered the case when the minimal value of the objective function is unknown; instead, it is given some approximation of this value. We describe conditions on the inexact minimal value of the objective function, under which convergence to the vicinity of the desired set of points with a rate of geometric progression is still preserved. The second considered variant of the sharp minimum does not depend on the desired accuracy of the problem. For this, we propose a slightly different way of checking whether the step is productive, which allows us to guarantee the convergence of the method to the exact solution with the rate of geometric progression in the case of exact information. Convergence estimates are proved under conditions of weak convexity of the constraints and some restrictions on the choice of the initial point, and a corollary is formulated for the convex case when the need for an additional assumption on the choice of the initial point disappears. For both approaches, it has been proven that the distance from the current point to the set of solutions decreases with increasing number of iterations. This, in particular, makes it possible to limit the requirements for the properties of the used functions (Lipschitz-continuous, sharp minimum) only for a bounded set. Some computational experiments are performed, including for the truss topology design problem.

В настоящей работе исследован турбулентный поток Тейлора – Куэтта с помощью двухмерного моделирования на базе осредненных уравнений Навье – Стокса (RANS) и нового двухжидкостного подхода к турбулентности при числах Рейнольдса в диапазоне от 1000 до 8000. Исследуется течение, обусловленное вращающимся внутренним и неподвижным внешним цилиндрами. Рассмотрен случай соотношения диаметров цилиндров 1:2. Известно, что возникающее круговое течение характеризуется анизотропной турбулентностью и математическое моделирование таких потоков является сложной задачей. Для описания таких потоков используются либо методы прямого моделирования, которые требуют больших вычислительных затрат, либо достаточно трудоемкие методы рейнольдсовых напряжений или же линейные RANS-модели со специальными поправками на вращение, которые способны описывать анизотропную турбулентность. В работе для сравнения различных подходов к моделированию турбулентности представлены численные результаты линейных RANS-моделей SARC, SST-RC, метода рейнольдсовых напряжений SSG/LRR-RSM-w2012, прямого моделирования турбулентности DNS, а также новой двухжидкостной модели. Показано, что недавно разработанная двухжидкостная модель адекватно описывает рассматриваемый поток. Помимо этого, двухжидкостная модель проста для численной реализации и имеет хорошую сходимость.

In this paper, the turbulent Taylor – Couette flow is investigated using two-dimensional modeling based on the averaged Navier – Stokes (RANS) equations and a new two-fluid approach to turbulence at Reynolds numbers in the range from 1000 to 8000. The flow due to a rotating internal and stationary external cylinders. The case of ratio of cylinder diameters 1:2 is considered. It is known that the emerging circular flow is characterized by anisotropic turbulence and mathematical modeling of such flows is a difficult task. To describe such flows, either direct modeling methods are used, which require large computational costs, or rather laborious Reynolds stress methods, or linear RANS models with special corrections for rotation, which are able to describe anisotropic turbulence. In order to compare different approaches to turbulence modeling, the paper presents the numerical results of linear RANS models SARC, SST-RC, Reynolds stress method SSG/LRR-RSM-w2012, DNS direct turbulence modeling, as well as a new two-fluid model. It is shown that the recently developed twofluid model adequately describes the considered flow. In addition, the two-fluid model is easy to implement numerically and has good convergence.

Задача поиска PageRank вектора представляет большой научный и практический интерес ввиду своей применимости к работе современных поисковых систем. Несмотря на то, что данная задача сводится к поиску собственного вектора стохастической матрицы $P$, потребность в новых алгоритмах для ее решения обусловлена большими размерами входных данных. Для достижения не более чем линейного времени работы применяются различные рандомизированные методы, возвращающие ожидаемый ответ лишь с некоторой достаточно близкой к единице вероятностью. Нами рассматриваются два таких способа, сводящие задачу поиска вектора PageRank к задаче поиска равновесия в антагонистической матричной игре, которая затем решается с помощью алгоритма Григориадиса – Хачияна. При этом данная реализация эффективно работает в предположении о разреженности матрицы, подаваемой на вход. Насколько нам известно, до сих пор не было ни одной успешной реализации ни алгоритма Григориадиса – Хачияна, ни его применения к задаче поиска вектора PageRank. Данная статья ставит перед собой задачу восполнить этот пробел. В работе приводится описание двух версий алгоритма с псевдокодом и некоторые детали их реализации. Кроме того, в работе рассматривается другой вероятностный метод поиска вектора PageRank, а именно Markov chain Monte Carlo (MCMC), с целью сравнения результатов работы указанных алгоритмов на матрицах с различными значениями спектральной щели. Последнее представляет особый интерес, поскольку значение спектральной щели сильно влияет на скорость сходимости MCMC, и не оказывает никакого влияния на два других подхода. Сравнение проводилось на сгенерированных графах двух видов: цепочках и $d$-мерных кубах. Проведенные эксперименты, как и предсказывает теория, демонстрируют эффективность алгоритма Григориадиса – Хачияна по сравнению с MCMC для разреженных графов с маленьким значением спектральной щели. Весь код находится в открытом доступе, так чтобы все желающие могли воспроизвести полученные результаты самостоятельно, или же использовать данную реализацию в своих нуждах. Работа имеет чисто практическую направленность, никаких теоретических результатов авторами получено не было.

Finding PageRank vector is of great scientific and practical interest due to its applicability to modern search engines. Despite the fact that this problem is reduced to finding the eigenvector of the stochastic matrix $P$, the need for new algorithms is justified by a large size of the input data. To achieve no more than linear execution time, various randomized methods have been proposed, returning the expected result only with some probability close enough to one. We will consider two of them by reducing the problem of calculating the PageRank vector to the problem of finding equilibrium in an antagonistic matrix game, which is then solved using the Grigoriadis – Khachiyan algorithm. This implementation works effectively under the assumption of sparsity of the input matrix. As far as we know, there are no successful implementations of neither the Grigoriadis – Khachiyan algorithm nor its application to the task of calculating the PageRank vector. The purpose of this paper is to fill this gap. The article describes an algorithm giving pseudocode and some details of the implementation. In addition, it discusses another randomized method of calculating the PageRank vector, namely, Markov chain Monte Carlo (MCMC), in order to compare the results of these algorithms on matrices with different values of the spectral gap. The latter is of particular interest, since the magnitude of the spectral gap strongly affects the convergence rate of MCMC and does not affect the other two approaches at all. The comparison was carried out on two types of generated graphs: chains and $d$-dimensional cubes. The experiments, as predicted by the theory, demonstrated the effectiveness of the Grigoriadis – Khachiyan algorithm in comparison with MCMC for sparse graphs with a small spectral gap value. The written code is publicly available, so everyone can reproduce the results themselves or use this implementation for their own needs. The work has a purely practical orientation, no theoretical results were obtained.

В данной статье предлагаются методы оптимизации высокого порядка (тензорные методы) для решения двух типов седловых задач. Первый тип — это классическая мин-макс-постановка для поиска седловой точки функционала. Второй тип — это поиск стационарной точки функционала седловой задачи путем минимизации нормы градиента этого функционала. Очевидно, что стационарная точка не всегда совпадает с точкой оптимума функции. Однако необходимость в решении подобного типа задач может возникать в случае, если присутствуют линейные ограничения. В данном случае из решения задачи поиска стационарной точки двойственного функционала можно восстановить решение задачи поиска оптимума прямого функционала. В обоих типах задач какие-либо ограничения на область определения целевого функционала отсутствуют. Также мы предполагаем, что целевой функционал является $\mu$-сильно выпуклыми $\mu$-сильно вогнутым, а также что выполняется условие Липшица для его $p$-й производной.

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

In this paper we propose high-order (tensor) methods for two types of saddle point problems. Firstly, we consider the classic min-max saddle point problem. Secondly, we consider the search for a stationary point of the saddle point problem objective by its gradient norm minimization. Obviously, the stationary point does not always coincide with the optimal point. However, if we have a linear optimization problem with linear constraints, the algorithm for gradient norm minimization becomes useful. In this case we can reconstruct the solution of the optimization problem of a primal function from the solution of gradient norm minimization of dual function. In this paper we consider both types of problems with no constraints. Additionally, we assume that the objective function is $\mu$-strongly convex by the first argument, $\mu$-strongly concave by the second argument, and that the $p$-th derivative of the objective is Lipschitz-continous.

For min-max problems we propose two algorithms. Since we consider strongly convex a strongly concave problem, the first algorithm uses the existing tensor method for regular convex concave saddle point problems and accelerates it with the restarts technique. The complexity of such an algorithm is linear. If we additionally assume that our objective is first and second order Lipschitz, we can improve its performance even more. To do this, we can switch to another existing algorithm in its area of quadratic convergence. Thus, we get the second algorithm, which has a global linear convergence rate and a local quadratic convergence rate.

Finally, in convex optimization there exists a special methodology to solve gradient norm minimization problems by tensor methods. Its main idea is to use existing (near-)optimal algorithms inside a special framework. I want to emphasize that inside this framework we do not necessarily need the assumptions of strong convexity, because we can regularize the convex objective in a special way to make it strongly convex. In our article we transfer this framework on convex-concave objective functions and use it with our aforementioned algorithm with a global linear convergence and a local quadratic convergence rate.

Since the saddle point problem is a particular case of the monotone variation inequality problem, the proposed methods will also work in solving strongly monotone variational inequality problems.