Все выпуски

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

В этой работе заново рассмотрена проблема предсказания максимального выхода роста живых клеток, основанная на балансе всего метаболизма клеток и его фрагментов, названных парциальными обменами (ПО). Для рассмотрения задачи использованы следующие ПО. При росте на любом субстрате мы рассматриваем стандартный конструктивный обмен (СКО), который состоит из одинаковых метаболических путей при росте различных организмов на любом субстрате. СКО начинается с нескольких стандартных соединений (узловых метаболитов): глюкоза, ацетил-КоА, $\alpha$-кетоглутарат, эритрозо-4-фосфат, оксалоацетат, рибозо-5-фосфат, 3-фосфоглицерат, фосфоенолпируват, пируват. Также рассматриваем передний метаболизм (ПМ) — остальная часть полного метаболизма. Первый ПО потребляет макроэргические связи (МЭС), образованные вторым ПО. В данной работе мы рассматриваем обобщенный вариант ПМ, когда учтены возможное наличие внеклеточных продуктов метаболизма и возможность как аэробного, так и анаэробного роста. Вместо отдельных балансов образования каждого узлового метаболита, как это было сделано в нашей предыдущей работе, данная работа имеет дело сразу со всем множеством этих метаболитов. Это делает решение задачи более компактным и требующим меньшего числа биохимических величин и значительно меньшего вычислительного времени. Выведено уравнение, выражающее максимальный выход биомассы через удельные количества МЭС, образованных и потребленных парциальными обменами. Оно содержит удельное потребление МЭС стандартным конструктивным обменом, которое является универсальным биохимическим параметром, применимым к широкому диапазону организмов и субстратов роста. Чтобы корректно определить этот параметр, полный конструктивный обмен и его передняя часть рассмотрены для роста клеток на глюкозе как наиболее изученном субстрате. Здесь мы использовали открытые ранее свойства элементного состава липидной и безлипидной частей биомассы. Было сделано численное исследование влияния вариаций соотношений между потоками через различные узловые метаболиты. Оно показало, что потребности СКО в макроэргических связях и NAD(P)H практически являются константами. Найденный коэффициент «МЭС/образованная биомасса» является эффективным средством для нахождения оценок максимального выхода биомассы из субстратов, для которых известен их первичный метаболизм. Вычисление отношения «АТФ/субстрат», необходимого для оценки выхода биомассы, сделано с помощью специального пакета компьютерных программ GenMetPath.

The biomass growth yield is the ratio of the newly synthesized substance of growing cells to the amount of the consumed substrate, the source of matter and energy for cell growth. The yield is a characteristic of the efficiency of substrate conversion to cell biomass. The conversion is carried out by the cell metabolism, which is a complete aggregate of biochemical reactions occurring in the cells.

This work newly considers the problem of maximal cell growth yield prediction basing on balances of the whole living cell metabolism and its fragments called as partial metabolisms (PM). The following PM’s are used for the present consideration. During growth on any substrate we consider i) the standard constructive metabolism (SCM) which consists of identical pathways during growth of various organisms on any substrate. SCM starts from several standard compounds (nodal metabolites): glucose, acetyl-CoA 2-oxoglutarate, erythrose-4-phosphate, oxaloacetate, ribose-5- phosphate, 3-phosphoglycerate, phosphoenolpyruvate, and pyruvate, and ii) the full forward metabolism (FM) — the remaining part of the whole metabolism. The first one consumes high-energy bonds (HEB) formed by the second one. In this work we examine a generalized variant of the FM, when the possible presence of extracellular products, as well as the possibilities of both aerobic and anaerobic growth are taken into account. Instead of separate balances of each nodal metabolite formation as it was made in our previous work, this work deals at once with the whole aggregate of these metabolites. This makes the problem solution more compact and requiring a smaller number of biochemical quantities and substantially less computational time. An equation expressing the maximal biomass yield via specific amounts of HEB formed and consumed by the partial metabolisms has been derived. It includes the specific HEB consumption by SCM which is a universal biochemical parameter applicable to the wide range of organisms and growth substrates. To correctly determine this parameter, the full constructive metabolism and its forward part are considered for the growth of cells on glucose as the mostly studied substrate. We used here the found earlier properties of the elemental composition of lipid and lipid-free fractions of cell biomass. Numerical study of the effect of various interrelations between flows via different nodal metabolites has been made. It showed that the requirements of the SCM in high-energy bonds and NAD(P)H are practically constants. The found HEB-to-formed-biomass coefficient is an efficient tool for finding estimates of maximal biomass yield from substrates for which the primary metabolism is known. Calculation of ATP-to-substrate ratio necessary for the yield estimation has been made using the special computer program package, GenMetPath.

