Determination of the rank of an integration lattice

The continuing and widespread use of lattice rules for high-dimensional numerical quadrature is driving the development of a rich and detailed theory. Part of this theory is devoted to computer searches for rules, appropriate to particular situations. In some applications, one is interested in obtaining the (lattice) rank of a lattice rule Q(Λ) directly from the elements of a generator matrix B (possibly in upper triangular lattice form) of the corresponding dual lattice Λ^⊥. We treat this problem in detail, demonstrating the connections between this (lattice) rank and the conventional matrix rank deficiency of modulo p versions of B. AMS subject classification (2000) 65D30     

Construction algorithms for polynomial lattice rules for multivariate integration

We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.

     

Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration

In this paper we study quasi-Monte Carlo integration of smooth functions using digital nets. We fold digital nets over ${\mathbb{Z}}_b$ by means of the $b$-adic tent transformation, which has recently been introduced by the authors, and employ such folded digital nets as quadrature points. We first analyze the worst-case error of quasi-Monte Carlo rules using folded digital nets in reproducing kernel Hilbert spaces. Here we need to permit digital nets with “infinite digit expansions”, which are beyond the scope of the classical definition of digital nets. We overcome this issue by considering the infinite product of cyclic groups and the characters on it. We then give an explicit means of constructing good folded digital nets as follows: we use higher order polynomial lattice point sets for digital nets and show that the component-by-component construction can find good folded higher order polynomial lattice rules that achieve the optimal convergence rate of the worst-case error in certain Sobolev spaces of smoothness of arbitrarily high order.     

An optimal sequential procedure for a multiple selling problem with independent observations

We consider a sequential problem of selling K identical assets over the finite time horizon with a fixed number of offers per time period and no recall of past offers. The objective is to find an optimal sequential procedure which maximizes the total expected revenue. In this paper, we derive an effective number of stoppings for an optimal sequential procedure for the selling problem with independent observations.     

Interpolatory integration rules and orthogonal polynomials with varying weights

We investigate which types of asymptotic distributions can be generated by the knots of convergent sequences of interpolatory integration rules. It will turn out that the class of all possible distributions can be described exactly, and it will be shown that the zeros of polynomials that are orthogonal with respect to varying weight functions are good candidates for knots of integration rules with a prescribed asymptotic distribution.Research supported by the Deutsche Forschungsgemeinschaft (AZ: Sta 299/4-2).     

Reducing the construction cost of the component-by-component construction of good lattice rules

The construction of randomly shifted rank- lattice rules, where the number of points is a prime number, has recently been developed by Sloan, Kuo and Joe for integration of functions in weighted Sobolev spaces and was extended by Kuo and Joe and by Dick to composite numbers. To construct -dimensional rules, the shifts were generated randomly and the generating vectors were constructed component-by-component at a cost of operations. Here we consider the situation where is the product of two distinct prime numbers and . We still generate the shifts randomly but we modify the algorithm so that the cost of constructing the, now two, generating vectors component-by-component is only operations. This reduction in cost allows, in practice, construction of rules with millions of points. The rules constructed again achieve a worst-case strong tractability error bound, with a rate of convergence for 0$">.

     

Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules

In this paper we prove the existence of digitally shifted polynomial lattice rules which achieve strong tractability results for Sobolev spaces of arbitrary high smoothness. The convergence rate is shown to be the best possible up to a given degree of smoothness of the integrand. Indeed we even show the existence of polynomial lattice rules which automatically adjust themselves to the smoothness of the integrand up to a certain given degree.Further we show that strong tractability under certain conditions on the weights can be obtained and that polynomial lattice rules exist for which the worst-case error can be bounded independently of the dimension. These results hold independent of the smoothness.     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

A dynamical systems result on asymptotic integration of linear differential systems

We are interested in the asymptotic integration of linear differential systems of the form x′=[Λ(t)+R(t)]x, where Λ is diagonal and R∈L^p[t₀,∞) for p∈[1,2]. Our dichotomy condition is in terms of the spectrum of the omega-limit set ω_Λ. Our results include examples that are not covered by the Hartman-Wintner theorem.     

A useful result in searches for good vertex-modified number-theoretic rules

Number-theoretic rules are particularly suited to the evaluation of multiple integrals in which the integrand is periodic. For nonperiodic integrands, an alternative is to use vertex-modified versions of number-theoretic rules. Good vertex-modified number-theoretic rules may be found by doing a computer search based on some criterion of goodness. Such criteria include a variant of the L₂ discrepancy and the vertex variance. Here we present a result which may be used to speed up searches for good vertex-modified number-theoretic rules based on these criteria when the generator vectors are of the one-parameter form of Korobov.     

