All issues

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

$$ \text{Argmin}_{x\in X}{\langle p,\,x \rangle} $$

для заданного вектора $p \in \mathbb{R}^n$. Существует целый ряд методов условного градиента, имеющих линейную скорость сходимости в сильно выпуклом случае. Однако во всех этих методах в оценку скорости сходимости входит размерность задачи, которая в современных приложениях может быть очень большой. В данной работе доказывается, что в сильно выпуклом случае скорость сходимости методов условного градиента в лучшем случае зависит от размерности задачи $n$ как $\widetilde{\Omega}\left(\!\sqrt{n}\right)$. Таким образом, методы условного градиента могут оказаться неэффективными для решения сильно выпуклых оптимизационных задач больших размерностей.

Отдельно рассматривается приложение методов условного градиента к задачам минимизации квадратичной формы. Уже была доказана эффективность метода Франк – Вульфа для решения задачи квадратичной оптимизации в выпуклом случае на симплексе (PageRank). Данная работа показывает, что использование методов условного градиента для минимизации квадратичной формы в сильно выпуклом случае малоэффективно из-за наличия размерности в оценке скорости сходимости этих методов. Поэтому рассматривается метод рестартов условного градиента (Shrinking Conditional Gradient). Его отличие от методов условного градиента заключается в том, что в нем используется модифицированный линейный минимизационный оракул, который для заданного вектора $p \in \mathbb{R}^n$ вычисляет решение задачи $$ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. $$ В оценку скорости сходимости такого алгоритма размерность уже не входит. С помощью рестартов метода условного градиента получена сложность (число арифметических операций) минимизации квадратичной формы на $\infty$-шаре. Полученная оценка работы метода сравнима со сложностью градиентного метода.

In this paper, we consider conditional gradient methods for optimizing strongly convex functions. These are methods that use a linear minimization oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem

\[ \text{Argmin}_{x\in X}{\langle p,\,x \rangle}. \]There are a variety of conditional gradient methods that have a linear convergence rate in a strongly convex case. However, in all these methods, the dimension of the problem is included in the rate of convergence, which in modern applications can be very large. In this paper, we prove that in the strongly convex case, the convergence rate of the conditional gradient methods in the best case depends on the dimension of the problem $ n $ as $ \widetilde {\Omega} \left(\!\sqrt {n}\right) $. Thus, the conditional gradient methods may turn out to be ineffective for solving strongly convex optimization problems of large dimensions.

Also, the application of conditional gradient methods to minimization problems of a quadratic form is considered. The effectiveness of the Frank – Wolfe method for solving the quadratic optimization problem in the convex case on a simplex (PageRank) has already been proved. This work shows that the use of conditional gradient methods to solve the minimization problem of a quadratic form in a strongly convex case is ineffective due to the presence of dimension in the convergence rate of these methods. Therefore, the Shrinking Conditional Gradient method is considered. Its difference from the conditional gradient methods is that it uses a modified linear minimization oracle. It's an oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem \[ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. \] The convergence rate of such an algorithm does not depend on dimension. Using the Shrinking Conditional Gradient method the complexity (the total number of arithmetic operations) of solving the minimization problem of quadratic form on a $ \infty $-ball is obtained. The resulting evaluation of the method is comparable to the complexity of the gradient method.

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

The work is devoted to modeling the processes of disassembling complex products in CADsystems. The ability to dismantle a product in a given sequence is formed at the early design stages, and is implemented at the end of the life cycle. Therefore, modern CAD-systems should have tools for assessing the complexity of dismantling parts and assembly units of a product. A hypergraph model of the mechanical structure of the product is proposed. It is shown that the mathematical description of coherent and sequential disassembly operations is the normal cutting of the edge of the hypergraph. A theorem on the properties of normal cuts is proved. This theorem allows us to organize a simple recursive procedure for generating all cuts of the hypergraph. The set of all cuts is represented as an AND/OR-tree. The tree contains information about plans for disassembling the product and its parts. Mathematical descriptions of various types of disassembly processes are proposed: complete, incomplete, linear, nonlinear. It is shown that the decisive graph of the AND/OR-tree is a model of disassembling the product and all its components obtained in the process of dismantling. An important characteristic of the complexity of dismantling parts is considered — the depth of nesting. A method of effective calculation of the estimate from below has been developed for this characteristic.

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

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

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.

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

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

