Multiheuristic approach to discrete optimization problems

In this paper, some heuristic decision-making techniques (methods) are considered that are used in various discrete optimization problems. The objective of each of these problems is the construction of anytime algorithms. The considered methods for solving these problems are constructed on the basis of a combination of some heuristics that belong to different areas of the theory of artificial intelligence. A brief variant of the present article is presented in [1]. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 32–42, May–June 2006.     

Analysis of a class of easily computable permutations

Properties of easily computable permutations specified in terms of a finite ring are investigated. It is established that problems of parametric identification for this class of permutations are reduced to the resolution of systems of Diophantine equations of sufficiently high degree and to the solution of systems of problems of taking discrete logarithms. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 12–24, September–October 2008.     

Identification Problem for Matrix-Functional Systems

Identification problems for the kernel of a functional transformation of a static input vector into a discrete and time-continuous output vector function based on a given number of observations are solved for data-dependent system inputs. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 99–110, September–October 2005.     

Quantum model of computations: Underlying principles and achievements

A quantum Turing machine is considered. A review of basic methodological principles and achievements in the field of quantum computations is given. Some problems of construction of correct quantum computations and their complexity are considered. The result of P. Shor concerning the solution of the problems of taking discrete logarithms in polynomial time relative to the length of numbers is considered in detail. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 58–76, January–February, 2000.     

An approach to solving discrete vector optimization problems over a combinatorial set of permutations

Complex discrete multicriteria problems over a combinatorial set of permutations are analyzed. Some properties of an admissible domain for a combinatorial multicriteria problem embedded into an arithmetic Euclidian space are considered. Optimality conditions are obtained for different types of effective solutions. A new approach to solving the problems formulated is constructed and substantiated. This work was supported by the Fundamental Research Fund of Ukraine (project Φ251/094). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 158–172, May–June 2008.     

General solution of terminal control and observation problems

Mathematical problems of construction of general solutions for terminal control and observation problems are considered. The conditions of existence of a general solution of these problems for linear dynamic systems with a continuous and discrete argument are given. The study was carried out with the support of the Ukrainian Scientific and Technical Center (project No. 545) and the State Fund for Fundamental Research of Ukraine (project No. 1.4/369). Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 80–89, March–April, 2000.     

Moving Mesh Finite Element Methods for an Optimal Control Problem for the Advection-Diffusion Equation

An optimal control problem for the advection-diffusion equation is studied using a Lagrangian-moving mesh finite element method. The weak formulation of the model advection–diffusion equation is based on Lagrangian coordinates, and semi–discrete (in space) error estimates are derived under minimal regularity assumptions. In addition, using these estimates and Brezzi-Rappaz-Raviart theory, symmetric error estimates for the optimality system are derived. The results also apply for advection dominated problems     

A Nonoverlapping Domain Decomposition Method for Legendre Spectral Collocation Problems

We consider the Dirichlet boundary value problem for Poisson’s equation in an L-shaped region or a rectangle with a cross-point. In both cases, we approximate the Dirichlet problem using Legendre spectral collocation, that is, polynomial collocation at the Legendre–Gauss nodes. The L-shaped region is partitioned into three nonoverlapping rectangular subregions with two interfaces and the rectangle with the cross-point is partitioned into four rectangular subregions with four interfaces. In each rectangular subregion, the approximate solution is a polynomial tensor product that satisfies Poisson’s equation at the collocation points. The approximate solution is continuous on the entire domain and its normal derivatives are continuous at the collocation points on the interfaces, but continuity of the normal derivatives across the interfaces is not guaranteed. At the cross point, we require continuity of the normal derivative in the vertical direction. The solution of the collocation problem is first reduced to finding the approximate solution on the interfaces. The discrete Steklov–Poincaré operator corresponding to the interfaces is self-adjoint and positive definite with respect to the discrete inner product associated with the collocation points on the interfaces. The approximate solution on the interfaces is computed using the preconditioned conjugate gradient method. A preconditioner is obtained from the discrete Steklov–Poincaré operators corresponding to pairs of the adjacent rectangular subregions. Once the solution of the discrete Steklov–Poincaré equation is obtained, the collocation solution in each rectangular subregion is computed using a matrix decomposition method. The total cost of the algorithm is O(N ³), where the number of unknowns is proportional to N ².      

Stability and regularization of the lexicographic vector problem of quadratic discrete programming

The paper studies the bounds of variation of input parameters for a vector quadratic discrete optimization problem, which do not expand the set of lexicographic optima. A stability criterion is described and a regularization method is presented, which makes it possible to pass from a possibly unstable problem to a series of perturbed stable problems with a previous set of lexicographic optima. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 54–62, March–April, 2000.     

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.     

Deriving a discrete approximate solution for a nonlinear dynamic system of two-phase soil media

A discrete approximate generalized solution is derived for a nonlinear differential model of the dynamics of two-phase soil media and its convergence is estimated for the corresponding generalized solution in the space W ₂ ¹ (Ω). Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 69–80, July–August 2009     

Method of empirical means in stochastic programming problems

This paper deals with the empirical mean method, which is one of the most well-known methods of solving stochastic programming problems. The authors present their results obtained in recent years and discuss their application to estimation and identification problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 3–18, November–December 2006.     

Splines in Higher Order TV Regularization

