All issues

Моделирование борьбы с террористическими, пиратскими и разбойными актами на море является актуальной научной задачей в силу распространенности силовых актов и недостаточного количества работ по данной проблематике. Действия пиратов и террористов разнообразны. С использованием судна-базы они могут нападать на суда на удалении до 450–500 миль от побережья. Выбрав цель, они ее преследуют и с применением оружия идут на абордаж. Действия по освобождению судна, захваченного пиратами или террористами, включают: блокирование судна, прогноз мест возможного нахождения пи- ратов на судне, проникновение (с борта на борт, по воздуху или из-под воды) и зачистка помещений судна. Анализ специальной литературы по действиям пиратов и террористов показал, что силовой акт (и действия по его нейтрализации) состоит из двух этапов: во-первых, это блокирование судна, заключающееся в принуждении к его остановке, и, во-вторых, нейтрализация команды (группы террористов, пиратов), включая проникновение на судно (корабль) и его зачистку. Этапам цикла поставлены в соответствие показатели — вероятность блокирования и вероятность нейтрализации. Переменными модели силового акта являются количество судов (кораблей, катеров) у нападающих и обороняющихся, а также численность группы захвата нападающих и экипажа судна — жертвы атаки. Параметры модели (показатели корабельного и боевого превосходства) оценены методом максимального правдоподобия с использованием международной базы по инцидентам на море. Значения названных параметров равны 7.6–8.5. Столь высокие значения параметров превосходства отражают возможности сторон по действиям в силовых актах. Предложен и статистически обоснован аналитический метод расчета параметров превосходства. В модели учитываются следующие показатели: возможности сторон по обнаружению противника, скоростные и маневренные характеристики судов, высота судна и характеристики средств абордажа, характеристики оружия и средств защиты и др. С использованием модели Г. Беккера и теории дискретного выбора оценена вероятность отказа от силового акта. Значимость полученных моделей для борьбы с силовыми актами в морском пространстве заключается в возможности количественного обоснования мер по защите судна от пиратских и террористических атак и мер сдерживания, направленных на предотвращение атак (наличие на борту судна вооруженной охраны, помощь военных кораблей и вертолетов).

Modeling the fight against terrorist, pirate and robbery acts at sea is an urgent scientific task due to the prevalence of force acts and the insufficient number of works on this issue. The actions of pirates and terrorists are diverse. Using a base ship, they can attack ships up to 450–500 miles from the coast. Having chosen the target, they pursue it and use the weapons to board the ship. Actions to free a ship captured by pirates or terrorists include: blocking the ship, predicting where pirates might be on the ship, penetrating (from board to board, by air or from under water) and cleaning up the ship’s premises. An analysis of the special literature on the actions of pirates and terrorists showed that the act of force (and actions to neutralize it) consists of two stages: firstly, blocking the vessel, which consists in forcing it to stop, and secondly, neutralizing the team (terrorist groups, pirates), including penetration of a ship (ship) and its cleaning. The stages of the cycle are matched by indicators — the probability of blocking and the probability of neutralization. The variables of the act of force model are the number of ships (ships, boats) of the attackers and defenders, as well as the strength of the capture group of the attackers and the crew of the ship - the victim of the attack. Model parameters (indicators of naval and combat superiority) were estimated using the maximum likelihood method using an international database of incidents at sea. The values of these parameters are 7.6–8.5. Such high values of superiority parameters reflect the parties' ability to act in force acts. An analytical method for calculating excellence parameters is proposed and statistically substantiated. The following indicators are taken into account in the model: the ability of the parties to detect the enemy, the speed and maneuverability characteristics of the vessels, the height of the vessel and the characteristics of the boarding equipment, the characteristics of weapons and protective equipment, etc. Using the Becker model and the theory of discrete choice, the probability of failure of the force act is estimated. The significance of the obtained models for combating acts of force in the sea space lies in the possibility of quantitative substantiation of measures to protect the ship from pirate and terrorist attacks and deterrence measures aimed at preventing attacks (the presence of armed guards on board the ship, assistance from warships and helicopters).

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

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

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