An application of Diophantine approximation to the construction of rank-1 lattice quadrature rules

Lattice quadrature rules were introduced by Frolov (1977), Sloan (1985) and Sloan and Kachoyan (1987). They are quasi-Monte Carlo rules for the approximation of integrals over the unit cube in and are generalizations of `number-theoretic' rules introduced by Korobov (1959) and Hlawka (1962)---themselves generalizations, in a sense, of rectangle rules for approximating one-dimensional integrals, and trapezoidal rules for periodic integrands. Error bounds for rank-1 rules are known for a variety of classes of integrands. For periodic integrands with unit period in each variable, these bounds are conveniently characterized by the figure of merit , which was originally introduced in the context of number-theoretic rules. The problem of finding good rules of order (that is, having nodes) then becomes that of finding rules with large values of . This paper presents a new approach, based on the theory of simultaneous Diophantine approximation, which uses a generalized continued fraction algorithm to construct rank-1 rules of high order.

     

An exact method for computing the nadir values in multiple objective linear programming

In this paper we propose a new method to determine the exact nadir (minimum) criterion values over the efficient set in multiple objective linear programming (MOLP). The basic idea of the method is to determine, for each criterion, the region of the weight space associated with the efficient solutions that have a value in that criterion below the minimum already known (by default, the minimum in the payoff table). If this region is empty, the nadir value has been found. Otherwise, a new efficient solution is computed using a weight vector picked from the delimited region and a new iteration is performed. The method is able to find the nadir values in MOLP problems with any number of objective functions, although the computational effort increases significantly with the number of objectives. Computational experiments are described and discussed, comparing two slightly different versions of the method.     

The index of merit of kth-copy integration lattices

r2d2lri   is an automatic two-dimensional cubature algorithm that demonstrates the practical value of using an augmentation sequence consisting of (2^k)²$(2^k{)}^2$-copy lattices as a basis for numerical integration. This paper investigates use of similar embedded augmentation sequences in higher dimensions by developing theoretical results relating to the index of merit of s  -dimensional (2^k)^s$(2^k{)}^s$-copy lattices generated from rank-1 simple lattices. The theoretical results can be used to guide the search for good augmentation sequences in s dimensions in the sense of high index of merit.     

An interactive satisficing method based on alternative tolerance for fuzzy multiple objective optimization

An interactive satisficing method based on alternative tolerance is proposed for fuzzy multiple objective optimization. The new tolerances of the dissatisficing objectives are generated using an auxiliary programming problem. According to the alternative tolerant limits, either the membership functions are changed, or the objective constraints are added. The lexicographic two-phase programming is implemented to find the final solution. The results of the dissatisficing objectives are iteratively improved. The presented method not only acquires the efficient or weak efficient solution of all the objectives, but also satisfies the progressive preference of decision maker. Numerical examples show its power.     

Transformation methods for finding multiple roots of nonlinear equations

In this paper, to estimate a multiple root p of an equation f(x) = 0, we transform the function f(x) to a hyper tangent function combined with a simple difference formula whose value changes from −1 to 1 as x passes through the root p. Then we apply the so-called numerical integration method to the transformed equation, which may result in a specious approximate root. Furthermore, in order to enhance the accuracy of the approximation we propose a Steffensen-type iterative method, which does not require any derivatives of f(x) nor is quite affected by an initial approximation. It is shown that the convergence order of the proposed method becomes cubic by simultaneous approximation to the root and its multiplicity. Results for some numerical examples show the efficiency of the new method.     

An algorithm for solving a multiple criteria optimal control problem

An algorithm for finding agood solution for a multiple criteria optimal control problem is given. The criteria are assumed to be ordered according to their importance to the decision-maker. The algorithm consists of successive solutions of single criterion optimal control problems. Other criteria are taken into account by adding constraints to the problem in a systematic manner.     

A comparison of numerical integration rules for the meshless local Petrov–Galerkin method

The meshless local Petrov–Galerkin (MLPG) method is a mesh-free procedure for solving partial differential equations. However, the benefit in avoiding the mesh construction and refinement is counterbalanced by the use of complicated non polynomial shape functions with subsequent difficulties, and a potentially large cost, when implementing numerical integration schemes. In this paper we describe and compare some numerical quadrature rules with the aim at preserving the MLPG solution accuracy and at the same time reducing its computational cost.