Greedy and Brute-Force Methods for Integer Equal-Weight Portfolios

# Portfolio Optimization - Equal Weighting Algorithm


# Portfolio Optimization - Equal Weighting Algorithm












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?

## Answer by Erik Kjellgren (score 3, accepted)

https://quant.stackexchange.com/a/59975

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

- You start with one of each stock.

- Calculate the weights of the stocks in your portfolio.

- Pick the stock that is furthest below your target weighting and add one.

- 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)$.

## Answer by Kermittfrog (score 1)

https://quant.stackexchange.com/a/59968

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:

- 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.

- 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$.

- 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).