All issues

В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближенного решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро – Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счет замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю. Е. Нестерова (2018 г.), а также за счет специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю. Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка $p \geqslant 3$.

In this work we consider Monteiro – Svaiter accelerated hybrid proximal extragradient (A-HPE) framework and accelerated Newton proximal extragradient (A-NPE) framework. The last framework contains an optimal method for rather smooth convex optimization problems with second-order oracle. We generalize A-NPE framework for higher order derivative oracle (schemes). We replace Newton’s type step in A-NPE that was used for auxiliary problem by Newton’s regularized (tensor) type step (Yu. Nesterov, 2018). Moreover we generalize large step A-HPE/A-NPE framework by replacing Monteiro – Svaiter’s large step condition so that this framework could work for high-order schemes. The main contribution of the paper is as follows: we propose optimal highorder methods for convex optimization problems. As far as we know for that moment there exist only zero, first and second order optimal methods that work according to the lower bounds. For higher order schemes there exists a gap between the lower bounds (Arjevani, Shamir, Shiff, 2017) and existing high-order (tensor) methods (Nesterov – Polyak, 2006; Yu.Nesterov, 2008; M. Baes, 2009; Yu.Nesterov, 2018). Asymptotically the ratio of the rates of convergences for the best existing methods and lower bounds is about 1.5. In this work we eliminate this gap and show that lower bounds are tight. We also consider rather smooth strongly convex optimization problems and show how to generalize the proposed methods to this case. The basic idea is to use restart technique until iteration sequence reach the region of quadratic convergence of Newton method and then use Newton method. One can show that the considered method converges with optimal rates up to a logarithmic factor. Note, that proposed in this work technique can be generalized in the case when we can’t solve auxiliary problem exactly, moreover we can’t even calculate the derivatives of the functional exactly. Moreover, the proposed technique can be generalized to the composite optimization problems and in particular to the constraint convex optimization problems. We also formulate a list of open questions that arise around the main result of this paper (optimal universal method of high order e.t.c.).

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

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

A direct algorithm for solving a linear programming problem (LP), given in canonical form, is considered. The algorithm consists of two successive stages, in which the following LP problems are solved by a direct method: a non-degenerate auxiliary problem at the first stage and some problem equivalent to the original one at the second. The construction of the auxiliary problem is based on a multiplicative version of the Gaussian exclusion method, in the very structure of which there are possibilities: identification of incompatibility and linear dependence of constraints; identification of variables whose optimal values are obviously zero; the actual exclusion of direct variables and the reduction of the dimension of the space in which the solution of the original problem is determined. In the process of actual exclusion of variables, the algorithm generates a sequence of multipliers, the main rows of which form a matrix of constraints of the auxiliary problem, and the possibility of minimizing the filling of the main rows of multipliers is inherent in the very structure of direct methods. At the same time, there is no need to transfer information (basis, plan and optimal value of the objective function) to the second stage of the algorithm and apply one of the ways to eliminate looping to guarantee final convergence.

Two variants of the algorithm for solving the auxiliary problem in conjugate canonical form are presented. The first one is based on its solution by a direct algorithm in terms of the simplex method, and the second one is based on solving a problem dual to it by the simplex method. It is shown that both variants of the algorithm for the same initial data (inputs) generate the same sequence of points: the basic solution and the current dual solution of the vector of row estimates. Hence, it is concluded that the direct algorithm is an algorithm of the simplex method type. It is also shown that the comparison of numerical schemes leads to the conclusion that the direct algorithm allows to reduce, according to the cubic law, the number of arithmetic operations necessary to solve the auxiliary problem, compared with the simplex method. An estimate of the number of iterations is given.

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

In this paper we describe an algorithm of numerical solving of an inverse problem on a hyperbolic heat equation with additional second time derivative with a small parameter. The problem in this case is finding an initial distribution with given final distribution. This algorithm allows finding a solution to the problem for any admissible given precision. Algorithm allows evading difficulties analogous to the case of heat equation with inverted time. Furthermore, it allows finding an optimal grid size by learning on a relatively big grid size and small amount of iterations of a gradient method and later extrapolates to the required grid size using Richardson’s method. This algorithm allows finding an adequate estimate of Lipschitz constant for the gradient of the target functional. Finally, this algorithm may easily be applied to the problems with similar structure, for example in solving equations for plasma, social processes and various biological problems. The theoretical novelty of the paper consists in the developing of an optimal procedure of finding of the required grid size using Richardson extrapolations for optimization problems with inexact gradient in ill-posed problems.

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

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

