This article applies the Simulated Annealing (SA) algorithm to the portfolio optimization problem. Simulated Annealing (SA) is a generic probabilistic and meta-heuristic search algorithm which can be used to find acceptable solutions to optimization problems characterized by a large search space with multiple optima. Portfolio optimization involves allocating capital between the assets in order to maximize risk adjusted return.

Basic Simulated Annealing Algorithm

The algorithm is inspired by a stochastic process in metallurgical annealing in which a material is repeatedly heated and cooled. This is done to increase the size of the materials crystals and reduce its defects. These material characteristics depend on the level of thermodynamic free energy in the material which is adjusted through the heating and cooling.

This real-world concept may, at first, seem quite difficult to translate into an optimization algorithm, however, with some 'algorithmic license' the resulting algorithm is actually quite simple. The simulated annealing algorithm for portfolio optimization essentially only consists of eleven steps, only two of which are really significant (underlined),

---

Initialize a random feasible solution, s
Initialize the best found solution, s*
Assign s* ← max(f(s), f(s*))
While the stopping condition is not satisfied:
  Generate a feasible random solution, s'
  Compute the probability of moving, P(s ← s')
  If the condition for moving is satisfied:
    Update the current solution, s ← s'
    If the fitness of s is greater than s*, f(s) > f(s*):
      Update the best found solution, s* ← s
Return the best found solution, s*

---

The reason why these two steps in particular are significant is because they impact the exploration exploitation trade off. Exploration describes the algorithms ability to explore different regions of the search space whereas Exploitation describes the algorithms ability to concentrate the search in a promising region of the search space.

These two steps are discussed in further detail for the remainder of this article. The diagram below illustrates the simulated annealing algorithm in a search space with multiple optima. The blue circle represents the current solution, the green circle represents a random feasible solutions, and the red circle tracks the best solution found.

Generating feasible random solutions

To understand the impact of where the random solution, s', is generated with respect to the current solution, s*, consider these two scenarios, (1) s' is generated close to s*, and (2) s' is generated far from s*. Assuming that s* is in a promising area of the search space then in (1) the algorithm is exploiting and in (2) the algorithm is exploring.

The maximum allocation of capital to any one asset in the portfolio is 1.00 and if we assume that no shorting is allowed, then the minimum allocation of capital to any one asset in the portfolio is 0.00. Because this active range is quite small, a new s' can be generated by applying a random percentage perturbations to each dimension of s*.

The impact of a small vs. a large perturbation is shown below,

By controlling the maximum percentage perturbation, the distance between s' and s* can be controlled. As such, the exploration and exploitation of the algorithm can be adjusted. Using a triangular distribution to shrink the maximum perturbation over time results in an improved simulated annealing algorithm for portfolio optimization,

The first image below shows a larger triangular distribution which facilitates greater exploration towards the beginning of the algorithm. The second image shows a smaller triangular distribution which facilitates greater exploitation towards the end of the algorithm. The green circles are possible locations to which the current solution (blue) has a probability of moving.

Note that the above green solutions are not generated all at once, like in a shotgun hill-climber, but rather in an iterative manner according to the probability distribution for that time period e.g. iterations 0 to 100 will have a wider triangular distribution than iterations 100 to 200.

Computing the probability of moving

In the simulated annealing algorithm the probability of the current solution, s, moving to one of the random solutions, s', depends on the fitness of s' relative to s as well as the number of iterations which have passed. During earlier iterations, s is more likely to move to s' even if it is less ideal. This resembles random search and exploration. During later iterations, s is more likely to move to s' if and only if it is more ideal. This resembles greedy and exploitation.

Simulated Annealing for Portfolio Optimization

To tie this back to the problem of portfolio optimization we represent each solution, s, as a vector the length of the portfolio's cardinality. Then each element in that vector, s(x), represents the weight of asset x in the portfolio. To make this problem more realistic we would normally need to impose a number of constraints on what those values and the vector may be,

With each additional constraint the set of feasible solutions shrinks. Furthermore, the search space warps and may end up containing multiple optima. This complexity causes many deterministic optimization algorithms to fail where stochastic optimization algorithms succeed. Stochastic algorithms, such as Simulated Annealing, search for solutions even after finding local optima. This is achieved by introducing an element of chance which allows them to randomly search in less desirable areas of the search space for better local optima.

Conclusion

The basic Simulated Annealing algorithm and the enhanced Simulated Annealing algorithm (which uses the triangular distribution technique described above) are both relatively simple algorithms which can be easily applied to complex portfolio optimization problems. These are portfolio optimization problems where multiple constraints have been asserted onto the search space introducing local minima and or discontinuous regions. Here is a gif of the algorithm finding a global optima in a rugged search space,