I am working on a portfolio optimisation that requires me to constrain on the number of assets used, e.g from S&P500 build a 20 asset portfolio that is feasible. After doing some research I came to the conclusion that there are no non-commercial solvers freely available that can handle mixed integer and quadratic problems (I probably need SOCP as well). So I thought about a pre-optimisation step, i.e use a MIP solver to get me those 20 assets that I can then use in CVXOPT afterwards. Or any heuristic approach like genetic programming. Maybe worth mentioning that I would like to keep it as simple as possible as a first step.

My question now is, has anyone experience how this is usually implemented? Is the MIP approach a feasible one? Or can I do s.th along the lines of PCA analysis first and pick the top 20 non correlated assets.

If mixed integer programming is the way to go does anyone have a brief python example where I could get an idea how it can be implemented?


EDIT: Implementation od David's LASSO suggestion using cvxpy

import numpy as np
import cvxpy as cvx

n = 100

mu = np.abs(np.random.randn(n, 1))
Sigma = np.random.randn(n, n)
Sigma = Sigma.T.dot(Sigma)

w = cvx.Variable(n)
lambda_ = cvx.Parameter(sign="positive")
range_ = np.arange(0,100,1)

ret = mu.T*w
risk = cvx.quad_form(w, Sigma)

objective = cvx.Minimize(risk + lambda_*cvx.norm(w,1))
constraints = [cvx.sum_entries(w) == 1, w >= 0]
prob = cvx.Problem(objective, constraints)

weights_count = []

for lambda_vals in range_:
    print 'Lambda : ',lambda_vals 
    lambda_.value = lambda_vals

    print prob.status

    output = []
    for i in range(len(w.value)):

    weights_count.append(sum(1 for i in output if i > 0))

print weights_count

In a quick and easy first step you could add $L_1$-regularization to the Markowitz problem. That is, you add a term $\lambda ||w||_1$ to the goal function of your optimization problem (where $w$ are the allocation weights to be optimized).

The $L_1$-regularization, which is often termed LASSO in the statistics community, will give you sparse solutions of the weight vectors, i.e. bring several $w_i$ down to zero and leave you with a selected number of remaining asset weights. How many assets exactly will remain depends on the choice of the regularization parameter $\lambda$, which you then should adjust accordingly in order to give 20 assets.

The nice thing about this approach is that you can stay in the same class of optimization algorithms, because the absolute value of the parameters can be incorporated by linear constraints. See for example here.

  • $\begingroup$ I will definitely give this a try, what I ended up doing in the mean time was what other commercial solvers do, e.g. APT they solve for the full universe, sort be weight and truncate that list iteratively until you either reach your target universe seize or the last feasible solution. Not a big fan of that solution $\endgroup$ – ThatQuantDude Sep 26 '16 at 12:08
  • 1
    $\begingroup$ Are you looking for long only solution ? L1 regularization will penalize short positions. Would it help to reduce cardinality in long positions ? Somebody is suggesting that regularizations of L^{1/2} or L^{p} might work better for long only portfolios. I am looking at the problem too and I was thinking of implementing something in python (but I might use NCVS to start with). Please let me know if you would be interested in doing something together. $\endgroup$ – Bozothegrey Sep 26 '16 at 12:49
  • $\begingroup$ @Bozothegrey: can you explain why L1-regularization should penalize short positions? Because imo adding the term $\lambda || w ||_1$ is from the first indifferent to the sign of $w_i$. (I mean it seems to be there as the paper also mentions it, but why? ... didn't really read the paper) $\endgroup$ – davidhigh Sep 26 '16 at 13:39
  • $\begingroup$ @Bozothegrey, 2: and if short positions matter, can't one introduce the (perfectly correlated) negative assets and include them all into the portfolio? (I have no clue here as I'm more of a statistics guy and haven't implemented the model yet) $\endgroup$ – davidhigh Sep 26 '16 at 13:44
  • $\begingroup$ @davidhigh 1. Consider the minimum variance portfolio with a full investment constraint, i.e. $\Sigma \omega = 1$. A long only portfolio would attract a regularization cost equal to $\lambda$. Introducing a short position of weight $\hat{\omega}$ (that has to be matched by a long position by virtue of the full investment constraint), would increase the regularization cost by $2 \lambda \hat{\omega}$. So you would do that only if the quadratic term decrease at least by the same amount. On a traditional optimization problem, a short portfolio would not attract this additional cost. $\endgroup$ – Bozothegrey Sep 26 '16 at 15:08

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.