How Collateral, Margin, and Funding Affect Perpetual Futures

# How to apply the "Knapsack Problem" to minimise a portfolio's volatility?


# How to apply the "Knapsack Problem" to minimise a portfolio's volatility?












Suppose I have a stock selection universe of 100 stocks.

I have estimated the covariance matrix of this 100 stocks.

I would like to create an equaly-weighted basket of 5 stocks which has the lowest volatility possible.

How could I modify knapsack algorithms to solve this?

I can't just use the standard algorithm, as the total volatility is not the sum of the constituent volatilities, but involves considering the correlations as well.

## Answer by jaamor (score 3)

https://quant.stackexchange.com/a/16528

This problem is not interesting enough, because putting your money in the bank guarantees you zero volatility (and a zero return on investment). In practice, whatever set of assets you chose you would get a very extreme solution (e.g. 100% weight on one asset with very low volatility.)

With a minor tweak, you can get a very interesting problem. You can constraint your portfolio to have at least an expected return of $R$. Now you get a mean-variance optimization problem, with cardinality constraints:

$$ min \,\,\, w^TCw $$ subject to $$ r^Tw = R $$ $$ w \ge 0 $$ $$ \Sigma w_i = 1 $$ and subject to "no more than 5 weights are non-zero (positive)".

Where $C$ is the covariance matrix and $w$ your weights vector. There is a way to formally define the last constraint using indicator integer variables, but I am not doing this here for the sake of simplicity.

Now, to the second part of the question: Here is why the knapsack problem is not a fitting approach to this problem. The knapsack problem is really hard because it does not allow fractional solutions. In portfolio optimization you usually assume that you can have a fractional amount of an asset.

Mean-variance optimization is a convex quadratic programming (QP) optimization problem, which can be solved extremely fast with many widely available solvers. Mean-variance optimization with cardinality constraints (e.g. you have to have exactly 5 assets in the portfolio) is a problem that is harder, a Mixed Integer Real optimization problem.

You can use heuristics to obtain a very satisfactory solutions. Here is a strategy:

- Solve the mean-variance problem without the cardinality constraints. The solution is usually extreme in that there is a small number of non-zero assets anyway.

- Then you can brute-force your way through the cardinality constraint or use heuristics (that could be for example based on a ranking of the sharpe ratio - which also is the value of the dual variables I believe) to obtain a satisfactory solution.

If you want to take a look into papers on mean-variance optimization with cardinality constraints, here is one of the most cited papers:

Heuristics for cardinality constrained portfolio optimisation (T.-J. Chang, N. Meade, Beasley)

Be mindful that metaheuristics, such as Genetic Algorithms are largely black box, and you would not get much educational value about the underlying securities by implementing them.

## Answer by demully (score 1)

https://quant.stackexchange.com/a/47527

If you're happy with equal stock weightings, then this can certainly be done iteratively. I don't know of any closed-form equation. It works for a universe of 100 stocks, but the calculations obviously grow exponentially if you want to increase your selection universe.

Pick five stocks at random.

Calculate the portfolio variance.

There are then 4 * 95 = 380 possible alternative portfolios that replace one of the current five with one of the 95 you don't own. Each of these has 25 relevant covariances (all weighted 4%) within it = 9500 datapoints. Big, but doable (and easy to look up from your full covar table)

Calculate the variances of these, and replace the current with the lowest of the 380. Rinse and repeat until none have a variance lower than the current. Which is taking and replacing one from your "knapsack" until you can't do better.

A similar process would allow you to do the same, if you allowed unequal stock weights. You'd need to calculate the minimum variance portfolio of the same 380 combinations as above. Since this requires the calculation of the inverse of the relevant 5x5 covariance matrix in each case, you have to cycle through until you get through a full cycle without any replacements.

## Answer by Enrico Schumann (score 0)

https://quant.stackexchange.com/a/47525

An "equal[l]y-weighted basket of 5 stocks" will not have a zero volatility, so this is a meaningful problem.

There is no "standard algorithm" to solve the problem. But it can be tackled via heuristics such as Local Search. A candidate solution can be coded as a vector of boolean variables ("included", "not included"). Such a solution maps, given your data inputs, into a portfolio volatility; thus, you can write an objective function.

An example for using a Local Search on a such a problem is described in Asset selection with Local Search (using `R` and the package NMOF, which I maintain).