当前位置:首页 >> >>


Diana Barro1 , Elio Canestrelli1 and Pierangelo Ciurlia1

1 Department of Applied Mathematics University Ca’ Foscari Venice (e-mail: d.barro@unive.it, canestre@unive.it, ciurlia@unive.it)

A BSTRACT: The solution of a multistage stochastic programming problem needs a suitable representation of uncertainty which may be obtained through a satisfactory scenario tree construction. Unfortunately there is a trade-off between the level of accuracy in the description of the stochastic component and the computational tractability of the resulting scenario-based problem. In this contribution we address the problem of how to face such a trade-off which plays a crucial role in the determination of the optimal solution. To this aim we discuss methods which allow to progressively reduce a given scenario tree by means of state aggregation. In this process it is important to take into account the choice of proper aggregation criteria in order to try to preserve all the relevant information. K EYWORDS: Stochastic Programming, Scenario tree, Reduction, Spatial Aggregation.

1 Introduction
A possible way to cope with uncertainty in multiperiod ?nancial optimization problems is to use scenarios to describe the possible future market situations. The introduction of a scenario tree structure to describe uncertainty allows to transform a stochastic programming problem into a deterministic equivalent optimization problem. Although the resulting scenario-based problem represents an approximation of the original stochastic problem, it may still be dif?cult to solve directly due to its large dimensions. To deal with this dif?culty we can resort to either proper optimization methods, which exploit the structure of the problem (see among others Barro & Canestrelli, 2005a), or aggregation techniques which reduce the dimensions of the original scenario tree. The construction of a scenario tree is a complex task which requires not only the modelling of the random data and the estimation of the underlying stochastic processes, but also the choice of proper discretization, approximation or sampling techniques. In this contribution we focus only on the problem of the reduction of a given scenario tree for a multistage portfolio model. We are interested in reducing the dimensions, i.e. the number of scenarios, of the original scenario tree in order to obtain a smaller tree while preserving as much of the information content as possible. In more detail we are interested in the distance between the two scenario trees, the original one and the reduced one, with respect

to probability distributions, optimal solutions and optimal values for the stochastic optimization problem.

2 Scenario tree reduction using aggregation methods
Several recent contributions in the literature address the problem of an optimal reduction of the original scenario tree for stochastic optimization problems both from a theoretical point of view (see for example Dupaˇ ov? et al. , 2003; Heitsch & R¨ misch, c a o 2003) and from a practical one (see for example Gr¨ we-Kuska et al. , 2003; Klaassen, o 1998). The optimal reduction problem is strictly related both with the optimal generation of a scenario tree (see Dupaˇ ov? et al. , 2000; P?ug, 2001), and with stability propc a erties of optimal solution of stochastic programming problems (see Dupaˇ ov? , 1990; c a Rachev & R¨ misch, 2002; Schultz, 2000; Shapiro, 1994). o To obtain a reduction in the dimension of the optimization problems we can apply different strategies based on spatial aggregation, time aggregation, or combinations of them. Time aggregation is obtained reducing the number of decision stages in the problem. A typical example is given by the multiperiod two-stage decision problem which represents a convenient form used to recast multistage stochastic programming problems. In this problem the planning horizon refers to a generic time horizon T while there are only two decision stages; that is, there is no correspondence between time periods and decision stages. Spatial aggregation consists in the reduction of the scenario tree by deleting scenarios, that is reducing the number of realizations for the random quantities. The two strategies can be jointly applied to obtain a substantial reduction in the original scenario tree. Moreover they can be at the basis of disaggregation techniques to solve stochastic programming problems. In Klaassen (1998) an application of time and state aggregations to built arbitrage-free scenario trees is presented. In the following we focus on a scenario reduction algorithm proposed by GroweKuska et al. (2003). Based on the minimization of a probability metric, this method allows to obtain, from the original scenario tree, a subset of scenarios of prescribed cardinality or accuracy. The probability distance used is the Kantorovich distance which in the case of discrete probability distributions with a ?nite number of scenarios corresponds to the optimal value of a linear transportation problem (for a more detailed description see Heitsch & R¨ misch, 2003). In the considered reduction algorithm o only the information on the probability of the deleted scenarios survives, through an optimal redistribution rule, while the information related to the values in the deleted nodes disappears. Starting from the method described in Gr¨ we-Kuska et al. , 2003, in this contrio bution we propose an aggregation algorithm in which we keep trace not only of the probabilities of the deleted scenarios but also of the values of the deleted nodes. In this way we reduce the amount of information which is lost at each step of the reduction process. Moreover in order to account not only for the distance among the probability

distributions but also between ?ltrations we consider a reduction which operates only on portions of the original tree thus allowing to preserve the ?ltration structure. The proposed algorithm works for a generic scenario tree built to describe the behavior of random data in a multistage stochastic programming problem. This means that there are no restrictions on the size or structure of the tree that has to be reduced. In order to test the proposed scenario reduction procedure we consider a multistage portfolio optimization problem and we assume that the dynamics of the asset returns are driven by geometric Brownian motions (for a detailed description of the model we refer to Barro & Canestrelli, 2005b). The behavior of the proposed algorithm is tested and the obtained results are compared with the ones obtained from the algorithm without the aggregation step. The quantities of interest which are monitored at each iteration are the optimal ?rst stage solutions, the optimal value of the objective function and the distance among the two scenario trees.

BARRO , D., & C ANESTRELLI , E. 2005a. A decomposition approach in multistage stochastic programming. Rendiconti per gli Studi Economici Quantitativi., 73– 88. BARRO , D., & C ANESTRELLI , E. 2005b. Dynamic portfolio optimization: time decomposition using the Maximum Principle with a scenario approach. European Journal of Operational Research., 163, 217–229. ˇ ? D UPA C OV A , J. 1990. Stability and sensitivity analysis for stochastic programming. Annals of Operations Research., 27, 21–38. ˇ ? D UPA C OV A , J., C ONSIGLI , G., & WALLACE , S.W. 2000. Scenarios for multistage stochastic programs. Annals of Operations Research., 100, 25–53. ˇ ? ¨ ¨ D UPA C OV A , J., G R OWE -K USKA , N., & R OMISCH , W. 2003. Scenario reduction in stochastic programming, an approach using probability metrics. Mathematical Programming Series A., 95, 493–511. ¨ ¨ G R OWE -K USKA , N., H EITSCH , H., & R OMISCH , W. 2003. Scenario reduction and scenario tree construction for power management problems. IEEE Bologna Power Tech Proceedings (A. Borghetti, C.A. Nucci, M. Paolone eds). ¨ H EITSCH , H., & R OMISCH , W. 2003. Scenario reduction algorithms in stochastic programming. Computational Optimization and Applications., 24, 187–206. K LAASSEN , P. 1998. Financial Asset-Pricing theory and stochastic programming models for asset/liability management: a synthesis. Management Science., 44, 31–48. P FLUG , G.C H . 2001. Scenario tree generation for multiperiod ?nancial optimization by optimal discretization. Mathematical Programming Series B., 89, 251–271. ¨ R ACHEV, S.T., & R OMISCH , W. 2002. Quantitative stability in stochastic programming: the method of probability metrics. Mathematics of Operations Research., 27, 792–818.

S CHULTZ , R. 2000. Some aspects of stability in stochastic programming. Annals of Operations Research., 100, 55–84. S HAPIRO , A. 1994. Quantitative stability in stochastic programming. Mathematical Programming., 67, 99–108.



All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。