Все выпуски

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

Variational inequalities constitute a broad class of problems with applications in a number of fields, including game theory, economics, and machine learning. Today’s practical applications of VIs are becoming increasingly computationally demanding. It is therefore necessary to employ distributed computations to solve such problems in a reasonable time. In this context, workers have to exchange data with each other, which creates a communication bottleneck. There are three main techniques to reduce the cost and the number of communications: the similarity of local operators, the compression of messages and the use of local steps on devices. There is an algorithm that uses all of these techniques to solve the VI problem and outperforms all previous methods in terms of communication complexity. However, this algorithm is limited to unbiased compression. Meanwhile, biased (contractive) compression leads to better results in practice, but it requires additional modifications within an algorithm and more effort to prove the convergence. In this work, we develop a new algorithm that solves distributed VI problems using data similarity, contractive compression and local steps on devices, derive the theoretical convergence of such an algorithm, and perform some experiments to show the applicability of the method.

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

We propose a family of Gauss –Newton methods for solving optimization problems and systems of nonlinear equations based on the ideas of using the upper estimate of the norm of the residual of the system of nonlinear equations and quadratic regularization. The paper presents a development of the «Three Squares Method» scheme with the addition of a momentum term to the update rule of the sought parameters in the problem to be solved. The resulting scheme has several remarkable properties. First, the paper algorithmically describes a whole parametric family of methods that minimize functionals of a special kind: compositions of the residual of a nonlinear equation and an unimodal functional. Such a functional, entirely consistent with the «gray box» paradigm in the problem description, combines a large number of solvable problems related to applications in machine learning, with the regression problems. Secondly, the obtained family of methods is described as a generalization of several forms of the Levenberg –Marquardt algorithm, allowing implementation in non-Euclidean spaces as well. The algorithm describing the parametric family of Gauss –Newton methods uses an iterative procedure that performs an inexact parametrized proximal mapping and shift using a momentum term. The paper contains a detailed analysis of the efficiency of the proposed family of Gauss – Newton methods; the derived estimates take into account the number of external iterations of the algorithm for solving the main problem, the accuracy and computational complexity of the local model representation and oracle computation. Sublinear and linear convergence conditions based on the Polak – Lojasiewicz inequality are derived for the family of methods. In both observed convergence regimes, the Lipschitz property of the residual of the nonlinear system of equations is locally assumed. In addition to the theoretical analysis of the scheme, the paper studies the issues of its practical implementation. In particular, in the experiments conducted for the suboptimal step, the schemes of effective calculation of the approximation of the best step are given, which makes it possible to improve the convergence of the method in practice in comparison with the original «Three Square Method». The proposed scheme combines several existing and frequently used in practice modifications of the Gauss –Newton method, in addition, the paper proposes a monotone momentum modification of the family of developed methods, which does not slow down the search for a solution in the worst case and demonstrates in practice an improvement in the convergence of the method.

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

This paper presents a model of replenishment of bank liquidity by additional income of banks. Given the methodological basis for the necessity for bank stabilization funds to cover losses during the economy crisis. An econometric derivation of the equations describing the behavior of the bank financial and operating activity performed. In accordance with the purpose of creating a stabilization fund introduces an optimality criterion used controls. Based on the equations of the behavior of the bank by the method of dynamic programming is derived a vector of optimal controls.

Добровольные вычисления напоминают частные desktop гриды, тогда как desktop гриды не полностью эквивалентны добровольным вычислениям. Известны несколько попыток отличить и категоризировать их, используя как неофициальные, так и формальные методы. Однако, наиболее формальные подходы моделируют специфическое промежуточное ПО (middleware) и не сосредотачиваются на общем понятии добровольного или desktop грид. Эта работа и есть попытка формализовать их характеристики и отношения. Для этой цели применяется формальное моделирование, которое пытается охватить семантику их функциональных возможностей — в противоположность сравнениям, основанным на свойствах, особенностях, и т. п. Мы применяем этот метод моделирования с целью формализовать добровольную вычислительную систему Открытой Инфраструктуры Беркли для сетевых вычислений (BOINC) [Anderson D. P., 2004].

Volunteer computing resembles private desktop grids whereas desktop grids are not fully equivalent to volunteer computing. There are several attempts to distinguish and categorize them using informal and formal methods. However, most formal approaches model a particular middleware and do not focus on the general notion of volunteer or desktop grid computing. This work makes an attempt to formalize their characteristics and relationship. To this end formal modeling is applied that tries to grasp the semantic of their functionalities — as opposed to comparisons based on properties, features, etc. We apply this modeling method to formalize the Berkeley Open Infrastructure for Network Computing (BOINC) [Anderson D. P., 2004] volunteer computing system.

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

This work is devoted to molecular dynamic modeling of the thermal impact processes on the metal sample consisting of nickel atoms. For the solution of this problem, a continuous mathematical model on the basis of the classical Newton mechanics equations has been used; a numerical method based on the Verlet scheme has been chosen; a parallel algorithm has been offered, and its realization within the MPI and OpenMP technologies has been executed. By means of the developed parallel program, the investigation of thermodynamic equilibrium of nickel atoms’ system under the conditions of heating a sample to desired temperature has been executed. In numerical experiments both optimum parameters of calculation procedure and physical parameters of analyzed process have been defined. The obtained numerical results are well corresponding to known theoretical and experimental data.

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

The paper presents a software system aimed at finding best (in some sense) parameters of an algorithm. The system handles both discrete and continuous parameters and employs massive parallelism offered by public clouds. The paper presents an overview of the system, a method to measure algorithm's performance in the cloud and numerical results of system's use on several problem sets.

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

The paper presents the results of application of machine learning methods: principle component analysis and support vector machine for classification of diffraction images produced in experiments at free-electron lasers. High efficiency of this approach presented by application to simulated data of adenovirus capsid and bluetongue virus core. This dataset were simulated with taking into account the real conditions of the experiment on lasers free electrons such as noise and features of used detectors.

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

Optimization is the heart of relational Database Management System (DMBS). Its can analyzes the SQL statements and determines the most efficient access plan to satisfy every query request. Optimization can solves this problem and analyzes SQL statements specifying which tables and columns are available. And then request the information system and statistical data stored in the system directory, to determine the best method of solving the tasks required to comply with the query requests.

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

The problem of allocation of Steiner points in Euclidean Steiner Tree is considered. The cost of network is sum of building costs and cost of the information transportation. Euclidean Steiner tree problem in the form of topological network design is a good model of this problem.

The package MatLab has the way to solve the second part of this problem — allocate Steiner points under condition that the adjacency matrix is set. The method to get solution has been worked out. The Steiner tree is formed by means of solving of the sequence of "three points" Steiner

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

The paper presents an implementation of branch and bound algorithm employing coarse grained parallelism. The system is based on CBC (COIN-OR branch and cut) open-source MIP solver and inter-process communication capabilities of Erlang. Numerical results show noticeable speedup in comparison to single-threaded CBC instance.