Modern power transportation systems are the complex engineering systems. Such systems include both point facilities (power producers, consumers, transformer substations, etc.) and the distributed elements (f.e. power lines). Such structures are presented in the form of the graphs with different types of nodes under creating the mathematical models. It is necessary to solve the system of partial differential equations of the hyperbolic type to study the dynamic effects in such systems.

An approach similar to one already applied in modeling similar problems earlier used in the work. New variant of the splitting method was used proposed by the authors. Unlike most known works, the splitting is not carried out according to physical processes (energy transport without dissipation, separately dissipative processes). We used splitting to the transport equations with the drain and the exchange between Reimann’s invariants. This splitting makes possible to construct the hybrid schemes for Riemann invariants with a high order of approximation and minimal dissipation error. An example of constructing such a hybrid differential scheme is described for a single-phase power line. The difference scheme proposed is based on the analysis of the properties of the schemes in the space of insufficient coefficients.

Examples of the model problem numerical solutions using the proposed splitting and the difference scheme are given. The results of the numerical calculations shows that the difference scheme allows to reproduce the arising regions of large gradients. It is shown that the difference schemes also allow detecting resonances in such the systems.

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

The article is devoted to first-order adaptive methods for optimization problems with relatively strongly convex functionals. The concept of relatively strong convexity significantly extends the classical concept of convexity by replacing the Euclidean norm in the definition by the distance in a more general sense (more precisely, by Bregman’s divergence). An important feature of the considered classes of problems is the reduced requirements concerting the level of smoothness of objective functionals. More precisely, we consider relatively smooth and relatively Lipschitz-continuous objective functionals, which allows us to apply the proposed techniques for solving many applied problems, such as the intersection of the ellipsoids problem (IEP), the Support Vector Machine (SVM) for a binary classification problem, etc. If the objective functional is convex, the condition of relatively strong convexity can be satisfied using the problem regularization. In this work, we propose adaptive gradient-type methods for optimization problems with relatively strongly convex and relatively Lipschitzcontinuous functionals for the first time. Further, we propose universal methods for relatively strongly convex optimization problems. This technique is based on introducing an artificial inaccuracy into the optimization model, so the proposed methods can be applied both to the case of relatively smooth and relatively Lipschitz-continuous functionals. Additionally, we demonstrate the optimality of the proposed universal gradient-type methods up to the multiplication by a constant for both classes of relatively strongly convex problems. Also, we show how to apply the technique of restarts of the mirror descent algorithm to solve relatively Lipschitz-continuous optimization problems. Moreover, we prove the optimal estimate of the rate of convergence of such a technique. Also, we present the results of numerical experiments to compare the performance of the proposed methods.

В работе предложен набор достаточно простых алгоритмов, который может быть применен для анализа широкого круга белок-белковых взаимодействий. В настоящей работе мы совместно используем методы броуновской и молекулярной динамики для описания процесса образования комплекса белков пластоцианина и цитохрома f высших растений. В диффузионно-столкновительном комплексе выявлено два кластера структур, переход между которыми возможен с сохранением положения центра масс молекул и сопровождается лишь поворотом пластоцианина на 134 градуса. Первый и второй кластеры структур столкновительных комплексов отличаются тем, что в первом кластере с положительно заряженной областью вблизи малого домена цитохрома f контактирует только «нижняя» область пластоцианина, в то время как во втором кластере — обе отрицательно заряженные области. «Верхняя» отрицательно заряженная область пластоцианина в первом кластере оказывается в контакте с аминокислотным остатком лизина K122. При образовании финального комплекса происходит поворот молекулы пластоцианина на 69 градусов вокруг оси, проходящей через обе области электростатического контакта. При этом повороте происходит вытеснение воды из областей, находящихся вблизи кофакторов молекул и сформированных гидрофобными аминокислотными остатками. Это приводит к появлению гидрофобных контактов, уменьшению расстояния между кофакторами до расстояния менее 1,5 нм и дальнейшей стабилизации комплекса в положении, пригодном для передачи электрона. Такие характеристики, как матрицы контактов, оси поворота при переходе между состояниями и графики изменения количества контактов в процессе моделирования, позволяют определить ключевые аминокислотные остатки, участвующие в формировании комплекса и выявить физико-химические механизмы, лежащие в основе этого процесса.

