Ann Oper Res (2013) 206:147–162

DOI 10.1007/s10479-013-1337-0

Optimization with a class of multivariate integral stochastic order constraints

William B. Haskell · J. George Shanthikumar ·

Z. Max Shen

Published online: 27 February 2013 © Springer Science+Business Media New York 2013

Abstract We study convex optimization problems with a class of multivariate integral stochastic order constraints defined in terms of parametrized families of increasing concave functions. We show that utility functions act as the Lagrange multipliers of the stochastic order constraints in this general setting, and that the dual problem is a search over utility functions. Practical implementation issues are discussed. 1 Introduction

This paper is concerned with risk preferences over multiple dependent random prospects.

In many stochastic optimization problems, decisions condition multiple jointly distributed random prospects. The decision maker must account for the joint variation/dispersion/spread of these random prospects to get a satisfactory solution.

It is challenging to model risk preferences over random vectors because the components of random vectors can have complicated interrelationships under a joint distribution. Our present approach is based on stochastic orders. Stochastic orders are partial orders on the space of random variables, and they are studied extensively in Muller and Stoyan (2002), and Shaked and Shanthikumar (2007). We will characterize multivariate risk preferences in terms of integral stochastic orders generated from parametrized families of increasing concave functions. We will set a benchmark random vector for desirable performance, and then we will require our decision to condition a random vector that dominates the benchmark in such an integral stochastic order. Benchmarking is intuitively appealing because it is easy to describe a desirable performance distribution for real systems.

W.B. Haskell ()

Los Angeles, CA, USA e-mail: wbhaskell@gmail.com

J.G. Shanthikumar

West Lafayette, IN, USA

Z.M. Shen

Berkeley, CA, USA 148 Ann Oper Res (2013) 206:147–162

Stochastic dominance constrained optimization is pioneered in Dentcheva and

Ruszczyn´ski (2003) based on the univariate increasing concave order (often referred to as “second order stochastic dominance” in the literature). In Dentcheva and Ruszczyn´ski (2003), “pure” stochastic dominance constraints are considered where the decision variables are random variables. This work is continued in Dentcheva and Ruszczyn´ski (2004) for more general optimization problems with nonlinear mappings from a decision space to the space of random variables. These works (Dentcheva and Ruszczyn´ski 2003, 2004) are the first to observe that a certain class of utility functions act as Lagrange multipliers for second order stochastic dominance constraints. In Dentcheva and Ruszczyn´ski (2010), uncertainty about the underlying probability distribution is studied and robust second order stochastic dominance constraints are proposed. Cutting plane methods are devised for second order stochastic dominance constraints in Fábián et al. (2011). Stochastic integer programs with second order stochastic dominance and mixed-integer linear recourse are introduced in Gollmer et al. (2011).

Other univariate stochastic orders beyond the increasing concave order have been applied to optimization. In Dentcheva and Ruszczyn´ski (2006b), optimization problems with Lorenz (or inverse) stochastic dominance constraints are considered. Optimality conditions and a duality theory are developed. The increasing stochastic order (also called the usual stochastic order, or first order stochastic dominance) has been considered. Relaxations of first order stochastic dominance constraints are developed in Noyan et al. (2006). In Dentcheva et al. (2007), perturbation of the underlying probability measure of problems with first order stochastic dominance constraints is analyzed. In Drapkin and Schultz (2010), algorithms for stochastic programs with first order stochastic dominance constraints are developed and studied.

Work on multivariate stochastic order constraints has already begun. In Dentcheva and

Ruszczyn´ski (2009), the “multivariate linear second order” is proposed and studied. This stochastic ordering between random vectors is based on applying the univariate increasing concave order to weighted sums of the components of random vectors. In Homem-de-Mello and Mehrotra (2009), the “polyhedral linear second order” is defined, and in Hu et al. (2012), the “linear convex second order” is defined. The three stochastic orders in Dentcheva and

Ruszczyn´ski (2009), Homem-de-Mello and Mehrotra (2009), Hu et al. (2012) are all based on the same idea, but differ in the choice of weights. Homem-de-Mello and Mehrotra (2009) develop a detailed cut generation algorithm, and Hu et al. (2012) show sample average approximation is consistent for this problem class and conduct a convergence rate analysis.

Stochastic order constraints have significant merit in applications. In Dentcheva and

Ruszczyn´ski (2006a) and Roman et al. (2006) portfolio optimization problems with second order stochastic dominance constraints are studied. In Nie et al. (2012), optimal path problems with second order stochastic dominance constraints are analyzed. An application to a homeland security problem is developed in Hu et al. (2011).

Our present paper makes two major contributions to the literature. First, we propose a general and flexible class of multivariate integral stochastic order constraints. In fact, a complete description of multivariate risk preferences must account for all of the ways that the marginal utility in one random prospect can depend on the others. Clearly, the family of increasing concave functions from which risk preferences can be drawn is larger than the class generated by the functions in Dentcheva and Ruszczyn´ski (2009), Homem-deMello and Mehrotra (2009), Hu et al. (2012). Our present paper generalizes (Dentcheva and Ruszczyn´ski 2009; Homem-de-Mello and Mehrotra 2009; Hu et al. 2012) with integral stochastic orders based on arbitrary parametrized families of increasing concave functions.