Problems of multiple covering ($k$-covering) of a bounded set $G$ with equal circles of a given radius are well known. They are thoroughly studied under the assumption that $G$ is a finite set. There are several papers concerned with studying this problem in the case where $G$ is a connected set. In this paper, we study the problem of minimizing the number of circles that form a $k$-covering, $k \geqslant 1$, provided that $G$ is a bounded convex plane domain.

For the above-mentioned problem, we state a 0-1 linear model, a general integer linear model, and a nonlinear model, imposing a constraint on the minimum distance between the centers of covering circles. The latter constraint is due to the fact that in practice one can place at most one device at each point. We establish necessary and sufficient solvability conditions for the linear models and describe one (easily realizable) variant of these conditions in the case where the covered set $G$ is a rectangle.

We propose some methods for finding an approximate number of circles of a given radius that provide the desired $k$-covering of the set $G$, both with and without constraints on distances between the circles’ centers. We treat the calculated values as approximate upper bounds for the number of circles. We also propose a technique that allows one to get approximate lower bounds for the number of circles that is necessary for providing a $k$-covering of the set $G$. In the general linear model, as distinct from the 0-1 linear model, we require no additional constraint. The difference between the upper and lower bounds for the number of circles characterizes the quality (acceptability) of the constructed $k$-covering.

We state a nonlinear mathematical model for the $k$-covering problem with the above-mentioned constraints imposed on distances between the centers of covering circles. For this model, we propose an algorithm which (in certain cases) allows one to find more exact solutions to covering problems than those calculated from linear models.

For implementing the proposed approach, we have developed computer programs and performed numerical experiments. Results of numerical experiments demonstrate the effectiveness of the method.

Problems of multiple covering ($k$-covering) of a bounded set $G$ with equal circles of a given radius are well known. They are thoroughly studied under the assumption that $G$ is a finite set. There are several papers concerned with studying this problem in the case where $G$ is a connected set. In this paper, we study the problem of minimizing the number of circles that form a $k$-covering, $k \geqslant 1$, provided that $G$ is a bounded convex plane domain.

For the above-mentioned problem, we state a 0-1 linear model, a general integer linear model, and a nonlinear model, imposing a constraint on the minimum distance between the centers of covering circles. The latter constraint is due to the fact that in practice one can place at most one device at each point. We establish necessary and sufficient solvability conditions for the linear models and describe one (easily realizable) variant of these conditions in the case where the covered set $G$ is a rectangle.

We propose some methods for finding an approximate number of circles of a given radius that provide the desired $k$-covering of the set $G$, both with and without constraints on distances between the circles’ centers. We treat the calculated values as approximate upper bounds for the number of circles. We also propose a technique that allows one to get approximate lower bounds for the number of circles that is necessary for providing a $k$-covering of the set $G$. In the general linear model, as distinct from the 0-1 linear model, we require no additional constraint. The difference between the upper and lower bounds for the number of circles characterizes the quality (acceptability) of the constructed $k$-covering.

We state a nonlinear mathematical model for the $k$-covering problem with the above-mentioned constraints imposed on distances between the centers of covering circles. For this model, we propose an algorithm which (in certain cases) allows one to find more exact solutions to covering problems than those calculated from linear models.

For implementing the proposed approach, we have developed computer programs and performed numerical experiments. Results of numerical experiments demonstrate the effectiveness of the method.

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

