...2004. Forthcoming) have already shown how obtain optimal moment inequalities for arbitrary distributions via semidefinite programming. These bounds are not sharp if the underlying distributions possess additional structural properties, including symmetry, unimodality, convexity, or smoothness. For convex distribution classes that are in some sense generated by an appropriate parametric family, we use conic duality to show how optimal moment bounds can be efficiently computed as semidefinite programs. In particular, we obtain generalizations of Chebyshev's inequality for symmetric and unimodal distributions and provide numerical calculations to compare these bounds, given higher-order moments. We also extend these results for multivariate distributions.

Key words: moment problems; Chebyshev inequalities; probability bounds: convex optimization: inventory: semidefinite programming

MSC2000 subject classification: Primary: 60E15: secondary: 90C22, 90C25

OR/MS subject classification: Primary: Probability distributions: secondary: infinite dimensional programming, mathematics convexity

History: Received April 5, 2002; revised April 2, 2004

1. Introduction. A generalized-moment hound is a problem of the following type: Given "moment" information, in the form E[[f.sub.i](X)] = [q.sub.i], i = 1, ..., n, about a random variable X, what are the "best possible" upper and/or lower bounds on the expectation of a related quantity, [phi](X), that can be derived from the available information? We can formulate the problem of finding such optimal upper (and similarly lower) bounds as an optimization program:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the optimization is taken over all possible distributions of the random variable X in the class P. This setup is made rigorous in the next section.

This formulation is powerful because of the variety of interpretations that can be given to the random variable X and the underlying class P, as well as the generality of the objective and constraint functions [phi] and [f.sub.i]. These are not assumed to be continuous or bounded, to allow for "moments" such as P(X [greater than or equal to] a) and distributions with unbounded support. Problem (P) provides a general framework for studying a multitude of moment problems, with applications. For example, moment inequalities are used to provide robust estimates for financial quantities, such as option and stock prices (see Lo [21], Grundy [13] or Bertsimas and Popescu [3]), wealth balance in option hedging (Yamada and Primbs [45]), or value at risk (El Ghaoui et al. [11]). In the decision sciences literature, Smith [35] explores several areas of application of moment bounds, including dynamic programming, decision analysis with incomplete information (see also Willassen [42], LiCalzi [20]), and Bayesian statistics.

