New permanental bounds for Ferrers matrices

We survey the most recent results on permanental bounds of a nonnegative matrix. Some older bounds are revisited as well. Applying refinements of the arithmetic mean-geometric mean inequality leads to sharp bounds for the permanent of a fully indecomposable Ferrers matrix. In the end, several relevant examples comparing the bounds are discussed.     

Estimating a largest eigenvector by Lanczos and polynomial algorithms with a random start

We study Lanczos and polynomial algorithms with random start for estimating an eigenvector corresponding to the largest eigenvalue of an n × n large symmetric positive definite matrix. We analyze the two error criteria: the randomized error and the randomized residual error. For the randomized error, we prove that it is not possible to get distribution-free bounds, i.e., the bounds must depend on the distribution of eigenvalues of the matrix. We supply such bounds and show that they depend on the ratio of the two largest eigenvalues. For the randomized residual error, distribution-free bounds exist and are provided in the paper. We also provide asymptotic bounds, as well as bounds depending on the ratio of the two largest eigenvalues. The bounds for the Lanczos algorithm may be helpful in a practical implementation and termination of this algorithm. © 1998 John Wiley & Sons, Ltd.     

Second-order bounds for linear recurrences with negative coefficients

This paper introduces a generalization of Fibonacci and Pell polynomials in order to obtain optimal second-order bounds for general linear recurrences with negative coefficients. An important aspect of the derived bounds is that they are applicable and easily computable. The results imply bounds on all entries in inverses of triangular matrices as well as on coefficients of reciprocals of power series.     

Bounds on the value of information in uncertain decision problems II†

In most stochastic decision problems one has the opportunity to collect information that would partially or totally eliminate the inherent uncertainty. One wishes to compare the cost and value of such information in terms of the decision maker's preferences to determine an optimal information gathering plan. The calculation of the value of information generally involves oneor more stochastic recourse problems as well as one or more expected value distribution problems. The difficulty and costs of obtaining solutions to these problems has led to a focus on the development of upper and lower bounds on the various subproblems that yield bounds on the value of information. In this paper we discuss published and new bounds for static problems with linear and concave preference functions for partial and perfect information. We also provide numerical examples utilizing simple production and investment problems that illustrate the calculations involved in the computation of the various bounds and provide a setting for a comparison of the bounds that yields some tentative guidelines for their use. The bounds compared are the Jensen's Inequality bound,the Conditional Jensen's Inequality bound and the Generalized Jensen and Edmundson-Madansky bounds.     

New Linear Program Performance Bounds for Queueing Networks

We obtain new linear programs for bounding the performance and proving the stability of queueing networks. They exploit the key facts that the transition probabilities of queueing networks are shift invariant on the relative interiors of faces and the cost functions of interest are linear in the state. A systematic procedure for choosing different quadratic functions on the relative interiors of faces to serve as surrogates of the differential costs in an inequality relaxation of the average cost function leads to linear program bounds. These bounds are probably better than earlier known bounds. It is also shown how to incorporate additional features, such as the presence of virtual multi-server stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.     

Upper bounds of degree 3 for the probability of the union of events via linear programming

We consider the problem of generating upper bounds for the probability of the union of events when the individual probabilities of the events as well as the probabilities of pairs and triples of these events are known. By formulating the problem as a Linear Program, we can obtain bounds as objective function values corresponding to dual basic solutions. The upper bounds are based on underlying graph structures.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

Optimal estimates on free boundary propagation in thin-film flow

We present a method for the derivation of lower bounds on free boundary propagation for the thin-film equation, one of the most prominent examples of a higher-order degenerate parabolic equation. In particular, we obtain sufficient conditions for instantaneous forward motion of the free boundary, upper bounds on waiting times, as well as lower bounds on asymptotic propagation rates. Our estimates coincide (up to a constant factor) with the previously known reverse bounds and are therefore optimal. To the best of our knowledge, these results constitute the first lower bounds on free boundary propagation for any higher-order degenerate parabolic equation. Our technique is based on new monotonicity formulas for solutions to the thin-film equation which involve weighted entropies with singular weight functions. It turns out that our method is not restricted to the thin-film equation, but also applicable to other higher-order parabolic equations like quantum drift-diffusion equations. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Comparison of homogenization, Hashin-Shtrikman bounds and the Halpin-Tsai Equations

In this paper we study a unidirectional and elastic fiber composite. We use the homogenization method to obtain numerical results of the plane strain bulk modulus and the transverse shear modulus. The results are compared with the Hashin-Shtrikman bounds and are found to be close to the lower bounds in both cases. This indicates that the lower bounds might be used as a first approximation of the plane strain bulk modulus and the transverse shear modulus. We also point out the connection with the Hashin-Shtrikman bounds and the Halpin-Tsai equations. Optimal bounds on the fitting parameters in the Halpin-Tsai equations have been formulated.     