Metal hydrides are an interesting class of chemical compounds that can reversibly bind a large amount of hydrogen and are, therefore, of interest for energy applications. Understanding the factors affecting the kinetics of hydride formation and decomposition is especially important. Features of the material, experimental setup and conditions affect the mathematical description of the processes, which can undergo significant changes during the processing of experimental data. The article proposes a general approach to numerical modeling of the formation and decomposition of metal hydrides and solving inverse problems of estimating material parameters from measurement data. The models are divided into two classes: diffusive ones, that take into account the gradient of hydrogen concentration in the metal lattice, and models with fast diffusion. The former are more complex and take the form of non-classical boundary value problems of parabolic type. A rather general approach to the grid solution of such problems is described. The second ones are solved relatively simply, but can change greatly when model assumptions change. Our experience in processing experimental data shows that a flexible software tool is needed; a tool that allows, on the one hand, building models from standard blocks, freely changing them if necessary, and, on the other hand, avoiding the implementation of routine algorithms. It also should be adapted for high-performance systems of different paradigms. These conditions are satisfied by the HIMICOS library presented in the paper, which has been tested on a large number of experimental data. It allows simulating the kinetics of formation and decomposition of metal hydrides, as well as related tasks, at three levels of abstraction. At the low level, the user defines the interface procedures, such as calculating the time layer based on the previous layer or the entire history, calculating the observed value and the independent variable from the task variables, comparing the curve with the reference. Special algorithms can be used for solving quite general parabolic-type boundary value problems with free boundaries and with various quasilinear (i.e., linear with respect to the derivative only) boundary conditions, as well as calculating the distance between the curves in different metric spaces and with different normalization. This is the middle level of abstraction. At the high level, it is enough to choose a ready tested model for a particular material and modify it in relation to the experimental conditions.

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

Рассматриваемая модель этого процесса учитывает нелинейный закон теплового излучения Стефана – Больцмана и бесконечное тепловое воздействие периодического излучения на ЭОСи пылинку. Эта модель описывается нелинейной системой дифференциальных уравнений для двух функций: температуры ЭОСи температуры пылинки. Доказывается, что в силу накапливающего воздействия периодического теплового воздействия процесс достиже- ния температуры возгорания пылинки происходит практически при любых априори возможных изменениях в этом процессе теплофизических параметров ЭОСи пылинки, а также коэффициентов теплообмена между ними и окружающим их воздухом. Усреднение этих параметров по переменным, относящимся как к объему, так и к поверхностям пылинки и ЭОС, корректно при указанных в работе естественных ограничениях. А благодаря рассмотрению задачи (включая численные результаты) в безразмерных единицах измерения, охвачен весь реально значимый спектр теплофизических параметров.

Проведенное тщательное математическое исследование соответствующей нелинейной системы дифференциальных уравнений впервые позволило для общего случая теплофизических параметров и характеристик теплового воздействия периодического лазерного излучения найти формулу для значения той допустимой интенсивности излучения, которая не приводит к разрушению ЭОСв результате возгорания пылинки, осевшей на ЭОС. Найденное в работе для общего случая теоретическое значение допустимой интенсивности в частном случае данных лазерного комплекса обсерватории в г. Грассе (на юге Франции) практически соответствует полученному там экспериментальному значению.

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

Laser damage to transparent solids is a major limiting factor output power of laser systems. For laser rangefinders, the most likely destruction cause of elements of the optical system (lenses, mirrors) actually, as a rule, somewhat dusty, is not an optical breakdown as a result of avalanche, but such a thermal effect on the dust speck deposited on an element of the optical system (EOS), which leads to its ignition. It is the ignition of a speck of dust that initiates the process of EOS damage.

The corresponding model of this process leading to the ignition of a speck of dust takes into account the nonlinear Stefan –Boltzmann law of thermal radiation and the infinite thermal effect of periodic radiation on the EOS and the speck of dust. This model is described by a nonlinear system of differential equations for two functions: the EOS temperature and the dust particle temperature. It is proved that due to the accumulating effect of periodic thermal action, the process of reaching the dust speck ignition temperature occurs almost at any a priori possible changes in this process of the thermophysical parameters of the EOS and the dust speck, as well as the heat exchange coefficients between them and the surrounding air. Averaging these parameters over the variables related to both the volume and the surfaces of the dust speck and the EOS is correct under the natural constraints specified in the paper. The entire really significant spectrum of thermophysical parameters is covered thanks to the use of dimensionless units in the problem (including numerical results).

A thorough mathematical study of the corresponding nonlinear system of differential equations made it possible for the first time for the general case of thermophysical parameters and characteristics of the thermal effect of periodic laser radiation to find a formula for the value of the permissible radiation intensity that does not lead to the destruction of the EOS as a result of the ignition of a speck of dust deposited on the EOS. The theoretical value of the permissible intensity found in the general case in the special case of the data from the Grasse laser ranging station (south of France) almost matches that experimentally observed in the observatory.

In parallel with the solution of the main problem, we derive a formula for the power absorption coefficient of laser radiation by an EOS expressed in terms of four dimensionless parameters: the relative intensity of laser radiation, the relative illumination of the EOS, the relative heat transfer coefficient from the EOS to the surrounding air, and the relative steady-state temperature of the EOS.

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