The paper proposes a set of fairly simple analysis algorithms that can be used to analyze a wide range of protein-protein interactions. In this work, we jointly use the methods of Brownian and molecular dynamics to describe the process of formation of a complex of plastocyanin and cytochrome f proteins in higher plants. In the diffusion-collision complex, two clusters of structures were revealed, the transition between which is possible with the preservation of the position of the center of mass of the molecules and is accompanied only by a rotation of plastocyanin by 134 degrees. The first and second clusters of structures of collisional complexes differ in that in the first cluster with a positively charged region near the small domain of cytochrome f, only the “lower” plastocyanin region contacts, while in the second cluster, both negatively charged regions. The “upper” negatively charged region of plastocyanin in the first cluster is in contact with the amino acid residue of lysine K122. When the final complex is formed, the plastocyanin molecule rotates by 69 degrees around an axis passing through both areas of electrostatic contact. With this rotation, water is displaced from the regions located near the cofactors of the molecules and formed by hydrophobic amino acid residues. This leads to the appearance of hydrophobic contacts, a decrease in the distance between the cofactors to a distance of less than 1.5 nm, and further stabilization of the complex in a position suitable for electron transfer. Characteristics such as contact matrices, rotation axes during the transition between states, and graphs of changes in the number of contacts during the modeling process make it possible to determine the key amino acid residues involved in the formation of the complex and to reveal the physicochemical mechanisms underlying this process.

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

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

The paper presents the results of research on the creation of a mathematical model of moral choice based on the development of the approach proposed by V. A. Lefebvre. Unlike V. A. Lefebvre, who considered a very speculative situation of a subject’s moral choice between abstract “good” and “evil” under pressure from the outside world, taking into account the subjective perception of this pressure by the subject, our study considers a more mundane and practically significant situation. The case is considered when the subject, when making decisions, is guided by his individual perception of the outside world (which may be distorted, for example, due to external purposeful informational influence on the subject and manipulation of his consciousness), and “good” and “evil” are not abstract, but are conditioned by a value system adopted in a particular society under consideration and tied to a specific ideology/religion, which may be different for different societies.

As a result of the conducted research, a basic mathematical model has been developed, and special cases of its application have been considered. Some patterns related to moral choice are revealed, and their formal description is given. In particular, the situation of manipulation of consciousness is considered in the language of the model, the law of reducing the “morality” of a society consisting of so-called free subjects (that is, those who strive to act in accordance with their intentions and correspond in their actions to the image of their “I”) is formulated.

Статья посвящена специальному подходу к субградиентным методам для задач сильно выпуклого программирования с несколькими функциональными ограничениями. Точнее говоря, рассматривается задача сильно выпуклой минимизации с несколькими сильно выпуклыми ограничениями-неравенствами и предлагаются оптимизационные методы первого порядка для такого класса задач. Особенность предложенных методов — возможность использования в теоретических оценках качества выдаваемого методом решения параметров сильной выпуклости именно тех функционалов ограничений, для которых нарушается условие продyктивности итерации. Основная задача — предложить для такой постановки субградиентный метод с адаптивными правилами подбора шагов и остановки метода. Ключевая идея предложенной в данной статье методики заключается в объединении двух подходов: схемы с переключениями по продуктивным и непродуктивным шагам и недавно предложенных модификаций зеркального спуска для задач выпуклого программирования, позволяющих игнорировать часть функциональных ограничений на непродуктивных шагах алгоритма. В статье описан субградиентний метод с переключением по продyктивным и непродyктивным шагам для задач сильно выпуклого программирования в случае, когда целевая функция и функциональные ограничения удовлетворяют условию Липшица. Также рассмотрен аналог этой схемы типа зеркального спуска для задач с относительно липшицевыми и относительно сильно выпуклыми целевой функцией и ограничениями. Для предлагаемых методов получены теоретические оценки качества выдаваемого решения, указывающие на оптимальность этих методов с точки зрения нижних оракульных оценок. Кроме того, поскольку во многих задачах операция нахождения точного вектора субградиента достаточно затратна, то для рассматриваемого класса задач исследованы аналоги указанных выше методов с заменой обычного субградиента на $\delta$-субградиент целевого функционала или функциональных ограничений-неравенств. Отмеченный подход может позволить сэкономить вычислительные затраты метода за счет отказа от требования доступности точного значения субградиента в текущей точке. Показано, что оценки качества решения при этом изменяются на величину $O(\delta)$. Также приводятся результаты численных экспериментов, иллюстрирующие преимущество предлагаемых в статье методов в сравнении с некоторыми ранее известными.

