Publishing House SB RAS:

Publishing House SB RAS:

Address of the Publishing House SB RAS:
Morskoy pr. 2, 630090 Novosibirsk, Russia

Advanced Search

Siberian Journal of Numerical Mathematics

2019 year, number 2

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems

A.V. Kel'manov1,2, A.V. Panasenko1,2, V.I. Khandeev1,2
1Sobolev Institute of Mathematics, Novosibirsk, Russia, 630090
2Novosibirsk State University, Novosibirsk, Russia, 630090
Keywords: евклидово пространство, 2-кластеризация, наибольшее подмножество, NP-трудность, целочисленная задача, псевдополиномиальная разрешимость, Euclidean space, 2-clustering, largest subset, NP-hardness, exact algorithm, pseudo- polynomial-time solvability

Abstract >>
We consider two related discrete optimization problems of searching for a subset in a finite set of points in the Euclidean space. Both problems are induced by the versions of the fundamental problem in data analysis, namely, by selecting a subset of similar elements in a set of objects. In each problem, an input set and a positive real number are given, and it is required to find a cluster (i.e., a subset) of the largest size under constraints on the value of a quadratic clusterization function. The points in the input set which are outside the sought for subset are treated as the second (complementary) cluster. In the first problem, the function under the constraint is the sum over both clusters of the intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first (i.e., the sought) cluster is unknown and determined as the centroid, while the center of the second one is fixed at a given point in the Euclidean space (without loss of generality in the origin). In the second problem, the function under the constraint is the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. As in the first problem, the center of the first cluster is unknown and determined as the centroid, while the center of the second one is fixed in the origin. In this paper, we show that both problems are strongly NP-hard. Also, we present the exact algorithms for the cases of these problems in which the input points have integer components. If the space dimension is bounded by some constant, the algorithms are pseudopolynomial.

Automated identification system of conditions for homogeneous and heterogeneous reactions in multipurpose optimization problems

K.F. Koledina1,2, S.N. Koledin2, I.M. Gubaydullin1,2
1Institute of petrochemistry and catalysis RSA, Ufa, Russian Federation, 450075
2Ufa State Technological Petroleum University, Ufa, Russian Federation, 450062
Keywords: автоматизированная система идентификации условий проведения гомогенных и гетерогенных реакций, кинетическая модель, многоцелевая оптимизация, островная модель распараллеливания, декомпозиция автоматизированной системы, automated system for identification conditions for carrying out homogeneous and heterogeneous reactions, kinetic model, multipurpose optimization, island model of parallelization, decomposition of automated system

Abstract >>
An automated system for identifying the conditions of homogeneous and heterogeneous reactions includes mathematical modeling of a chemical reaction, determination of optimization criteria conditions for variable parameters, setting and multipurpose optimization problem solution and an optimal control problem, development of efficient algorithms for a computing experiment. Modeling and optimization of a homogeneous and heterogeneous catalytic reactions are carried out. Optimal conditions for carrying out reactions to achieve the specified criteria are determined.

A method of obtaining analytical solutions to boundary value problems based on defining additional boundary conditions and additional desired functions

I.V. Kudinov, E.V. Kotova, V.A. Kudinov
Samara State Technical University, Samara, Russia, 443100
Keywords: нестационарная теплопроводность, аналитическое решение, интегральный метод теплового баланса, дополнительные граничные условия, дополнительные искомые функции, фронт температурного возмущения, координатные функции, бесконечная скорость распространения теплоты, transient thermal conductivity, analytical solution, integral method of heat balance, additional boundary conditions, additional desired function, front of temperature perturbations, coordinate functions, infinite velocity of propagation of heat

Abstract >>
Using additional boundary conditions and additional unknown functions in the integral method of heat balance, we consider the method of obtaining analytical solutions to the thermal conductivity problem associated with the separation process of thermal conductivity of two phases with respect to time, which allows reducing the solution of partial differential equations to the integration of two ordinary differential equations for some additional desired functions. The first stage is characterized by a rapid convergence of the analytical solution to an exact one. For the second stage, the exact analytical solution has been obtained. Additional boundary conditions for both phases are in such a form that their execution by a desired solution be equivalent to realization of the original equation at boundary points and at a front of the temperature perturbations. It is shown that the implementation of the equations at the boundary points leads to its execution also inside the domain.

Two-grid methods for a new mixed finite element approximation of semilinear parabolic integro-differential equations

C. Liu1, T. Hou2
1Institute of Computational Mathematics, Yongzhou 425100, Hunan, China
2School of Mathematics and Statistics, 132013, Jilin, China
Keywords: полулинейные параболические интегро-дифференциальные уравнения, новый смешанный метод конечных элементов, априорная оценка ошибки, двухсеточный, пространство квадратично интегрируемых функций, semilinear parabolic integro-differential equations, a new mixed finite element method, a priori error estimate, two-grid, space of square integrable functions

