Portfolio optimization with “ Threshold Accepting ” : a practical guide 203
portfolios with the Omega ratio ( Keating & Shadwick, 2002 ), but this is only
possible by imposing a specific distributional assumption on the data.
In this chapter, we will outline an alternative approach, namely optimiza-
tion with a heuristic technique. The term “ heuristic ” is used in different scien-
tific disciplines, with different but related meanings. Mathematicians use it to
describe an explanation that is strictly speaking not correct, but leads to the
correct conclusion nonetheless; in the language of psychologists, heuristics are
“ rules of thumb ” for decision making that, though sometimes seemingly crude,
work robustly in many circumstances ( Gigerenzer, 2004, 2008 ). In optimiza-
tion theory, the term is characterized by Winker and Maringer (2007) , Barr,
Golden, Kelly, Resende, and Stewart (1995) via several criteria:
● The method should produce “ good ” stochastic approximations of the true opti-
mum, where “ good ” is measured in terms of solution quality and computing time.
● The method should be robust in case of comparatively small changes to the given
problem (e.g., when a constraint is added). Furthermore, obtained results should
not vary too much for changes in the parameter settings of the heuristic.
● The technique should be easy to implement.
● Implementation and application of the technique should not require subjective
elements.
It must be stressed that heuristics, following this definition, are not ad hoc
procedures that are tailored to specific problems. For many techniques like
Genetic Algorithms ( Holland, 1992 ) or Simulated Annealing ( Kirkpatrick,
Gelatt, & Vecchi, 1983 ), a considerable theoretical background is available,
including convergence proofs. Heuristics have been shown to work well for
problems that are completely infeasible for classical optimization approaches
( Michalewicz & Fogel, 2004 ). Conceptually, they are often very simple; imple-
menting them rarely requires high levels of mathematical sophistication or
programming skills. Heuristics are flexible as adding, removing, or changing
constraints or exchanging objective functions can be accomplished very easily.
These advantages come at a cost as well, as the obtained solution is only a
stochastic approximation, a random variable. But still, such an approximation
may be better than a poor deterministic solution (which, even worse, may not
even become recognized as such) or no solution at all when other methods can-
not be applied.
In this chapter, we will outline how to implement such a heuristic technique,
Threshold Accepting (TA), for a portfolio optimization problem. TA was intro-
duced in the 1980s ( Dueck & Scheuer, 1990 ) and was, incidentally, the first heu-
ristic method to be applied to non-mean – variance portfolio selection ( Dueck &
Winker, 1992 ). The reader we have in mind is primarily the analyst or engi-
neer who wishes to implement the algorithms, hence all relevant procedures are
given in pseudocode. But this chapter should also be of interest to the portfo-
lio manager who uses the resulting implementation, since he or she should be
aware of the possibilities and limitations of the method. The chapter is struc-
tured as follows: Section 9.2 will briefly outline the portfolio selection problem.