250 Optimizing Optimization
method of moments estimation and brute-force optimization algorithm mean
that the methods can only be applied to a maximum of five assets. 4 It appears
that the combination of non-Gaussianity, large numbers of assets, and the
direct maximization of expected utility necessitates an alterative approach to
optimization.
The alternative approach we consider is known as the “ heuristic ” approach
to optimization. Although there are many types of optimization algorithm
that can be classified as “ heuristic, ” and a full description of each of them is
beyond the scope of this chapter, we nevertheless note that it is the class of
“ local search ” methods that have been most fruitfully applied to portfolio
optimization.^5 Within this class, there are two important subclasses: first, there
are “ trajectory methods ” that focus on a single solution at any point in time
(e.g., threshold acceptance, simulated annealing, and tabu search), and second,
there are “ population methods ” that update sets of potential solutions simul-
taneously (e.g., genetic algorithms, differential evolution methods, and particle
swarm optimization).
Although each local search procedure is often very different from another,
they are all based on the same underlying principle. That is, we start from an
initial solution that may, or may not, be randomly generated and continue the
search process by comparing the current solution with potential solutions in
the same neighborhood. The decision to update the current solution is gov-
erned by the “ quality ” of the potential solution. If the decision is “ positive, ”
the current solution is replaced by the neighboring one and is then used as the
new starting point for subsequent iterations of the algorithm. The whole proc-
ess is continued until a termination criterion is satisfied.
Owing to the complex and computationally burdensome nature of many of
the problems encountered in finance, these algorithms are at the heart of a rap-
idly growing literature. For instance, the threshold acceptance algorithm has
been used by Gilli and K ë llezi (2002) for index tracking problems with highly
nonlinear constraints, and by Gilli, K ë llezi, and Hysi (2006) in the construc-
tion of optimal portfolios under different downside risk measures. In addition,
Maringer (2007) demonstrates how differential evolution methods can be used
for utility maximization with loss aversion. 6 Whereas the tabu search was first
applied to utility maximization by Glover, Mulvey, and Hoyland (1996).
With such a variety of algorithms on offer, it is no surprise that choosing
between them is a difficult task. And this is made even more complicated
by the fact that each one of them depends on multiple “ tuning ” parameters,
which, if not chosen correctly, can greatly inhibit convergence to the optimal
4 For further examples, we refer the reader to Ramchand and Susmel (1998) or Ang and Bekaert
(2002) who consider regime-switching return distributions. In both cases, the maximum number
of assets is less than four.
5 See Winker (2001) , Osman and Laporte (1996) , and Gilli and Winker (2004) for a comprehen-
sive overview of optimization heuristics and a detailed discussion of their various forms.
6 See Maringer and Parpas (2009) for further information on the differential evolution algorithm.