Все выпуски

Предложено обобщение блочного клеточного автомата Марголуса на гексагональную сетку. Проведена статистическая обработка результатов вероятностных клеточно-автоматных вычислений для ряда модификаций схемы, решающей тестовую задачу диффузии вещества. Показано, что выбор блоков в виде гексагонов на 25% эффективнее, чем в виде Y-блоков. Показано, что алгоритмы имеют полиномиальную сложность, причем степень полинома для параллельных вычислителей лежит в пределах 0.6÷0.8, а для последовательных — в пределах 1.5÷1.7. Исследовалось влияние внедренных в поле клеточного автомата дефектных ячеек на скорость сходимости.

The generalization of Margolus’s block cellular automaton on a hexagonal grid is formulated. Statistical analysis of the results of probabilistic cellular automation for vast variety of this scheme solving the test task of diffusion is done. It is shown that the choice of the hexagon blocks is 25% more efficient than Y-blocks. It is shown that the algorithms have polynomial complexity, and the polynom degree lies within 0.6÷0.8 for parallel computer, and in the range 1.5÷1.7 for serial computer. The effects of embedded into automaton’s field defective cells on the rate of convergence are studied also.

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

$$ \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.

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

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

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.

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

Methods of the solution of a problem of focal approximation — approach on point-by-point given smooth closed empirical curve by multifocal lemniscates are investigated. Criteria and convergence of the developed approached methods with use of the description, both in real, and in complex variables are analyzed. Topological equivalence of the used criteria is proved.

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

The stationary flame spread rate has been calculated using the relationship based on the thermodynamic variational principle. It has been shown that proposed numerical algorithm provides the stable convergence under any initial approximation, which could be noticeably far from the searched solution.

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

We construct necessary and sufficient conditions for the existence of solution of seminonlinear matrix boundary value problem for a parametric excitation system of ordinary differential equations. The convergent iteration algorithms for the construction of the solutions of the semi-nonlinear matrix boundary value problem for a parametric excitation system differential equations in the critical case have been found. Using the convergent iteration algorithms we expand solution of seminonlinear periodical boundary value problem for a parametric excitation Riccati type equation in the neighborhood of the generating solution. Estimates for the value of residual of the solutions of the seminonlinear periodical boundary value problem for a parametric excitation Riccati type equation are found.

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

We present the iterative algorithm that solves numerically both Urysohn type Fredholm and Volterra nonlinear one-dimensional nonsingular integral equations of the second kind to a specified, modest user-defined accuracy. The algorithm is based on descending recursive sequence of quadratures. Convergence of numerical scheme is guaranteed by fixed-point theorems. Picard’s method of integrating successive approximations is of great importance for the existence theory of integral equations but surprisingly very little appears on numerical algorithms for its direct implementation in the literature. We show that successive approximations method can be readily employed in numerical solution of integral equations. By that the quadrature algorithm is thoroughly designed. It is based on the explicit form of fifth-order embedded Runge–Kutta rule with adaptive step-size self-control. Since local error estimates may be cheaply obtained, continuous monitoring of the quadrature makes it possible to create very accurate automatic numerical schemes and to reduce considerably the main drawback of Picard iterations namely the extremely large amount of computations with increasing recursion depth. Our algorithm is organized so that as compared to most approaches the nonlinearity of integral equations does not induce any additional computational difficulties, it is very simple to apply and to make a program realization. Our algorithm exhibits some features of universality. First, it should be stressed that the method is as easy to apply to nonlinear as to linear equations of both Fredholm and Volterra kind. Second, the algorithm is equipped by stopping rules by which the calculations may to considerable extent be controlled automatically. A compact C++-code of described algorithm is presented. Our program realization is self-consistent: it demands no preliminary calculations, no external libraries and no additional memory is needed. Numerical examples are provided to show applicability, efficiency, robustness and accuracy of our approach.

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

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

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

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

We consider a finite-dimensional optimization problem, the formulation of which in addition to the required variables contains parameters. The solution to this problem is a dependence of optimal values of variables on parameters. In general, these dependencies are not functions because they can have ambiguous meanings and in the functional case be nondifferentiable. In addition, their domain of definition may be narrower than the domains of definition of functions in the condition of the original problem. All these properties make it difficult to solve both the original parametric problem and other tasks, the statement of which includes these dependencies. To overcome these difficulties, usually methods such as non-differentiable optimization are used.

