Home – Home – Jornals – Numerical Analysis and Applications 2019 number 2

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.

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.

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.

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 ₀²- P ₁ 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 ⁶ |ln H |²). 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 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 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.

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.

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.