Description
Decision making can be regarded as the cognitive process resulting in the selection of a course of action among several alternative scenarios. Every decision making process produces a final choice.
In
problems of
decision
making
under
uncertainty,
we are often
STUDY REPORTS ON DECISION MAKING
PROBLEMS UNDER UNCERTAINTY
faced with the problem of representing the uncertainties in a form suitable for quantitative models. Huge databases
for the financial system now exist that facilitate the analysis of uncertainties representation. In portfolio management, one
has to decide how much wealth to put in each asset. In this paper we present a decision making process that incorporates
particle filters and a genetic algorithm into a state dependent dynamic portfolio optimization system. We propose particle
filters and scenario trees as a means of capturing uncertainty in future asset returns. Genetic algorithm was used as an
optimization method in scenario generation, and for determining the asset allocation. The proposed method shows better
results in comparison with the standard mean variance strategy according to Sharpe ratio.
Key words: Uncertainty representation, Particle filters, Scenario trees
1 INTRODUCTION lem is how to estimate parameters of the distribution [5].
A naive method would consist of the estimation of parame-
The development and use of dynamic portfolio opti-
mization algorithms is extremely important in financial
markets. This is the result of a major growth of financial
engineering, including the technological advances, global-
ization, increased competition, and ability to solve com- plex
financial models [1]. The goal of portfolio optimiza- tion is to
automatically determine the optimal percentage of the total
investment value allocated to each asset in the portfolio [2].
Optimality is expressed in terms of return maximization or
risk minimization. The core of a portfolio optimization
problem is a good representation of uncer- tainty.
Uncertainties should be represented in a form that re?ects the
reality and complexity of the financial system, but should also
be simple enough for algorithmic imple- mentation [3].
Uncertainty can be represented in a number of ways.
One approach is to represent uncertainty by multidimen-
sional continuous distributions or discrete distributions with
large number of outcomes [4]. In both cases, the prob-
ters directly from the historical data. However, such an ap-
proach fails to take into account the fact that newer data has
more in?uence on the parameters than older data. In line
with that, it is important to note that the problem does not lie
in modeling of historical data, but in predicting future
uncertainty from the above mentioned data. The most pop- ular
approach to parameter estimation is that of Bayesian
estimators, developed in [6], [7], and described in [8]. The
idea of Bayesian inference is to combine prior information
with sample returns. Besides parameter estimation, there is
also a problem of selecting the right multivariate distri-
bution, especially if statistical properties of uncertainty are
time variant.
A different method for representing uncertainty is sce-
nario trees. The goal of scenario trees is to represent the
underlying uncertainty with a small set of discrete out-
comes [1]. A scenario is a deterministic realization of all
uncertain parameters. There are two approaches in gen-
245
erating scenario trees: simulation based and optimization
based approach [9]. Simulation based approach is used in
[10], [11], and [12]. Optimization based approach is intro-
duced in [4] and used in [13]. The main idea is to generate a
set of scenarios that matches some specified statistical
properties of the underlying uncertainty. Those properties
could be moments, co-moments, marginals, or any other
relevant properties of the uncertainty. Scenario generation is
done by solving an optimization problem where the goal is to
minimize a measure of a distance between the statisti- cal
properties of constructed distribution and the statistical
properties of the underlying uncertainty. The method can
capture various kinds of uncertainties, but a realistic esti-
mation of the statistical properties of the underlying uncer-
tainty remains the biggest challenge in a good uncertainty
Particle filters, introduced in [15], are a technique for
implementing a recursive Bayesian filter by Monte Carlo
simulations. The key idea is to represent the required den- sity
function by a set of random samples with associated weights,
and to compute estimates based on these samples and weights.
As the number of samples highly increases, this
approximation becomes an equivalent representation to the
usual functional description of the required PDF, and the
particle filter approaches the optimal Bayesian es- timate. For
a more general description, see [16] and refer- ences therein.
To describe the algorithm, we introduce the following
notation. The state vector x
k
is assumed to evolve accord-
ing to the following system model:
representation. x
k
+1 = f
k
(x
k
, w
k
) (1 )
Here we propose a method for uncertainty representa-
tion based on particle filters and scenario trees. Particle filter
is used for estimation of the statistical properties of the
underlying uncertainty in future asset returns. We have created
a nonlinear model which exploits the known prop- erties of
asset returns. The parameters of the model are mean and
volatility of returns, whereas with particle filter
where f
k
is the system transition function and w
k
is a zero
mean, white noise sequence independent of past and cur-
rent states. At discrete time steps, measurements y
k
be-
come available. These measurements are related to the
state vector via the observation equation:
we maintain a sampled distribution of asset returns through the
steps of prediction and correction. Higher moments,
y
k
= h
k
(x
k
, v
k
)
(2 )
skewness and kurtosis, are estimated from the above men-
tioned distribution. Together with correlations between
different assets, those properties form a set of statistical
properties used for scenario generation. In scenario gen-
eration, a genetic algorithm was used as an optimization
method. Based on the proposed uncertainty representation
method, we have created a system for portfolio manage-
ment. Generated portfolios frequently demonstrate higher
returns than the ones based on a standard mean-variance
strategy while maintaining the same amount of risk.
where h
k
is the measurement function and v
k
is another
zero mean, white noise sequence with known PDF, inde-
pendent of past and present states and the system noise.
One of the particle filter algorithms proposed in the liter-
ature is sampling importance resampling (SIR) filter [15]. The
assumptions required to use the SIR filter are very weak. We
need to known state dynamics and measure- ment functions
(1) and (2), and have to be able to sam-
ple realizations from the process noise distribution v
k
and
from the prior density p(x
k
,x
k
÷
1
). Finally, the likelihood function
p(y
k
,x
k
) is necessary for pointwise evaluation (at
2 MODELLING APPROACH least up to proportionality). A set of particles and weights
2.1 Particle filters
Numerous problems in science require an estimation of
the state of a certain system that changes over time by us- ing
a sequence of noisy measurements on the system. For
example, in the financial system, it is a common task to es-
timate the expected value of an asset return, or the volatility of
asset returns. The standard Bayesian approach to state
estimation is to construct the probability density function
(PDF) of the state based on all possible information, in-
cluding the set of received measurements [14]. When cer-
tain constraints hold, the optimal solution is tractable. The
Kalman filter and Hidden Markov model are two such so-
lutions. When the optimal solution is intractable, there are
various strategies that may help approximate the optimal
solution. These approaches include extended Kalman fil-
ter, approximate grid-based filters, and particle filters.
246
{x
ik
, w
ik
}
N
1 is used to represent the sampled distribution i=
p(x
k
,y
1:
k
). The SIR filter uses resampling (elimination of
particles that have small weights and concentrating on par-
ticles with large weights) at each discrete time step. An
iteration of the SIR algorithm is given in Algorithm 1.
2.2 Scenario trees
The issue of modeling stochastic elements is critical to
any stochastic optimization. A method to obtain the dis-
crete outcomes for the random variables is referred to as
scenario tree generation. We define a scenario as a deter-
ministic realization of all uncertain parameters. Some sce-
narios may have identical history to some point. Because of
that, scenarios are organized in a scenario tree (see Fig. 1).
The scenario generation process should build scenarios that
represent the universe of all possible outcomes - we
Algorithm 1 SIR Particle Filter:
{x
ik
, w
ik
}
N
1
i=
=
scenario. f
i
(x, p) is a mathematical expression for calcu-
SIR({x
ik
÷
1
, w
ik
÷
1
}
N
1, y
k
) i=
lating statistical property i in the scenario tree, and SV
i
is
Input: {x
ik
÷
1
, w
ik
÷
1
}
N
1, y
k
i=
the specified value of statistical property i. Weighting with
w
i
enables the emphasis of certain properties.
Output: {x
ik
, w
ik
}
N
1 i=
1. for i = 1 to N do
Since the described optimization problem is generally
2.
3.
Draw x
ik
? p(x
k
,x
ik
÷
1
)
Calculate w
ik
= p(y
k
,x
ik
÷
1
)
not convex, the solution is probably a local one. However,
for most applications, it is satisfactory to have a scenario
4. end for
5. Calculate total weight t = SUM({w
i
}
N
1) k i=
6. for i = 1 to N do
tree with properties equal to or close to the specifications.
Solving of the optimization problem can be done in a num- ber
of ways, by using traditional non-convex optimization
7.
Normalize: w
ik
= t
÷
1
w
ik
methods, or metaheuristics, like simulated annealing or ge-
8. end for netic algorithm.
9. {x
ik
, w
i
}
N
1) = RESAMPLE({x
ik
, w
i
}
N
1)
k i=
10. return {x
ik
, w
i
}
N
1 k i=
k i= 3 MODEL DESCRIPTION
The focus of this paper is the applying of a stochastic
optimization method in portfolio management. Therefore, we
present a model for obtaining an optimal asset alloca- tion.
To find an optimal set of weights of each asset in a portfolio,
we need to represent the uncertainties from fi- nancial factors
in a form suitable for algorithmic computa- tion. We choose
scenario trees as a means of capturing
Fig. 1. An example of the scenario tree
want a representative set of scenarios. There exist different
methods of scenario generation. The two most widely used
ones are scenario reduction and moment matching [17].
The scenario reduction method is introduced and dis-
cussed in [18] and [19]. The goal is to eliminate sce- narios
that are similar or have a small probability. The method starts
with a large number of scenarios, which usu- ally result from a
simulation. With the scenario reduction method, the goal is to
represent the underlying distribution in an acceptable way
with a reduced number of scenarios.
The second method of scenario tree generation is based
on moment matching and is described in [4]. The starting
point for generating the scenario tree is a description of the
statistical properties of the underlying random variables. The
procedure generates a scenario tree that matches those
statistical properties as closely as possible. Generation of
scenarios is an optimization problem where the objective
function is the distance between statistical properties cal-
culated from scenarios and specified statistical properties. If
the distance is measured with a square norm, the follow-
ing optimization problem needs to be solved:
those uncertainties. In order to generate scenario trees,
estimation of statistical properties of underlying random
variables is needed. We propose particle filters for the esti-
mation of relevant statistical properties. With this in mind, our
portfolio management model consists of three indepen-
dent parts:
1. Estimation of statistical properties of asset returns,
2. Generation of scenario trees, 3.
Portfolio optimization.
Statistical properties of asset returns which we use are mean,
standard deviation, skewness and kurtosis of the re- turn
distributions of each asset in our portfolio. The corre- lations
between returns of different assets are also required. In order to
make an estimation, the model of the financial system is
developed, based on the known properties of as- set returns.
The estimation of the parameters of the model is done with
particle filter algorithm because of the nonlin- earity of the
developed model.
The estimated statistical properties form the basis of the
scenario generation method. We use the moment matching
method described in [4]. In order to generate the scenario
tree, we solve the optimization problem where the objec-
min
i
w
i
(f
i
(x, p) ÷ SV
i
),
i
p
i
= 1 , p
i
> 0 .
(3 )
tive function is the distance between statistical properties
calculated from scenarios and specified statistical proper- ties.
The solution of the resulting non-convex optimization
Minimization is done over vector x, which is a vector problem is obtained from a genetic algorithm.
of outcomes of all underlying random variables in all sce- After generating the scenario tree, we can solve the
narios, and p, which is a vector of probabilities of each deterministic equivalent of the stochastic asset allocation
247
problem. The solution of the problem is a set of asset
weights that maximize some utility function of wealth.
Solving of the given optimization problem is done with the
1. The system model is non-linear and we deal with a
non-linear state estimation
2. The particle filter can represent the proposed distribu-
genetic algorithm.
The following subsections describe the parts of the
model. Simultaneously, we demonstrate our approach on
tion f (ˆ
k
+1,r
k
) in case when the shape of the distri- r
bution is unimodal and when the shape is bimodal
the example of the equity indexes of France, Germany,
Japan, UK and USA in January 1975. With particle filters we
estimate the distribution of returns of index values for
February 1975, and then we generate scenarios that match the
parameters of that distribution. It is important to note
that we deal with logarithmic index returns, defined as:
3. The particle filter forms the distribution f (ˆ
k
+1,r
k
) r
with importance sampling so that the estimates of its
moments can be calculated efficiently by using a com-
puter.
For the sake of the simplicity of the model, particle fil-
ters are used only in estimation of parameters of univari-
r
k
= ln SS
k
k ÷1
(4 )
ate distribution. Still, correlation coefficients are needed in the
process of portfolio optimization. We find correlation
coefficients by using statistical estimators from historical
where S
k
and S
k
÷
1
are current and previous index values.
3.1 Estimation of statistical properties of asset re-
turns
In order to use particle filters for state estimation of a
dynamic system, one has to build a model of the system. We
use a different particle filter for different assets. Each
values on a time window of 60 months. The estimation
problem is solved using an SIR particle filter described in
Section 2. This filter uses the prior density as the impor-
tance density function. We use multinomial resampling for the
resampling procedure. The quality of state estimation could
be improved with other, more advanced methods, and it is a
topic of an ongoing research.
particle filter uses mean and variance of returns of the asset
as state variables. So, the state of the system at time step k
is a vector
The example of the distribution f (ˆ
k
+1,r
k
) for the r
Japan equity index on February 1975 is shown in Figure
x
k
= µ
k
2. The comparison is made in Table 1. We notice that
o
2
k
(5 ) the statistical properties of this distribution differ from the
properties obtained with estimation from historical data.
where µ
k
represents the mean of the asset returns ando
2
is k
the variance of asset returns. The input to the system is the
last known asset return r
k
. The state vector x
k
is assumed
to evolve according to the following system model,
5
4
3
µ
k
=oµ
k
÷
1
+ (1 ÷o)r
k
+c
k
o
2
k
=|o
2
÷
1
+ (1 ÷|)r
2
+q
k
(6 )
2
k k
where variablesc
k
andq
k
represent the additive Gaussian 1
white noise. For technical reasons, samples fromq
k
which
would result with negativeo
2
are ignored. Those equations k
follow the exponentially weighted moving average model.
-0.4 -0.3 -0.2 -0.1 0
Monthly return
0.1 0.2 0 .3 0.4
The output of the system is the estimated return in the ˆ
k
+1 r
in the next time step. We propose the following distribution
Fig. 2. Probability density function of estimated Japan eq-
uity index return for February 1975
of ˆ
k
+1, r
C
f (ˆ
k
+1,r
k
) = r
1+
(ˆk+1÷µk)2r
+
((ˆk+1÷µk)2÷(rk÷µk)2)2r Table 1. Comparison of statistical properties estimated
o2k 2o2k
(7 )
with different methods
Mean Std. dev Skewness Kurtosis
where C is the normalization constant. Historical 0.009 0 .0 6 3 - 0 .4 3 7 3 .1 9 6
As a result of the estimation procedure, we need esti- Particle F. 0.005 0 .0 8 2 - 0 .0 8 4 1 .5 7 6
mates of the mean, standard deviation, skewness and kur-
tosis of the distribution f (ˆ
k
+1,r
k
). Since particle filter r
maintains the distribution in a sampled form from one time
step to another, estimates can be computed efficiently by
using statistical estimators. There are numerous reasons
for using particle filters in this particular task:
248
P
r
o
b
a
b
i
l
i
t
y
d
e
n
s
i
t
y
f
u
n
c
t
i
o
n
3.2 Scenario tree generation
We use scenario trees for representing uncertainty in fu-
ture asset returns. For the generation of the tree we use op-
timization method based on moment matching described
in [4]. Parameters of the uncertainty distribution serve as an
input to the scenario generation process. Optimization
problem (3) is solved by the genetic algorithm. The output of
the optimization process is the optimal set of scenarios
organized in a tree, where the optimality is expressed in
terms of the distance to the specified statistical properties.
Naturally, the fitness function of the genetic algorithm is the
distance between the properties. The genetic algorithm
3.3 Portfolio optimization
We implement the method for representing uncertainty
in the example of portfolio management. In this applica-
tion, the goal is to maximize the sum of the expected utility of
wealth subject to budget constraints.
The optimization problem can be formulated in a fol-
lowing manner:
that solves the problem (3) uses: a rank fitness scaling,
max EU =t
s
f (w
s
)
stochastic uniform selection, a modified Gaussian muta-
s t t
tion and scattered crossover. The size of the population
w
s
=
I
depends on the extent of the problem. In our example, we
t
r
s
,t÷
1
o
s
,t÷1
use 5 assets and 30 statistical properties. The usual choice
s.t.
i=1
o
s
,t = 1 i
i i (8 )
for the number of scenarios, based on the discussion in [9],
is 6 scenarios, which leads to 36 unknown parameters of
i
t
s
,t = 1 1
scenarios (each scenario has a probability value and values for
returns for each asset). For optimizing a function of 36
variables, we use a population of 250 candidates. To en-
wheret
s
is the probability that scenario s occurs at time t
step t; w
s
is the wealth at time step t under scenario s; t
r
s
,t is return of asset i at time step t under scenario s;o
s
,t
sure that the solution found is indeed a global solution, we i i
rerun the algorithm from different starting points.
For example, given the statistical properties in Table
2, we build a single period scenario tree that consists of six
scenarios. With genetic algorithm, we obtain a perfect match.
A set of six generated scenarios is given in Fig- ure 3 where
the return of each asset in every scenario is presented.
Table 2. Statistical properties of index returns for February
1975. All properties but correlations are estimated with
particle filters
is the weight for asset i at time step t under scenario s.
The optimization problem (8) is a deterministic equivalent
of the underlying stochastic problem which we solve with
genetic algorithm. The output of the optimization process is
the set of weights of assets in the optimal portfolio for which
the maximum of expected utility is obtained. As a fitness
function we use negative utility, since the goal of genetic
algorithm is function minimization. Compared to the size of
the optimization problem (3), the problem (8) is simpler and
easier to solve. For example, when there are 5 assets in a
portfolio and 6 scenarios in a tree, problem
Mean Std. dev Skewness Kurtosis
(3) finds 36 variables, while problem (8) finds only 5 of
US A
UK
Japan
Germany
France
-0.022
-0.048
0.005
0.007 -
0.017
0.035
0.104
0.082
0.074
0.047
0.153
0.064
-0.084
-0.112
-0.086
3.227
1.355
1.576
1.633
2.844
them. For that reason, we use a population size of only 60
candidates.
Given the scenarios in Figure 3, we find the optimal
weights using the logarithmic utility function. The results are
reported in Table 3 and compared to the classical mean
Correlations of returns variance analysis. The difference due to different estima-
US A UK Japan Germany France
tion methods used clearly exists.
US A 1 0.508 0.320 0.337 0.398
UK
Japan
Germany
France
1 0.372
1
0.313
0.471
1
0.588
0.319
0.608
1
Table 3. Weights of the optimal portfolio calculated with
our model using compared to the classical mean variance
portfolio
0,2
0,1
0
-0,1
-0,2
-0,3
USA
UK
Japan
Germany
France
4
Scenario trees
Classic mean-
variance
RESULTS
US A
0.325
0.320
UK
0
0
Japan
0.080
0.462
Germany
0.517
0.218
France
0.078
0
0,081 0,043 0,316 0,444 0,061 0,055
Fig. 3. Generated scenarios (with probabilities) for which the
distribution properties match the properties in Table 2
The experiments are based on the data set from MSCI
(Morgan Stanley Capital International). We use the to- tal
return equity indices of France, Germany, Japan, UK and the
USA. Equity returns are based on the month-end
249
US-dollar value of the equity index for the period between
January 1970 and December 2000. To verify the perfor-
mance of the different portfolio models, the weights from
each model are determined, and the return from holding this
portfolio in the next month is calculated. In case of models
that create historical estimates of parameters, those estimates
are based on a window of 60 months. In each case, the out-
of-sample period is from January 1975 to De- cember 2000.
Table 4 shows summary statistics for themonthly returns on
the five indices and the correlations of the returns.
Table 4. Summary statistics of the data from January 1970
to January 2000
developed. Particle filters were used for estimation of sta-
tistical properties of uncertainty from historical data, and
scenario trees were used as a model for uncertainty rep-
resentation. The described method was included into the
decision making process for dynamic portfolio optimiza-
tion. Uncertainty in future asset returns, being the main
problem in portfolio optimization, was captured by the pro-
posed method. By using obtained uncertainty representa-
tion, portfolio optimization was performed by maximiza-
tion of logarithmic utility function of the wealth. For the
purpose of the above mentioned maximization, and for the
estimation of the parameters of the scenario trees, a genetic
algorithm was used.
US A
UK
Japan
Germany
France
Mean
0.0049
0.0060
0.0117
0.0065
0.0060
Correlation coefficients
Std. dev.
0.0446
0.0717
0.0658
0.0603
0.0694
The described method was validated by the use of the
MSCI data sets. The method showed better results in com-
parison to the standard mean variance strategy according to
Sharpe ratio. Generated portfolios frequently demonstrate
higher returns than Markowitz optimal portfolios while
maintaining the same amount of risk.
Future research in this area should continue along sev-
US A UK Japan Germany France
US A 1 0.5171 0.2699 0.3598 0.4405
eral dimensions. Firstly, in this research, a single scenario
UK
Japan
Germany
France
1 0.3708
1
0.4393
0.3889
1
0.5440
0.3922
0.6136
1
trees was used. A combination of multiple scenario trees
and particle filters could result in some new enhancements.
Secondly, different utility functions in portfolio optimiza-
tions could create valuable progress. Thirdly, there is no
fundamental reason why 1,000 or 10,000 scenarios cannot
To assess the performance of the different portfolio
models, we calculate the average out of sample means,
volatilities and Sharpe ratios of each strategy - the mean-
variance analysis, scenario trees and scenario trees with
particle filters. The results are reported in Table 5. Com-
pared with mean-variance analysis, in which the histori- cal
mean returns are taken to be the estimator of the ex-
pected returns µ, the portfolios constructed by using the
model for representing uncertainty showed higher returns
while maintaining the same level of volatility. In the case in
which scenario trees were generated without particle fil- ters,
the key difference was the utility function used, which gave
more balanced portfolios. When particle filters were used as
estimators of the statistical parameters of future re- turns,
portfolios with even higher returns were generated. Both
methods clearly outperform the traditional method.
Table 5. Experiment results
be created by parallel and distributed computers.
REFERENCES
[1] J. M. Mulvey, D. P. Rosenbaum, B. Shetty, Strategic finan-
cial risk management and operations research, European
Journal of Operational Research, 1997.
[2] H. Markowitz, Portfolio selection, Journal of finance, pp.
77-91. 1952.
[3] J. M. Mulvey, B. Shetty, Financial planning via muti-
stage stochastic optimization, Computers & Operations
Research, pp. 1-20, 2004.
[4] K. Hoyland, S. W. Wallace, Generating Scenario Trees for
Multistage Decision Problems, Management Science, pp.
295-307, 2001.
[5] V. K. Chopra, W. T. Ziemba, The effect of errors in means,
variances, and covariances on optimal portfolio choice,
Journal of Portfolio Management, pp. 6-11, 1993.
5
Mean-variance
Scenario trees
Scenario trees with PF
CONCLUSION
Mean
0.0087
0.0091
0.0103
Std. dev.
0.0465
0.0458
0.0483
Sharpe ratio
0.1871
0.1987
0.2133
[6] P. Jorion, Bayes-Stein estimation for portfolio analysis,
The Journal of Financial and Quantitative Analysis, pp. 279-
292, 1986.
[7] P. Jorion, International portfolio diversification with es-
timation risk, Journal of Business, pp. 259-278. 1985.
[8] R. Kan, G. Zhou, Optimal Portfolio Choice with Param-
In this paper a method for the uncertainty representa- eter Uncertainty, Journal of Financial and Quantitative
tion based on particle filters and scenario trees has been Analysis, 2007.
250
[9] N. Gülpinar, B. Rustem, R. Settergren, Simulation and op-
timization approach scenario tree generation, Journal of Economic Dynamics and Control, pp. 1291-1315, 2004.
[10] P?ug, G., Scenario tree generation for multiperiod finan-
cial optimization by optimal discretization, Mathematical Programming, 251-271, 2001.
doc_126036646.docx
Decision making can be regarded as the cognitive process resulting in the selection of a course of action among several alternative scenarios. Every decision making process produces a final choice.
In
problems of
decision
making
under
uncertainty,
we are often
STUDY REPORTS ON DECISION MAKING
PROBLEMS UNDER UNCERTAINTY
faced with the problem of representing the uncertainties in a form suitable for quantitative models. Huge databases
for the financial system now exist that facilitate the analysis of uncertainties representation. In portfolio management, one
has to decide how much wealth to put in each asset. In this paper we present a decision making process that incorporates
particle filters and a genetic algorithm into a state dependent dynamic portfolio optimization system. We propose particle
filters and scenario trees as a means of capturing uncertainty in future asset returns. Genetic algorithm was used as an
optimization method in scenario generation, and for determining the asset allocation. The proposed method shows better
results in comparison with the standard mean variance strategy according to Sharpe ratio.
Key words: Uncertainty representation, Particle filters, Scenario trees
1 INTRODUCTION lem is how to estimate parameters of the distribution [5].
A naive method would consist of the estimation of parame-
The development and use of dynamic portfolio opti-
mization algorithms is extremely important in financial
markets. This is the result of a major growth of financial
engineering, including the technological advances, global-
ization, increased competition, and ability to solve com- plex
financial models [1]. The goal of portfolio optimiza- tion is to
automatically determine the optimal percentage of the total
investment value allocated to each asset in the portfolio [2].
Optimality is expressed in terms of return maximization or
risk minimization. The core of a portfolio optimization
problem is a good representation of uncer- tainty.
Uncertainties should be represented in a form that re?ects the
reality and complexity of the financial system, but should also
be simple enough for algorithmic imple- mentation [3].
Uncertainty can be represented in a number of ways.
One approach is to represent uncertainty by multidimen-
sional continuous distributions or discrete distributions with
large number of outcomes [4]. In both cases, the prob-
ters directly from the historical data. However, such an ap-
proach fails to take into account the fact that newer data has
more in?uence on the parameters than older data. In line
with that, it is important to note that the problem does not lie
in modeling of historical data, but in predicting future
uncertainty from the above mentioned data. The most pop- ular
approach to parameter estimation is that of Bayesian
estimators, developed in [6], [7], and described in [8]. The
idea of Bayesian inference is to combine prior information
with sample returns. Besides parameter estimation, there is
also a problem of selecting the right multivariate distri-
bution, especially if statistical properties of uncertainty are
time variant.
A different method for representing uncertainty is sce-
nario trees. The goal of scenario trees is to represent the
underlying uncertainty with a small set of discrete out-
comes [1]. A scenario is a deterministic realization of all
uncertain parameters. There are two approaches in gen-
245
erating scenario trees: simulation based and optimization
based approach [9]. Simulation based approach is used in
[10], [11], and [12]. Optimization based approach is intro-
duced in [4] and used in [13]. The main idea is to generate a
set of scenarios that matches some specified statistical
properties of the underlying uncertainty. Those properties
could be moments, co-moments, marginals, or any other
relevant properties of the uncertainty. Scenario generation is
done by solving an optimization problem where the goal is to
minimize a measure of a distance between the statisti- cal
properties of constructed distribution and the statistical
properties of the underlying uncertainty. The method can
capture various kinds of uncertainties, but a realistic esti-
mation of the statistical properties of the underlying uncer-
tainty remains the biggest challenge in a good uncertainty
Particle filters, introduced in [15], are a technique for
implementing a recursive Bayesian filter by Monte Carlo
simulations. The key idea is to represent the required den- sity
function by a set of random samples with associated weights,
and to compute estimates based on these samples and weights.
As the number of samples highly increases, this
approximation becomes an equivalent representation to the
usual functional description of the required PDF, and the
particle filter approaches the optimal Bayesian es- timate. For
a more general description, see [16] and refer- ences therein.
To describe the algorithm, we introduce the following
notation. The state vector x
k
is assumed to evolve accord-
ing to the following system model:
representation. x
k
+1 = f
k
(x
k
, w
k
) (1 )
Here we propose a method for uncertainty representa-
tion based on particle filters and scenario trees. Particle filter
is used for estimation of the statistical properties of the
underlying uncertainty in future asset returns. We have created
a nonlinear model which exploits the known prop- erties of
asset returns. The parameters of the model are mean and
volatility of returns, whereas with particle filter
where f
k
is the system transition function and w
k
is a zero
mean, white noise sequence independent of past and cur-
rent states. At discrete time steps, measurements y
k
be-
come available. These measurements are related to the
state vector via the observation equation:
we maintain a sampled distribution of asset returns through the
steps of prediction and correction. Higher moments,
y
k
= h
k
(x
k
, v
k
)
(2 )
skewness and kurtosis, are estimated from the above men-
tioned distribution. Together with correlations between
different assets, those properties form a set of statistical
properties used for scenario generation. In scenario gen-
eration, a genetic algorithm was used as an optimization
method. Based on the proposed uncertainty representation
method, we have created a system for portfolio manage-
ment. Generated portfolios frequently demonstrate higher
returns than the ones based on a standard mean-variance
strategy while maintaining the same amount of risk.
where h
k
is the measurement function and v
k
is another
zero mean, white noise sequence with known PDF, inde-
pendent of past and present states and the system noise.
One of the particle filter algorithms proposed in the liter-
ature is sampling importance resampling (SIR) filter [15]. The
assumptions required to use the SIR filter are very weak. We
need to known state dynamics and measure- ment functions
(1) and (2), and have to be able to sam-
ple realizations from the process noise distribution v
k
and
from the prior density p(x
k
,x
k
÷
1
). Finally, the likelihood function
p(y
k
,x
k
) is necessary for pointwise evaluation (at
2 MODELLING APPROACH least up to proportionality). A set of particles and weights
2.1 Particle filters
Numerous problems in science require an estimation of
the state of a certain system that changes over time by us- ing
a sequence of noisy measurements on the system. For
example, in the financial system, it is a common task to es-
timate the expected value of an asset return, or the volatility of
asset returns. The standard Bayesian approach to state
estimation is to construct the probability density function
(PDF) of the state based on all possible information, in-
cluding the set of received measurements [14]. When cer-
tain constraints hold, the optimal solution is tractable. The
Kalman filter and Hidden Markov model are two such so-
lutions. When the optimal solution is intractable, there are
various strategies that may help approximate the optimal
solution. These approaches include extended Kalman fil-
ter, approximate grid-based filters, and particle filters.
246
{x
ik
, w
ik
}
N
1 is used to represent the sampled distribution i=
p(x
k
,y
1:
k
). The SIR filter uses resampling (elimination of
particles that have small weights and concentrating on par-
ticles with large weights) at each discrete time step. An
iteration of the SIR algorithm is given in Algorithm 1.
2.2 Scenario trees
The issue of modeling stochastic elements is critical to
any stochastic optimization. A method to obtain the dis-
crete outcomes for the random variables is referred to as
scenario tree generation. We define a scenario as a deter-
ministic realization of all uncertain parameters. Some sce-
narios may have identical history to some point. Because of
that, scenarios are organized in a scenario tree (see Fig. 1).
The scenario generation process should build scenarios that
represent the universe of all possible outcomes - we
Algorithm 1 SIR Particle Filter:
{x
ik
, w
ik
}
N
1
i=
=
scenario. f
i
(x, p) is a mathematical expression for calcu-
SIR({x
ik
÷
1
, w
ik
÷
1
}
N
1, y
k
) i=
lating statistical property i in the scenario tree, and SV
i
is
Input: {x
ik
÷
1
, w
ik
÷
1
}
N
1, y
k
i=
the specified value of statistical property i. Weighting with
w
i
enables the emphasis of certain properties.
Output: {x
ik
, w
ik
}
N
1 i=
1. for i = 1 to N do
Since the described optimization problem is generally
2.
3.
Draw x
ik
? p(x
k
,x
ik
÷
1
)
Calculate w
ik
= p(y
k
,x
ik
÷
1
)
not convex, the solution is probably a local one. However,
for most applications, it is satisfactory to have a scenario
4. end for
5. Calculate total weight t = SUM({w
i
}
N
1) k i=
6. for i = 1 to N do
tree with properties equal to or close to the specifications.
Solving of the optimization problem can be done in a num- ber
of ways, by using traditional non-convex optimization
7.
Normalize: w
ik
= t
÷
1
w
ik
methods, or metaheuristics, like simulated annealing or ge-
8. end for netic algorithm.
9. {x
ik
, w
i
}
N
1) = RESAMPLE({x
ik
, w
i
}
N
1)
k i=
10. return {x
ik
, w
i
}
N
1 k i=
k i= 3 MODEL DESCRIPTION
The focus of this paper is the applying of a stochastic
optimization method in portfolio management. Therefore, we
present a model for obtaining an optimal asset alloca- tion.
To find an optimal set of weights of each asset in a portfolio,
we need to represent the uncertainties from fi- nancial factors
in a form suitable for algorithmic computa- tion. We choose
scenario trees as a means of capturing
Fig. 1. An example of the scenario tree
want a representative set of scenarios. There exist different
methods of scenario generation. The two most widely used
ones are scenario reduction and moment matching [17].
The scenario reduction method is introduced and dis-
cussed in [18] and [19]. The goal is to eliminate sce- narios
that are similar or have a small probability. The method starts
with a large number of scenarios, which usu- ally result from a
simulation. With the scenario reduction method, the goal is to
represent the underlying distribution in an acceptable way
with a reduced number of scenarios.
The second method of scenario tree generation is based
on moment matching and is described in [4]. The starting
point for generating the scenario tree is a description of the
statistical properties of the underlying random variables. The
procedure generates a scenario tree that matches those
statistical properties as closely as possible. Generation of
scenarios is an optimization problem where the objective
function is the distance between statistical properties cal-
culated from scenarios and specified statistical properties. If
the distance is measured with a square norm, the follow-
ing optimization problem needs to be solved:
those uncertainties. In order to generate scenario trees,
estimation of statistical properties of underlying random
variables is needed. We propose particle filters for the esti-
mation of relevant statistical properties. With this in mind, our
portfolio management model consists of three indepen-
dent parts:
1. Estimation of statistical properties of asset returns,
2. Generation of scenario trees, 3.
Portfolio optimization.
Statistical properties of asset returns which we use are mean,
standard deviation, skewness and kurtosis of the re- turn
distributions of each asset in our portfolio. The corre- lations
between returns of different assets are also required. In order to
make an estimation, the model of the financial system is
developed, based on the known properties of as- set returns.
The estimation of the parameters of the model is done with
particle filter algorithm because of the nonlin- earity of the
developed model.
The estimated statistical properties form the basis of the
scenario generation method. We use the moment matching
method described in [4]. In order to generate the scenario
tree, we solve the optimization problem where the objec-
min
i
w
i
(f
i
(x, p) ÷ SV
i
),
i
p
i
= 1 , p
i
> 0 .
(3 )
tive function is the distance between statistical properties
calculated from scenarios and specified statistical proper- ties.
The solution of the resulting non-convex optimization
Minimization is done over vector x, which is a vector problem is obtained from a genetic algorithm.
of outcomes of all underlying random variables in all sce- After generating the scenario tree, we can solve the
narios, and p, which is a vector of probabilities of each deterministic equivalent of the stochastic asset allocation
247
problem. The solution of the problem is a set of asset
weights that maximize some utility function of wealth.
Solving of the given optimization problem is done with the
1. The system model is non-linear and we deal with a
non-linear state estimation
2. The particle filter can represent the proposed distribu-
genetic algorithm.
The following subsections describe the parts of the
model. Simultaneously, we demonstrate our approach on
tion f (ˆ
k
+1,r
k
) in case when the shape of the distri- r
bution is unimodal and when the shape is bimodal
the example of the equity indexes of France, Germany,
Japan, UK and USA in January 1975. With particle filters we
estimate the distribution of returns of index values for
February 1975, and then we generate scenarios that match the
parameters of that distribution. It is important to note
that we deal with logarithmic index returns, defined as:
3. The particle filter forms the distribution f (ˆ
k
+1,r
k
) r
with importance sampling so that the estimates of its
moments can be calculated efficiently by using a com-
puter.
For the sake of the simplicity of the model, particle fil-
ters are used only in estimation of parameters of univari-
r
k
= ln SS
k
k ÷1
(4 )
ate distribution. Still, correlation coefficients are needed in the
process of portfolio optimization. We find correlation
coefficients by using statistical estimators from historical
where S
k
and S
k
÷
1
are current and previous index values.
3.1 Estimation of statistical properties of asset re-
turns
In order to use particle filters for state estimation of a
dynamic system, one has to build a model of the system. We
use a different particle filter for different assets. Each
values on a time window of 60 months. The estimation
problem is solved using an SIR particle filter described in
Section 2. This filter uses the prior density as the impor-
tance density function. We use multinomial resampling for the
resampling procedure. The quality of state estimation could
be improved with other, more advanced methods, and it is a
topic of an ongoing research.
particle filter uses mean and variance of returns of the asset
as state variables. So, the state of the system at time step k
is a vector
The example of the distribution f (ˆ
k
+1,r
k
) for the r
Japan equity index on February 1975 is shown in Figure
x
k
= µ
k
2. The comparison is made in Table 1. We notice that
o
2
k
(5 ) the statistical properties of this distribution differ from the
properties obtained with estimation from historical data.
where µ
k
represents the mean of the asset returns ando
2
is k
the variance of asset returns. The input to the system is the
last known asset return r
k
. The state vector x
k
is assumed
to evolve according to the following system model,
5
4
3
µ
k
=oµ
k
÷
1
+ (1 ÷o)r
k
+c
k
o
2
k
=|o
2
÷
1
+ (1 ÷|)r
2
+q
k
(6 )
2
k k
where variablesc
k
andq
k
represent the additive Gaussian 1
white noise. For technical reasons, samples fromq
k
which
would result with negativeo
2
are ignored. Those equations k
follow the exponentially weighted moving average model.
-0.4 -0.3 -0.2 -0.1 0
Monthly return
0.1 0.2 0 .3 0.4
The output of the system is the estimated return in the ˆ
k
+1 r
in the next time step. We propose the following distribution
Fig. 2. Probability density function of estimated Japan eq-
uity index return for February 1975
of ˆ
k
+1, r
C
f (ˆ
k
+1,r
k
) = r
1+
(ˆk+1÷µk)2r
+
((ˆk+1÷µk)2÷(rk÷µk)2)2r Table 1. Comparison of statistical properties estimated
o2k 2o2k
(7 )
with different methods
Mean Std. dev Skewness Kurtosis
where C is the normalization constant. Historical 0.009 0 .0 6 3 - 0 .4 3 7 3 .1 9 6
As a result of the estimation procedure, we need esti- Particle F. 0.005 0 .0 8 2 - 0 .0 8 4 1 .5 7 6
mates of the mean, standard deviation, skewness and kur-
tosis of the distribution f (ˆ
k
+1,r
k
). Since particle filter r
maintains the distribution in a sampled form from one time
step to another, estimates can be computed efficiently by
using statistical estimators. There are numerous reasons
for using particle filters in this particular task:
248
P
r
o
b
a
b
i
l
i
t
y
d
e
n
s
i
t
y
f
u
n
c
t
i
o
n
3.2 Scenario tree generation
We use scenario trees for representing uncertainty in fu-
ture asset returns. For the generation of the tree we use op-
timization method based on moment matching described
in [4]. Parameters of the uncertainty distribution serve as an
input to the scenario generation process. Optimization
problem (3) is solved by the genetic algorithm. The output of
the optimization process is the optimal set of scenarios
organized in a tree, where the optimality is expressed in
terms of the distance to the specified statistical properties.
Naturally, the fitness function of the genetic algorithm is the
distance between the properties. The genetic algorithm
3.3 Portfolio optimization
We implement the method for representing uncertainty
in the example of portfolio management. In this applica-
tion, the goal is to maximize the sum of the expected utility of
wealth subject to budget constraints.
The optimization problem can be formulated in a fol-
lowing manner:
that solves the problem (3) uses: a rank fitness scaling,
max EU =t
s
f (w
s
)
stochastic uniform selection, a modified Gaussian muta-
s t t
tion and scattered crossover. The size of the population
w
s
=
I
depends on the extent of the problem. In our example, we
t
r
s
,t÷
1
o
s
,t÷1
use 5 assets and 30 statistical properties. The usual choice
s.t.
i=1
o
s
,t = 1 i
i i (8 )
for the number of scenarios, based on the discussion in [9],
is 6 scenarios, which leads to 36 unknown parameters of
i
t
s
,t = 1 1
scenarios (each scenario has a probability value and values for
returns for each asset). For optimizing a function of 36
variables, we use a population of 250 candidates. To en-
wheret
s
is the probability that scenario s occurs at time t
step t; w
s
is the wealth at time step t under scenario s; t
r
s
,t is return of asset i at time step t under scenario s;o
s
,t
sure that the solution found is indeed a global solution, we i i
rerun the algorithm from different starting points.
For example, given the statistical properties in Table
2, we build a single period scenario tree that consists of six
scenarios. With genetic algorithm, we obtain a perfect match.
A set of six generated scenarios is given in Fig- ure 3 where
the return of each asset in every scenario is presented.
Table 2. Statistical properties of index returns for February
1975. All properties but correlations are estimated with
particle filters
is the weight for asset i at time step t under scenario s.
The optimization problem (8) is a deterministic equivalent
of the underlying stochastic problem which we solve with
genetic algorithm. The output of the optimization process is
the set of weights of assets in the optimal portfolio for which
the maximum of expected utility is obtained. As a fitness
function we use negative utility, since the goal of genetic
algorithm is function minimization. Compared to the size of
the optimization problem (3), the problem (8) is simpler and
easier to solve. For example, when there are 5 assets in a
portfolio and 6 scenarios in a tree, problem
Mean Std. dev Skewness Kurtosis
(3) finds 36 variables, while problem (8) finds only 5 of
US A
UK
Japan
Germany
France
-0.022
-0.048
0.005
0.007 -
0.017
0.035
0.104
0.082
0.074
0.047
0.153
0.064
-0.084
-0.112
-0.086
3.227
1.355
1.576
1.633
2.844
them. For that reason, we use a population size of only 60
candidates.
Given the scenarios in Figure 3, we find the optimal
weights using the logarithmic utility function. The results are
reported in Table 3 and compared to the classical mean
Correlations of returns variance analysis. The difference due to different estima-
US A UK Japan Germany France
tion methods used clearly exists.
US A 1 0.508 0.320 0.337 0.398
UK
Japan
Germany
France
1 0.372
1
0.313
0.471
1
0.588
0.319
0.608
1
Table 3. Weights of the optimal portfolio calculated with
our model using compared to the classical mean variance
portfolio
0,2
0,1
0
-0,1
-0,2
-0,3
USA
UK
Japan
Germany
France
4
Scenario trees
Classic mean-
variance
RESULTS
US A
0.325
0.320
UK
0
0
Japan
0.080
0.462
Germany
0.517
0.218
France
0.078
0
0,081 0,043 0,316 0,444 0,061 0,055
Fig. 3. Generated scenarios (with probabilities) for which the
distribution properties match the properties in Table 2
The experiments are based on the data set from MSCI
(Morgan Stanley Capital International). We use the to- tal
return equity indices of France, Germany, Japan, UK and the
USA. Equity returns are based on the month-end
249
US-dollar value of the equity index for the period between
January 1970 and December 2000. To verify the perfor-
mance of the different portfolio models, the weights from
each model are determined, and the return from holding this
portfolio in the next month is calculated. In case of models
that create historical estimates of parameters, those estimates
are based on a window of 60 months. In each case, the out-
of-sample period is from January 1975 to De- cember 2000.
Table 4 shows summary statistics for themonthly returns on
the five indices and the correlations of the returns.
Table 4. Summary statistics of the data from January 1970
to January 2000
developed. Particle filters were used for estimation of sta-
tistical properties of uncertainty from historical data, and
scenario trees were used as a model for uncertainty rep-
resentation. The described method was included into the
decision making process for dynamic portfolio optimiza-
tion. Uncertainty in future asset returns, being the main
problem in portfolio optimization, was captured by the pro-
posed method. By using obtained uncertainty representa-
tion, portfolio optimization was performed by maximiza-
tion of logarithmic utility function of the wealth. For the
purpose of the above mentioned maximization, and for the
estimation of the parameters of the scenario trees, a genetic
algorithm was used.
US A
UK
Japan
Germany
France
Mean
0.0049
0.0060
0.0117
0.0065
0.0060
Correlation coefficients
Std. dev.
0.0446
0.0717
0.0658
0.0603
0.0694
The described method was validated by the use of the
MSCI data sets. The method showed better results in com-
parison to the standard mean variance strategy according to
Sharpe ratio. Generated portfolios frequently demonstrate
higher returns than Markowitz optimal portfolios while
maintaining the same amount of risk.
Future research in this area should continue along sev-
US A UK Japan Germany France
US A 1 0.5171 0.2699 0.3598 0.4405
eral dimensions. Firstly, in this research, a single scenario
UK
Japan
Germany
France
1 0.3708
1
0.4393
0.3889
1
0.5440
0.3922
0.6136
1
trees was used. A combination of multiple scenario trees
and particle filters could result in some new enhancements.
Secondly, different utility functions in portfolio optimiza-
tions could create valuable progress. Thirdly, there is no
fundamental reason why 1,000 or 10,000 scenarios cannot
To assess the performance of the different portfolio
models, we calculate the average out of sample means,
volatilities and Sharpe ratios of each strategy - the mean-
variance analysis, scenario trees and scenario trees with
particle filters. The results are reported in Table 5. Com-
pared with mean-variance analysis, in which the histori- cal
mean returns are taken to be the estimator of the ex-
pected returns µ, the portfolios constructed by using the
model for representing uncertainty showed higher returns
while maintaining the same level of volatility. In the case in
which scenario trees were generated without particle fil- ters,
the key difference was the utility function used, which gave
more balanced portfolios. When particle filters were used as
estimators of the statistical parameters of future re- turns,
portfolios with even higher returns were generated. Both
methods clearly outperform the traditional method.
Table 5. Experiment results
be created by parallel and distributed computers.
REFERENCES
[1] J. M. Mulvey, D. P. Rosenbaum, B. Shetty, Strategic finan-
cial risk management and operations research, European
Journal of Operational Research, 1997.
[2] H. Markowitz, Portfolio selection, Journal of finance, pp.
77-91. 1952.
[3] J. M. Mulvey, B. Shetty, Financial planning via muti-
stage stochastic optimization, Computers & Operations
Research, pp. 1-20, 2004.
[4] K. Hoyland, S. W. Wallace, Generating Scenario Trees for
Multistage Decision Problems, Management Science, pp.
295-307, 2001.
[5] V. K. Chopra, W. T. Ziemba, The effect of errors in means,
variances, and covariances on optimal portfolio choice,
Journal of Portfolio Management, pp. 6-11, 1993.
5
Mean-variance
Scenario trees
Scenario trees with PF
CONCLUSION
Mean
0.0087
0.0091
0.0103
Std. dev.
0.0465
0.0458
0.0483
Sharpe ratio
0.1871
0.1987
0.2133
[6] P. Jorion, Bayes-Stein estimation for portfolio analysis,
The Journal of Financial and Quantitative Analysis, pp. 279-
292, 1986.
[7] P. Jorion, International portfolio diversification with es-
timation risk, Journal of Business, pp. 259-278. 1985.
[8] R. Kan, G. Zhou, Optimal Portfolio Choice with Param-
In this paper a method for the uncertainty representa- eter Uncertainty, Journal of Financial and Quantitative
tion based on particle filters and scenario trees has been Analysis, 2007.
250
[9] N. Gülpinar, B. Rustem, R. Settergren, Simulation and op-
timization approach scenario tree generation, Journal of Economic Dynamics and Control, pp. 1291-1315, 2004.
[10] P?ug, G., Scenario tree generation for multiperiod finan-
cial optimization by optimal discretization, Mathematical Programming, 251-271, 2001.
doc_126036646.docx