Mean Variance portfolio optimisation (Long Only) CVXPY including cardinality constraint

Question

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?

thanks

EDIT: Implementation od David's LASSO suggestion using cvxpy

import numpy as np
import cvxpy as cvx

np.random.seed(1)
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

    prob.solve(verbose=False)
    print prob.status

    output = []
    for i in range(len(w.value)):
        output.append(round(w[i].value,2))

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

print weights_count

Answer 1

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.