2
$\begingroup$

I want to optimise a portfolio of assets from different countries (A,B,C...) where the set of all country-asset combinations is (A1, A2, A3, A4.... B1, B2, B3... C1...). I want to include a restriction such that I can only invest in one asset from a given country. For example, if I invest in asset A1, then I cannot invest in any other "A" asset.

I am new to portfolio optimisation and wanted to ask if there is any package in R perhaps that can efficiently solve this problem? Is this called nonlinear integer constrained optimisation?

I would appreciate any references that deal with this problem and any links to R packages that might be useful.

Thank you!

$\endgroup$
  • $\begingroup$ I would suggest that before you go into packages, let's try to understand a few things: (1) What is your objective function (mean-variance, or something else)? (2) Once you have an objective function, the restrictions that you are considering is pretty straightforward. Suppose you have portfolio weights $\pi_A = (\pi_{A1}, \ldots, \pi_{An})^\top$. Then the type of constraint you are looking for is simply $K_{11} \pi_A = e_1$, where $K_{11}$ is the $n \times n$ matrix with all zeros except for the $(1,1)$-element that equals to $1$, and $e_1 = (1,0,\ldots,0)$. $\endgroup$ – user32416 Mar 16 '17 at 3:42
  • $\begingroup$ Once you realize how to do this for country $A$, the other countries $B, C, \ldots$ are analogous. $\endgroup$ – user32416 Mar 16 '17 at 3:43
  • $\begingroup$ My objective function is mean-variance optimisation. In your example, does it imply that the weight in the asset A subgroup will be the same as that in all other subgroups, such that we get an equally weighted portfolio across subgroups? $\endgroup$ – roland Mar 16 '17 at 4:06
  • $\begingroup$ No, clearly the portfolio weights will not necessarily equate. See my solution below. $\endgroup$ – user32416 Mar 16 '17 at 4:46
2
$\begingroup$

You could try a heuristic approach.

The problem can be split into two nested optimisations: i) in the inner optimisation, given a set of selected assets, compute mean--variance efficient weights; ii) in the outer optimisation, you iterate through combinations of assets.

The inner optimisation can be solved via a quadratic programme (QP). For the outer optimisation, you could use a local-search technique. To sketch how such a method could be applied, I create some random data. I will assume that for every asset, there are 60 return observations (for intuition, think of them as monthly returns).

set.seed(75578)

I <- cbind(0:15*1440+1, 1:16*1440)
rownames(I) <- LETTERS[1:nrow(I)]
colnames(I) <- c("first", "last")

R <- rnorm(60*max(I), sd = 0.02)
dim(R) <- c(60, max(I))

The returns matrix R is of size 60 times 23040, as per your comment: 16 countries with 1440 assets each. The columns of R are assigned to countries A, B, ... and the start and end indices for each country are in matrix I. This latter matrix looks like this:

   first   last
A      1   1440
B   1441   2880
C   2881   4320
D   4321   5760
E   5761   7200
F   7201   8640
G   8641  10080
H  10081  11520
I  11521  12960
J  12961  14400
K  14401  15840
L  15841  17280
M  17281  18720
N  18721  20160
O  20161  21600
P  21601  23040

I collect all these data in a single list, which makes it easier to pass the information to a function.

Data <- list(I = I,
             nc = nrow(I),
             R = R)

Now suppose we have some set of assets:

x <- Data$I[,1]

x looks as follows:

    A     B     C     D     E     F     G     H 
    1  1441  2881  4321  5761  7201  8641 10081 
    I     J     K     L     M     N     O     P 
11521 12961 14401 15841 17281 18721 20161 21601

To compute the solution to the inner problem, I use the function mvar. To keep things simple, it computes the long-only minimum-variance portfolio. The function makes use of the NMOF package. (I am the author of the package. You will need the latest version, which can be installed as shown below or from GitHub; with the CRAN version, you will have to write NMOF:::minvar).

## install.packages('NMOF', type = 'source',
##                  repos = c('http://enricoschumann.net/R',
##                            getOption('repos')))
require("NMOF")

mvar <- function(x, Data) {
    cv <- cov(Data$R[ ,x])
    w <- minvar(cv, wmin = 0, wmax = 0.5)
    c(sqrt(w %*% cv %*% w))
}

We check how good the portfolio x is by computing its objective function value.

mvar(x, Data)

which, with the given seed, is

0.003645508

Actually, before we use a local search, let us try a 'constructive' solution as a benchmark: select the asset with the lowest volatility from every country, and then compute the minimum-variance weights for this selection.

x_sort <- numeric(Data$nc)
for (i in 1:nrow(Data$I)) {
    cols  <- Data$I[i,1]:Data$I[i,2]
    x_sort[i] <- cols[order(apply(Data$R[ ,cols ], 2, sd))[1]]
}

We can compute this solution's objective function value

mvar(x_sort, Data)

which is better:

0.002234832

Note that the volatility (0.2%) is an order of magnitude lower than the average volatility in the random data set, which was 2%.

Now, in a local search, we start with some solution and try to improve it iteratively. For this, we need a neighbourhood function that takes a solutions and returns a slightly changed solution. Here is one way to write such a function.

nb <- function(x, Data) {

    ## randomly pick one country 
    i <- sample(Data$nc, 1)

    ## randomly pick one asset 
    x[i] <- sample(Data$I[i,1]:Data$I[i,2], 1)

    x
}

Now I try two local-search algorithms: a simple stochastic local search (LSopt) and Threshold Accepting (TAopt). I use the implementations in the NMOF package. The difference between the two algorithms is that LSopt will only accept neighbours that are not worse than the current solution, whereas TAopt is more forgiving and will even accept solutions that are slightly worse than the current solution. In this way, TAopt may escape from local minima. Both methods use 100000 iterations.

