MPT: Adding constraint on minimum asset weight

Question

I'm new to finance in general, and recently read about Modern Portfolio Theory. Now I'm wondering how to add the following constraint on asset weights:

• Each asset weight $w_i$ should either be $w_i = 0$, or it should be $0.05 <= w_i <= 1.0$

(With 0.05 as the lower bound just being an example.)

From doodling a bit, it looks to me as if that would give a non-convex problem, and thus the usual optimization approaches won't work.

Can someone point me into the right direction on how to efficiently solve this problem for a large number of assets?

Edit: Alternatively, I could reformulate the additional constraint as

• For each asset weight $0.05 <= w_i <= 1.0$
• For each asset there is an indicator $I_i \in {0, 1}$
• The combined weight of the selected assets must be 1: $\sum I_i w_i = 1$

What optimization technique is suitable for this problem?

Answer 1

You can use a branch-and-cut algorithm (this is what mixed-integer solvers use).

The idea is to solve the problem recursively, by considering subproblems in which the constraints are $w_i=0$ for some stocks and $0.05 \leq w_i \leq 1$ for others. This gives $2^n$ convex optimization problems, and you want the best solution among them. Even when $n$ is small, that too much, but you can arrange those optimization problems in a tree, and prune large parts of it, as follows.

The root of the tree has constraints of the form $0 \leq w_i \leq 1$ (and gives a bound on the value of the optimal portfolio). Its children add constraints on the first stock: $w_1=0$ for the first child, $0.05\leq w_1 \leq 1$ for the second. The grand-children similarily add constraints on the second stock, and so on. The fully constrained problems we are interested in are the leaves of this tree.

First solve the problem at the root of the tree and one leaf: this gives you two values that bound the value of the optimal portfolio. Then, search the tree, depth-first, but discard a subtree without exploring it if its value is worse than the best leaf found so far.

Answer 2

A very basic implementation using the quadprog package in R would look something like the following:

library(quadprog)
library(MASS)

# --------------------------------------------------------    
# Generate a set of random returns for a covariance matrix
# --------------------------------------------------------

set.seed(100)
n <- 100   # number of assets
m <- 200   # number of states of the world
rho <- 0.7
sigma <- 0.2
mu <- .10
Cov <- matrix(rho*sigma*sigma, ncol=n, nrow=n)
diag(Cov) <- rep(sigma*sigma, n)
S <- 1 + matrix(mvrnorm(m, rep(mu, n), Sigma=Cov), ncol=n)
Dmat <- var(S)

# --------------------------------------------------------
# Setup quadratic problem        
# --------------------------------------------------------

# The weights must sum to 1
Amat <- matrix(1, n)

# x >= 5%
bLo <- rep(0, n)
bvec <- c(1, bLo)
Amat <- cbind(Amat, diag(n))

# x <= 5%
bHi <- rep(.05, n)
bvec <- c(bvec, -bHi)
Amat <- cbind(Amat, -diag(n))

dvec <- rep(0, nrow(Amat))
meq <- 1  # the first column of Amat is an equality constraint

sol <- solve.QP(Dmat=Dmat, dvec=dvec, Amat=Amat, bvec=bvec, meq)