Исследуются динамические теоретико-игровые модели инновационного развития корпорации. Предлагаемые модели основаны на согласовании частных и общественных интересов агентов. Предполагается, что структура интересов каждого агента включает как частную (личные интересы), так и общественную (интересы компании в целом, в первую очередь отражающие необходимость ее инновационного развития) составляющие. Агенты могут делить персональные ресурсы между этими направлениями. Динамика системы описывается не дифференциальным, а разностным уравнением. При исследовании предложенной модели инновационного развития используются имитация и метод перебора областей допустимых управлений субъектов с некоторым шагом. Основной вклад работы — сравнительный анализ эффективности методов иерархического управления для информационных регламентов Штакельберга/Гермейера при принуждении/побуждении (четыре регламента) с помощью индексов системной согласованности. Предлагаемая модель носит универсальный характер и может быть использована для научно обоснованной поддержки ПИР компаний всех отраслей экономики. Специфика конкретной компании учитывается в ходе идентификации модели (определения конкретных классов ис- пользуемых в модели функций и числовых значений параметров), которая представляет собой отдельную сложную задачу и предполагает анализ системы официальной отчетности компании и применение экспертных оценок ее специалистов. Приняты следующие предположения относительно информационного регламента иерархической игры: все игроки используют программные стратегии; ведущий выбирает и сообщает ведомым экономические управления либо административные управления, которые могут быть только функциями времени (игры Штакельберга) либо зависеть также от управлений ведомых (игры Гермейера); при известных стратегиях ведущего ведомые одновременно и независимо выбирают свои стратегии, что приводит к равновесию Нэша в игре ведомых. За конечное число итераций предложенный алгоритм имитационного моделирования позволяет построить приближенное решение модели или сделать вывод, что равновесия не существует. Достоверность и эффективность предложенного алгоритма следуют из свойств методов сценариев и прямого упорядоченного перебора с постоянным шагом. Получен ряд содержательных выводов относительно сравнительной эффективности методов иерархического управления инновациями.

Dynamic game theoretic models of the corporative innovative development are investigated. The proposed models are based on concordance of private and public interests of agents. It is supposed that the structure of interests of each agent includes both private (personal interests) and public (interests of the whole company connected with its innovative development first) components. The agents allocate their personal resources between these two directions. The system dynamics is described by a difference (not differential) equation. The proposed model of innovative development is studied by simulation and the method of enumeration of the domains of feasible controls with a constant step. The main contribution of the paper consists in comparative analysis of efficiency of the methods of hierarchical control (compulsion or impulsion) for information structures of Stackelberg or Germeier (four structures) by means of the indices of system compatibility. The proposed model is a universal one and can be used for a scientifically grounded support of the programs of innovative development of any economic firm. The features of a specific company are considered in the process of model identification (a determination of the specific classes of model functions and numerical values of its parameters) which forms a separate complex problem and requires an analysis of the statistical data and expert estimations. The following assumptions about information rules of the hierarchical game are accepted: all players use open-loop strategies; the leader chooses and reports to the followers some values of administrative (compulsion) or economic (impulsion) control variables which can be only functions of time (Stackelberg games) or depend also on the followers’ controls (Germeier games); given the leader’s strategies all followers simultaneously and independently choose their strategies that gives a Nash equilibrium in the followers’ game. For a finite number of iterations the proposed algorithm of simulation modeling allows to build an approximate solution of the model or to conclude that it doesn’t exist. A reliability and efficiency of the proposed algorithm follow from the properties of the scenario method and the method of a direct ordered enumeration with a constant step. Some comprehensive conclusions about the comparative efficiency of methods of hierarchical control of innovations are received.

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

Investigation of logical deterministic cellular automata models of population dynamics allows to reveal detailed individual-based mechanisms. The search for such mechanisms is important in connection with ecological problems caused by overexploitation of natural resources, environmental pollution and climate change. Classical models of population dynamics have the phenomenological nature, as they are “black boxes”. Phenomenological models fundamentally complicate research of detailed mechanisms of ecosystem functioning. We have investigated the role of fecundity and duration of resources regeneration in mechanisms of population growth using four models of ecosystem with one species. These models are logical deterministic cellular automata and are based on physical axiomatics of excitable medium with regeneration. We have modeled catastrophic death of population arising from increasing of resources regeneration duration. It has been shown that greater fecundity accelerates population extinction. The investigated mechanisms are important for understanding mechanisms of sustainability of ecosystems and biodiversity conservation. Prospects of the presented modeling approach as a method of transparent multilevel modeling of complex systems are discussed.

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