Сравнение описанных методов проводится для двух типов стохастических задач — выпуклой оптимизации и седел. Для задач стохастической выпуклой оптимизации существующие решения позволяют довольно подробно сравнить онлайн- и офлайн-алгоритмы. В частности, для сильно выпуклых задач вычислительная сложность алгоритмов одинаковая, причем условие сильной выпуклости может быть ослаблено до условия $\gamma$-роста целевой функции. С этой точки зрения седловые задачи являются гораздо менее изученными. Тем не менее существующие решения позволяют наметить основные направления исследования. Так, значительные продвижения сделаны для билинейных седловых задач с помощью онлайн-алгоритмов. Оффлайн-алгоритмы представлены всего одним исследованием. В данной работе на этом примере демонстрируется аналогичная с выпуклой оптимизацией схожесть обоих алгоритмов. Также был проработан вопрос точности решения вспомогательной задачи для седел. С другой стороны, седловая задача стохастической оптимизации обобщает выпуклую, то есть является ее логичным продолжением. Это проявляется в том, что существующие результаты из выпуклой оптимизации можно перенести на седла. В данной работе такой перенос осуществляется для результатов онлайн-алгоритма в выпуклом случае, когда целевая функция удовлетворяет условию $\gamma$-роста.

Stochastic optimization is a current area of research due to significant advances in machine learning and their applications to everyday problems. In this paper, we consider two fundamentally different methods for solving the problem of stochastic optimization — online and offline algorithms. The corresponding algorithms have their qualitative advantages over each other. So, for offline algorithms, it is required to solve an auxiliary problem with high accuracy. However, this can be done in a distributed manner, and this opens up fundamental possibilities such as, for example, the construction of a dual problem. Despite this, both online and offline algorithms pursue a common goal — solving the stochastic optimization problem with a given accuracy. This is reflected in the comparison of the computational complexity of the described algorithms, which is demonstrated in this paper.

The comparison of the described methods is carried out for two types of stochastic problems — convex optimization and saddles. For problems of stochastic convex optimization, the existing solutions make it possible to compare online and offline algorithms in some detail. In particular, for strongly convex problems, the computational complexity of the algorithms is the same, and the condition of strong convexity can be weakened to the condition of $\gamma$-growth of the objective function. From this point of view, saddle point problems are much less studied. Nevertheless, existing solutions allow us to outline the main directions of research. Thus, significant progress has been made for bilinear saddle point problems using online algorithms. Offline algorithms are represented by just one study. In this paper, this example demonstrates the similarity of both algorithms with convex optimization. The issue of the accuracy of solving the auxiliary problem for saddles was also worked out. On the other hand, the saddle point problem of stochastic optimization generalizes the convex one, that is, it is its logical continuation. This is manifested in the fact that existing results from convex optimization can be transferred to saddles. In this paper, such a transfer is carried out for the results of the online algorithm in the convex case, when the objective function satisfies the $\gamma$-growth condition.

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

Recently many investigations have been devoted to theoretical models in new areas concerning description of different biological, sociological and historical processes. In the present paper we investigate the nazi Germany invasion in Poland, France and USSR from the kinetic theory point of view. We model this process with the Cauchy boundary problem for the two-element kinetic equations with spatial uniform initial conditions. The solution of the problem is given in the form of the traveling wave and the propagation velocity of a frontline depends on the quotient between initial forces concentrations. Moreover it is obtained that the general solution of the model can be obtained in terms of the quadratures and elementary functions. Finally it is shown that the frontline velocities are complied with the historical data.

