1
$\begingroup$

I am trying to write an algorithm which can output the number of stocks to purchase so that it equal weights positions in a portfolio of stocks.

Say we want to invest $1000 in 5 stocks with equal weighting -

Ticker    Price    Target Weight
AAA        $30     20%
BBB        $32     20%
CCC        $46     20%
DDD        $53     20%
EEE        $41     20%

I am trying to minimise the sum of the differences between the target and the actual weight. Can someone suggest some pseudocode for this problem?

$\endgroup$
3
$\begingroup$

You can simply use an algorithm where you pick one stock at a time.

  1. You start with one of each stock.
  2. Calculate the weights of the stocks in your portfolio.
  3. Pick the stock that is furthest below your target weighting and add one.
  4. Stop if you have no more capital, else go to 2.

Here is a Python implementation of this simple algorithm.

import numpy as np

prices = np.array([30, 32, 46, 53, 21])
targets = np.array([0.2, 0.2, 0.2, 0.2, 0.2])
stocks = np.array([1, 1, 1, 1, 1])
capital = 1000 - np.sum(prices*stocks)

while True:
    weights = prices*stocks / np.sum(prices*stocks)
    idx = np.argmin(weights - targets)
    if capital - prices[idx] < 0:
        break
    else:
        stocks[idx] += 1
        capital -= prices[idx]

With this algorithm and the conditions I get, [6, 6, 4, 4, 5] number of stocks. This is a weighting of [0.18499486, 0.19732785, 0.18910586, 0.21788284, 0.21068859].

This the same result that Kermittfrog, but the algorithm is not as fancy and scales better for large cases.

For very large cases the initial number of stocks can be improved by setting it equal to:

stocks = np.ones(5, dtype=int) * ((capital/len(prices))//prices).astype('int')

Note that this start guess will always be very close to the "optimal" solution.

As found by Kermittfrog, in some cases the algorithm would not give the correct answer, here is, therefore, a new more stable algorithm:

import numpy as np

prices = np.array([133, 100])
targets = np.array([0.5, 0.5])
capital = 1000
stocks = np.ones(len(prices), dtype=int) * ((capital/len(prices))//prices).astype('int')
capital = capital - np.sum(prices*stocks)

fitness = np.zeros(len(prices))
while True:
    for i in range(len(prices)):
        stocks[i] += 1
        fitness[i] = np.sum((prices*stocks / np.sum(prices*stocks) - targets)**2)
        stocks[i] -= 1
    idx = np.argmin(fitness)
    if capital - prices[idx] < 0:
        break
    else:
        stocks[idx] += 1
        capital -= prices[idx]

The scaling of the above is sadly now in the worst-case $\mathcal{O}(N^2)$.

$\endgroup$
5
  • 1
    $\begingroup$ Hi Erik, that's an interesting idea and I like its simplicity and its nice scaling behavior (have played around with it for a bit) - Thanks!. I think the algorithm is not robust enough (for practical purposes, I mean). For example, a portfolio fo 1000 and two assets (133, 100) will result in (4,4) with this algo, but minimizing the abs distance vs $500 = 0.5 \times 1000$ with a corner selection algorithm yields the (correct) result (3,5). Then again, corner-checking may be robust; but becomes way to slow with $N\to \infty$, of course... $\endgroup$ Dec 15 '20 at 9:43
  • 1
    $\begingroup$ @Kermittfrog Thanks for finding an error in the algorithm! I have now modified the algorithm such that it should always fulfill the fitness that you purposed, i.e. $\phi_i=(w_iS_i-w_i^*S_i)^2$. The algorithm is now sadly in worst case $N^2$. $\endgroup$ Dec 15 '20 at 13:04
  • $\begingroup$ If that's truly only $O(N^2)$, then it's still way better than $O(2^N)$, cool. $\endgroup$ Dec 15 '20 at 13:30
  • $\begingroup$ Thanks to you both. I also found a library called pyportfolioopt which has solves my problem. $\endgroup$
    – Ron95
    Dec 15 '20 at 13:38
  • $\begingroup$ @Kermittfrog, here is a notebook that demonstrates the $O(N^2)$ scaling. github.com/erikkjellgren/Shared_notebooks/blob/main/… $\endgroup$ Dec 15 '20 at 13:47
1
$\begingroup$

I understand that you want to find a portfolio consisting of $N$ assets at current prices $S_i$ whose individual investment levels $w_iS_i$ are, in some sense, close to a pre-determined reference portfolio $w_i^*S_i$. Asset weights must be non-negative, $w_i\geq 0$, and the budget is restricted, $\sum_i w_iS_i\leq B$. Ultimately, the investment units $w_i$ are integer, $w_i \in \mathbb{N}.$

Whichever way you formulate the distance function, $\phi(w_iS_i,w_i^*S_i$), this is an optimization problem to be used by some form of integer programming.

Nevertheless, a brute-force method to solve this is this:

  1. For each asset $i$, find $w_i^l \equiv \lfloor w_i^*S_i\rfloor$ and $w_i^h \equiv \lceil w_i^*S_i\rceil$, with $\lfloor x\rfloor $ and $\lceil x\rceil$ the flooring and ceiling functions. This results in $2\times N$ numbers.
  2. Brute force your way through all $2^N$ potential portfolio combinations, i.e.

$$ \begin{align} P_1&=\begin{pmatrix}w_1^l&w_2^l&w_3^l&w_4^l&w_5^l \end{pmatrix}\\ P_2&=\begin{pmatrix}w_1^l&w_2^l&w_3^l&w_4^l&w_5^u \end{pmatrix}\\ P_3&=\begin{pmatrix}w_1^l&w_2^l&w_3^l&w_4^u&w_5^l \end{pmatrix}\\ P_4&=\begin{pmatrix}w_1^l&w_2^l&w_3^l&w_4^u&w_5^u \end{pmatrix}\\ P_k&=\ldots\\ P_{32}&=\begin{pmatrix}w_1^u&w_2^u&w_3^u&w_4^u&w_5^u \end{pmatrix} \end{align} $$ 3. For each of these $2^N$ combinations, you check the goal function (distance to target investments under your distance measure) and the budget constraint $\sum_i w_iS_i\leq B$.

  1. From all portfolios fulfilling the investment constraint, select the one with the smallest distance from optimum.

Again, this method is quite brute and does not scale well to larger $N$...


In your example, assuming a penalty $\phi_i=(w_iS_i-w_i^*S_i)^2$, I find an optimal portfolio of $P^*=\begin{pmatrix}6&6&4&4&5\end{pmatrix}$ with a total investment of 973.

HTH (at least a bit).

$\endgroup$
2
  • $\begingroup$ Thanks Kermittfrog, I had thought about the brute force method for this solution but I felt there might be a more efficient approach. $\endgroup$
    – Ron95
    Dec 14 '20 at 15:16
  • $\begingroup$ Do state it here as soon as you have it, please. $\endgroup$ Dec 14 '20 at 15:19

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.