DECUHR: an algorithm for automatic integration of singular functions over a hyperrectangular region

We describe an automatic cubature algorithm for functions that have a singularity on the surface of the integration region. The algorithm combines an adaptive subdivision strategy with extrapolation. The extrapolation uses a non-uniform subdivision that can be directly incorporated into the subdivision strategy used for the adaptive algorithm. The algorithm is designed to integrate a vector function over ann-dimensional rectangular region and a FORTRAN implementation is included.Supported by the Norwegian Research Council for Science and the Humanities.     

Symbolic models for infinite networks of control systems: A compositional approach

This paper presents a compositional framework for the construction of symbolic models for a network composed of a countably infinite number of finite-dimensional discrete-time control subsystems. We refer to such a network as infinite network. The proposed approach is based on the notion of alternating simulation functions. This notion relates a concrete network to its symbolic model with guaranteed mismatch bounds between their output behaviors. We propose a compositional approach to construct a symbolic model for an infinite network, together with an alternating simulation function, by composing symbolic models and alternating simulation functions constructed for subsystems. Assuming that each subsystem is incrementally input-to-state stable and under some small-gain type conditions, we present an algorithm for orderly constructing local symbolic models with properly designed quantization parameters. In this way, the proposed compositional approach can provide us a guideline for constructing an overall symbolic model with any desired approximation accuracy. A compositional controller synthesis scheme is also provided to enforce safety properties on the infinite network in a decentralized fashion. The effectiveness of our result is illustrated through a road traffic network consisting of infinitely many road cells.     

Zur theorie rotierender und schwingender schaufelkränze in einer unterschallstromung durch einen ringkanal

In this paper the three-dimensional perturbation flow induced by a rotating and oscillating blade row which operates in a subsonic flow in axial direction of an annular channel is studied. The velocity potential is reduced to the infinite Hilbert space vector of Fourier coefficients of an eigen-function expansion with respect to vanishing normal derivatives on both cylinder walls. These coefficients satisfy an infinite set of ordinary differential equations of second order after an application of a one-dimensional Fourier transform in axial direction. Several canonical two-part mixed boundary value problems are then investigated by reduction to “infinite two-by-two-Wiener-Hopf functional systems”. In case of strong factorizability of certain matrix-operator-valued functions on the line these systems may be solved explicitely. Criteria for the factorization are not given here.     

A modified Hooke and Jeeves algorithm with likelihood ratio performance extrapolation for simulation optimization

The Hooke and Jeeves algorithm (HJ) is a pattern search procedure widely used to optimize non-linear functions that are not necessarily continuous or differentiable. The algorithm performs repeatedly two types of search routines; an exploratory search and a pattern search. The HJ algorithm requires deterministic evaluation of the function being optimized. In this paper we consider situations where the objective function is stochastic and can be evaluated only through Monte Carlo simulation. To overcome the problem of expensive use of function evaluations for Monte Carlo simulation, a likelihood ratio performance extrapolation (LRPE) technique is used. We extrapolate the performance measure for different values of the decision parameters while simulating a single sample path from the underlying system. Our modified Hooke and Jeeves algorithm uses a likelihood ratio performance extrapolation for simulation optimization. Computational results are provided to demonstrate the performance of the proposed modified HJ algorithm.     

Efficient and weakly efficient solutions for the vector topical optimization

In this paper, we consider some scalarization functions, which consist of the generalized min-type function, the so-called plus-Minkowski function and their convex combinations. We investigate the abstract convexity properties of these scalarization functions and use them to identify the maximal points of a set in an ordered vector space. Then, we establish some versions of Farkas type results for the infinite inequality system involving vector topical functions. As applications, we obtain the necessary and sufficient conditions of efficient solutions and weakly efficient solutions for a vector topical optimization problem, respectively.     

On Markovian decision programming with recursive reward functions

In this paper, the infinite horizon Markovian decision programming with recursive reward functions is discussed. We show that Bellman's optimal principle is applicable for our model. Then, a sufficient and necessary condition for a policy to be optimal is given. For the stationary case, an iteration algorithm for finding a stationary optimal policy is designed. The algorithm is a generalization of Howard's [7] and Iwamoto's [3] algorithms.This research was supported by the National Natural Science Foundation of China.     

The modular properties and the integral representations of the multiple elliptic gamma functions

We show the modular properties of the multiple “elliptic” gamma functions, which are an extension of those of the theta function and the elliptic gamma function. The modular property of the theta function is known as Jacobi's transformation, and that of the elliptic gamma function was provided by Felder and Varchenko. In this paper, we deal with the multiple sine functions, since the modular properties of the multiple elliptic gamma functions result from the equivalence between two ways to represent the multiple sine functions as infinite products.We also derive integral representations of the multiple sine functions and the multiple elliptic gamma functions. We introduce correspondences between the multiple elliptic gamma functions and the multiple sine functions.     

On the Vector ε-Algorithm for Solving Linear Systems of Equations

