On evaluation of the blocking probability in multiwave time division multiplexing networks

A new technique of estimating the blocking probability in multiwave time division multiplexing networks is proposed. The technique is based on solution of combinatorial problems of calculating the number of compositions with bounded parts.     

Unbiased estimates for gradients of stochastic network performance measures

Three classes of stochastic networks and their performance measures are considered. These performance measures are defined as the expected value of some random variables and cannot normally be obtained analytically as functions of network parameters in a closed form. We give similar representations for the random variables to provide a useful way of analytical study of these functions and their gradients. The representations are used to obtain sufficient conditions for the gradient estimates to be unbiased. The conditions are rather general and usually met in simulation study of the stochastic networks. Applications of the results are discussed and some practical algorithms of calculating unbiased estimates of the gradients are also presented.     

Solution of a Multidimensional Tropical Optimization Problem Using Matrix Sparsification

A complete solution is proposed for the problem of minimizing a function defined on vectors with elements in a tropical (idempotent) semifield. The tropical optimization problem under consideration arises, for example, when we need to find the best (in the sense of the Chebyshev metric) approximate solution to tropical vector equations and occurs in various applications, including scheduling, location, and decision-making problems. To solve the problem, the minimum value of the objective function is determined, the set of solutions is described by a system of inequalities, and one of the solutions is obtained. Thereafter, an extended set of solutions is constructed using the sparsification of the matrix of the problem, and then a complete solution in the form of a family of subsets is derived. Procedures that make it possible to reduce the number of subsets to be examined when constructing the complete solution are described. It is shown how the complete solution can be represented parametrically in a compact vector form. The solution obtained in this study generalizes known results, which are commonly reduced to deriving one solution and do not allow us to find the entire solution set. To illustrate the main results of the work, an example of numerically solving the problem in the set of three-dimensional vectors is given.     

Using tropical optimization to solve minimax location problems with a rectilinear metric on the line

Methods of tropical (idempotent) mathematics are applied to the solution of minimax location problems under constraints on the feasible location region. A tropical optimization problem is first considered, formulated in terms of a general semifield with idempotent addition. To solve the optimization problem, a parameter is introduced to represent the minimum value of the objective function, and then the problem is reduced to a parametrized system of inequalities. The parameter is evaluated using existence conditions for solutions of the system, whereas the solutions of the system for the obtained value of the parameter are taken as the solutions of the initial optimization problem. Then, a minimax location problem is formulated to locate a single facility on a line segment in the plane with a rectilinear metric. When no constraints are imposed, this problem, which is also known as the Rawls problem or the messenger boy problem, has known geometric and algebraic solutions. For the location problems, where the location region is restricted to a line segment, a new solution is obtained, based on the representation of the problems in the form of the tropical optimization problem considered above. Explicit solutions of the problems for various positions of the line are given both in terms of tropical mathematics and in the standard form.     

Growth rate of the state vector in a generalized linear stochastic system with a symmetric matrix

The mean growth rate of the state vector is evaluated for a generalized linear stochastic second-order system with a symmetric matrix. Diagonal entries of the matrix are assumed to be independent and exponentially distributed with different means, while the off-diagonal entries are equal to zero. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 341, 2007, pp. 134–141.     

Identification of Parameters of Nonlinear Dynamical Systems Simulated by Volterra Polynomials

We study the identification methods for the nonlinear dynamical systems described by Volterra series. One of the main problems in the dynamical system simulation is the problem of the choice of the parameters allowing the realization of a desired behavior of the system. If the structure of the model is identified in advance, then the solution to this problem closely resembles the identification problem of the system parameters. We also investigate the parameter identification of continuous and discrete nonlinear dynamical systems. The identification methods in the continuous case are based on application of the generalized Borel Theorem in combination with integral transformations. To investigate discrete systems, we use a discrete analog of the generalized Borel Theorem in conjunction with discrete transformations. Using model examples, we illustrate the application of the developed methods for simulation of systems with specified characteristics.     

Calculating the mean growth rate of the vector of states of a stochastic system with synchronization of events

A stochastic dynamical system with synchronization is considered. The dynamics of the system is described by a linear vector equation with a second-order matrix in an idempotent semiring with the operations of taking maximum and addition. It is assumed that one diagonal entry of the matrix is an exponentially distributed random variable, whereas all other entries are equal to some nonnegative constant. To solve the problem of calculating the mean rate of growth of the state vector of the system, we make a change of variables: instead of the random coordinates of the state vector of the system we introduce new random variables which are more convenient to analyze. After that, the corresponding sequences of one-dimensional distribution functions are constructed and examined for convergence. The mean rate of growth is calculated as the mean value of the limit distribution. In addition, expressions for the limit probabilities of some events in the systems are derived.     

Rank-One Approximation of Positive Matrices Based on Methods of Tropical Mathematics

Low-rank matrix approximation finds wide application in the analysis of big data, in recommendation systems on the Internet, for the approximate solution of some equations of mechanics, and in other fields. In this paper, a method for approximating positive matrices by rank-one matrices on the basis of minimization of log-Chebyshev distance is proposed. The problem of approximation reduces to an optimization problem having a compact representation in terms of an idempotent semifield in which the operation of taking the maximum plays the role of addition and which is often referred to as max-algebra. The necessary definitions and preliminary results of tropical mathematics are given, on the basis of which the solution of the original problem is constructed. Using the methods and results of tropical optimization, all positive matrices at which the minimum of approximation error is reached are found in explicit form. A numerical example illustrating the application of the rank-one approximation is considered.     

An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem

An extremal property of the eigenvalue of an irreducible matrix in idempotent algebra is studied. It is shown that this value is the minimum value of some functional defined using this matrix on the set of vectors with nonzero components. The minimax problem of location of a single facility (the Rawls problem) on a plane with rectilinear distance is considered. For this problem, we give the corresponding representation in terms of idempotent algebra and suggest a new algebraic solution, which is based on the results of investigation of the extremal property of eigenvalue and reduces to finding the eigenvalue and eigenvectors of a certain matrix.     

Evaluation of the growth rate of the state vector in a second-order generalized linear stochastic system

A second-order generalized linear stochastic dynamical system is considered. The entries of the system matrix are assumed to be independent and exponentially distributed. Evaluation of the growth rate of the system state vector is reduced to algebraic computations which involve solving an algebraic linear system and evaluating a linear functional for the solution.