Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

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?

share|improve this question
    
This is actually a standard linear constraint that just about any basic portfolio optimizer can handle (assuming you don't have any integer constraints, like maximum number of names). Is there a particular software package that you're using? –  michaelv2 May 4 '12 at 20:25
    
Michael, thanks for your comment. I'm not using any specific software yet. My very limited knowledge about optimization comes from stanford.edu/~wfsharpe/mia/opt/mia_opt1.htm, which talks about steepest ascent. If the solution space is non-convex, this wouldn't work I guess. Can you point me to a suitable optimization technique? (Sorry if this is a very basic question ...) –  rodion May 4 '12 at 20:55
    
I'm not sure what you're saying is as simple as what michael is saying. He is solving a traditional problem that uses linear inequality constraints and appears to be correct. If I'm not mistaken, what you're saying is technically a mixed integer problem. I think CPLEX is a popular solver to use. You'd have to look at some examples on how to set it up, but it's similar to what michael did. –  John May 4 '12 at 21:31
    
I think I would express the third bullet as it is done traditionally, without the I. The trick is the first constraint needs to be re-specified so it's like an either/or constraint. You need to make it so that it is between 0.05% and 1% or equal to zero. –  John May 4 '12 at 21:35
    
I see you edited the original problem specification, but the second bullet (which is analogous to a group definition) can be formulated as a linear constraint as well (for an example, see: quant.stackexchange.com/questions/3089/…). For true mixed-integer problems, Rglpk also offers a fair amount of functionality (and is free, unlike CPLEX). –  michaelv2 May 4 '12 at 22:04
show 1 more comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks a lot! The bounds for w_i you mention are a bit different from my question, but I understand the concept. –  rodion May 5 '12 at 10:38
    
I made an edit but was not really sure about "Its children add..." so I reverted it. –  Bob Jansen May 5 '12 at 14:51
    
@BobJansen: I have made the change you suggested, to match the constraints in the question. –  Vincent Zoonekynd May 5 '12 at 15:03
add comment

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)
share|improve this answer
    
That only considers the constraint $0 \leq w_i \leq 0.05$, not the non-convex constraint ``$w_i=0$ or $0.01 \leq w_i \leq 0.05$''. –  Vincent Zoonekynd May 4 '12 at 23:15
    
Quite right, I completely mis-read that first part. I'll re-formulate the answer using Rglpk and post an edit shortly... –  michaelv2 May 4 '12 at 23:36
1  
The constraints ``$w_i = 0$ or $0.01 \leq w_i \leq 0.05$'' can be rewritten as $0.01 n_i \leq w_i \leq 0.05 n_i$ by adding binary variables $n_i \in \{0,1\}$. The constraints are still linear, but the objective function is still quadratic: we would need a mixed integer quadratic solver -- Rglpk is only a (mixed integer) linear solver... –  Vincent Zoonekynd May 5 '12 at 12:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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