The paper is devoted to one approach to constructing subgradient methods for strongly convex programming problems with several functional constraints. More precisely, the strongly convex minimization problem with several strongly convex (inequality-type) constraints is considered, and first-order optimization methods for this class of problems are proposed. The special feature of the proposed methods is the possibility of using the strong convexity parameters of the violated functional constraints at nonproductive iterations, in theoretical estimates of the quality of the produced solution by the methods. The main task, to solve the considered problem, is to propose a subgradient method with adaptive rules for selecting steps and stopping rule of the method. The key idea of the proposed methods in this paper is to combine two approaches: a scheme with switching on productive and nonproductive steps and recently proposed modifications of mirror descent for convex programming problems, allowing to ignore some of the functional constraints on nonproductive steps of the algorithms. In the paper, it was described a subgradient method with switching by productive and nonproductive steps for strongly convex programming problems in the case where the objective function and functional constraints satisfy the Lipschitz condition. An analog of the proposed subgradient method, a mirror descent scheme for problems with relatively Lipschitz and relatively strongly convex objective functions and constraints is also considered. For the proposed methods, it obtained theoretical estimates of the quality of the solution, they indicate the optimality of these methods from the point of view of lower oracle estimates. In addition, since in many problems, the operation of finding the exact subgradient vector is quite expensive, then for the class of problems under consideration, analogs of the mentioned above methods with the replacement of the usual subgradient of the objective function or functional constraints by the $\delta$-subgradient were investigated. The noted approach can save computational costs of the method by refusing to require the availability of the exact value of the subgradient at the current point. It is shown that the quality estimates of the solution change by $O(\delta)$. The results of numerical experiments illustrating the advantages of the proposed methods in comparison with some previously known ones are also presented.

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

This paper studies a model of a population with non-overlapping generations and density-dependent regulation of birth rate. The population breeds seasonally, and its reproductive potential is determined genetically. The model proposed combines an ecological dynamic model of a limited population with non-overlapping generations and microevolutionary model of its genetic structure dynamics for the case when adaptive trait of birth rate controlled by a single diallelic autosomal locus with allelomorphs A and a. The study showed the genetic composition of the population, namely, will it be polymorphic or monomorphic, is mainly determined by the values of the reproductive potentials of heterozygote and homozygotes. Moreover, the average reproductive potential of mature individuals and intensity of self-regulation processes determine population dynamics. In particularly, increasing the average value of the reproductive potential leads to destabilization of the dynamics of age group sizes. The intensity of self-regulation processes determines the nature of emerging oscillations, since scenario of stability loss of fixed points depends on the values of this parameter. It is shown that patterns of occurrence and evolution of cyclic dynamics regimes are mainly determined by the features of life cycle of individuals in population. The life cycle leading to existence of non-overlapping generation gives isolated subpopulations in different years, which results in the possibility of independent microevolution of these subpopulations and, as a result, the complex dynamics emergence of both stage structure and genetic one. Fixing various adaptive mutations will gradually lead to genetic (and possibly morphological) differentiation and to differences in the average reproductive potentials of subpopulations that give different values of equilibrium subpopulation sizes. Further evolutionary growth of reproductive potentials of limited subpopulations leads to their number fluctuations which can differ in both amplitude and phase.

Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применятьмет оды первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужитьуслови е острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможностьпр именения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.

