Recursive lower and dual upper bounds for Bermudan-style options

Although Bermudan options are routinely priced by simulation and least-squares methods using lower and dual upper bounds, the latter are hardly optimized. In this paper, we optimize recursive upper bounds, which are more tractable than the original/nonrecursive ones, and derive two new results: (1) An upper bound based on (a martingale that depends on) stopping times is independent of the next-stage exercise decision and hence cannot be optimized. Instead, we optimize the recursive lower bound, and use its optimal recursive policy to evaluate the upper bound as well. (2) Less time-intensive upper bounds that are based on a continuation-value function only need this function in the continuation region, where this continuation value is less nonlinear and easier to fit (than in the entire support). In the numerical exercise, both upper bounds improve over state-of-the-art methods (including standard least-squares and pathwise optimization). Specifically, the very small gap between the lower and the upper bounds derived in (1) implies the recursive policy and the associated martingale are near optimal, so that these two specific lower/upper bounds are hard to improve, yet the upper bound is tighter than the lower bound.     

Some improvements for two-sided bounds on the inverse of diagonally dominant tridiagonal matrices

In this paper, we obtain lower and upper bounds for the entries of the inverses of diagonally dominant tridiagonal matrices. First of all we derive the bounds for off-diagonal elements of the inverse as a function of the diagonal ones, then we improve the two-sided bounds for the diagonal entries obtaining sharper lower and upper bounds for all the elements of the inverse.     

A dynamic bounding algorithm for approximating multi-state two-terminal reliability

This paper modifies Jane and Laih’s (2008) exact and direct algorithm to provide sequences of upper bounds and lower bounds that converge to the NP-hard multi-state two-terminal reliability. Advantages of the modified algorithm include (1) it does not require a priori the lower and/or upper boundary points of the network, (2) it derives a series of increasing lower bounds and a series of decreasing upper bounds simultaneously, guaranteed to enclose the exact reliability value, and (3) trade-off between accuracy and execution time can be made to ensure an exact difference between the upper and lower bounds within an acceptable time. Examples are analyzed to illustrate the bounding algorithm, and to compare the bounding algorithm with existing algorithms. Computational experiments on a large network are conducted to realize the performance of the bounding algorithm.     

Computing closely matching upper and lower bounds on textile nesting problems

We consider an industrial cutting problem in textile manufacturing and report on algorithms for computing cutting images and lower bounds on waste for this problem. For the upper bounds we use greedy strategies based on hodographs and global optimization based on simulated annealing. For the lower bounds we use branch-and-bound methods for computing optimal solutions of placement subproblems that determine the performance of the overall subproblem. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within 0.4% of the upper bound for certain types of clothing (e.g., for pants).     

An improved balanced job bound analysis of closed queuing networks

Balanced job bounds (BJB) is a technique for obtaining lower and upper bounds on the throughput of a separable closed queuing network. The conceptual simplicity and the low computational complexity of this technique make these bounds very attractive. However, whereas the lower bound is usually quite good, the upper bound may be loose. In this paper, we present an improved BJB analysis for obtaining a tight upper bound.     

Rate Functions for Symmetric Markov Processes via Heat Kernel

By making full use of heat kernel estimates, we establish the integral tests on the zero-one laws of upper and lower bounds for the sample path ranges of symmetric Markov processes. In particular, these results concerning on upper rate bounds are applicable for local and non-local Dirichlet forms, while lower rate bounds are investigated in both subcritical setting and critical setting.     

Analyse sur les groupes de Lie à croissance polynômiale

From Gaussian upper bounds on the heat kernel we deduce similar upper bounds on the first space derivatives of the heat kernel. Gaussian lower bounds on the heat kernel are deduced and some applications are given.     

Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates

This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed formulation of the problem is investigated in order to derive efficient lower bounds throught column generation or Lagrangean relaxation. A simple local search algorithm is also presented in order to derive an upper bound. Computational experiments compare these bounds for both the one machine and parallel machine problems and show that the gap between upper and lower bounds is about 1.5%.     

Tail bounds for the joint distribution of the surplus prior to and at ruin

