Computable error bounds of multidimensional Euler inversion and their financial applications

Transform inversion is an efficient approximation procedure in operations research, yet the inversion results are sometimes unstable which calls for comprehensive error analysis. This article proposes a multidimensional Euler inversion (MEI) algorithm with computable error bounds. We design mild sufficient conditions that validate the inversion formula, and provide closed-form upper bounds of the inversion errors. Numerical experiments are conducted to compute the joint probability of default and barrier option prices under complicated stochastic models, and output the associated error bounds.     

Regularities and their relations to error bounds

In this paper, we mainly study various notions of regularity for a finite collection {C₁,,C_m} of closed convex subsets of a Banach space X and their relations with other fundamental concepts. We show that a proper lower semicontinuous function f on X has a Lipschitz error bound (resp., -error bound) if and only if the pair {epi(f),X×{0}} of sets in the product space X× is linearly regular (resp., regular). Similar results for multifunctions are also established. Next, we prove that {C₁,,C_m} is linearly regular if and only if it has the strong CHIP and the collection {N_C1(z),,N_Cm(z)} of normal cones at z has property (G) for each zC:=_i=1^mC_i. Provided that C₁ is a closed convex cone and that C₂=Y is a closed vector subspace of X, we show that {C₁,Y} is linearly regular if and only if there exists >0 such that each positive (relative to the order induced by C₁) linear functional on Y of norm one can be extended to a positive linear functional on X with norm bounded by . Similar characterization is given in terms of normal cones.Mathematics Subject Classifications: 90C25, 90C31, 49J52, 46A40This research was supported by an Earmarked grant from the Research Grant Council of Hong Kong     

Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates

Mathematical Programming - The paper addresses parametric inequality systems described by polynomial functions in finite dimensions, where state-dependent infinite parameter sets are given by...     

Guaranteed error bounds for finite element approximations of noncoercive elliptic problems and their applications

In this paper, we discuss with guaranteed a priori and a posteriori error estimates of finite element approximations for not necessarily coercive linear second order Dirichlet problems. Here, ‘guaranteed’ means we can get the error bounds in which all constants included are explicitly given or represented as a numerically computable form. Using the invertibility condition of concerning elliptic operator, guaranteed a priori and a posteriori error estimates are formulated. This kind of estimates plays essential and important roles in the numerical verification of solutions for nonlinear elliptic problems. Several numerical examples that confirm the actual effectiveness of the method are presented.     

Finite element interpolation error bounds with applications to eigenvalue problems

Optimal finite element interpolation eror bounds are presented for piecewise linear, quadratic and Hermite-cubic elements in one dimenson. These bounds can be used to compute upper and lower bounds for eigenvalues of second and fourth order elliptic problems. Numerical computations demonstrate the usefulness of the theoretical results.

---

Zusammenfassung Es werden optimale Fehlerschranken für die eindimensionale finite Element-Interpolation mit stückweise linearen, quadratischen und Hermite-kubischen Elementen angegeben. Diese Schranken können dazu verwendet werden, unter und obere Schranken für Eigenwerte von elliptischen Problemen 2. und 4. Ordnung zu berechnen. Dazu werden numerische Resultate angeführt, welche die Nützlichkeit der theoretischen Resultate zeigen.

     

Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimen-sional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line bin packing and on-line dynamic allocation. The results also solve a long-open question in mathematical statistics.This research was supported by Air Force Contracts AFOSR-82-0326 and AFOSR-86-0078, NSF Grant 8120790, and DARPA contract N00014-80-C-0326. In addition, Tom Leighton was supported by an NSF Presidential Young Investigator Award with matching funds from Xerox and IBM.     

ON THE CONVERGENCE OF MULTIPLICATIVE ITERATIVE ALGORITHMS WITH INEXACT LINE SEARCH

1.IntroductionIntillspaperweanalyzetheconvergenceonmultiplicativeiterativealgorithmsfortheIninimizationofadiffcrentiablefunctiondefinedonthepositiveorthantofR".ThealgorithmissllggestedbyEggermolltl'],andisrelatedtotheEM[2](Expextation--Maximization)algoritllnlforPositronemissiontonlography[']andimagereconstructi..14].Wecollsidertheproblenl"linf(x)s.t.x20.Themultiplicativeiterativealgorithmshavethel'orlniforj=l,2,',n,withAhdeterminedthroughalinesearch.Whilelusem[5]establishedanelegantconv…     