The question of feasibility of Problem (P) given standard moment constraints E[[X.sup.i] = [q.sub.i], i = 1, ..., n, is the classical moment problem. It has been investigated by probabilists since the 19th century, most notably by Chebyshev [7], Markov [23], Stieltjes [37], Akhiezer and Krein [1], and Karlin and Studden [15]. For collected works on moment problems, see also Shohat and Tamarkin [34], Tong [39], Landau [19], and references therein. Given the first and second moment of a univariate random variable, Chebyshev's inequality (Chebyshev [7], Markov [23]) gives a bound on the distribution function. A generalization of this result is due to Bertsimas and Popescu [4], who compute optimal bounds on arbitrary distributions given any finite number of generalized moments, using semidefinite programming.

Moment bounds are used to provide robust, worst-case estimates of unknown random quantities. These estimates, however, can be overly pessimistic. The reason is that moment bounds are achieved by discrete distributions, which are not always realistic for practical applications. For example, in finance, Yamada and Primbs [45] observe that their upper and lower moment bounds can be far apart, hence not providing much valuable information. This is partly due to ignoring additional structural properties of the underlying stock price distributions. In an inventory control application, Scarf [32] and Gallego [12] derive worst-case order quantities given mean-variance demand information. The resulting bound is very conservative, as it corresponds to an unrealistic two-point distribution of demand.

In contrast to worst-case moment-based estimates, an alternate approach taken in the literature is to fit a (functional) parametric distribution to the moment data. For example, unknown financial quantities are usually modeled as normal or lognormal distributions. In a decision sciences context, Soll and Klayman [36] provide measures of overconfidence by estimating mean absolute dispersion and other distributional properties given sample quantiles of a distribution that is known to be continuous and unimodal. To make the analysis tractable, they fit a beta distribution to the data. This approach, akin to the method of moments estimators, is ubiquitous in a variety of settings for statistical estimation. Lanckriet et al. [18] compare general distribution-free moment bounds with traditional approaches based on normal densities. Their numerical data-classification tests on medical disease data show a significant gap between the estimates provided by the two methods.

Our results are useful in settings where one needs to provide measurements of random quantities when incomplete distributional information is available. Instead of assuming a particular distribution type (normal, lognormal, beta), or solving a pure moment problem, we propose an intermediary approach by incorporating structural distributional properties into the moment problem.

The contribution of this paper is a general approach for deriving moment bounds that are tight for some special convex classes of distributions. Our main result (Theorem 3.2) states that for piecewise polynomial objective and constraint functions [phi] and [f.sub.i], the optimal bound in Problem (P) can be efficiently (1) computed as a semidefinite program (SDP), when the underlying distributions form a convex class that can be "generated" by an appropriate parametric family (see Assumptions A and B). Such classes include symmetric and/or unimodal distributions, distributions with convex and/or concave densities, and slope constraints. The tighter bounds for these classes extend the results of Bertsimas and Popescu [4] for arbitrary distributions.

For example, suppose that we want to find the best upper bound on the probability P(X - M [greater than or equal to] 2[sigma]) that a realization of a random variable X, with mean M and variance [[sigma].sup.2] falls at least two standard deviations above the mean. Furthermore, suppose that X is known to be symmetric and unimodal. The one-sided Chebyshev inequality provides a worst-case estimate of 0.20. For a normal random variable the true value is 0.025, compared to which Chebyshev's bound is disappointingly weak. However, by incorporating symmetry and unimodality conditions, but without assuming normality, the tight bound can be reduced to 0.05, a 75% error improvement over Chebyshev (see Proposition 7.1). Our numerical results show even greater improvements for higher-order moments.

Univariate moment bounds for unimodal and higher-order convexity classes have been previously investigated in the remarkable monograph of Karlin and Studden [15, Chapter 12], who also provide closed-form solutions for the mean-variance case. Their proof relies on a clever integration by parts argument, which is valid only if the random variables have unbounded support. A similar approach is taken by Mulholland and Rogers [24], who also characterize the corresponding extremal distributions, thereby extending ad hoc results of Mallows [22]. None of these papers, however, provides any computational approach. The main contribution of our results is to provide a simple and efficient method for computing the optimal solution for special classes of moment problems via semidefinite programming. Moreover, our duality-based approach allows us to characterize more general classes of distributions, including multivariate extensions.

From a methodological standpoint, mathematical programming tools such as conic duality and semidefinite optimization provide a powerful framework for solving efficiently what otherwise appears to be a difficult problem in probability. Our results exploit and bring a new dimension--that of special convex distribution classes--to the intriguing connection between moment problems and semidefinite optimization.

Section 2 formalizes the problem and reviews the main known results. Section 3 develops the conic duality framework and our main result for univariate convex distribution classes generated by a one-parameter family. Section 4 derives optimal-moment bounds for symmetric and unimodal distributions. Section 5 investigates the moment problem for distributions with convex--respectively, concave--densities, including bounds on the slope. Several results for combined classes are also outlined. A general multivariate result, and applications for unimodal and symmetric classes, are obtained in [section] 6. As an illustration of our approach, in [section] 7 we derive semidefinite programming (SDP) formulations for sharp moment bounds on tail probabilities for some special classes of distributions. In particular, we obtain analytical analogues and extensions of Chebyshev's inequality. Numerical results illustrate the comparative performance of these bounds. Concluding comments are given in [section] 8.

2. Moment bounds for arbitrary distributions via SDP. In this section, we briefly review the general-moment bounds and corresponding SDP approach from Bertsimas and Popescu [4]. We first set up the problem by introducing some definitions and notation.

2.1. The problem and notation. The goal is to find the best upper bound on E[[phi](X)], given expectations [q.sub.i] of functionals [f.sub.i](X) of the random vector X, defined on a closed set [OMEGA] [subset equal to] [R.sup.m], endowed with a Borel sigma algebra B = [B.sub.[OMEGA]], typically omitted for notational convenience. The distribution (2) [mu] B [right arrow] [0, 1] of X, defined by [mu](S) = P(X [member of] S), is restricted to a particular convex class P. For a vector of moment functions f = ([f.sub.0], [f.sub.1], ..., [f.sub.n]): [OMEGA] [right arrow] [R.sup.n], we denote the set of feasible moment sequences by [Q.sub.P](f) = {q = ([q.sub.0], [q.sub.1], ..., [q.sub.n]) | q = [E.sub.[mu]][f(X)] for some [mu] [member of] P]}. We explicitly include the probability mass constraint by setting [q.sub.0] = 1, [f.sub.0] [equivalent to] [1.sub.[OMEGA]] where [1.sub.S](x) is the indicator function of a set S. The central problem of this research is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