В настоящей работе с помощью разработанной компьютерной модели на основе клеточного автомата исследовали эволюцию коррозионного фронта при взаимодействии поверхности поликристаллического металла с жидкой агрессивной средой. Зеренная структура металла задавалась с помощью многоугольников Вороного, используемых для моделирования поликристаллических сплавов. Коррозионное разрушение осуществлялось при помощи задания вероятностной функции перехода между ячейками клеточного автомата. Принималось во внимание, что коррозионная прочность зерен неодинакова вследствие кристаллографической анизотропии. Показано, что это приводит к формированию шероховатой фазовой границы в ходе коррозионного процесса. Снижение концентрации активных частиц в растворе агрессивной среды в ходе протекающей химической реакции приводит к затуханию коррозии за конечное число итераций расчета. Установлено, что конечная фазовая граница имеет фрактальную структуру с размерностью 1.323 ± 0.002, близкой к размерности фронта градиентной перколяции, что хорошо согласуется с фрактальной размерностью фронта травления поликристаллического алюминий-магниевого сплава АМг6 концентрированным раствором соляной кислоты. Показано, что коррозия поликристаллического металла в жидкой агрессивной среде представляет новый пример топохимического процесса, кинетика которого описывается теорией Колмогорова–Джонсона–Мейла–Аврами.

Corrosion damage to metals and alloys is one of the main problems of strength and durability of metal structures and products operated in contact with chemically aggressive environments. Recently, there has been a growing interest in computer modeling of the evolution of corrosion damage, especially pitting corrosion, for a deeper understanding of the corrosion process, its impact on the morphology, physical and chemical properties of the surface and mechanical strength of the material. This is mainly due to the complexity of analytical and high cost of experimental in situ studies of real corrosion processes. However, the computing power of modern computers allows you to calculate corrosion with high accuracy only on relatively small areas of the surface. Therefore, the development of new mathematical models that allow calculating large areas for predicting the evolution of corrosion damage to metals is currently an urgent problem.

In this paper, the evolution of the corrosion front in the interaction of a polycrystalline metal surface with a liquid aggressive medium was studied using a computer model based on a cellular automat. A distinctive feature of the model is the specification of the solid body structure in the form of Voronoi polygons used for modeling polycrystalline alloys. Corrosion destruction was performed by setting the probability function of the transition between cells of the cellular automaton. It was taken into account that the corrosion strength of the grains varies due to crystallographic anisotropy. It is shown that this leads to the formation of a rough phase boundary during the corrosion process. Reducing the concentration of active particles in a solution of an aggressive medium during a chemical reaction leads to corrosion attenuation in a finite number of calculation iterations. It is established that the final morphology of the phase boundary has a fractal structure with a dimension of 1.323 ± 0.002 close to the dimension of the gradient percolation front, which is in good agreement with the fractal dimension of the etching front of a polycrystalline aluminum-magnesium alloy AlMg6 with a concentrated solution of hydrochloric acid. It is shown that corrosion of a polycrystalline metal in a liquid aggressive medium is a new example of a topochemical process, the kinetics of which is described by the Kolmogorov–Johnson– Meil–Avrami theory.

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

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.

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

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

Общий вывод, который вытекает из результатов моделирования, сводится к тому, что эмпирическое правило принятия решений по принципу «консенсус минус один» имеет соответствующее математиче- ское обоснование. Результаты моделирования показали, что применение правила «консенсус минус один» позволяет сократить время достижения консенсуса в группе на 76–95 %, что важно для практики.

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

In many social groups, for example, in technical committees for standardization, at the international, regional and national levels, in European communities, managers of ecovillages, social movements (occupy), international organizations, decision-making is based on the consensus of the group members. Instead of voting, where the majority wins over the minority, consensus allows for a solution that each member of the group supports, or at least considers acceptable. This approach ensures that all group members’ opinions, ideas and needs are taken into account. At the same time, it is noted that reaching consensus takes a long time, since it is necessary to ensure agreement within the group, regardless of its size. It was shown that in some situations the number of iterations (agreements, negotiations) is very significant. Moreover, in the decision-making process, there is always a risk of blocking the decision by the minority in the group, which not only delays the decisionmaking time, but makes it impossible. Typically, such a minority is one or two odious people in the group. At the same time, such a member of the group tries to dominate in the discussion, always remaining in his opinion, ignoring the position of other colleagues. This leads to a delay in the decision-making process, on the one hand, and a deterioration in the quality of consensus, on the other, since only the opinion of the dominant member of the group has to be taken into account. To overcome the crisis in this situation, it was proposed to make a decision on the principle of «consensus minus one» or «consensus minus two», that is, do not take into account the opinion of one or two odious members of the group.