The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension

Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation.

Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor is bounded by for some exponent and some positive constant . The -exponent of tractability is defined as the smallest power of in these bounds. It is shown by using Monte Carlo quadrature that the -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.

     

Some improved projected quasi-Newton algorithms and their convergence

In this paper we improve the two versions of the two-sided projected quasi-Newton method-one was proposed by Nocedal & Overton in [1] and the other was discussed in our previous paper, by introducing three different merit functions to make inexact one-dimensional searches.It is shown that these improved quasi-Newton algorithms have gained global convergence property which is not possessed by the original two algorithms.This research was supported in part by the National Natural Science Foundation of China.     

Truncation error bounds for modified continued fractions with applications to special functions

Much recent work has been done to investigate convergence of modified continued fractions (MCF's), following the proof by Thron and Waadeland [35] in 1980 that a limit-periodic MCFK(a _n , 1;x ₁), with andnth approximant

Cycle detection algorithms and their applications

This paper considers several cycle detection algorithms. Proofs of their correctness are given, bounds for complexity are obtained, some number theory applications like the factorization of integers and the discrete log problem are examined.     

Weak sharpness for set-valued variational inequalities and applications to finite termination of iterative algorithms

In this paper, we introduce the notion of weak sharpness for set-valued variational inequalities in the n-dimensional Euclidean space and then present some characterizations of weak sharpness. We also give some examples to illustrate this notion. Under the assumption of weak sharpness, by using the inner limit of a set sequence we establish a sufficient and necessary condition to guarantee the finite termination of an arbitrary algorithm for solving a set-valued variational inequality involving maximal monotone mappings. As an application, we show that the sequence generated by the hybrid projection-proximal point algorithm proposed by Solodov and Svaiter terminates at solutions in a finite number of iterations. These obtained results extend some known results of classical variational inequalities.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

On the convergence of the SAOR method and the error bounds for its acceleration

Given a linear system with Hermitian positive definite coefficient matrix A, a splitting of Varga's type [1] is considered, and the corresponding generalised SAOR scheme is presented. We obtain the convergence theorem for the SAOR method and give the error bound for the A-norm of the error vector for the SAOR semi-iterative method, hence extending the SAOR theory.     

Nested monotony for variational inequalities over product of spaces and convergence of iterative algorithms

The auxiliary problem principle has been proposed by the first author as a framework to describe and analyze iterative algorithms such as gradient as well as decomposition/coordination algorithms for optimization problems (Refs. 1–3) and variational inequalities (Ref. 4). The key assumption to prove the global and strong convergence of such algorithms, as well as of most of the other algorithms proposed in the literature, is the strong monotony of the operator involved in the variational inequalities. In this paper, we consider variational inequalities defined over a product of spaces and we introduce a new property of strong nested monotony, which is weaker than the ordinary overall strong monotony generally assumed. In some sense, this new concept seems to be a minimal requirement to insure convergence of the algorithms alluded to above. A convergence theorem based on this weaker assumption is given. Application of this result to the computation of Nash equilibria can be found in another paper (Ref. 5).This research has been supported by the Centre National de la Recherche Scientifique (ATP Complex Technological Systems) and by the Centre National d'Etudes des Télécommunications (Contract 83.5B.034.PAA).     

On the convergence rate and some applications of regularized ranking algorithms

This paper studies the ranking problem in the context of the regularization theory that allows a simultaneous analysis of a wide class of ranking algorithms. Some of them were previously studied separately. For such ones, our analysis gives a better convergence rate compared to the reported in the literature. We also supplement our theoretical results with numerical illustrations and discuss the application of ranking to the problem of estimating the risk from errors in blood glucose measurements of diabetic patients.     

Lower bounds of some singular integrals and their applications

Let and . We are interested in the lower bounds of the integral:

New error bounds for the penalty method and extrapolation

New error bounds are obtained for the Babu?ka penalty method which justify the use of extrapolation. For the problemΔu=f in Ω,u=g on ?Ω we show that, for a particular choice of boundary weight, repeated extrapolation yields a quasioptimal approximate solution. For example, the error in the second extrapolate (using cubic spline approximants) isO (h ³) when measured in the energy norm. Nearly optimalL ₂ error estimates are also obtained.