Solving optimization problems with linear-fractional objective functions and additional constraints on arrangements

The paper proposes an exact method to solve an optimization problem on arrangements with a linear-fractional objective function and additional linear constraints. The efficiency of the solution algorithm is analyzed by means of numerical experiments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 79–85, September–October 2006.     

Modeling convection–diffusion processes based on a multidimensional integro-differential equation with degenerate parabolicity

An initial–boundary-value problem for a multidimensional integro-differential equation with degenerate parabolicity is considered. Based on the maximum-principle theorem and splitting method, a nonlinear monotonic high-order (higher than the first) numerical scheme is constructed for an implicit two-layer scheme. For the error of a numerical solution, a priori estimates are obtained and the sufficient convergence conditions are proved. A posteriori estimates for the numerical error of the solution are analyzed. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 83–96, March–April 2009.     

Analysis of an algorithm for solution of conditional optimization problems with linear-fractional objective functions over permutations

A method is considered to solve a conditional optimization problem with a linear-fractional objective function over permutations. The performance of sub algorithms to solve this problem is evaluated. The practical efficiency of the algorithm is analyzed by conducting numerical experiments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 133–146, July–August 2007.     

A method for numerical solution of a multidimensional convection-diffusion problem

We propose a modification of the additive splitting algorithm to solve the convection-diffusion problem using an efficient finite-difference scheme. The modification decreases the number of data exchanges and their amount during the numerical solution of a system of multidimensional equations. Approximation, stability, and convergence are considered. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 100–107, January–February 2009.     

The quasi-newtonian method of solution of convex variational inequalities with descent decomposition

The problem of numerical solution of convex variational inequalities with nonlinear constraints is considered. An equivalent optimization problem is constructed. To solve it, a Newtonian-type method with descent decomposition with respect to direct and dual variables of a variational inequality is developed. The nonlocal convergence of the algorithm and the superlinear rate of convergence in a neighborhood of the solution are proved. Translated from Kibemetika i Sistemnyi Analiz, No. 4, pp. 90–105, July–August, 1999.     

On Parabolic Boundary Layers for Convection–Diffusion Equations in a Channel: Analysis and Numerical Applications

In this article we discuss singularly perturbed convection–diffusion equations in a channel in cases producing parabolic boundary layers. It has been shown that one can improve the numerical resolution of singularly perturbed problems involving boundary layers, by incorporating the structure of the boundary layers into the finite element spaces, when this structure is available; see e.g. [Cheng, W. and Temam, R. (2002). Comput. Fluid. V.31, 453–466; Jung, C. (2005). Numer. Meth. Partial Differ. Eq. V.21, 623–648]. This approach is developed in this article for a convection–diffusion equation. Using an analytical approach, we first derive an approximate (simplified) form of the parabolic boundary layers (elements) for our problem; we then develop new numerical schemes using these boundary layer elements. The results are performed for the perturbation parameter ε in the range 10⁻¹–10⁻¹⁵ whereas the discretization mesh is in the range of order 1/10–1/100 in the x-direction and of order 1/10–1/30 in the y-direction. Indications on various extensions of this work are briefly described at the end of the Introduction.Dedicated to David Gottlieb on his 60th birthday.     

Metaheuristic downhill simplex method in combinatorial optimization

The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented. The study was supported by INTAS (Project 06-1000017-8909). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–79, November–December 2007.     

Solvability problems for ND-systems

Insolubility of the equivalence problem is proved for nondeterminate normalized finite transducers, which have two states (one input symbol and two output symbols) and can read no more than one input symbol in one step. Translated from Kibernetika i Sistemnyi Analiz, No, 2, pp. 164–167, March–April, 2000.     

Regularization of a lexicographic vector problem of integer programming

A stability criterion for a vector integer linear problem of lexicographic optimization is obtained. A regularization method is proposed that allows us to reduce a possible unstable output problem to a sequence of perturbed stable equivalent problems. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 125–130, November–December, 1999.     

Realization of a bounded feedback in a nonlinear control problem

We substantiate a method for design of a limited feedback to control a system whose mathematical model includes a nonlinear state function. Designing such a feedback is based on a positional solution of auxiliary optimal control problems which provides the transition from the vicinity of one equilibrium state to the vicinity of a new equilibrium state and stabilization of the system in the new state. Preassigned additional constrains on the trajectory of the control system are satisfied. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 108–116, January–February 2009.     

Stability of a combinatorial vector partition problem

The vector variant of the partition problem is considered. It is shown that the coincidence of the Pareto and Slater sets is the necessary and sufficient condition of stability of the problem with respect to its functional. __________ Translated from Kibernetika i Sistemny i Analiz, No. 3, pp. 177–181, May–June 2007.     

An approach to solution uniqueness in game problems

A new concept of strong conflict equilibrium is proposed that supplements the well-known fundamental system of conflict equilibria and considerably increases the possibility of finding a unique strongest equilibrium (solution) in any game problem. The efficiency of this new equilibrium is illustrated by static and dynamic game problems. This work was carried out under the program “Basic foundations of information technologies and systems” of the Russian Academy of Science (Project No. 1–3). Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 116–127, March–April 2009.     