Решение общей проблемы информационного взрыва связано с системами автоматической обработки цифровых данных, включая их распознавание, сортировку, содержательную обработку и представление в виде, приемлемом для восприятия человеком. Естественным решением является создание интеллектуальных систем извлечения знаний из неструктурированной информации. При этом явные успехи в области обработки структурированных данных контрастируют со скромными достижениями в области анализа неструктурированной информации, в частности в задачах обработки текстовых документов. В настоящее время данное направление находится в стадии интенсивных исследований и разработок. Данная работа представляет собой системный обзор международных и отечественных публикаций, посвященных ведущему тренду в области автоматической обработки потоков текстовой информации, а именно интеллектуальному анализу текстов или Text Mining (TM). Рассмотрены основные задачи и понятия TM, его место в области проблемы искусственного интеллекта, а также указаны сложности при обработке текстов на естественном языке (NLP), обусловленные слабой структурированностью и неоднозначностью лингвистической ин- формации. Описаны стадии предварительной обработки текстов, их очистка и селекция признаков, которые, наряду с результатами морфологического, синтаксического и семантического анализа, являются компонентами TM. Процесс интеллектуального анализа текстов представлен как отображение множества текстовых документов в «знания», т.е. в очищенную от избыточности и шума совокупность сведений, необходимых для решения конкретной прикладной задачи. На примере задачи трейдинга продемонстрирована формализация принятия торгового решения, основанная на совокупности аналитических рекомендаций. Типичными примерами TM являются задачи и технологии информационного поиска (IR), суммаризации текста, анализа тональности, классификации и кластеризации документов и т. п. Общим вопросом для всех методов TM является выбор типа словоформ и их производных, используемых для распознавания контента в последовательностях символов NL. На примере IR рассмотрены типовые алгоритмы поиска, основанные на простых словоформах, фразах, шаблонах и концептах, а также более сложные технологии, связанные с дополнением шаблонов синтаксической и семантической информацией. В общем виде дано описание механизмов NLP: морфологический, синтаксический, семантический и прагматический анализ. Приведен сравнительный анализ современных инструментов TM, позволяющий осуществить выбор платформы, исходя из особенности решаемой задачи и практических навыков пользователя.

In general, solving the information explosion problem can be delegated to systems for automatic processing of digital data. These systems are intended for recognizing, sorting, meaningfully processing and presenting data in formats readable and interpretable by humans. The creation of intelligent knowledge extraction systems that handle unstructured data would be a natural solution in this area. At the same time, the evident progress in these tasks for structured data contrasts with the limited success of unstructured data processing, and, in particular, document processing. Currently, this research area is undergoing active development and investigation. The present paper is a systematic survey on both Russian and international publications that are dedicated to the leading trend in automatic text data processing: Text Mining (TM). We cover the main tasks and notions of TM, as well as its place in the current AI landscape. Furthermore, we analyze the complications that arise during the processing of texts written in natural language (NLP) which are weakly structured and often provide ambiguous linguistic information. We describe the stages of text data preparation, cleaning, and selecting features which, alongside the data obtained via morphological, syntactic, and semantic analysis, constitute the input for the TM process. This process can be represented as mapping a set of text documents to «knowledge». Using the case of stock trading, we demonstrate the formalization of the problem of making a trade decision based on a set of analytical recommendations. Examples of such mappings are methods of Information Retrieval (IR), text summarization, sentiment analysis, document classification and clustering, etc. The common point of all tasks and techniques of TM is the selection of word forms and their derivatives used to recognize content in NL symbol sequences. Considering IR as an example, we examine classic types of search, such as searching for word forms, phrases, patterns and concepts. Additionally, we consider the augmentation of patterns with syntactic and semantic information. Next, we provide a general description of all NLP instruments: morphological, syntactic, semantic and pragmatic analysis. Finally, we end the paper with a comparative analysis of modern TM tools which can be helpful for selecting a suitable TM platform based on the user’s needs and skills.

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

This paper is devoted to some variants of improving the convergence rate guarantees of the gradient-type algorithms for relatively smooth and relatively Lipschitz-continuous problems in the case of additional information about some analogues of the strong convexity of the objective function. We consider two classes of problems, namely, convex problems with a relative functional growth condition, and problems (generally, non-convex) with an analogue of the Polyak – Lojasiewicz gradient dominance condition with respect to Bregman divergence. For the first type of problems, we propose two restart schemes for the gradient type methods and justify theoretical estimates of the convergence of two algorithms with adaptively chosen parameters corresponding to the relative smoothness or Lipschitz property of the objective function. The first of these algorithms is simpler in terms of the stopping criterion from the iteration, but for this algorithm, the near-optimal computational guarantees are justified only on the class of relatively Lipschitz-continuous problems. The restart procedure of another algorithm, in its turn, allowed us to obtain more universal theoretical results. We proved a near-optimal estimate of the complexity on the class of convex relatively Lipschitz continuous problems with a functional growth condition. We also obtained linear convergence rate guarantees on the class of relatively smooth problems with a functional growth condition. For a class of problems with an analogue of the gradient dominance condition with respect to the Bregman divergence, estimates of the quality of the output solution were obtained using adaptively selected parameters. We also present the results of some computational experiments illustrating the performance of the methods for the second approach at the conclusion of the paper. As examples, we considered a linear inverse Poisson problem (minimizing the Kullback – Leibler divergence), its regularized version which allows guaranteeing a relative strong convexity of the objective function, as well as an example of a relatively smooth and relatively strongly convex problem. In particular, calculations show that a relatively strongly convex function may not satisfy the relative variant of the gradient dominance condition.

