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.     

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.     

Lower bounds for the zeros of analytic functions

Summary In the present work the problem of finding lower bounds for the zeros of an analytic function is reduced by a Hilbert space technique to the well-known problem of finding upper bounds for the zeros of a polynomial. Several lower bounds for all the zeros of analytic functions are thus found, which are always better than the well-known Carmichael-Mason inequality. Several numerical examples are also given and a comparison of our bounds with well-known bounds in literature and/or the exact solution is made.     

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%.     

Using dual network bounds in algorithms for solving generalized set packing partitioning problems

This article deals with a method to compute bounds in algorithms for solving the generalized set packing/partitioning problems. The problems under investigation can be solved by the branch and bound method. Linear bounds computed by the simplex method are usually used. It is well known that this method breaks down on some occasions because the corresponding linear programming problems are degenerate. However, it is possible to use the dual (Lagrange) bounds instead of the linear bounds. A partial realization of this approach is described that uses a network relaxation of the initial problem. The possibilities for using the dual network bounds in the approximation techniques to solve the problems under investigation are described.     

Solution Bounds of the Continuous and Discrete Lyapunov Matrix Equations

A unified approach is proposed to solve the estimation problem for the solution of continuous and discrete Lyapunov equations. Upper and lower matrix bounds and corresponding eigenvalue bounds of the solution of the so-called unified algebraic Lyapunov equation are presented in this paper. From the obtained results, the bounds for the solutions of continuous and discrete Lyapunov equations can be obtained as limiting cases. It is shown that the eigenvalue bounds of the unified Lyapunov equation are tighter than some parallel results and that the lower matrix bounds of the continuous Lyapunov equation are more general than the majority of those which have appeared in the literature.     

Analysis of upper bounds for the Pallet Loading Problem

This paper is concerned with upper bounds for the well-known Pallet Loading Problem (PLP), which is the problem of packing identical boxes into a rectangular pallet so as to maximize the number of boxes fitted. After giving a comprehensive review of the known upper bounds in the literature, we conduct a detailed analysis to determine which bounds dominate which others. The result is a ranking of the bounds in a partial order. It turns out that two of the bounds dominate all others: a bound due to Nelissen and a bound obtained from the linear programming relaxation of a set packing formulation. Experiments show that the latter is almost always optimal and can be computed quickly.     

Bounds for aggregating nodes in network problems

It is often necessary or desirable in practice to replace a large, detailed optimization model with a smaller, approximate model. It would be useful to have bounds on the error resulting from this process of aggregation. This paper develops such bounds for a class of linear minimum-cost network-flow problems, where groups of nodes in a large problem are replaced by aggregate nodes. Two types of bounds are derived: A priori bounds are available before solving the aggregated problem; a posteriori bounds, which are generally tighter, may be computed afterwards.     

Sharp probability bounds for the binomial moment problem with symmetry

Sharp bounds in terms of the first few binomial moments are found for the probability of a union of events, when the random variable denoting the number of events that occur follows symmetric distribution. Connection between the bounds of this paper and the bounds from a special case of the binomial moment problem of Prekopa (1995) is shown. As a special case, bounds for the probability when the underlying probability distribution is unimodal-symmetric are also found.     

Discretize-then-relax approach for convex/concave relaxations of the solutions of parametric ODEs

This paper presents a discretize-then-relax methodology to compute convex/concave bounds for the solutions of a wide class of parametric nonlinear ODEs. The procedure builds upon interval methods for ODEs and uses the McCormick relaxation technique to propagate convex/concave bounds. At each integration step, a two-phase procedure is applied: a priori convex/concave bounds that are valid over the entire step are calculated in the first phase; then, pointwise-in-time convex/concave bounds at the end of the step are obtained in the second phase. An approach that refines the interval state bounds by considering subgradients and affine relaxations at a number of reference parameter values is also presented. The discretize-then-relax method is implemented in an object-oriented manner and is demonstrated using several numerical examples.     

Sharp bounds on the volume fractions of two materials in a two-dimensional body from electrical boundary measurements: the translation method

We deal with the problem of estimating the volume of inclusions using a small number of boundary measurements in electrical impedance tomography. We derive upper and lower bounds on the volume fractions of inclusions, or more generally two phase mixtures, using two boundary measurements in two dimensions. These bounds are optimal in the sense that they are attained by certain configurations with some boundary data. We derive the bounds using the translation method which uses classical variational principles with a null Lagrangian. We then obtain necessary conditions for the bounds to be attained and prove that these bounds are attained by inclusions inside which the field is uniform. When special boundary conditions are imposed the bounds reduce to those obtained by Milton and these in turn are shown here to reduce to those of Capdeboscq–Vogelius in the limit when the volume fraction tends to zero. The bounds of this article, and those of Milton, work for inclusions of arbitrary volume fractions. We then perform some numerical experiments to demonstrate how good these bounds are.     