Исследована начально-краевая задача в прямоугольнике $\overline{D}=\{(x,\,t)\colon 0\leqslant x\leqslant l,\;0\leqslant t\leqslant T\}$ для нагруженного дифференциального уравнения теплопроводности с композицией дробной производной Римана – Лиувилля и Капуто – Герасимова и с граничными условиями первого и третьего рода. С помощью метода энергетических неравенств получена априорная оценка в дифференциальной и в разностной форме. Полученные неравенства означают единственность решения и непрерывную зависимость решения от входных данных задачи. Получен разностный аналог для композиции дробной производной Римана – Лиувилля и Капуто – Герасимова порядка $(2-\beta )$ и построена разностная схема, аппроксимирующая исходную задачу с порядком $O\left(\tau +h^{2-\beta } \right)$. Доказана сходимость решения разностной схемы к решению исходной дифференциальной задачи со скоростью, равной порядку аппроксимации разностной схемы.

Recently, to describe various mathematical models of physical processes, fractional differential calculus has been widely used. In this regard, much attention is paid to partial differential equations of fractional order, which are a generalization of partial differential equations of integer order. In this case, various settings are possible.

Loaded differential equations in the literature are called equations containing values of a solution or its derivatives on manifolds of lower dimension than the dimension of the definitional domain of the desired function. Currently, numerical methods for solving loaded partial differential equations of integer and fractional orders are widely used, since analytical solving methods for solving are impossible. A fairly effective method for solving this kind of problem is the finite difference method, or the grid method.

We studied the initial-boundary value problem in the rectangle $\overline{D}=\{(x,\,t)\colon 0\leqslant x\leqslant l,\;0\leqslant t\leqslant T\}$ for the loaded differential heat equation with composition fractional derivative of Riemann – Liouville and Caputo – Gerasimov and with boundary conditions of the first and third kind. We have gotten an a priori assessment in differential and difference interpretations. The obtained inequalities mean the uniqueness of the solution and the continuous dependence of the solution on the input data of the problem. A difference analogue of the composition fractional derivative of Riemann – Liouville and Caputo –Gerasimov order $(2-\beta )$ is obtained and a difference scheme is constructed that approximates the original problem with the order $O\left(\tau +h^{2-\beta } \right)$. The convergence of the approximate solution to the exact one is proven at a rate equal to the order of approximation of the difference scheme.

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

Conversion of numeric data to the spiking form and information losses in this process are serious problems limiting usage of spiking neural networks in applied informational systems. While physical values are represented by numbers, internal representation of information inside spiking neural networks is based on spikes — elementary objects emitted and processed by neurons. This problem is especially hard in the reinforcement learning applications where an agent should learn to behave in the dynamic real world because beside the accuracy of the encoding method, its dynamic characteristics should be considered as well. The encoding algorithm based on the Gaussian receptive fields (GRF) is frequently used. In this method, one numeric variable fed to the network is represented by spike streams emitted by a certain set of network input nodes. The spike frequency in each stream is determined by proximity of the current variable value to the center of the receptive field corresponding to the given input node. In the standard GRF algorithm, the receptive field centers are placed equidistantly. However, it is inefficient in the case of very uneven distribution of the variable encoded. In the present paper, an improved version of this method is proposed which is based on adaptive selection of the Gaussian centers and spike stream frequencies. This improved GRF algorithm is compared with its standard version in terms of amount of information lost in the coding process and of accuracy of classification models built on spike-encoded data. The fraction of information retained in the process of the standard and adaptive GRF encoding is estimated using the direct and reverse encoding procedures applied to a large sample from the triangular probability distribution and counting coinciding bits in the original and restored samples. The comparison based on classification was performed on a task of evaluation of current state in reinforcement learning. For this purpose, the classification models were created by machine learning algorithms of very different nature — nearest neighbors algorithm, random forest and multi-layer perceptron. Superiority of our approach is demonstrated on all these tests.

