260 Optimizing Optimization
11.4.2 The threshold acceptance algorithm
The complex nature of the maximization problem described in the previ-
ous section necessitates the use of a heuristic optimization algorithm. In low
dimensions, one could feasibly consider a grid-search procedure instead; how-
ever, this method becomes increasingly intractable for even a small numbers of
assets (cf. Duxbury, 2008 ). In this section, we therefore describe the threshold
acceptance optimization algorithm, which we use to derive the optimum set of
portfolio weights.
TA was introduced by Dueck and Scheuer (1990) as a deterministic alterna-
tive to simulated annealing. It is a refined local search procedure that escapes
local minima by accepting solutions that are not worse by more than a given
threshold. The algorithm is deterministic in the sense that we fix a number
of iterations, N (^) Iterations , and explore the neighborhood with a fixed number
of steps during each iteration, N (^) Steps. The threshold is then decreased succes-
sively and reaches the value of zero in the last iteration. This procedure is then
repeated N (^) Restarts times with different starting values in order to fully explore
the parameter space. The optimal solution corresponds to the maximum out
of all restarts. In total, the number of function evaluations is of the order O
( N (^) Restarts N (^) Iter N (^) Steps ). The pseudocode for the three constituent blocks of
the TA algorithm: (1) optimization routine; (2) definition of a neighbor; and
(3) choice of threshold sequence, is described in Appendix 11.9.2.
Although instructive, the pseudocode should be accompanied by two further
comments. First, in the spirit of Alth ö fer and Koschnick (1991) , who proved
the convergence of the algorithm given an appropriate threshold sequence, we
follow Gilli et al. (2006) in retrieving the threshold sequence from the empiri-
cal distribution of N (^) Steps distances between the value of the objective function
for successive neighbors. And second, to generate initial solutions to the asset
allocation problem, we generate weights from the beta distribution, Beta( α , β ),
until the constraint Σ w i 1 is violated. The parameters α and β describe the
shape of the distribution and thus control the sparsity of the weight vector. For
instance, a choice of α β 1 corresponds to a uniform distribution that will
deliver a very sparse solution to the large-dimension problem. 17 These weights
are then randomly assigned to the assets in the portfolio. If there are fewer
weights than assets, then the remaining weights are set to zero, and if the con-
verse is true then we drop the appropriate number of weights and renormalize.
We conclude this section with a formal assessment of the TA algorithm. As
we have already mentioned, for low-dimensional asset allocation problems, a
grid-search (GS) procedure is feasible and so we select this as our benchmark
algorithm. Our comparison is based on comparing the absolute difference in
the optimal portfolio weights using between 6 and 18 months of data between
17 The mean of a Beta ( α, β ) distribution is given by α /( α β ) and so the average number of
nonzero weights is given by || w || 0 ( α β )/ α.