For the classical risk model with Poisson arrivals, we study the (bivariate) tail of the joint distribution of the surplus prior to and at ruin. We obtain some exact expressions and new bounds for this tail, and we suggest three numerical methods that may yield upper and lower bounds for it. As a by-product of the analysis, we obtain new upper and lower bounds for the probability and severity of ruin. Many of the bounds in the present paper improve and generalise corresponding bounds that have appeared earlier. For the numerical bounds, their performance is also compared against bounds available in the literature.     

Comparisons of weak regular splittings and multisplitting methods

Summary Comparison results for weak regular splittings of monotone matrices are derived. As an application we get upper and lower bounds for the convergence rate of iterative procedures based on multisplittings. This yields a very simple proof of results of Neumann-Plemmons on upper bounds, and establishes lower bounds, which has in special cases been conjectured by these authors.Dedicated to the memory of Peter Henrici     

Heat kernels of non-symmetric jump processes with exponentially decaying jumping kernel

In this paper we study the transition densities for a large class of non-symmetric Markov processes whose jumping kernels decay exponentially or subexponentially. We obtain their upper bounds which also decay at the same rate as their jumping kernels. When the lower bounds of jumping kernels satisfy the weak upper scaling condition at zero, we also establish lower bounds for the transition densities, which are sharp.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

Integrating heuristic information into exact methods: The case of the vertex p-centre problem

We solve the vertex p-centre problem optimally using an exact method that considers both upper and lower bounds as part of its search engine. Tight upper bounds are generated quickly via an efficient three-level heuristic, which are then used to derive potential ‘lower bounds’ accordingly. These two pieces of information when used together make our chosen exact method more efficient at obtaining optimal solutions relatively quickly. The proposed implementation produced excellent results when tested on the OR Library data set. This integrated approach can be adopted for those exact methods that consider both upper and lower bounds within their search engine and hence provide a wider spectrum of applicability in other hard combinatorial problems.     

Structural Properties of Tensors and Complementarity Problems

In this paper, one of our main purposes is to prove the boundedness of the solution set of tensor complementarity problems such that the specific bounds depend only on the structural properties of such a tensor. To achieve this purpose, firstly, we prove that this class of structured tensors is strictly semi-positive. Subsequently, the strictly lower and upper bounds of operator norms are given for two positively homogeneous operators. Finally, with the help of the above upper bounds, we show that the solution set of tensor complementarity problems has the strictly lower bound. Furthermore, the upper bounds of spectral radius are obtained, which depends only on the principal diagonal entries of tensors.     

Convergence rates in strong ergodicity for Markov processes

A coupling method is used to obtain the explicit upper and lower bounds for convergence rates in strong ergodicity for Markov processes. For one-dimensional diffusion processes and birth–death processes, these bounds are sharp in the sense that the upper one and the lower one only differ in a constant.     

A non-stationary periodic review production–inventory model with uncertain production capacity and uncertain demand

In this paper we consider a nonstationary periodic review dynamic production–inventory model with uncertain production capacity and uncertain demand. The maximum production capacity varies stochastically. It is known that order up-to (or base-stock, critical number) policies are optimal for both finite horizon problems and infinite horizon problems. We obtain upper and lower bounds of the optimal order up-to levels, and show that for an infinite horizon problem the upper and the lower bounds of the optimal order up-to levels for the finite horizon counterparts converge as the planning horizons considered get longer. Furthermore, under mild conditions the differences between the upper and the lower bounds converge exponentially to zero.     

图的代数连通度的界(英文)

本文首先给出了简单图的度序列的平方和的上界,利用这些结果,求出了简单图的代数连通度的几个上下界并确定了它们的临界图。另外,文章也给出了加权图的代数连通度的一个下界。     

On exit time from balls of jump-type symmetric Markov processes

We obtain upper and lower bounds of the exit times from balls of a jump-type symmetric Markov process. The proofs are delivered separately. The upper bounds are obtained by using the Levy system corresponding to the process, while the precise expression of the （L^2-）generator of the Dirichlet form associated with the process is used to obtain the lower bounds.