Optimizing Optimization: The Next Generation of Optimization Applications and Theory (Quantitative Finance)

Portfolio optimization with “ Threshold Accepting ” : a practical guide 215

Many variations are possible. For example, Algorithm 4 uses equidistant

quantiles, so for n (^) Rounds  5, the 80th, 60th, 40th, 20th, and 0th quantiles are
used. The convention in software packages like Matlab or R is to set the 0th
quantile equal to the minimum of the sample, hence the last threshold is not
necessarily 0. There is some evidence that the efficiency of the algorithm can be
increased by starting with a lower quantile (e.g., the 50th), but generally, TA is
very robust to different settings of these parameters.
For this second variant, Gilli and Schumann (2008) study the quality of
solutions obtained in portfolio optimization problems for different numbers of
thresholds for a fixed n (^) Rounds  n (^) Steps. They find that the performance of the
algorithm deteriorates for very small numbers of thresholds (e.g., 2 or 3), but
stays roughly the same beyond 10 thresholds.

Constraints

There are several generic approaches to include constraints into the opti-

mization. A first one is to create new solutions such that they conform with

the given constraints. The budget constraint, for example, is automatically

enforced by the specification of the neighborhood. Cardinality constraints can

be implemented in this way as well. An alternative technique is to implement

restrictions by penalty terms. If a constraint is violated, the objective function

is impaired by an amount that increases with the magnitude of the violation.

The penalty term often also increases over time, so to allow the algorithm to

move relatively freely initially.

When penalizing the objective function to enforce constraints, the computa-

tional architecture needs hardly be changed, since we only add a scalar to the

objective function. A further advantage is that the approach works very well

if the search space is not convex, or even disconnected. Finally, penalties also

allow to incorporate soft constraints, which can sometimes be more appropri-

ate than hard constraints.

The stopping criterion

A stopping criterion is introduced by setting a fixed number of iterations, i.e.,

by the product n (^) Rounds  n (^) Steps. An emergency brake may be included that stops
the search if there has been no improvement in the current portfolio for a large
number of iterations.

9.4 Stochastics

For a convex problem, repeatedly running a deterministic method like a linear
program will always result in the same solution. But now assume we have a
problem like minimizing a portfolio’s VaR (see Figure 9.1 ), so Φ is given by
Qq/1 (note that the reward in this ratio is a constant, hence we just minimize
risk). This problem has many local minima, and if we vary the starting point