Non-smooth optimization often arises in many applied problems. The issues of developing efficient computational procedures for such problems in high-dimensional spaces are very topical. First-order methods (subgradient methods) are well applicable here, but in fairly general situations they lead to low speed guarantees for large-scale problems. One of the approaches to this type of problem can be to identify a subclass of non-smooth problems that allow relatively optimistic results on the rate of convergence. For example, one of the options for additional assumptions can be the condition of a sharp minimum, proposed in the late 1960s by B. T. Polyak. In the case of the availability of information about the minimal value of the function for Lipschitz-continuous problems with a sharp minimum, it turned out to be possible to propose a subgradient method with a Polyak step-size, which guarantees a linear rate of convergence in the argument. This approach made it possible to cover a number of important applied problems (for example, the problem of projecting onto a convex compact set). However, both the condition of the availability of the minimal value of the function and the condition of a sharp minimum itself look rather restrictive. In this regard, in this paper, we propose a generalized condition for a sharp minimum, somewhat similar to the inexact oracle proposed recently by Devolder – Glineur – Nesterov. The proposed approach makes it possible to extend the class of applicability of subgradient methods with the Polyak step-size, to the situation of inexact information about the value of the minimum, as well as the unknown Lipschitz constant of the objective function. Moreover, the use of local analogs of the global characteristics of the objective function makes it possible to apply the results of this type to wider classes of problems. We show the possibility of applying the proposed approach to strongly convex nonsmooth problems, also, we make an experimental comparison with the known optimal subgradient method for such a class of problems. Moreover, there were obtained some results connected to the applicability of the proposed technique to some types of problems with convexity relaxations: the recently proposed notion of weak $\beta$-quasi-convexity and ordinary quasiconvexity. Also in the paper, we study a generalization of the described technique to the situation with the assumption that the $\delta$-subgradient of the objective function is available instead of the usual subgradient. For one of the considered methods, conditions are found under which, in practice, it is possible to escape the projection of the considered iterative sequence onto the feasible set of the problem.

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

В настоящей работе схемы расщепления 3-го и 4-го порядка были применены непосредственно к решению двумерной гиперболической системы уравнений в частных производных линейной теории упругости. Это позволило повысить итоговый порядок сходимости расчетного алгоритма. В работе эмпирически оценена сходимость по нормам $L_1$ и $L_\infty$ с использованиемана литических решений определяющей системы достаточной степени гладкости. Для получения объективных результатов рассмотрены случаи продольных и поперечных плоских волн, распространяющихся как вдоль диагонали расчетной ячейки, так и не вдоль нее. Проведенные численные эксперименты подтверждают повышение точности метода и демонстрируют теоретически ожидаемый порядок сходимости. При этом увеличивается в 3 и в 4 раза время моделирования (для схем 3-го и 4-го порядка соответственно), но не возрастает потребление оперативной памяти. Предложенное усовершенствование вычислительного алгоритма сохраняет простоту его параллельной реализации на основе пространственной декомпозиции расчетной сетки.

The grid-characteristic method is successfully used for solving hyperbolic systems of partial differential equations (for example, transport / acoustic / elastic equations). It allows to construct correctly algorithms on contact boundaries and boundaries of the integration domain, to a certain extent to take into account the physics of the problem (propagation of discontinuities along characteristic curves), and has the property of monotonicity, which is important for considered problems. In the cases of two-dimensional and three-dimensional problems the method makes use of a coordinate splitting technique, which enables us to solve the original equations by solving several one-dimensional ones consecutively. It is common to use up to 3-rd order one-dimensional schemes with simple splitting techniques which do not allow for the convergence order to be higher than two (with respect to time). Significant achievements in the operator splitting theory were done, the existence of higher-order schemes was proved. Its peculiarity is the need to perform a step in the opposite direction in time, which gives rise to difficulties, for example, for parabolic problems.