Во многих социальных группах, например в технических комитетах по стандартизации, на между- народном, региональном и национальных уровнях, в европейских общинах, управляющих экопоселени- ями, социальных общественных движениях (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.

В работе рассматривается метод исследования панельных данных, основанный на использовании агломеративной иерархической кластеризации — группировки объектов на основании сходства и разли- чия их признаков в иерархию вложенных друг в друга кластеров. Применялись 2 альтернативных способа вычисления евклидовых расстояний между объектами — расстояния между усредненными по интервалу наблюдений значениями и расстояния с использованием данных за все рассматриваемые годы. Сравнивались 3 альтернативных метода вычисления расстояний между кластерами. В первом случае таким расстоянием считается расстояние между ближайшими элементами из двух кластеров, во втором — среднее по парам элементов, в третьем — расстояние между наиболее удаленными элементами. Исследована эффективность использования двух индексов качества кластеризации — индекса Данна и Силуэта для выбора оптимального числа кластеров и оценки статистической значимости полученных решений. Способ оценивания статистической достоверности кластерной структуры заключался в сравнении качества кластеризации, на реальной выборке с качеством кластеризаций на искусственно сгенерированных выборках панельных данных с теми же самыми числом объектов, признаков и длиной рядов. Генерация производилась из фиксированного вероятностного распределения. Использовались способы симуляции, имитирующие гауссов белый шум и случайное блуждание. Расчеты с индексом Силуэт показали, что случайное блуждание характеризуется не только ложной регрессией, но и ложной кластеризацией. Кластеризация принималась достоверной для данного числа выделенных кластеров, если значение индекса на реальной выборке оказывалось больше значения 95%-ного квантиля для искусственных данных. В качестве выборки реальных данных использован набор временных рядов показателей, характеризующих производство в российских регионах. Для этих данных только Силуэт показывает достоверную кластеризацию на уровне $p < 0.05$. Расчеты также показали, что значения индексов для реальных данных в целом ближе к значениям для случайных блужданий, чем для белого шума, но имеют значимые отличия и от тех, и от других. Визуально можно выделить скопления близко расположенных друг от друга в трехмерном признаковом пространстве точек, выделяемые также в качестве кластеров применяемым алгоритмом иерархической кластеризации.

The paper considers a method for studying panel data based on the use of agglomerative hierarchical clustering — grouping objects based on the similarities and differences in their features into a hierarchy of clusters nested into each other. We used 2 alternative methods for calculating Euclidean distances between objects — the distance between the values averaged over observation interval, and the distance using data for all considered years. Three alternative methods for calculating the distances between clusters were compared. In the first case, the distance between the nearest elements from two clusters is considered to be distance between these clusters, in the second — the average over pairs of elements, in the third — the distance between the most distant elements. The efficiency of using two clustering quality indices, the Dunn and Silhouette index, was studied to select the optimal number of clusters and evaluate the statistical significance of the obtained solutions. The method of assessing statistical reliability of cluster structure consisted in comparing the quality of clustering on a real sample with the quality of clustering on artificially generated samples of panel data with the same number of objects, features and lengths of time series. Generation was made from a fixed probability distribution. At the same time, simulation methods imitating Gaussian white noise and random walk were used. Calculations with the Silhouette index showed that a random walk is characterized not only by spurious regression, but also by “spurious clustering”. Clustering was considered reliable for a given number of selected clusters if the index value on the real sample turned out to be greater than the value of the 95% quantile for artificial data. A set of time series of indicators characterizing production in the regions of the Russian Federation was used as a sample of real data. For these data only Silhouette shows reliable clustering at the level p < 0.05. Calculations also showed that index values for real data are generally closer to values for random walks than for white noise, but it have significant differences from both. Since three-dimensional feature space is used, the quality of clustering was also evaluated visually. Visually, one can distinguish clusters of points located close to each other, also distinguished as clusters by the applied hierarchical clustering algorithm.