In this paper, by solving Problem (P) we mean calculating its optimal value. Our use of "max" and "min" operators does not automatically imply that the corresponding optimal value is attained. We focus on Problem (P) as an upper-bound problem, but all results hold true for the lower-bound problem as well, via a simple change of sign transformation. Moreover, the mathematical programming setup extends to problems involving inequality constraints on the moments.

Consider the set [L.sup.+] = [L.sup.+]([OMEGA]) of all measures on ([OMEGA], B) such that the functions [phi] and [f.sub.i] are [mu]-measurable for all [mu] [member of] [L.sup.+]. Let [M.sup.+] = [M.sup.+]([OMEGA]) denote the corresponding subset of probability measures (i.e. [mu]([OMEGA]) = 1) and let L = L([OMEGA]) denote the span of [M.sup.+], which is a linear space of signed measures. Let [L.sup.*] denote the span of [phi], [f.sub.0], ..., [f.sub.n]. The vector spaces L and [L.sup.*] are paired by a bilinear form (scalar product) given by the integral operator : = [[integral].sub.[OMEGA]] hd[mu] = [[integral].sub.[OMEGA]] h([omega])d[mu]([omega]). For probability measures, this is the expectation operator: [E.sub.[mu]][h(X)] = [[integral].sub.[OMEGA]] hd[mu].

The convex bull of a set T is denoted CX(T), and CO(T) denotes the cone generated by a set T. Because we are working on infinite-dimensional spaces, we extend these concepts to allow for a continuum of convex combinations. We define the convex set of generalized mixtures of distributions [tau] [member of] T by

mix(T) = {[mu] [member of] [M.sup.+]: [mu](A) = [[integral].sub.T] [tau](A)dv(tau) [for all] A [member of] B | v [member of] [M.sup.+](T)}, (2)

where [M.sup.+](T) is the set of all mixing distributions v over T, with the sigma algebra on T defined so that the functions [tau] [right arrow] [tau](A) are measurable in [tau] [member of] T for every A [member of] B. In functional analysis, [mu] is known as the resultant or barycenter of v.

Throughout the paper, we denote closure with a bar. We implicitly work with the standard topology of the reals and the weak topology of measures (e.g., see Billingsley [5] or Parthasarathy [27]), unless stated otherwise.

Finally, we use standard notation = {[alpha]a + (1 - [alpha])b | [alpha] [member of] [0, 1]} for the closed segment between vectors a and b, and [(x).sup.+] = max(0, x) for the positive part of x.

2.2. Review...

NOTE: All illustrations and photos have been removed from this article.



More articles from Mathematics of Operations Research
Optimal investments for robust utility functionals in complete market ..., August 01, 2005
Note on multimodularity and L-convexity., August 01, 2005
Second-order lower bounds on the expectation of a convex function., August 01, 2005
Exponential lower bounds on the lengths of some classes of branch-and-..., August 01, 2005
Error bounds for degenerate cone inclusion problems., August 01, 2005

Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.