In this work coordinate splitting of the 3-rd and 4-th order were used for the two-dimensional hyperbolic problem of the linear elasticity. This made it possible to increase the final convergence order of the computational algorithm. The paper empirically estimates the convergence in L1 and L∞ norms using analytical solutions of the system with the sufficient degree of smoothness. To obtain objective results, we considered the cases of longitudinal and transverse plane waves propagating both along the diagonal of the computational cell and not along it. Numerical experiments demonstrated the improved accuracy and convergence order of constructed schemes. These improvements are achieved with the cost of three- or fourfold increase of the computational time (for the 3-rd and 4-th order respectively) and no additional memory requirements. The proposed improvement of the computational algorithm preserves the simplicity of its parallel implementation based on the spatial decomposition of the computational grid.

Предложен метод отображения промежуточных представлений C-, C++-программ в пространство векторов (эмбеддингов) для оценки производительности программ на этапе компиляции, без необходимости исполнения. Использование эмбеддингов для данной цели позволяет не проводить сравнение графов исследуемых программ непосредственно, что вычислительно упрощает задачу сравнения программ. Метод основан на серии трансформаций исходного промежуточного представления (IR), таких как: инструментирование — добавление фиктивных инструкций в оптимизационном проходе компилятора в зависимости от разности смещений в текущей инструкции обращения к памяти относительно предыдущей, преобразование IR в многомерный вектор с помощью технологии IR2Vec с понижением размерности по алгоритму t-SNE (стохастическое вложение соседей с t-распределением). В качестве метрики производительности предлагается доля кэш-промахов 1-го уровня (D1 cache misses). Приводится эвристический критерий отличия программ с большей долей кэш-промахов от программ с меньшей долей по их образам. Также описан разработанный в ходе работы проход компилятора, генерирующий и добавляющий фиктивные инструкции IR согласно используемой модели памяти. Приведено описание разработанного программного комплекса, реализующего предложенный способ оценивания на базе компиляторной инфраструктуры LLVM. Проведен ряд вычислительных экспериментов на синтетических тестах из наборов программ с идентичными потоками управления, но различным порядком обращений к одномерному массиву, показано, что коэффициент корреляции между метрикой производительности и расстоянием до эмбеддинга худшей программы в наборе отрицателен вне зависимости от инициализации t-SNE, что позволяет сделать заключение о достоверности эвристического критерия. Также в статье рассмотрен способ генерации тестов. По результатам экспериментов, вариативность значений метрики производительности на исследуемых множествах предложена как метрика для улучшения генератора тестов.

The method for mapping of intermediate representations (IR) set of C, C++ programs to vector embedding space is considered to create an empirical estimation framework for static performance prediction using LLVM compiler infrastructure. The usage of embeddings makes programs easier to compare due to avoiding Control Flow Graphs (CFG) and Data Flow Graphs (DFG) direct comparison. This method is based on transformation series of the initial IR such as: instrumentation — injection of artificial instructions in an instrumentation compiler’s pass depending on load offset delta in the current instruction compared to the previous one, mapping of instrumented IR into multidimensional vector with IR2Vec and dimension reduction with t-SNE (t-distributed stochastic neighbor embedding) method. The D1 cache miss ratio measured with perf stat tool is considered as performance metric. A heuristic criterion of programs having more or less cache miss ratio is given. This criterion is based on embeddings of programs in 2D-space. The instrumentation compiler’s pass developed in this work is described: how it generates and injects artificial instructions into IR within the used memory model. The software pipeline that implements the performance estimation based on LLVM compiler infrastructure is given. Computational experiments are performed on synthetic tests which are the sets of programs with the same CFGs but with different sequences of offsets used when accessing the one-dimensional array of a given size. The correlation coefficient between performance metric and distance to the worst program’s embedding is measured and proved to be negative regardless of t-SNE initialization. This fact proves the heuristic criterion to be true. The process of such synthetic tests generation is also considered. Moreover, the variety of performance metric in programs set in such a test is proposed as a metric to be improved with exploration of more tests generators.