Mortality problem and affine automata

The mortality problem for 2×2 matrices is treated from the automata theory viewpoint. This problem is shown to be closely related to the reachability problem for linear and affine automata of low dimensions. The decidability of the reachability problem is proved for some subclasses of one-dimensional affine automata. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 24–29, March–April 2008.     

A Numerical Comparison of the Lax–Wendroff Discontinuous Galerkin Method Based on Different Numerical Fluxes

Discontinuous Galerkin (DG) method is a spatial discretization procedure, employing useful features from high-resolution finite volume schemes, such as the exact or approximate Riemann solvers serving as numerical fluxes and limiters. In [(2005). Comput. Methods Appl. Mech. Eng. 194, 4528], we developed a Lax–Wendroff time discretization procedure for the DG method (LWDG), an alternative method for time discretization to the popular total variation diminishing (TVD) Runge–Kutta time discretizations. In most of the DG papers in the literature, the Lax–Friedrichs numerical flux is used due to its simplicity, although there are many other numerical fluxes, which could also be used. In this paper, we systematically investigate the performance of the LWDG method based on different numerical fluxes, including the first-order monotone fluxes such as the Godunov flux, the Engquist–Osher flux, etc., the second-order TVD fluxes and generalized Riemann solver, with the objective of obtaining better performance by choosing suitable numerical fluxes. The detailed numerical study is mainly performed for the one-dimensional system case, addressing the issues of CPU cost, accuracy, non-oscillatory property, and resolution of discontinuities. Numerical tests are also performed for two-dimensional systems.      

Boolean problem of sequential minimization of moduli of linear functions and stability theorems

A multicriterion Boolean problem of lexicographic optimization with partial criteria represented by moduli (absolute values) of linear functions is considered. Five types of stability of a set of lexicographic optima under “small” variations in the parameters of a vector criterion are investigated. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 178–187, September–October 2007.     

Algebraic Fractional-Step Schemes for Time-Dependent Incompressible Navier–Stokes Equations

The numerical investigation of a recent family of algebraic fractional-step methods (the so called Yosida methods) for the solution of the incompressible time-dependent Navier–Stokes equations is presented. A comparison with the Karniadakis–Israeli–Orszag method Karniadakis et al. (1991, J. Comput. Phys. 97, 414–443) is carried out. The high accuracy in time of these schemes well combines with the high accuracy in space of spectral methods.     

An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing

Summary The discrete Laplace–Beltrami operator plays a prominent role in many digital geometry processing applications ranging from denoising to parameterization, editing, and physical simulation. The standard discretization uses the cotangents of the angles in the immersed mesh which leads to a variety of numerical problems. We advocate the use of the intrinsic Laplace–Beltrami operator. It satisfies a local maximum principle, guaranteeing, e.g., that no flipped triangles can occur in parameterizations. It also leads to better conditioned linear systems. The intrinsic Laplace–Beltrami operator is based on an intrinsic Delaunay triangulation of the surface. We detail an incremental algorithm to construct such triangulations together with an overlay structure which captures the relationship between the extrinsic and intrinsic triangulations. Using a variety of example meshes we demonstrate the numerical benefits of the intrinsic Laplace–Beltrami operator.     

The Performance of German Firms in the Business-Related Service Sectors Revisited: Differential Evolution Markov Chain Estimation of the Multinomial Probit Model

We outline a new estimation method for the multinomial probit model (MNP). The method is a differential evolution Markov chain algorithm that employs a Metropolis-within-Gibbs sampler with data augmentation and the Geweke–Hajivassiliou–Keane (GHK) probability simulator. The method lifts the curse of dimensionality in numerical integration as it neither requires simulation of the whole likelihood function nor the computation of its analytical or numerical derivatives. The method is applied to an unbalanced panel dataset of firms from the German business-related service sector over the period 1994–2000. In spite of its less restricted character, the MNP model is found not to provide more accurate estimates for explaining the performance of these firms than the multinomial logit model.     

Problems with conjugation conditions and their high-accuracy computational discretization algorithms

New classes of problems with discontinuous solutions are considered. The corresponding generalized problems are obtained. Numerical schemes, which are as asymptotically accurate as similar schemes for problems with smooth solutions, are proposed for the new classes of problems. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 100–124, November–December, 1999.     

A Dynamic Penalty or Projection Method for Incompressible Fluids

In a previous work (Angot et al. in J. Comput. Appl. Math. 226:228–245, 2009), some penalty–projection methods have been tested for the numerical analysis of the Navier-Stokes equations. The purpose of this study is to introduce a variant of the penalty–projection method which allows us to compute the solutions faster than by using the previous solver. This new variant combines dynamically and alternatively a penalty procedure and a projection procedure according to the size of the divergence of the velocity. In other words, this study aims to prove that it is possible to project the intermediate velocity, computed by the first step of the penalty–projection method, only if its divergence is larger than a specified threshold. Theoretical estimates for the new method are given, which are in accordance with the numerical results provided.