|
Article Excerpt
We develop a goal-driven stochastic optimization model that considers a random objective function in achieving an aspiration level, target, or goal. Our model maximizes the shortfall-aware aspiration-level criterion, which encompasses the probability of success in achieving the aspiration level and an expected level of underperformance or shortfall. The key advantage of the proposed model is its tractability. We can obtain its solution by solving a small collection of stochastic linear optimization problems with objectives evaluated under the popular conditional-value-at-risk (CVaR) measure. Using techniques in robust optimization, we propose a decision-rule-based deterministic approximation of the goal-driven optimization problem by solving subproblems whose number is a polynomial with respect to the accuracy, with each subproblem being a second-order cone optimization problem (SOCP). We compare the numerical performance of the deterministic approximation with sampling-based approximation and report the computational insights on a multiproduct newsvendor problem.
Subject classifications: programming: stochastic.
Area of review: Optimization.
History: Received May 2006; revisions received December 2006, March 2007, September 2007, November 2007; accepted December 2007. Published online in Articles in Advance January 21, 2009.
1. Introduction
Stochastic optimization is an adopted framework for modeling optimization problems that involve uncertainty. In many standard stochastic optimization problems, the decision makers choose to minimize the aggregated expected profits over a multistage planning horizon, which are good models for decision makers who are risk neutral; see, for example, Birge and Louveaux (1997). However, optimizing an expectation assumes that the decision can be repeated a great number of times under identical conditions. Such assumptions may not be widely applicable in practice. The framework of stochastic optimization can also be adopted to address risk by optimizing over an expected utility or a mean risk objective; see Chapter 2 of Birge and Louveaux (1997), Ahmed (2006), and Ogryczak and Ruszczynski (2002). In such a model, the onus is on the decision maker to articulate his/her utility function or to determine the right parameter for the mean risk functional. This can be rather subjective and difficult to ascertain in practice.
Recent research in decision theory suggests a way of comprehensively and rigorously discussing decision theory without using utility functions; see Castagnoli and LiCalzi (1996) and Bordley and LiCalzi (2000). With the introduction of an aspiration level, target, or goal, the decision risk analysis focuses on making decisions so as to maximize the probability of reaching the aspiration level. As a matter of fact, aspiration level plays an important role in daily decision making. Lanzillotti's study (1958) interviewed officials of 20 large companies and verified that managers are more concerned about a target return on investment. In another study, Payne et al. (1980, 1981) illustrated that managers tend to disregard investment possibilities that are likely to underperform against their target. Simon (1959) also argued that most firms, goals are not maximizing profit, but attaining a target profit. Mao (1970), in an empirical study on managers' definitions of risk, concluded that risk is primarily considered to be the prospect of not meeting some target rate of return.
Based on these motivations, we study a two-stage stochastic optimization model that takes into account an aspiration level. This work is closely related to Charnes et al.'s (1958) and Charnes and Cooper's (1963) P-model, and Bereanu's (1964) optimality criterion of maximizing the probability of getting a profit above a target level. However, maximizing the probability of achieving a target is generally not a computationally tractable model. As such, studies along this objective have been confined to simple problems such as the newsvendor problem; see Sankarasubramanian and Kumaraswamy (1983), Lau and Lau (1988), Li et al. (1991), and Parlar and Weng (2003).
Besides its computational intractability, maximizing the success probability assumes that the modeler is indifferent to the level of losses. It does not address how catas trophic these losses can be expected to be when the "bad," small-probability events occur. Studies have suggested that subjects are not completely insensitive to these losses; see, for example, Payne et al. (1980, 1981). Diecidue and van de Ven (2008, p. 687) argued that a model that solely maximizes the success probability is "too crude to be normatively or descriptively relevant." They suggested an objective that takes into account a weighted combination of the success probability as well as an expected utility. However, when applied to the stochastic optimization framework, such a model remains computationally intractable.
Our goal-driven optimization model maximizes the shortfall-aware aspiration-level criterion, which takes into account the probability of success in achieving the goal and an expected level of underperformance or shortfall. We show that the proposed model is reduced to solving a small collection of stochastic optimization problems with objectives evaluated under the conditional-value-at-risk (CVaR) measure popularized by Rockafellar and Uryasev (2002). However, it is usually impractical or impossible to find the optimal solution to a stochastic optimization problem, and approximations are required. A sampling-based approximation is simple and attractive, but even in a two-stage model, the number of sampled scenarios required to approximate the solution to reasonable accuracy can be astronomically large, for example, in the presence of rare but catastrophic scenarios or in the absence of relatively complete recourse; see Shapiro and Nemirovski (2006). Moreover, sampling-based approximation of a stochastic optimization problem requires complete probability descriptions of the underlying uncertainties, which are almost never available in practice. It is conceivable that a solution derived from solving a model based on some assumed distributions may perform poorly if the actual distributions differ.
Motivated by recent development in robust optimization involving multistage decision processes (see Ben-Tal et al. 2004 and Chen et al. 2007, 2008), we propose a new decision-rule-based deterministic approximation for solving each of the stochastic optimization problems evaluated under the CVaR objective. In line with robust optimization, we require only modest assumptions on distributions, such as known means and bounded supports, standard deviations, and the forward and backward deviations introduced by Chen et al. (2007). We adopt a comprehensive model of uncertainty that incorporates both models of Chen et al. (2007, 2008). We also introduce new bounds on the CVaR measure and the expected positivity of a weighted sum of random variables, both of which are integral for us to obtain a tractable approximation that is in the form of a second-order cone optimization problem (SOCP); see Ben-Tal and Nemirovski (2001). This allows us to leverage on the state-of-the-art SOCP solvers, which are increasingly becoming more powerful, efficient, and robust. Finally, we compare the performance of the deterministic approximation with a sampling-based approximation on a class of multiproduct newsvendor problems that maximizes the shortfall-aware aspiration-level criterion.
This paper is organized as follows. In [section]2, we introduce the goal-driven model and propose the shortfall-aware aspiration-level criterion. We show that the goal-driven optimization problem can be reduced to solving a sequence of stochastic optimization problems with CVaR objectives. Using techniques in robust optimization, we develop in [section]3 a deterministic approximation of the stochastic optimization problem with CVaR objectives. In [section]4, we report some computational results and insights on a multiproduct newsvendor problem. Finally, [section]5 concludes this paper.
Notations. We denote a random variable by the tilde sign, i.e., [~.x]. Boldface lower-case letters such as x represent vectors, and the corresponding upper-case letters such as A denote matrices. In addition, [x.sup.+] = max{x, 0} and [x.sup.-]= max {- x, 0}. The same operations can be used on vectors, such as [y.sup.+] and [z.sup.-] in which corresponding operations are performed componentwise.
2. A Goal-Driven Optimization Model
We consider a two-stage decision process in which the decision maker first selects a feasible solution [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], or a so-called here-and-now solution in the face of uncertain outcomes that may influence the optimization model. Upon realization of [~.z] which denotes the vector of N random variables whose realizations correspond to the various scenarios, we select an optimal wait-and-see solution, or recourse action. We also refer to [~.Z] as the vector of primitive uncertainties, which consolidates all underlying uncertainties in the stochastic model. Given the solution, x, and a realization of scenario, z, the optimal wait-and-see objective we consider is given by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)
where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are known vectors, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are known matrices, [MATHEMATICAL EXPRESSION NOT...
|
