as well as the search history. An advanced formof Tabu Search (see e.g., [164]) is superimposed to control the composition ofreference points at each stage. In its simplest manifestations, adaptive memory isexploited to prohibit the search from reinvestigating solutions that have alreadybeen evaluated. However, the use of memory of the applied algorithm is much moreadvanced and calls upon memory functions that encourage search diversificationand intensification in order to allow the search to escape from locally optimal solutions and possibly find a globally optimal solution. For instance, in the course ofsearching for a global optimum, the population may contain many reference points
158
14 Model Implementation
with similar characteristics. That is, in the process of generating offspring from amixture of high-quality reference points and ordinary reference point members ofthe current population, the diversity of the population may tend to decrease and thelikelihood increases that the system gets stuck in a local optimum. A strategy thatremedies this situation considers the creation of a new population by a restartingmechanism which intends to create a population that is a blend of high qualitypoints found in earlier explorations (referred to as elite points) complemented withpoints generated in the same way as during the initialization phase. The restartingmechanism, therefore, injects diversity through newly generated points and preserves quality through the inclusion of elite points. Diversity is achieved by meansof an age strategy, a form of long-term memory, which assigns to each candidatesolution of a population a measure of “attractiveness.” Since some of the points inthe initial population may have poor objective function values with a high probability, they may never be chosen to play the role of a parent and would remainin the population until restarting. To additionally diversify the search, the systemincreases the attractiveness of these unused points over time. Thus, at the start ofthe search process, all the reference points x in a population of size p have an age ofzero. At the end of the first iteration, there will be p − 1 reference points from theoriginal population and one new offspring. The ages of the p − 1 reference pointsare set to one and that of the new offspring is set to zero. The same logic is followedin subsequent iterations and therefore, the age of every reference point increasesby one in each iteration except for the age of the new population member whichis initialized to zero. Each reference point in the population has an associated ageand an objective function value. These two values are used to define a function ofattractiveness that makes an old high-quality point the most attractive. Low-qualitypoints become more attractive as their age increases.In order to speed up the system’s search engine, a neural network is used to asa prediction model to help the system accelerate the search by avoiding the needfor evaluating f (x) for a newly created reference point x, in situations where thef (x) value can be predicted to be of low quality [239]. During the search, the neuralnetwork is trained by historical values of x and fα (x) which are collected for anumber of past iterations, where α denotes a percentage of the total number ofsimulation trials. The predicted value of the objective function for x as determinedby the neural network is therefore given by fˆ(x, fα (x)). During each training round,an error value is calculated which reflects the accuracy of the network as a predictionmodel. That is, if the network is used to predict f (x) for a newly created x, thenthe error indicates how good the prediction is expected to be. The error term iscalculated by computing the differences between the known f (x) and the predictedfˆ(x, fα (x)) objective function values. The training continues until the error fallswithin a specified maximum value.
Reference Set Update MethodThe RefSet Update method accompanies each application of the improvementmethod. The update operation is to maintain a record of the b best solutions found.
14.3 Optimization Model
159
Let bNow denote the current number of solutions in RefSet. Initially, bNow beginsat zero, and is increased each time a new solution is added to RefSet, until reaching the value bMax. At each step, RefSet stores the best solutions in an array x[i],i = 1 to bNow. An associated location array loc(i), i = 1 to bNow, indicates theranking of the solutions. That is, x[loc(1)] (the x vector stored in location loc(1)) isthe best solution, x[loc(2)] is the next best solution, and so on. A solution x = x isnot permitted to be recorded, if it duplicates another already in RefSet. The searchterminates when no new solutions are admitted to RefSet.
Subset Generation MethodAnother important feature relates to the strategy for selecting particular subsets ofsolutions to combine. According to Step 3 in Fig. 14.9, NewSubsets is constructedby systematically including all those pairs of RefSet elements that contain at leastone new solution. This means that the procedure does not allow for two solutionsto be subjected to the solution combination method more than once. We considersubsets of size 2, and specify that the cardinality of NewSubsets corresponding to theinitial reference set is given by (b2 − b)/2, which accounts for all pairs of solutionsin RefSet.
Solution Combination (Path Relinking) MethodAfter NewSubsets is constructed and NewSolutions is switched to FALSE, the algorithm chooses two elements of the reference set out of NewSubsets in lexicographical order and the solution combination method is applied to all pairs of solutionsin the RefSet in order to generate one or more solutions in Step 5. Solutions arecombined in a linear way through path relinking, an approach that was originallysuggested to integrate intensification and diversification strategies in the context oftabu search ([164]). Here, path relinking extends the combination mechanisms ofscatter search. Instead of directly producing a new solution when combining twoor more original solutions, path relinking generates paths between and beyond theselected solutions in the neighborhood space. The desired paths are generated byselecting moves that perform the following role: upon starting from an initiating solution x , the moves must progressively contain attributes from a guiding solution x(or reduce the distance between attributes of the initiating and guiding solutions).Consider the creation of paths that join two selected reference solutions x and x ,restricting attention to the part of the path that lies between the solutions, producinga solution sequence x = x(1), x(2), . . . , x(r) = x . The combinations are based onthe following three types:• x = x −d• x = x +d• x = x −dwhere d = r × (x − x )/2, and r is a random number in the range (0,1).
160
14 Model Implementation
Combinations beyond the segment [x ,x ], “outside” of x (i.e., nonconvex combinations), are generated by three strategies:• Strategy 1: Computes the maximum value of r that yields a feasible solution xwhen considering both the bounds and the constraints in the model.• Strategy 2: Considers the fact that variables may hit bounds before leaving thefeasible region relative to other constraints. The first departure variable from thefeasible region may happen because some variable hits a bound, which is followed by the others, before any of the linear constraints is violated. In such acase, the departing variable is fixed at its bound when it hits it, and the exploration continues with this variable held constant. This is done with each variableencountering a bound before other constraints are violated. The process finisheswhen the boundary defined by the other constraints is reached.• Strategy 3: Considers that the exploration hits a boundary that may be defined byeither bounds or any of the linear constraints. When this happens, one or moreconstraints are binding and the corresponding r-value cannot be increased without causing the violation of at least one constraint. At this point, OCL choosesa variable to make a substitution that geometrically corresponds to a projectionthat makes the search continue on a line that has the same direction, relativeto the constraint that was reached, as it did upon approaching the hyperplanedefined by the constraint. The process continues until the last unfixed variablehits a constraint. At this point, the value of all the previously fixed variables iscomputed.Each of these three boundary strategies generates a boundary solution xb outsidex . A fourth solution is being generated in the midpoint between xb and x . Interchanging the role of x and x gives the extension outside the “other end” of the linesegment.The Improvement Method is applied every NumImp steps of the relinking process in each path (Steps 6 and 8). Each of the generated solutions, in each path,including also those obtained after the application of the Improvement Method, ischecked to see whether it improves upon the worst solution currently in RefSet.If so, the new solution replaces the worst and RefSet is reordered in Step 6. TheNewSolutions flag is switched to TRUE and the pair (x , x ) that was just combinedis deleted from NewSubsets in Step 11. The number of solutions created from thelinear combination of two reference solutions depends on the quality of the solutionsbeing combined. Specifically, when the best two reference solutions are combined,they generate up to five new solutions, while when the worst two solutions are combined they generate only one. In the course of searching for a global optimum, thecombination method may not be able to generate solutions of enough quality tobecome members of the reference set. If the reference set does not change and allthe combinations of solutions have been explored, a diversification step is triggered.This step consists of rebuilding the reference set to create a balance between solution quality and diversity. To preserve quality, a small set of the best (elite) solutionsin the current reference set is used to seed the new reference set. The remainingsolutions are eliminated from the reference set. Then, the diversification generation
14.3 Optimization Model
161
method is used to repopulate the reference set with solutions that are diverse withrespect to the elite set. This reference set is used as the starting point for a new roundof combinations.The structured combinations produced by scatter search are designed with thegoal of creating weighted centers of selected sub-regions. These include nonconvexcombinations that project new centers into regions that are external to the originalreference solutions. The dispersion patterns created by such centers and their external projections are therefore based on both current and past evaluations of inputs.The procedure carries out a nonmonotonic search, where the successively generatedinputs produce varying evaluations, not all of them improving, but which over timeprovide a highly efficient trajectory to the best solutions. The process continues until an appropriate termination criterion is satisfied, such as a particular amount ofiterations or an amount of time to be devoted to the search.
Chapter 15
Simulation/Optimization Experiments
15.1 Practical MotivationA situation is presented, where a manufacturing company, located in Eurozone, sellsits goods via foreign subsidiaries to the end-customer in the United States.Generally, a strong foreign currency (weak EUR) is considered to be beneficialfor the company because of a larger purchasing power for the customer abroad.Since one unit of foreign currency is worth more units of home currency, Eurozonemanufactured goods – if prices remain constant – are cheaper which in theory hasa positive effect on international sales. Foreign exchange risk arises at the UnitedStates subsidiary, which on the 15th of every month needs to exchange its USDturnover into EUR in order to meet its liabilities with the Eurozone parent company.Since it is not clear what the spot exchange rates for the given currencies will be onthe future transaction dates, the subsidiary is exposed to foreign exchange transaction risk. In this case, risk consists in an appreciating EUR against foreign currency.For the US subsidiary, a stronger EUR is associated with higher cost of goods and alower turnover at period end as a consequence. The described situation is illustratedin Fig. 15.1.
15.2 Model Backtesting15.2.1 OverviewFor the purpose of model validation, historical data backtesting was carried out viaa dynamic rolling window approach. We split the historical data into two parts.Part 1 comprises 168 monthly observations (January 1985 to December 1998) andPart 2 comprises 72 months (January 1999 to December 2004) of the total 96 months(January 1999 to December 2006). We do not conduct backtesting of the decision
C. Ullrich, Forecasting and Hedging in the Foreign Exchange Markets, Lecture Notesin Economics and Mathematical Systems 623, DOI: 10.1007/978-3-642-00495-7 15,c Springer-Verlag Berlin Heidelberg 2009
163
164
15 Simulation/Optimization Experiments
Fig. 15.1 Case study forhedging EUR/USD
CustomerGoods
USD
US
EUR
GoodsEU
Backtesting period
Calibration of simulation parameters, determination of hedge intensities
January 1985t=1
January 1999t = 169
January 2005t = 241
January 2007t = 265
Fig. 15.2 Backtesting procedure
model over the remaining 24 months of the historical sample (January 2005 toDecember 2006) because when solving the model we need 24 months of futureactual realized exchange rates.Thus, the last roll of the decision model should be 24 months before the end ofthe historical sample of exchange rates. In Fig. 15.2 we explain this using a timeline where January 1999 and January 2005 indicate the months, when backtestingstarts and ends, respectively. The experimental set up is progressively described inthe following.
15.2.2 Data Inputs and Parameters15.2.2.1 ExposuresExposures are assumed to be deterministic and set to 1 at any time. This allows usto focus solely on exchange rate effects, and eases interpretation of results. If weconsider the fact that in a multinational firm, exposure forecasting is not a typical
15.2 Model Backtesting
165
risk management discipline but rather a sales planning task that is usually taken asgiven in practice, assuming deterministic exposures is not an unrealistic assumptioneither.
15.2.2.2 Hedge IntensityThe intensity of a hedge is a fraction of the total estimated exposure within a certainperiod of time.It is formally captured by the variable z in Problem 13.1. The hedge intensityis calculated according to the procedure described in Fig. 15.3. In a PPP-revertingworld, the cheaper it is to buy EUR according to the equilibrium rate, the highershould be the intensity of a hedge. This logic is captured by the simple Pseudocodeas written in Fig. 15.3. For instance let min = 0.6850, max = 1.5508 and I = 24.Then the grid range is evenly divided into 24 slots of size b = 0.0361. If currentspot is 0.9815, then t ∗ = 15 is returned, suggesting that the exposures for the next15 months should be hedged. Note that according to Problem 13.1, z is nonnegative and hence, imposes a speculation constraint. The minimum intensity musttherefore be t ∗ = 0 months, in case the spot exchange rate exceeds the historicalmaximum and is thus, considered to be very unfavorable. The maximum intensity is t ∗ = 24 months in case the spot exchange rate is lower than the historicalminimum.Figure 15.4 gives the results of the routine as applied on the period from January1985 to December 2004. Hedge intensities are depicted by bar charts which referto the y-axis on the right-hand side. The chart demonstrates that according to theproposed procedure, hedge intensities are perfectly correlated with the degree ofdisequilibrium. Hence, this approach of determining hedge intensities is consistentto the broader logic of foreign exchange hedging in a PPP-reverting context.1. Determine grid range:• from January 1985 until ‘current date’: identify minimum spot rate (minspot) and maximumspot rate (maxspot)2. Set maximum hedge intensity to I = 243. Calculate grid slot size b = (maxspot − minspot)/I4. Set up grid:• define array of length I + 1• for 0 ≤ i ≤ I: calculate g[i] = minspot + b × i5. Determine hedge intensity for current month:• Check in which grid slot current spot falls• for 0 ≤ i ≤ I: if current spot ≤ g[i], return hedge intensity iFig. 15.3 Pseudocode template for calculation of hedge intensity
166
15 Simulation/Optimization Experiments
1.60
0
1.501.40
5
1.20
10
1.101.00
15
Intensity (months)
EUR/USD spot
1.30
0.900.80
20
0.700.60Jan-85
Jan-87
Jan-89
Jan-91
Jan-93
Hedge Intensity
Jan-95
Jan-97
Jan-99
Jan-01
EUR/USD spot (monthly average)
Jan-03
Jan-05
25Jan-07
PPP
Fig. 15.4 Historical hedge intensities
15.2.2.3 Exchange Rate DataFor the 15th of every month in the backtesting period, historical spot exchange rates,forward exchange rates, strike prices and option premia for the following 24 monthswere obtained from Bloomberg. According to CIP, the no-arbitrage price of theforward contract or the forward price is determined by the spot rate today and theinterest rate differential between the two currencies for the relevant maturity, alsoknown as the forward premium. Figure 15.5 depicts EUR/USD forward premia,which correspond to the interest rate differentials between Eurozone and the UnitedStates for maturities from 1 to 24 months [43]. The forward rate at a certain date fora particular maturity is simply obtained by adding the respective forward premiumon this date’s spot rate.Without loss of generality, it is assumed that the firm uses a single type of European option. Due to the existence of transaction costs, it is never optimal to combineoptions with different strike prices in this setting. In particular, a forward contractcan be replicated with two options by put-call parity [200]. However, the syntheticforward produced in this way is dominated by the outright forward because transactions costs are doubled. Specifically, we consider option contracts with maturitiesranging from one to 24 months. So, at maturity, an option which has been purchasedat some decision stage is either exercised, if it yields a positive payoff, or is simplyleft to expire. Option strike prices for European style straddle options with maturities from 1 month to 24 months, as depicted in Fig. 15.6, were specified exogenouslyas inputs to the model and were obtained from the Bloomberg database [44].
15.2 Model Backtesting
167
1.40
EUR/USD forward
1.30
1.20
1.10
1.00
0.90
1M14M
2M15M
3M16M
4M17M
5M18M
6M19M
7M20M
9M22M
10M23M
12M
Jul-06
Oct-06
Apr-06
Jan-06
Jul-05
11M24M
Oct-05
Apr-05
Jan-05
Jul-04
Oct-04
Apr-04
Jan-04
Jul-03
8M21M
Oct-03
Apr-03
Jan-03
Jul-02
Oct-02
Apr-02
Jan-02
Jul-01
Oct-01
Apr-01
Jan-01
Jul-00
Oct-00
Apr-00
Jan-00
Jul-99
Oct-99
Apr-99
Jan-99
0.80
13M
Fig. 15.5 At-the-money forward rates1.40
EUR/USD straddle strike
1.30
1.20
1.10
1.00
0.90
M
Ja
n99ay-9Se 9p9Ja 9n0M 0ay-0Se 0p0Ja 0n0M 1ay-0Se 1p0Ja 1n0M 2ay-0Se 2p0Ja 2n03May-0Se 3p0Ja 3n04May-0Se 4p0Ja 4n05May-0Se 5p0Ja 5n0M 6ay-0Se 6p06
0.80
1M14M
2M15M
3M16M
4M17M
5M18M
6M19M
7M20M
8M21M
9M22M
10M23M
11M24M
12M
13M
Fig. 15.6 At-the-money strike prices for European style straddle options
Strike prices for given maturities were chosen by taking the arithmetic meanbetween the firm’s expected exchange rate for that maturity as given by the PPPreverting simulation model, and the exchange rate as expected by the market whichis given by the at-the-money straddle premium. It is only under this circumstancethat the firm and the capital market expect equal payoffs and hence, the straddle canbe considered as fairly valued from the firm’s point of view [323].
0.60
0.00
Spot (monthly average)
PPP
Dec-04
0.10
Dec-03
0.70
Dec-02
0.20
Dec-01
0.80
Dec-00
0.30
Dec-99
0.90
Dec-98
0.40
Dec-97
1.00
Dec-96
0.50
Dec-95
1.10
Dec-94
0.60
Dec-93
1.20
Dec-92
0.70
Dec-91
1.30
Dec-90
0.80
Dec-89
1.40
Dec-88
0.90
Dec-87
1.50
Dec-86
1.00
Dec-85
1.60
G
15 Simulation/Optimization Experiments
Dec-84
EUR/USD spot
168
G
Fig. 15.7 Historical transition function estimates
15.2.2.4 Simulation ParametersAn exchange rate scenario is a sequence of values for a single exchange rate over theanalysis period. The purpose of scenario generation is to come up with levels for theexchange rate path between t = 0 and T = 24. For a single factor the discrete form ofthe evolution equation for the exchange rate st is given by (14.7). For ease of modelcalibration, we assume c1 = c2 = PPP. The variables γ and σ were estimated onthe 15th of every month according to (14.8) and (14.9) for the time period betweenJanuary 1985 and December 2004 (252 months).Figure 15.7 illustrates the resulting estimated values for the transition functionG over the backtesting period. Obviously, G is strongly reacting to the degree ofdisequilibrium. Figure 15.8 displays the estimated values for σ , where each estimaterefers to the standard deviation of EUR/USD moves of the past 24 months. Sinceonly one exchange rate is considered there is no need to make assumptions aboutdependence structures.
15.2.2.5 Optimization Parameter SettingsIn order to derive decisions on the mix of instruments, we consider the SCOP problem with a mean-variance-skewness objective as formulated in Problem 4.1. Thedecision variables are represented by the amount of the hedge that is to be allocatedto each of the hedging vehicles. The optimal solution is represented by the allocation of instruments x∗ = (x∗F , x∗O , x∗S ) that yields the minimal objective function value.For exposition purposes, the optimal weight sets used to construct the hedges given
15.2 Model Backtesting
169
0.12
0.05
0.10
0.05
0.080.040.060.040.04
−0.04
Jan-04
Jan-03
Jan-02
Jan-01
Jan-00
Jan-99
Jan-98
Jan-97
Jan-96
Jan-95
Jan-94
Jan-93
Jan-92
Jan-91
Jan-90
Jan-89
Jan-88
Jan-87
Jan-86
−0.02
Jan-85
0.00
0.03
Sigma
0.03
0.02
0.020.02
−0.060.01
−0.08
0.01
−0.10−0.12
0.00Monthly moves
Sigma
Fig. 15.8 Historical standard deviation estimates
the firm’s preference are set to λ = κ = 1. This preference set is a compromise casewhere the weights for mean, variance, and skewness are equal, indicating that mean,variance, and skewness of return are of equal importance to the firm. The startingvalues for the decision variables were set to x∗F = 0.33, x∗O = 0.33, and x∗S = 0.34 inorder to provide a neutral start for the search. The step size for the decision variableswas set to 0.01, and according to Problem 13.1, 0 and 1 provide the lower and upperbounds for xF , xO , xS whose sum must equal 1. We further specify that the searchstops after 150 simulations with each simulation comprising 10,000 replications ofthe exchange rate with the same initial population given a specific pseudorandomgenerator seed. The latter reduces the variance between runs and makes the searchfor an optimum more efficient. All tests were carried out on a standard desktop PC(2 GHz single CPU) with Windows XP.
15.2.2.6 Algorithmic ReferenceThe commercial Monte Carlo spreadsheet add-in, Crystal Ball version 7.02, wasused for generating exchange rate scenarios.1 To estimate optimal values for the decision variables, we applied the scatter search/path relinking algorithm according to[238]. The algorithm is implemented in the commercial OptQuest package, a standalone optimization routine that is bundled with Crystal Ball. Being a completelyseparate software package, OptQuest treats the simulation model as a black box,i.e., it observes only the input/output of the simulation model.1 Crystal Ball’s random number generator has a period of length 231 − 2 which means that the cycle
of random numbers repeats after several billion trials.
170
15 Simulation/Optimization Experiments
15.2.3 Evaluation ProcedureThe role of the historical market data, the exposure data, their interaction with thedecision model and backtesting are described in the following. The experimentalsetup requires that we dynamically:1. Use market data in order to revalue the forward and straddle positions2. Record the decisions made in the current step of the model as an input of thestarting position of the next “roll” of the modelAs we stepped through time the model database was updated with the most currently available equilibrium, spot, forward and straddle rates. Once the current forward exposures for the next 24 months were accessed, the favorability of the currentexchange rate was evaluated resulting in a recommendation on the future exposureto be hedged, i.e., a target hedge intensity. If this number was equal or higher thanthe current amount of months hedged, a decision on the composition of the hedgehad to be made. In this case, OptQuest was used to solve the resulting optimizationproblem. For instance, consider the situation on 15 November 2000. The suggestedhedge intensity according to Fig. 15.4 is 19 months. Since 18 months have beenhedged in the past, a decision on the instrument mix had to be made for month 19,i.e., June 2002 only.Figure 15.9 shows the performance graph that resulted from an OptQuest run of100 simulations. The graph shows the value of the objective for the best alternativefound as the search progresses. The search began from a solution with an expectedobjective function value of 2.5454, which happened to be a goal-feasible solution.The best solution was found on the 70th simulation and had an objective functionvalue of 2.5522. One can also observe that the best value changes quickly early2.554
2.552
Objective function
2.550
2.548
2.546
2.544
2.542
2.5400
10
20
Fig. 15.9 Performance graph
30
40
50Simulation
60
70
80
90
100
15.2 Model Backtesting
171
Table 15.1 Best solutionfound
Simulation
Objective
Spot
Forward
Straddle
122028686970
2.545362.551122.551762.551982.552132.552212.55222
0.340.000.000.000.000.000.00
0.330.500.460.440.420.400.38
0.330.500.540.560.580.600.62
Table 15.2 Robustness of best solution foundName
Best
Minimum
Average
Maximum
Std. Dev.
ObjectiveSpotForwardStraddle
2.55220.000.380.62
2.52040.000.000.00
2.54140.23360.35260.4139
2.55221.001.001.00
0.00930.29540.26810.2904
in the run, as improvements are being found frequently, and then it changes moreslowly as better solutions become harder to find. We find in our experiments thatscatter search is a search method that is both aggressive and robust. It is aggressivebecause it finds high-quality solutions early in the search. It is robust because itcontinues to improve upon the best solution when allowed to search longer.The details of this run are reported in Table 15.1, where each row gives the values of the decision variables in case they led to a higher objective function value.The best solution was achieved in the 70th run which recommends to hedge the exposure completely with a combination of 38% forwards and 62% straddles. Theseselections meet the category bounds specified in Problem 13.1, and provide a singlegood solution, thereby guiding policy for increasing mean-variance-skewness.Given a set of solutions, all possible of increasing mean-variance-skewness, it isinteresting to ask how similar these solutions are in terms of their suggested allocations. If all these solutions suggest a similar strategy, then one can be more confidentthat this policy is robust to small changes in the amounts allocated. Alternatively,if these solutions correspond to extremely different allocations, then this impliesthat the solution is extremely sensitive to the amounts allocated. We identified 101solutions that had an objective within 10% of the best objective.The solution report given by Table 15.2 provides evidence that the objective function value is relatively noisy. This is not the result of a low number of simulationtrials but due to the relatively wide spreads between the minimum and maximumvalues for the decision variables from the set of solutions that fell within the analysis range.Furthermore, we analyze the runtime behavior of the respective algorithm by therequired computing time on the reference PC. Under the settings described, solvingthe problem for three decision variables took approximately 12 min and solving theproblem for six decision variables came at the expense of approximately 20 min.
172
15 Simulation/Optimization Experiments
On the one hand, the computing time should not be overinterpreted because it isdependent on the reference machine and on implementation details, but on the otherhand, it is an indication for real-world applications.In order to validate the model over time, we calculated its effect on net incomevia a rolling window approach where the objective function is given byT
U(w) = ∑ U(wt )
(15.1)
t=1
As per 31 December 