5
$\begingroup$

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.

Improve this question
$\endgroup$
3
$\begingroup$

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:

  1. 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.
  2. 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Cardinality-constrained with inequalities optimization is pretty interesting stuff. di.ens.fr/~aspremon/PDF/MeanRevVec.pdf is a good resource (and his other papers) for some alternatives to LASSO, though I haven't gotten around to implementing myself yet. $\endgroup$ – experquisite Feb 11 '15 at 19:42
  • $\begingroup$ There is a version of Knapsack that does allow fractions. It's called FRACTIONAL KNAPSACK. The best algorithm for this problem outputs an optimal solution in O(n) time. $\endgroup$ – Soggiorno Jun 24 '18 at 9:41
  • $\begingroup$ Exactly, as you mention once the integer constraint is dropped and fractionals are allowed, more efficient solutions are possible. Not too familiar with the fractional knapsack problem but it looks like a vanilla LP, which would be solvable by SIMPLEX. $\endgroup$ – jaamor Jun 28 '18 at 12:18
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.