Splines play an important role as solutions of various interpolation and approximation problems that minimize special functionals in some smoothness spaces. In this paper, we show in a strictly discrete setting that splines of degree m−1 solve also a minimization problem with quadratic data term and m-th order total variation (TV) regularization term. In contrast to problems with quadratic regularization terms involving m-th order derivatives, the spline knots are not known in advance but depend on the input data and the regularization parameter λ. More precisely, the spline knots are determined by the contact points of the m–th discrete antiderivative of the solution with the tube of width 2λ around the m-th discrete antiderivative of the input data. We point out that the dual formulation of our minimization problem can be considered as support vector regression problem in the discrete counterpart of the Sobolev space W _2,0 ^m . From this point of view, the solution of our minimization problem has a sparse representation in terms of discrete fundamental splines.     

Formulation and analysis of problems for dynamic systems of inhomogeneous two-phase media

A mixed initial—boundary-value problem with a discontinuous solution for a system of dynamic equations of water-saturated soil consolidation is analyzed. The classical solution is proved to be unique. Error estimates are obtained for time-continuous and fully discrete approximate generalized solutions constructed by the finite-element method. The study was sponsored by the State Fund for Basic Research (GFFI), Grant No. F7/307-2001. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 85–100, November–December 2005.     

A nonconforming finite element method¶with anisotropic mesh grading¶for the incompressible Navier–Stokes equations¶in domains with edges

Any solution of the incompressible Navier–Stokes equations in three-dimensional domains with edges has anisotropic singular behaviour which is treated numerically by using anisotropic finite element meshes. The velocity is approximated by Crouzeix–Raviart (nonconforming 𝒫₁) elements and the pressure by piecewise constants. This method is stable for general meshes since the inf-sup condition is satisfied without minimal or maximal angle condition. The existence of solutions to the discrete problems follows. Consistency error estimates for the divergence equation are obtained for anisotropic tensor product meshes. As applications, the consistency error estimate for the Navier–Stokes solution and some discrete Sobolev inequalities are derived on such meshes. These last results provide optimal error estimates in the uniqueness case by the use of appropriately refined anisotropic tensor product meshes, namely, if N _e is the number of elements of the mesh, we prove that the optimal order of convergence h∼ N _e ^{− 1/3}. Received:July 2001 / Accepted: July 2002     

Pricing Multi-Asset American Options: A Finite Element Method-of-Lines with Smooth Penalty

This paper studies the problem of pricing multi-asset American-style options in the Black–Scholes–Merton framework. The value function of an option contract is known to satisfy a partial differential variational inequality (PDVI) when early exercise is permitted. We develop a computational method for the valuation of multi-asset American-style options based on approximating the PDVI by a non-linear penalized PDE with a penalty term with continuous Jacobian. We convert the non-linear PDE to a variational (weak) form, discretize the weak formulation spatially by a Galerkin finite element method to obtain a system of ODEs, and integrate the resulting system of ODEs in time with an adaptive variable order and variable step size solver SUNDIALS. Numerical results demonstrate that employing a penalty term with continuous Jacobian in contrast to the penalty terms with discontinuous Jacobians in use in the literature improves computational performance of the adaptive temporal integrator. In our framework we are able to price American-style options with payoffs dependent on up to six assets on a PC. This is in contrast to the existing literature on the pricing of American options by PDE methods, that has so far been limited to at most three-dimensional problems. Our results open avenues for further applications to multi-dimensional problems, such as pricing convertible bonds in multi-factor models, that will be explored in future work. This research was supported by the National Science Foundation under grants DMI–0422937 and DMI–0422985.     

To bee or not to bee—comments on “Discrete optimum design of truss structures using artificial bee colony algorithm”

An Artificial Bee Colony algorithm was presented by Sonmez (Struct Multidisc Optim 43:85–97, 2011) for solving discrete truss design problems. It was numerically tested on four benchmark examples and concluded to be robust and efficient. We compare the Artificial Bee Colony algorithm numerically to three alternative heuristics on the same benchmark examples. The most advanced heuristics presented herein find equally good, or better, designs compared to those presented in Sonmez (Struct Multidisc Optim 43:85–97, 2011). However, for the largest benchmark example, we use four orders of magnitude fewer function evaluations.     

Fast parallel DNA-based algorithms for molecular computation: discrete logarithm

Diffie and Hellman (IEEE Trans. Inf. Theory 22(6):644–654, 1976) wrote the paper in which the concept of a trapdoor one-way function was first proposed. The Diffie–Hellman public-key cryptosystem is an algorithm that converts input data to an unrecognizable encryption, and converts the unrecognizable data back into its original decryption form. The security of the Diffie–Hellman public-key cryptosystem is based on the difficulty of solving the problem of discrete logarithms. In this paper, we demonstrate that basic biological operations can be applied to solve the problem of discrete logarithms. In order to achieve this, we propose DNA-based algorithms that formally verify our designed molecular solutions for solving the problem of discrete logarithms. Furthermore, this work indicates that public-key cryptosystems based on the difficulty of solving the problem of discrete logarithms are perhaps insecure.     

State estimation and filtering in stochastic systems using adequate simplification

The method of order reduction in solving stochastic problems of state estimation and filtering is considered. The method presented concerns the case where mathematical models of objects being studied are defined by systems of nonstationary differential equations. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 98–102, September–October, 1999.