Higher-Order Upper Bounds on the Expectation of a Convex Function

Abstract

We develop a decreasing sequence of upper bounds on the expectation of a convex function. The n-th term in the sequence uses moments and cross-moments of up to degree n from the underlying random vector. Our work has application to a class of two-stage stochastic programs with recourse. The objective function of such a model can defy computation when: (i) the underlying distribution is assumed to be known only through a limited number of moments or (ii) the function is computationally intractable, even though the distribution is known. A tractable approximating model arises by replacing the objective function by one of our bounding elements. We justify this approach by showing that as n grows, solutions of the order-n approximation solve the true stochastic program.