The four vector extrapolation methods, minimal polynomial extrapolation, reduced rank extrapolation, modified minimal polynomial extrapolation and the topological epsilon algorithm, when applied to linearly generated vector sequences are Krylov subspace methods and it is known that they are equivalent to some well-known conjugate gradient type methods. However, the vector -algorithm is an extrapolation method, older than the four extrapolation methods above, and no similar results are known for it. In this paper, a determinantal formula for the vector -algorithm is given. Then it is shown that, when applied to a linearly generated vector sequence, the algorithm is also a Krylov subspace method and for a class of matrices the method is equivalent to a preconditioned Lanczos method. A new determinantal formula for the CGS is given, and an algebraic comparison between the vector -algorithm for linear systems and CGS is also given.     

Hybrid vector transformations

We present in this paper hybrid and semi-hybrid vector extrapolation methods. For a vector sequence transformation, we will define the generalized residual which allows us to introduce a new hybrid vector transformation. When solving linear systems, this new transformation reduces to the hybrid procedure defined by Brezinski and Redivo Zaglia (1994) which is a generalization of the smoothing technique. In the second part of this paper, we define a new composite transformation called semi-hybrid. When applied to linearly generated sequences, we will show that the residual polynomial of the semi-hybrid transformation is the product of two residual polynomials.     

Soil-structure interaction of tunnel-structures under consideration of far- and near-field effects

The response of a tunnel structure under a moving and oscillating dynamic load can be calculated by means of a hybrid Integral–Transformation–Method–FEM approach. In the ITM approach analytical solutions of ideal geometries of the infinite continuum are superposed such that the wave–number impedance and transfer–function at the interior of a circular tunnel can be calculated efficiently. By this means the infinite continuum can be coupled to an arbitrary tunnel structure which is modelled by the FEM with corresponding form–functions. In order to reduce the effort for the coupling, the characteristics of the analytically given transfer–functions which can be split into near– and far–fields is taken into account. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Abel群的一些分解定理的推广(Ⅲ)

从主理想整环上有界模分解的Prüfer-Baer定理出发,研究(无限维)向量空间的代数的线性变换的几个基本问题,得到了如下结果:设V是域F上的(无限维)向量空间,A是V上的一个代数的线性变换,则有(1)若任何与A可交换的线性变换均与线性变换B可交换,则B=f(A),其中f是F上的多项式.进而线性变换B也是代数的.(2) V中存在一组基,使A在这组基下的矩阵是有理标准型(经典标准型)矩阵.当F是代数闭域时,经典标准型矩阵即为若当标准型矩阵.(3)当F是代数闭域时,A存在相应的Jordan-Chevalley分解.进一步,该结论在完全域上仍成立.这些研究推广了有限维向量空间上线性变换的相关结果.     

Policy iteration for robust nonstationary Markov decision processes

Policy iteration is a well-studied algorithm for solving stationary Markov decision processes (MDPs). It has also been extended to robust stationary MDPs. For robust nonstationary MDPs, however, an “as is” execution of this algorithm is not possible because it would call for an infinite amount of computation in each iteration. We therefore present a policy iteration algorithm for robust nonstationary MDPs, which performs finitely implementable approximate variants of policy evaluation and policy improvement in each iteration. We prove that the sequence of cost-to-go functions produced by this algorithm monotonically converges pointwise to the optimal cost-to-go function; the policies generated converge subsequentially to an optimal policy.     

New maximum entropy-based algorithm for structural design optimization

A new algorithm based on nonlinear transformation is proposed to improve the classical maximum entropy method and solve practical problems of reliability analysis. There are three steps in the new algorithm. Firstly, the performance function of reliability analysis is normalized, dividing by its value when each input is the mean value of the corresponding random variable. Then the nonlinear transformation of such normalized performance function is completed by using a monotonic nonlinear function with an adjustable parameter. Finally, the predictions of probability density function and/or the failure probability in reliability analysis are achieved by looking the result of transformation as a new form of performance function in the classical procedure of maximum entropy method in which the statistic moments are given through the univariate dimension reduction method. In the proposed method, the uncontrollable error of integration on the infinite interval is removed by transforming it into a bounded one. Three typical nonlinear transformation functions are studied and compared in the numerical examples. Comparing with results from Monte Carlo simulation, it is found that a proper choice of the adjustable parameter can lead to a better result of the prediction of failure probability. It is confirmed in the examples that result from the proposed method with the arctangent transformation function is better than the other transformation functions. The error of prediction of failure probability is controllable if the adjustable parameter is chosen in a given interval, but the suggested value of the adjustable parameter can only be given empirically.     

Split common fixed point and common null point problem

In this paper, we present a new algorithm for solving the split common null point and common fixed point problem, to find a point that belongs to the common element of common zero points of an infinite family of maximal monotone operators and common fixed points of an infinite family of demicontractive mappings such that its image under a linear transformation belongs to the common zero points of another infinite family of maximal monotone operators and its image under another linear transformation belongs to the common fixed point of another infinite family of demicontractive mappings in the image space. We establish strong convergence for the algorithm to find a unique solution of the variational inequality, which is the optimality condition for the minimization problem. As special cases, we shall use our results to study the split equilibrium problems and the split optimization problems.     