The article, based on modeling consensus using the model of regular Markov chains, examines the question of how much the decision-making time according to the «consensus minus one» rule is reduced, when the position of the dominant member of the group is not taken into account.

The general conclusion that follows from the simulation results is that the rule of thumb for making decisions on the principle of «consensus minus one» has a corresponding mathematical justification. The simulation results showed that the application of the «consensus minus one» rule can reduce the time to reach consensus in the group by 76–95%, which is important for practice.

The average number of agreements hyperbolically depends on the average authoritarianism of the group members (excluding the authoritarian one), which means the possibility of delaying the agreement process at high values of the authoritarianism of the group members.

Задача вероятностного тематического моделирования заключается в том, чтобы по заданной коллекции текстовых документов найти две матрицы: матрицу условных вероятностей тем в документах и матрицу условных вероятностей слов в темах. Каждый документ представляется в виде мультимножества слов, то есть предполагается, что для выявления тематики документа не важен порядок слов в нем, а важна только их частота. При таком предположении задача сводится к вычислению низкорангового неотрицательного матричного разложения, наилучшего по критерию максимума правдоподобия. Данная задача имеет в общем случае бесконечное множество решений, то есть является некорректно поставленной. Для регуляризации ее решения к логарифму правдоподобия добавляется взвешенная сумма оптимизационных критериев, с помощью которых формализуются дополнительные требования к модели. При моделировании больших текстовых коллекций хранение первой матрицы представляется нецелесообразным, поскольку ее размер пропорционален числу документов в коллекции. В то же время тематические векторные представления документов необходимы для решения многих задач текстовой аналитики — информационного поиска, кластеризации, классификации, суммаризации текстов. На практике тематический вектор вычисляется для каждого документа по необходимости, что может потребовать десятков итераций по всем словам документа. В данной работе предлагается способ быстрого вычисления тематического вектора для произвольного текста, требующий лишь одной итерации, то есть однократного прохода по всем словам документа. Для этого в модель вводится дополнительное ограничение в виде уравнения, позволяющего вычислять первую матрицу через вторую за линейное время. Хотя формально данное ограничение не является оптимизационным критерием, фактически оно выполняет роль регуляризатора и может применяться в сочетании с другими критериями в рамках теории аддитивной регуляризации тематических моделей ARTM. Эксперименты на трех свободно доступных текстовых коллекциях показали, что предложенный метод улучшает качество модели по пяти оценкам качества, характеризующим разреженность, различность, информативность и когерентность тем. Для проведения экспериментов использовались библиотеки с открытымк одомB igARTM и TopicNet.

The probabilistic topic model of a text document collection finds two matrices: a matrix of conditional probabilities of topics in documents and a matrix of conditional probabilities of words in topics. Each document is represented by a multiset of words also called the “bag of words”, thus assuming that the order of words is not important for revealing the latent topics of the document. Under this assumption, the problem is reduced to a low-rank non-negative matrix factorization governed by likelihood maximization. In general, this problem is ill-posed having an infinite set of solutions. In order to regularize the solution, a weighted sum of optimization criteria is added to the log-likelihood. When modeling large text collections, storing the first matrix seems to be impractical, since its size is proportional to the number of documents in the collection. At the same time, the topical vector representation (embedding) of documents is necessary for solving many text analysis tasks, such as information retrieval, clustering, classification, and summarization of texts. In practice, the topical embedding is calculated for a document “on-the-fly”, which may require dozens of iterations over all the words of the document. In this paper, we propose a way to calculate a topical embedding quickly, by one pass over document words. For this, an additional constraint is introduced into the model in the form of an equation, which calculates the first matrix from the second one in linear time. Although formally this constraint is not an optimization criterion, in fact it plays the role of a regularizer and can be used in combination with other regularizers within the additive regularization framework ARTM. Experiments on three text collections have shown that the proposed method improves the model in terms of sparseness, difference, logLift and coherence measures of topic quality. The open source libraries BigARTM and TopicNet were used for the experiments.