Delta sets for divisors supported in two points

In Duursma and Park (2010) [7], the authors formulate new coset bounds for algebraic geometric codes. The bounds give improved lower bounds for the minimum distance of algebraic geometric codes as well as improved thresholds for algebraic geometric linear secret sharing schemes. The bounds depend on the delta set of a coset and on the choice of a sequence of divisors inside the delta set. In this paper we give general properties of delta sets and we analyze sequences of divisors supported in two points on Hermitian and Suzuki curves.     

Coset bounds for algebraic geometric codes

We develop new coset bounds for algebraic geometric codes. The bounds have a natural interpretation as an adversary threshold for algebraic geometric secret sharing schemes and lead to improved bounds for the minimum distance of an AG code. Our bounds improve both floor bounds and order bounds and provide for the first time a connection between the two types of bounds.     

Bounds on compound distributions and stop-loss premiums

In the actuarial literature a lot of attention is given to the approximation of aggregate claims distributions by compound Poisson and Polya distributions and their subsequent numerical evaluation. The present contribution derives bounds for the tail of compound distributions and stop-loss premiums. The bounds are obtained in an elementary manner based on a version of the Chebyshev inequality. The main point of this contribution consists in deriving bounds with explicit dependence on the distribution function itself as well as on some partial moments of it.     

New perturbation bounds for denumerable Markov chains

This paper is devoted to perturbation analysis of denumerable Markov chains. Bounds are provided for the deviation between the stationary distribution of the perturbed and nominal chain, where the bounds are given by the weighted supremum norm. In addition, bounds for the perturbed stationary probabilities are established. Furthermore, bounds on the norm of the asymptotic decomposition of the perturbed stationary distribution are provided, where the bounds are expressed in terms of the norm of the ergodicity coefficient, or the norm of a special residual matrix. Refinements of our bounds for Doeblin Markov chains are considered as well. Our results are illustrated with a number of examples.     

Bounds and estimates on the effective properties for nonlinear composites

In this paper we derive lower bounds and upper bounds on the effective properties for nonlinear heterogeneous systems. The key result to obtain these bounds is to derive a variational principle, which generalizes the variational principle by P. Ponte Castaneda from 1992. In general, when the Ponte Castaneda variational principle is used one only gets either a lower or an upper bound depending on the growth conditions. In this paper we overcome this problem by using our new variational principle together with the bounds presented by Lukkassen, Persson and Wall in 1995. Moreover, we also present some examples where the bounds are so tight that they may be used as a good estimate of the effective behavior.     

Some upper and lower bounds on PSD-rank

Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.     

Equality conditions for lower bounds on the smallest singular value of a bidiagonal matrix

Several lower bounds have been proposed for the smallest singular value of a square matrix, such as Johnson’s bound, Brauer-type bound, Li’s bound and Ostrowski-type bound. In this paper, we focus on a bidiagonal matrix and investigate the equality conditions for these bounds. We show that the former three bounds give strict lower bounds if all the bidiagonal elements are non-zero. For the Ostrowski-type bound, we present an easily verifiable necessary and sufficient condition for the equality to hold.     

Sub-Laplacian Eigenvalue Bounds on CR Manifolds

We prove upper bounds for sub-Laplacian eigenvalues independent of a pseudo-Hermitian structure on a CR manifold. These bounds are compatible with the Menikoff-Sjöstrand asymptotic law, and can be viewed as a CR version of Korevaar's bounds for Laplace eigenvalues of conformal metrics.     

Convex bounds on multiplicative processes, with applications to pricing in incomplete markets

Extremal distributions have been extensively used in the actuarial literature in order to derive bounds on functionals of the underlying risks, such as stop-loss premiums or ruin probabilities, for instance. In this paper, the idea is extended to a dynamic setting. Specifically, convex bounds on multiplicative processes are derived. Despite their relative simplicity, the extremal processes are shown to produce reasonably accurate bounds on option prices in the classical trinomial model for incomplete markets.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

Third-order extensions of Lo’s semiparametric bound for European call options

Computing semiparametric bounds for option prices is a widely studied pricing technique. In contrast to parametric pricing techniques, such as Monte-Carlo simulations, semiparametric pricing techniques do not require strong assumptions about the underlying asset price distribution. We extend classical results in this area. Specifically, we derive closed-form semiparametric bounds for the payoff of a European call option, given up to third-order moment (i.e., mean, variance, and skewness) information on the underlying asset price. We analyze how these bounds tighten the corresponding bounds, when only second-order moment (i.e., mean and variance) information is provided. We describe applications of these results in the context of option pricing; as well as in other areas such as inventory management, and actuarial science.