On improving the absolute stability of local extrapolation

Summary A widely used technique for improving the accuracy of solutions of initial value problems in ordinary differential equations is local extrapolation. It is well known, however, that when using methods appropriate for solving stiff systems of ODES, the stability of the method can be seriously degraded if local extrapolation is employed. This is due to the fact that performing local extrapolation on a low order method is equivalent to using a higher order formula and this high order formula may not be suitable for solving stiff systems. In the present paper a general approach is proposed whereby the correction term added on in the process of local extrapolation is in a sense a rational, rather than a polynomial, function. This approach allows high order formulae with bounded growth functions to be developed. As an example we derive anA-stable rational correction algorithm based on the trapezoidal rule. This new algorithm is found to be efficient when low accuracy is requested (say a relative accuracy of about 1%) and its performance is compared with that of the more familiar Richardson extrapolation method on a large set of stiff test problems.     

On the adaptive control of a class of partially observed Markov decision processes

This paper is concerned with the adaptive control problem, over the infinite horizon, for partially observable Markov decision processes whose transition functions are parameterized by an unknown vector. We treat finite models and impose relatively mild assumptions on the transition function. Provided that a sequence of parameter estimates converging in probability to the true parameter value is available, we show that the certainty equivalence adaptive policy is optimal in the long-run average sense.     

Numerical treatment of a twisted tail using extrapolation methods

Highly oscillatory integral, called a twisted tail, is proposed as a challenge in The SIAM 100-digit challenge. A Study in High-Accuracy Numerical Computing, where Drik Laurie developed numerical algorithms based on the use of Aitken’s Δ²-method, complex integration and transformation to a Fourier integral. Another algorithm is developed by Walter Gautschi based on Longman’s method; Newton’s method for solving a nonlinear equation; Gaussian quadrature; and the epsilon algorithm of Wynn for accelerating the convergence of infinite series. In the present work, nonlinear transformations for improving the convergence of oscillatory integrals are applied to the integration of this wildly oscillating function. Specifically, the transformation and its companion the W algorithm, and the G transformation are all used in the analysis of the integral. A Fortran program is developed employing each of the methods, and accuracies of up to 15 correct digits are reached in double precision.     

A Post-Optimality Analysis Algorithm for Multi-Objective Optimization

Algorithms for multi-objective optimization problems are designed to generate a single Pareto optimum (non-dominated solution) or a set of Pareto optima that reflect the preferences of the decision-maker. If a set of Pareto optima are generated, then it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optima using an unbiased technique of filtering solutions. This suggests the need for an efficient selection procedure to identify such a preferred subset that reflects the preferences of the decision-maker with respect to the objective functions. Selection procedures typically use a value function or a scalarizing function to express preferences among objective functions. This paper introduces and analyzes the Greedy Reduction (GR) algorithm for obtaining subsets of Pareto optima from large solution sets in multi-objective optimization. Selection of these subsets is based on maximizing a scalarizing function of the vector of percentile ordinal rankings of the Pareto optima within the larger set. A proof of optimality of the GR algorithm that relies on the non-dominated property of the vector of percentile ordinal rankings is provided. The GR algorithm executes in linear time in the worst case. The GR algorithm is illustrated on sets of Pareto optima obtained from five interactive methods for multi-objective optimization and three non-linear multi-objective test problems. These results suggest that the GR algorithm provides an efficient way to identify subsets of preferred Pareto optima from larger sets.     

On the optimal error of algorithms for solving a scalar autonomous ode

We study the error of algorithms for solving an initial value problem for a scalar autonomous differential equation. We show that the minimal error of an algorithm using the values of the righthand side function and/or its derivatives atm points is of orderm ^–r for functions with boundedr ^th derivative and bounded support and is infinite for functions with non-bounded support. The asymptotic optimality of the Taylor algorithm is shown and the complexity of the problem is discussed.     

Equivariant perturbation in Gomory and Johnson’s infinite group problem—III: foundations for the k-dimensional case with applications to $$ $$

We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, we present the general regular solution to Cauchy’s additive functional equation on restricted lower-dimensional convex domains. This provides a k-dimensional generalization of the so-called Interval Lemma, allowing us to deduce affine properties of the function from certain additivity relations. Next, we study the discrete geometry of additivity domains of piecewise linear functions, providing a framework for finite tests of minimality and extremality. We then give a theory of non-extremality certificates in the form of perturbation functions. We apply these tools in the context of minimal valid functions for the two-dimensional infinite group problem that are piecewise linear on a standard triangulation of the plane, under a regularity condition called diagonal constrainedness. We show that the extremality of a minimal valid function is equivalent to the extremality of its restriction to a certain finite two-dimensional group problem. This gives an algorithm for testing the extremality of a given minimal valid function.