Heuristic Algorithms for Portfolio Optimisation

1. What is a heuristic algorithm?

From the Greek heuriskein — to find or discover. Heuristics are exploratory methods for solving problems in which solutions are discovered by evaluating progress towards a final result.

A heuristic algorithm is a procedure that searches for near-optimal solutions at a reasonable computational cost, without guaranteeing the feasibility of the solutions found or their distance from the true optimum.

Key characteristics

They do not guarantee the optimal solution.
The quality of the result cannot be formally bounded.
Computation time is acceptable.
Statistical analysis of results is possible across multiple runs.

2. Why use heuristics for portfolio optimisation?

The classical Markowitz problem is a quadratic programme solvable with Lagrange multipliers. However, real-world portfolio construction requires constraints that break convexity and make classical methods ineffective.

Complicating constraints

Weight bounds

Min/max allocation per asset: ε_i ≤ x_i ≤ δ_i

Sector limits

Maximum weight allocated to any sector or group

Cardinality

Maximum number of assets K in the portfolio (binary variable z_i)

Sector cardinality

Limit on the number of assets from each sector

Non-smooth objective functions

Classical optimisers also struggle when the objective function is non-smooth or non-convex. Common examples in portfolio construction:

Historical VaR (a discrete percentile)
Expected Shortfall / CVaR
Omega Ratio

In these cases, heuristic methods become the natural alternative.

3. Types of heuristic algorithms

Simulated Annealing

Start from an initial portfolio.
Generate random neighbouring portfolios.
Accept improvements always; accept worse solutions with probability p(T).
Temperature T decreases over time — fewer bad moves accepted.

Threshold Accepting

Similar to SA but accepts worse solutions if the deterioration is below a threshold Δ.
Threshold decreases over iterations.
Deterministic acceptance rule — no random draw.

Tabu Search

Start from an initial portfolio.
Always move to the best neighbour.
Maintain a tabu list of recent moves to avoid cycling.
Repeat until stopping criterion met.

Genetic Algorithms

Generate a population of candidate portfolios.
Evaluate fitness (objective function).
Select the best; apply crossover and mutation.
Repeat over multiple generations.

4. Simulated Annealing in detail

SA is inspired by the annealing process in metallurgy, where a material is slowly cooled to reach a low-energy crystalline structure. The analogy: the objective function is energy; temperature controls the probability of accepting worse solutions.

Algorithm

1

Choose an initial portfolio x(0). Compute F(x(0)). Set x* = x(0).

2

Generate a random neighbour x in the neighbourhood V(x(n)).

3

If F(x) < F(x(n)): accept x(n+1) = x. Update x* if improvement.

4

If F(x) > F(x(n)): accept with Boltzmann probability p = exp(−ΔF / T_n). Draw u ~ U[0,1]; accept if u < p.

5

After L iterations at current temperature, cool: T_{k+1} = α · T_k with α ∈ [0,1], typically α = 0.95.

6

Repeat until stopping criterion (e.g. maximum iterations or temperature threshold).

Temperature calibration

The initial temperature T₀ is set such that during the first cooling phase, the probability of accepting a worsening move is approximately X₀ = 0.8. This is achieved by running L unconstrained moves, computing the mean objective variation Δ̄, and setting:

T₀ = −Δ̄ / ln(X₀)

5. Constraint handling and neighbourhood generation

Feasibility vs. penalty approach

All-feasible approach — only feasible solutions are generated. The budget constraint (weights sum to 1) is enforced by normalisation.
Penalty approach — infeasible solutions are accepted but penalised in the objective: F_penalty = F + a · |violation|^p. Requires careful calibration of scale factors a and p.

Generating feasible neighbours with a return constraint

To enforce both the budget and return constraints simultaneously, moves are generated by modifying the weights of three assets (i₁, i₂, i₃) such that:

x'_{i1} = x_{i1} − step x'_{i2} = x_{i2} + step · (R_{i1} − R_{i3}) / (R_{i2} − R_{i3}) x'_{i3} = x_{i3} + step · (R_{i1} − R_{i2}) / (R_{i3} − R_{i2})

This construction guarantees that if x satisfies the return constraint, x' also does. The step size is determined by the radius of a sphere centred at the current solution, bounded by asset-level weight constraints.

Cardinality constraints

The cardinality constraint (maximum K assets) is best handled via the all-feasible approach. When a randomly selected asset i₃ is not in the current portfolio, the move implies replacing asset i₁ with asset i₃ — the weight of i₁ is set to zero and those of i₂ and i₃ are adjusted to satisfy budget and return constraints.

Programme structure

Generation of the initial feasible solution
Boltzmann acceptance function
Procedure for selecting the three assets to modify
Neighbourhood generation function

References

Gilli, M. and Kellezi, E. — A Heuristic Approach to Portfolio Optimization

Crama, Y. and Schyns, M. — Simulated Annealing for complex portfolio selection problems