Mixed-Integer Optimization for Minimum Portfolio Weights
Summary
The document considers a portfolio constraint under which each asset must either have zero weight or meet a positive minimum allocation. This creates a non-convex feasible set, so an ordinary continuous portfolio optimizer cannot represent the choice directly. The accepted answer describes branch-and-cut: divide the problem into subproblems that assign each asset to either excluded or included, solve relaxations to obtain bounds, and prune branches that cannot beat the best feasible portfolio found so far.
A second response provides a basic quadratic-programming example for a different formulation in which each asset is required to have a minimum weight, without the zero-or-minimum selection choice. That example illustrates continuous optimization but does not implement the binary inclusion constraint. The branch-and-cut explanation gives the core approach rather than a full practical algorithm; performance depends on problem structure, solver bounds, and asset count, and the worst-case search can still grow rapidly.
Key ideas
- A zero-or-minimum allocation rule makes the portfolio feasible set non-convex.
- Binary inclusion variables can represent whether each asset is selected.
- Branch-and-cut explores inclusion choices while using bounds to prune subproblems.
- A continuous quadratic program with lower bounds does not by itself model optional asset inclusion.
- Search efficiency depends on the problem and pruning quality, and worst-case complexity remains high.
Tags
Full text
# MPT: Adding constraint on minimum asset weight
# MPT: Adding constraint on minimum asset weight
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 by Vincent Zoonekynd (score 3, accepted)
https://quant.stackexchange.com/a/3444
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 by michaelv2 (score 1)
https://quant.stackexchange.com/a/3442
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)
```Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.