The effect of redundancy on probability bounds

Lower bounds on the probability of a union obtained by applying optimal bounds to subsets of events can provide excellent bounds. Comparisons are made with bounds obtained by linear programming and in the cases considered, the best bound is obtained with a subset that contains no redundant events contributing to the union. It is shown that redundant events may increase or decrease the value of a lower bound but surprisingly even removal of a non-redundant event can increase the bound.     

Refinement of Lagrangian bounds in optimization problems

Lagrangian constraint relaxation and the corresponding bounds for the optimal value of an original optimization problem are examined. Techniques for the refinement of the classical Lagrangian bounds are investigated in the case where the complementary slackness conditions are not fulfilled because either the original formulation is nonconvex or the Lagrange multipliers are nonoptimal. Examples are given of integer and convex problems for which the modified bounds improve the classical Lagrangian bounds.     

A Posteriori Error Bounds for Gaussian Elimination

Explicit bounds are constructed for the error in the solutionof a system of linear algebraic equations obtained by Gaussianelimination using floating-point arithmetic. The bounds takeaccount of inherent errors in the data and all abbreviations(choppings or roundings) introduced during the process of solution.The bounds are strict and agree with the estimate for the maximumerror obtained by linearized perturbation theory. The formulationof the bounds avoids the need for specially directed roundingprocedures in the hardware or software; in consequence the boundscan be evaluated on most existing computers. The cost of computingthe bounds is comparable with the cost of computing the originalsolution.     

Copula界在多元VaR中的应用

首先介绍了多元随机变量和的边界,以及由此导出的VaR边界,然后全面总结了有关Copula下界的公式,而Copula下界及其对偶函数分别构成计算VaR边界的依据.最后根据VaR边界的数值算法,针对不同的Copula下界,分多种情景详细分析了VaR的边界范围.关于上证指数和深成指数收益率序列的实证分析发现.Spearman相关系数和正象限相依对VaR界的收窄作用最强.     

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.     

Logarithmic sample bounds for Sample Average Approximation with capacity- or budget-constraints

Sample Average Approximation (SAA) is used to approximately solve stochastic optimization problems. In practice, SAA requires much fewer samples than predicted by existing theoretical bounds that ensure the SAA solution is close to optimal. Here, we derive new sample-size bounds for SAA that, for certain problems, are logarithmic (existing bounds are polynomial) in problem dimension. Notably, our new bounds provide a theoretical explanation for the success of SAA for many capacity- or budget-constrained optimization problems.     

On the perturbation of the Q‐factor of the QR factorization

This paper gives normwise and componentwise perturbation analyses for the Q‐factor of the QR factorization of the matrix A with full column rank when A suffers from an additive perturbation. Rigorous perturbation bounds are derived on the projections of the perturbation of the Q‐factor in the range of A and its orthogonal complement. These bounds overcome a serious shortcoming of the first‐order perturbation bounds in the literature and can be used safely. From these bounds, identical or equivalent first‐order perturbation bounds in the literature can easily be derived. When A is square and nonsingular, tighter and simpler rigorous perturbation bounds on the perturbation of the Q‐factor are presented. Copyright © 2011 John Wiley & Sons, Ltd.     

Two-sided bounds for the distribution of the deficit at ruin in the renewal risk model

We obtain lower and upper bounds for the severity of ruin in the renewal (Sparre Andersen) model of risk theory. We present two types of bounds: (i) bounds applicable generally; and (ii) exponential bounds for the case where the adjustment coefficient of the risk process exists. Many of these bounds are obtained using existing bounds and the integral equation for the severity of ruin.     

Mixed volume techniques for embeddings of Laman graphs

Determining the number of embeddings of Laman graph frameworks is an open problem which corresponds to understanding the solutions of the resulting systems of equations. In this paper we investigate the bounds which can be obtained from the viewpoint of Bernstein's Theorem. The focus of the paper is to provide methods to study the mixed volume of suitable systems of polynomial equations obtained from the edge length constraints. While in most cases the resulting bounds are weaker than the best known bounds on the number of embeddings, for some classes of graphs the bounds are tight.