steps <- 100000
sol_LS <- LSopt(mvar, list(x0 = Data$I[,1],
                           neighbour = nb,
                           nS = steps),
                Data = Data)

sol_TA <- TAopt(mvar, list(x0 = Data$I[,1],
                           neighbour = nb,
                           nS = steps/10),
         Data = Data)

We can compare the results of both methods with our benchmark solution, which I add as a blue horizontal line.

par(mar = c(5,5,1,1), las = 1, mgp = c(3,0.25,0), tck = 0.01)
plot(x = seq(1, steps, length.out = 1000),
     y = sol_TA$Fmat[seq(1, steps, length.out = 1000),2], log = "y",
     xlab = "iteration", ylab = "portfolio vol", type = "l")
lines(x = seq(1, steps, length.out = 1000),
     y = sol_LS$Fmat[seq(1, steps, length.out = 1000),2], col = grey(.4))
abline(h = mvar(x_sort, Data), col = "blue")
legend("topright", 
       legend = c("Local Search", "Threshold Accepting"),
       col = c(grey(.4), "black"), lwd = 4, lty =1)
text(x = steps*0.8, y = mvar(x_sort, Data), pos = 3,
     "lowest-vol asset per country", col = "blue")

enter image description here

LSopt (grey) and TAopt (black) both achieve solutions of around 0.1%, so substantially better than the constructive solution. Threshold Accepting performs slightly better than a simple local search.

$\endgroup$
1
$\begingroup$

Since you'd specified the objective function is mean-variance, then this is an easy problem to tackle. Let $R = (R_{A1}, \ldots, R_{An}, \ldots, R_{Z1}, \ldots, R_{Zn})$ be the vector of returns for all $A$ to $Z$ countries, and for simplicity in notation, let's just say each country has the same number of stocks (just adjust the notations and dimensions accordingly if it were not the case). Let $dim(R) = N$, and let $\mu = E[R]$ be the mean return vector, and $\Sigma = Var(R)$ be the variance-covariance matrix.

The usual mean-variance optimization problem (can be written in a several different ways, but this is one way):

$$ \max_{\pi} \; \pi^\top \mu - \frac{\eta}{2} \pi^\top \Sigma \pi \tag{O} $$ where $\eta > 0$ can be thought of as the risk aversion of the investor. Here, $\pi$ is the $N$-dimensional vector representing the portfolio weights, and so we have the budget constraint that

$$ \pi^\top \iota = 1 \tag{1} $$, where $\iota$ is the $N$-dimensional vector of one's.

Without any further constraints, the solution to the above optimization problem is the mean-variance solution.

What you are looking for is a problem with additional constraints. Without loss of generality, reorder the indexing if necessary, let's just say you want to only invest into stock number 1 of each country. Define an $n \times n$ matrix $K$ of the form,

$$ K = \begin{bmatrix} 1 & 0 & \ldots & 0 \\ 1 & 0 & \ldots & 0 \\ & & \ddots & \\ 1 & 0 & \ldots & 0 \end{bmatrix} $$ then you define the constraints on countries A through Z as,

$$ K\pi_A = e_1, \ldots, K\pi_Z = e_1 \tag{2} $$ where $\pi_j = (\pi_{j1}, \ldots, \pi_{jn} )^\top$ is the portfolio vector for country $j$. (there's clearly a way to stack all of this into one big matrix equation, but the dimensions and notation will get messy and I'm too lazy to rewrite the OP's notation for countries A through Z).

In all, we have a concave objective function $(O)$, subject to two linear constraints, where $(1)$ is a (linear) budget constraint, and $(2)$ is a (linear) country constraint. The solution exists and is unique. Moreover, at this time, any quadratic programming solver can solve this (indeed, one can even setup the Lagrangian and all and solve this almost explicitly).

$\endgroup$
  • $\begingroup$ I would also like to add that there's nothing inherently "conditional" in this problem (in the sense of conditional probabilities). For the lack of a better word, this is a pretty trivial linear constraint problem on the portfolio weights. And upon further thought, maybe even all this setup is a huge overkill. $\endgroup$ – user32416 Mar 16 '17 at 4:48
  • $\begingroup$ How do you determine the ordering of the assets? (After all, the algorithm should decide which asset from a given country is chosen, not the user.) $\endgroup$ – Enrico Schumann Mar 16 '17 at 11:11
  • $\begingroup$ @EnricoSchumann The OP wants to have it in such a way that if one invests into stock 1 of country A, then he doesn't want to invest into stocks 2, ... , n of country A. The written solution that I have right now is the optimal portfolio when you only invest into stock 1 of all countries, and that results in some value function from the objective function. Now, let's consider the next perturbation: invest into stock 2 of country A, stock 1 of country B, ... stock 1 of country Z; consider the next perturbation and so on. $\endgroup$ – user32416 Mar 16 '17 at 11:17
  • $\begingroup$ In all, you'll have a list of value functions --- pick the one with the highest value then this is the solution. (PS. I thought this perturbation part would be obvious, but I guess not?) $\endgroup$ – user32416 Mar 16 '17 at 11:18
  • $\begingroup$ Thank you; I understood it. But I wanted to point out that it may not be a practically-feasible approach: Suppose you have 10 countries with 100 assets each. Assuming you can compute 1000 LPs in a second, say, it would take more than 3 billion years to compute them all. $\endgroup$ – Enrico Schumann Mar 16 '17 at 11:35

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.