Abstract >>
In this paper, we present a two-grid scheme for a semilinear parabolic integro-differential equation using a new mixed finite element method. The gradient for the method belongs to the space of square integrable functions instead of the classical H (div;Ω) space. The velocity and the pressure are approximated by a P 02- P 1 pair which satisfies an inf-sup condition. Firstly, we solve the original nonlinear problem on the coarse grid in our two-grid scheme. Then, to linearize the discretized equations, we use Newton's iteration on the fine grid twice. It is shown that the algorithm can achieve an asymptotically optimal approximation as long as the mesh sizes satisfy h = O ( H 6 |ln H |2). As a result, solving such a large class of nonlinear equations will not be much more difficult than solving one linearized equation. Finally, a numerical experiment is provided to verify the theoretical results of the two-grid method.

Randomized algorithms of Monte Carlo method for problems with random parameters (“double randomization” method)

G.A. Mikhailov1,2
1Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk, 630090 Russia
2Novosibirsk State University, Novosibirsk, 630090 Russia
Keywords: вероятностная модель, статистическое моделирование, случайный параметр, рандомизированный алгоритм, метод двойной рандомизации, случайная среда, метод расщепления, статистическая ядерная оценка, probabilistic model, statistic modeling, random parameter, randomized algorithm, double randomization method, random medium, splitting method, statistic kernel estimator

Abstract >>
Randomized algorithms of Monte Carlo method are constructed by the combined realization of the base probabilistic model and its random parameters for investigation of the parametric distribution of linear functionals. The optimization of algorithms with the use of the statistical kernel estimator for the probability density is presented. The randomized projection algorithm for estimating a nonlinear functional distribution as applied to the investigation of criticality fluctuations for the particles multiplication process in a random medium is formulated.

An adaptive analog of Nesterov's method for variational inequalities with a strongly monotone operator

F.S. Stonyakin
V.I. Vernadsky Crimean Federal University, Simferopol, Russia, 295007
Keywords: вариационное неравенство, сильно монотонный оператор, адаптивный метод, условие Липшица, качество решения, variational inequality, strongly monotone operator, adaptive method, Lipschitz condition, solution quality

Abstract >>
An adaptive analog of the Nesterov method for variational inequalities with a strongly monotone operator is proposed. The main idea of the method proposed is the adaptive choice of constants in maximized concave functional at each iteration. In this case there is no need in specifying an exact value of this constant, because the method proposed makes possible to find a suitable constant at each iteration. Some estimates for the parameters determining the quality of the solution of the variational inequality depending on the number of iterations have been obtained.

Parameter-uniform numerical methods for a class of parameterized singular perturbation problems

D. Shakti, J. Mohapatra
National Institute of Technology, Rourkela, 769008, India
Keywords: параметризованная задача, сингулярные возмущения, граничный слой, обратный метод Эйлера, монотонная гибридная схема, parameterized problem, singular perturbation, boundary layer, backward Euler method, monotone hybrid scheme

Abstract >>
In this article, a weighted finite difference scheme is proposed for solving a class of parameterized singularly perturbed problems (SPPs). Depending upon the choice of the weight parameter, the scheme is automatically transformed from the backward Euler scheme to a monotone hybrid scheme. Three kinds of nonuniform grids are considered: a standard Shishkin mesh, a Bakhavalov-Shishkin mesh, and an adaptive grid. The methods are shown to be uniformly convergent with respect to the perturbation parameter for all three types of meshes. The rate of convergence is of first order for the backward Euler scheme and of second order for the monotone hybrid scheme. Furthermore, the proposed method is extended to a parameterized problem with mixed type boundary conditions and is shown to be uniformly convergent. Numerical experiments are carried out to show the efficiency of the proposed schemes, which indicate that the estimates are optimal.

Sensitivity of functionals to observation data in a variational assimilation problem for the sea thermodynamics model

V.P. Shutyaev1,2, E.I. Parmuzin1
1Institute of Numerical Mathematics, RAS, Moscow, 119333, Russia
2Marine Hydrophysical Institute of RAS, Sevastopol, 299011, Russia
Keywords: вариационное усвоение данных наблюдений, оптимальное управление, сопряженные уравнения, ковариационные матрицы, чувствительность функционалов, температура поверхности моря, variational data assimilation, optimal control, adjoint equations, covariance matrices, sensitivity of functionals, sea surface temperature

Abstract >>
For the mathematical model of the sea thermodynamics, developed in the Institute of Numerical Mathematics of the Russian Academy of Sciences, the problem of variational assimilation of the sea surface temperature data is considered, with allowance for the observation data error covariance matrices. Based on the variational assimilation of satellite observation data, the inverse problem of restoring a heat flux on the sea surface is solved. The sensitivity of functionals with respect to observation data in a problem of variational assimilation is studied, and the results of numerical experiments for the model of the Baltic Sea dynamics are presented.