This article proposes an alternative approach that makes it possible to obtain solutions to parametric problems in a form devoid of the specified properties. It is shown that such representations can be explored using standard algorithms, based on the Taylor formula. This form is a function smoothly approximating the solution of the original problem for any parameter values, specified in its statement. In this case, the value of the approximation error is controlled by a special parameter. Construction of proposed approximations is performed using special functions that establish feedback (within optimality conditions for the original problem) between variables and Lagrange multipliers. This method is described for linear problems with subsequent generalization to the nonlinear case.

From a computational point of view the construction of the approximation consists in finding the saddle point of the modified Lagrange function of the original problem. Moreover, this modification is performed in a special way using feedback functions. It is shown that the necessary conditions for the existence of such a saddle point are similar to the conditions of the Karush – Kuhn – Tucker theorem, but do not contain constraints such as inequalities and conditions of complementary slackness. Necessary conditions for the existence of a saddle point determine this approximation implicitly. Therefore, to calculate its differential characteristics, the implicit function theorem is used. The same theorem is used to reduce the approximation error to an acceptable level.

Features of the practical implementation feedback function method, including estimates of the rate of convergence to the exact solution are demonstrated for several specific classes of parametric optimization problems. Specifically, tasks searching for the global extremum of functions of many variables and the problem of multiple extremum (maximin-minimax) are considered. Optimization problems that arise when using multicriteria mathematical models are also considered. For each of these classes, there are demo examples.

Численное решение системы уравнений высокотемпературной радиационной газовой динамики (ВРГД) является вычислительно трудоемкой задачей, так как взаимодействие излучения с веществом нелинейно и нелокально. Коэффициенты поглощения излучения зависят от температуры, а поле температур определяется как газодинамическими процессами, так и переносом излучения. Обычно для решения системы ВРГД используется метод расщепления по физическим процессам, выделяется блок решения уравнения переноса совместно с уравнением баланса энергии вещества при известных давлениях и температурах. Построенные ранее разностные схемы, используемые для решения этого блока, обладают порядками сходимости не выше второго. Так как даже на современном уровне развития вычислительной техники имеются ограничения по памяти, то для решения сложных технических задач приходится применять не слишком подробные сетки. Это повышает требования к порядку аппроксимации разностных схем. В данной работе впервые реализованы бикомпактные схемы высокого порядка аппроксимации для алгоритма совместного решения уравнения переноса излучения и уравнения баланса энергии. Предложенный метод может быть применен для решения широкого круга практических задач, так как обладает высокой точностью и подходит для решения задач с разрывами коэффициентов. Нелинейность задачи и использование неявной схемы приводит к итерационному процессу, который может медленно сходиться. В данной работе используется мультипликативный HOLO-алгоритм — метод квазидиффузии В.Я. Гольдина. Ключевая идея HOLO-алгоритмов состоит в совместном решении уравнений высокого порядка (high order, HO) и низкого порядка (low order, LO). Уравнением высокого порядка (HO) является уравнение переноса излучения, которое решается в многогрупповом приближении, далее уравнение осредняется по угловой переменной и получается система уравнений квазидиффузии в многогрупповом приближении (LO₁). Следующим этапом является осреднение по энергии, при этом получается эффективная одногрупповая система уравнений квазидиффузии (LO₂), которая решается совместно с уравнением энергии. Решения, получаемые на каждом этапе HOLO-алгоритма, оказываются тесно связанными, что в итоге приводит к ускорению сходимости итерационного процесса. Для каждого из этапов HOLO-алгоритма предложены разностные схемы, построенные методом прямых в рамках одной ячейки и обладающие четвертым порядком аппроксимации по пространству и третьим порядком по времени. Схемы для уравнения переноса были разработаны Б.В. Роговым и его коллегами, схемы для уравнений LO₁ и LO₂ разработаны авторами. Предложен аналитический тест, на котором демонстрируются заявленные порядки сходимости. Рассматриваются различные варианты постановки граничных условий и исследовано их влияние на порядок сходимости по времени и пространству.