В работе получены количественные условия устойчивости алгоритма квантовой оценки фазы (QPE) при равномерном распределении собственных значений унитарного оператора. На основе теории возмущений для линейных операторов показано, что точность определения фазы ограничена логарифмической зависимостью от возмущения: число точно определяемых двоичных разрядов удовлетворяет условию $n = o( -\log_2^{}(\epsilon) )$. Установлено, что фазы становятся различимыми при возмущении, не превышающем минимальное расстояние $\frac{1}{m}$ между соседними фазами, т.е. соблюдается условие $m = o \left(\epsilon^{-1}\right)$. Эти результаты выявляют фундаментальные ограничения разрешающей способности QPE в условиях неточных входных данных и имеют прямое значение при проектировании устойчивых квантовых алгоритмов, использующих QPE в качестве подпрограммы.

This paper establishes quantitative conditions for the stability of the Quantum Phase Estimation (QPE) algorithm under the assumption of a uniform distribution of eigenvalues of the unitary operator. Using perturbation theory for linear operators, we demonstrate that the accuracy of phase estimation is fundamentally limited by a logarithmic dependence on the perturbation magnitude: the number of reliably recoverable binary digits of the phase satisfies the condition $n=o(-\log_2^{}(\epsilon))$. Furthermore, we show that distinct phases remain resolvable only if the perturbation does not exceed the minimal distance $\frac{1}{m}$ between adjacent phases, which leads to the condition $m=o\left(\epsilon^{-1}\right)$. These results reveal fundamental limitations on the resolving power of QPE in the presence of imperfect input data and are of direct practical relevance for the design of robust quantum algorithms that employ QPE as a~subroutine.

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

A boundary value problem for partial differential equation with nonlocal boundary relations of special type is resolved by means of a slight modification of the separation of variables method. Ordinal differential operator of the second order subject to boundary conditions of the main problem is not self-adjoint. The system of eigenfunctions generated by the operator has no basis property in L₂[0,1] space. A special system of functions is proposed to expand the solution of the boundary value problem.

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

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

The basic subset of two-stage Rosenbrock schemes with complex coefficients for numerical solution of autonomous systems of ordinary differential equations (ODE) has been considered. Numerical realization of such schemes requires one LU-decomposition, two computations of right side function and one computation of Jacoby matrix of the system per one step. The full theoretical investigation of accuracy and stability of such schemes have been done. New A-stable methods of the 3-rd order of accuracy with different properties have been constructed. There are high order L-decremented schemes as well as schemes with simple estimation of the main term of truncation error which is necessary for automatic evaluation of time step. Testing of new methods has been performed.

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

Difference of software development for parallel computing technology from sequential programming is dicussed. Arguements for introduction of new phases into technology of software engineering are given. These phases are: decomposition of algorithms, assignment of jobs to performers, conducting and mapping of logical to physical performers. Issues of performance evaluation of algorithms are briefly discussed. Decomposition of algorithms and programs into parts that can be executed in parallel is dicussed.

Данная работа посвящена сравнению двух критериев однородности: критерия χ², основанного на таблицах сопряженности признаков 2 × 2, и критерия однородности, основанного на асимптотических распределениях суммируемых квадратичных уклонений оценок функции распределения в модели зависимости «доза–эффект». Оценка мощности критериев производится при помощи компьютерного моделирования. Для построения функций эффективности используется метод ядерной оценки регрессии, основанный на оценке Надарая–Ватсона.

The given work is devoted to the comparison of two tests for homogeneity: chi-square test based on contingency tables of 2 × 2 and test for homogeneity based on asymptotic distributions of the summarized square error of a distribution function estimators in the model of ”dose–effect” dependence. The evaluation of test power is performed by means of computer simulation. In order to design efficiency functions the method of kernel regression estimator based on Nadaray–Watson estimator is used.