Portfolio optimization with “ Threshold Accepting ” : a practical guide 213
new portfolio will be created by a small perturbation of the original portfolio,
hence:
xxxncΔwhere x ^ is a vector with few nonzero elements (usually only two). Then,
PxncP x x PxcPx
known()ΔΔ Since many elements of x ^ are zero, the part of P relevant for the matrixmultiplication consists of only a few columns. Thus, by creating a matrix P (^)
that only holds the columns where x ^ is nonzero, and a vector x
Δ
that com-
prises only the nonzero elements of x ^ , we can often considerably speed up the
matrix computation Px ^ by replacing it by Px**Δ.
The neighborhood function
To move from one solution to the next, we need to define a neighborhood
N from which new candidate solutions are chosen. For portfolio selection
problems, there exists a very natural way to create neighbor solutions: Pick
one asset in the portfolio randomly, “ sell ” a small quantity of this asset, and
“ invest ” the amount obtained in another asset. If short positions are allowed,
the chosen asset to be sold does not have to be in the portfolio. The “ small
quantity ” may either be a random number or a small fixed fraction (e.g.,
0.1%). Experiments suggest that, for practical purposes, both methods give
similar results.
Note that the neighborhood definition stays unchanged over the course of
the optimization. A variant is to decrease the portfolio changes over time, thus
to make smaller steps. In our experience, this is not helpful for portfolio selec-
tion problems. It is true that we often want the algorithm to become more
select over time, but this can be achieved by setting the threshold sequence
appropriately.
The threshold sequence
The threshold sequence is an ordered vector of positive numbers that decrease
to zero or at least become very small. The neighborhood definition and the
thresholds are strongly connected. Larger neighborhoods, which imply larger
changes from one candidate portfolio to the next, need generally be accompa-
nied by larger initial threshold values, and vice versa.
Winker and Fang (1997) were the first to suggest a data-driven method to
obtain the thresholds: generate a large number of random solutions and select
a neighbor for every solution. All these solutions are then evaluated according
to the objective function, so for every pair (random solution – neighbor solu-
tion), we obtain a difference in the objective function value. The thresholds are