Portfolio Optimization Problem

A comprehensive implementation of various optimization algorithms for solving the portfolio optimization problem. This project compares different heuristic and meta-heuristic approaches to find optimal asset allocation that maximizes the return-to-risk ratio (Sharpe-like ratio).

🎯 Overview

Portfolio optimization is a fundamental problem in finance where investors seek to allocate their capital across different assets to achieve the best possible return while minimizing risk. This project implements and compares four different optimization algorithms:

1. Beam Search (Heuristic)
2. Random Local Beam Search (Heuristic)
3. Simulated Annealing (Meta-Heuristic)
4. Genetic Algorithm (Meta-Heuristic)

📊 Mathematical Background

Portfolio Risk and Covariance Matrix

The covariance matrix in portfolio optimization is a key factor in calculating and understanding the risk of the portfolio. Here's how they are related:

1. Covariance and Portfolio Risk

• In portfolio optimization, risk is often measured as the variance or standard deviation of the portfolio's returns.
• The covariance matrix captures the relationships between the returns of different assets in the portfolio. Each element in the covariance matrix represents the extent to which two assets move together (covariance).
• Variance is the measure of how much the returns of an asset vary from its average. For a portfolio, the variance depends on both the variances of individual assets and the covariances between them.

2. Portfolio Variance Formula

For a portfolio of $n$ assets with weights $w = [w_1, w_2, \dots, w_n]$, the portfolio variance (which represents the risk) is calculated as:

$$\sigma_p^2 = w^T \Sigma w$$

where:

• $\sigma_p^2$ is the portfolio variance.
• $w$ is a column vector of asset weights.
• $\Sigma$ is the covariance matrix of asset returns.
• $w^T$ is the transpose of $w$, so $w^T \Sigma w$ represents the quadratic form that combines individual variances and covariances.

3. Breaking Down Portfolio Variance

Expanding the matrix multiplication, the portfolio variance can be expressed as:

$$\sigma_p^2 = \sum_{i=1}^{n} \sum_{j=1}^{n} w_i w_j \sigma_{ij}$$

where $\sigma_{ij}$ is the covariance between assets $i$ and $j$.

• If $i = j$ (the same asset), $\sigma_{ii}$ represents the variance of asset $i$, contributing directly to the portfolio's total variance based on its weight.
• If $i \neq j$ (different assets), $\sigma_{ij}$ represents the covariance between the two assets, contributing to the overall portfolio variance based on how their returns move together.

4. Understanding the Impact of Covariance on Risk

• Positive Covariance: If two assets have positive covariance, their returns tend to move in the same direction. High positive covariances increase portfolio risk, as losses in one asset are likely to coincide with losses in another.
• Negative Covariance: If two assets have negative covariance, they tend to move in opposite directions. Negative covariances can reduce overall portfolio risk because when one asset's return goes down, another's goes up, balancing the portfolio.
• Diversification: The covariance matrix is crucial for diversification. If assets have low or negative covariance, they reduce total portfolio risk compared to holding assets with high positive covariance.

5. Standard Deviation as Portfolio Risk

• The standard deviation $\sigma_p$ is the square root of the portfolio variance $\sigma_p^2$.
• Standard deviation is commonly used to express portfolio risk in percentage terms, providing a clearer picture of the potential deviation of returns from the expected mean.

🚀 Algorithms Implemented

1. Beam Search

A systematic search algorithm that maintains a fixed number of best solutions (beams) at each iteration and explores their combinations.

2. Random Local Beam Search

An enhanced version of beam search that introduces randomization and local mutations to escape local optima.

3. Simulated Annealing

A probabilistic optimization technique that allows for occasional acceptance of worse solutions to escape local optima, with the probability decreasing over time (cooling).

4. Genetic Algorithm

An evolutionary algorithm that mimics natural selection, using operations like selection, crossover, and mutation to evolve a population of solutions.

🧮 Mathematical Formulation

Objective Function

Maximize the Sharpe-like ratio: $$\text{Fitness}(w) = \frac{\text{Expected Return}}{\text{Risk}} = \frac{w^T \mu}{\sqrt{w^T \Sigma w}}$$

Constraints

• $\sum_{i=1}^n w_i = 1$ (weights sum to 1)
• $w_i \geq 0$ for all $i$ (no short selling)

Where:

• $w$ = portfolio weights vector
• $\mu$ = expected returns vector
• $\Sigma$ = covariance matrix
• $n$ = number of assets

Summary

To summarize the relationship:

• The covariance matrix encodes the risk interactions between different assets.
• The portfolio variance (total risk) is computed using this matrix and asset weights, summing up individual variances and covariances.
• By adjusting asset weights based on the covariance structure, investors can minimize risk (variance) for a desired level of expected return, achieving an efficient portfolio.