The numerical solving of the system of high-temperature radiative gas dynamics (HTRGD) equations is a computationally laborious task, since the interaction of radiation with matter is nonlinear and non-local. The radiation absorption coefficients depend on temperature, and the temperature field is determined by both gas-dynamic processes and radiation transport. The method of splitting into physical processes is usually used to solve the HTRGD system, one of the blocks consists of a joint solving of the radiative transport equation and the energy balance equation of matter under known pressure and temperature fields. Usually difference schemes with orders of convergence no higher than the second are used to solve this block. Due to computer memory limitations it is necessary to use not too detailed grids to solve complex technical problems. This increases the requirements for the order of approximation of difference schemes. In this work, bicompact schemes of a high order of approximation for the algorithm for the joint solution of the radiative transport equation and the energy balance equation are implemented for the first time. The proposed method can be applied to solve a wide range of practical problems, as it has high accuracy and it is suitable for solving problems with coefficient discontinuities. The non-linearity of the problem and the use of an implicit scheme lead to an iterative process that may slowly converge. In this paper, we use a multiplicative HOLO algorithm named the quasi-diffusion method by V.Ya.Goldin. The key idea of HOLO algorithms is the joint solving of high order (HO) and low order (LO) equations. The high-order equation (HO) is the radiative transport equation solved in the energy multigroup approximation, the system of quasi-diffusion equations in the multigroup approximation (LO₁) is obtained by averaging HO equations over the angular variable. The next step is averaging over energy, resulting in an effective one-group system of quasi-diffusion equations (LO₂), which is solved jointly with the energy equation. The solutions obtained at each stage of the HOLO algorithm are closely related that ultimately leads to an acceleration of the convergence of the iterative process. Difference schemes constructed by the method of lines within one cell are proposed for each of the stages of the HOLO algorithm. The schemes have the fourth order of approximation in space and the third order of approximation in time. Schemes for the transport equation were developed by B.V. Rogov and his colleagues, the schemes for the LO₁ and LO₂ equations were developed by the authors. An analytical test is constructed to demonstrate the declared orders of convergence. Various options for setting boundary conditions are considered and their influence on the order of convergence in time and space is studied.

Алгоритмы сопряженных градиентов представляют собой важный класс алгоритмов безусловной оптимизации с хорошей локальной и глобальной сходимостью и скромными требованиями к памяти. Они занимают промежуточное место между методом наискорейшего спуска и методом Ньютона, поскольку требуют вычисленияи хранения только первых производных и как правило быстрее методов наискорейшего спуска. В данном исследовании рассмотрен новый подход в задаче восстановления изображений. Он наследует одновременно методу сопряженных градиентов Флетчера – Ривза (FR) и трехкомпонентному методу сопряженных градиентов (TTCG), и поэтому назван авторами гибридным трехкомпонентным методом сопряженных градиентов (HYCGM). Новое направление спуска в нем учитывает текущее направления градиента, предыдущее направления спуска и градиент из предыдущей итерации. Показано, что новый алгоритм обладает свойствами глобальной сходимости и монотонности при использовании неточного линейного поиска типа Вулфа при некоторых стандартных предположениях. Для подтверждения эффективности предложенного алгоритма приводятся результаты численных экспериментов предложенного метода в сравнении с классическим методом Флетчера – Ривза (FR) и трехкомпонентным методом Флетчера – Ривза (TTFR).

Conjugate gradient algorithms represent an important class of unconstrained optimization algorithms with strong local and global convergence properties and simple memory requirements. These algorithms have advantages that place them between the steep regression method and Newton’s algorithm because they require calculating the first derivatives only and do not require calculating and storing the second derivatives that Newton’s algorithm needs. They are also faster than the steep descent algorithm, meaning that they have overcome the slow convergence of this algorithm, and it does not need to calculate the Hessian matrix or any of its approximations, so it is widely used in optimization applications. This study proposes a novel method for image restoration by fusing the convex combination method with the hybrid (CG) method to create a hybrid three-term (CG) algorithm. Combining the features of both the Fletcher and Revees (FR) conjugate parameter and the hybrid Fletcher and Revees (FR), we get the search direction conjugate parameter. The search direction is the result of concatenating the gradient direction, the previous search direction, and the gradient from the previous iteration. We have shown that the new algorithm possesses the properties of global convergence and descent when using an inexact search line, relying on the standard Wolfe conditions, and using some assumptions. To guarantee the effectiveness of the suggested algorithm and processing image restoration problems. The numerical results of the new algorithm show high efficiency and accuracy in image restoration and speed of convergence when used in image restoration problems compared to Fletcher and Revees (FR) and three-term Fletcher and Revees (TTFR).