Heuristics for cardinality constrained portfolio optimisation
The current project aims to make an investment decision of £1 billion, by identifying the best portfolio of ten assets determined by the level of return and risk associated with them. Considering also that those assets are not independent of each other, hence the optimising equation also contains the correlation among assets. The proportion of total investment (£1B) can vary for each of the ten assets in the portfolio, however a constraint of a minimum proportion of investment, i.e. £100,000, was levied.
The two key objectives identified for reaching the desired result were:
- Minimization of the expected variance (risk) of the portfolio
- Maximization of the expected return of the portfolio
With the use of efficient algorithms for portfolio optimization we can derive the optimal combination of assets to invest on and the relationship between the revenue and risk. Heuristic algorithms enable us to guide the solution search to optimum solutions fast and efficiently, as the examination of all possible combination of assets is computationally expensive.
In order to validate our findings, a sensitivity analysis was performed by examining different input parameters of the algorithms and critically comparing the returns they yielded.
After examining the trade-off between return and risk, inferior sets of assets which had relatively lower return and higher risk were eliminated from further analysis. For each stock market, a set of optimal solutions (efficient solutions) was produced that was later used as the basis for comparison of the five markets. As a result, underperforming markets were eliminated and thus, a well-informed decision can be made to invest on the best stock market based on the desired return and risk.
Based on the comparison of the efficient frontiers of the 5 markets, we can conclude that, overall, the investments on DAX outperform all candidate investment portfolios for FTSE, S&P and Nikkei, and can be an ideal investment opportunity. DAX investments qualify as high return and low risk. By investing on DAX stock, we can have a maximum return of approximately £9 million with a risk of £2 million. However, analysis yielded that without considering the risk, investing on Hang Seng market can result to the highest possible return among all stock markets. Investing on ten assets of the Hang Seng market we can obtain a maximum return of slightly more than £10 million. Though, Investments on Hang Seng market with returns higher than £8 million are especially risky.
Let's assume the following scenario. A fund manager approaches us to optimise their investment portfolio of assets. They have a budget of £ 1 billion (£1B) and they want to invest it on exactly 10 assets. A decision must be made, for each asset that is included, about the proportion of the £1B that is invested on it, which must be larger than a given minimum transaction level (min-buy) of 1% (or 0.01). We are given for each asset its expected return of investment and the standard deviation of this return (which can be seen as the risk associated with an asset). The asset returns are not independent, and we are also given the correlation between assets.
Based on the paper (see references) we decide to minimise the following objective:
by minimizing the expected variance of the portfolio and maximizing the expected return of the portfolio:
where
- Initially, we'll apply the algorithms to each dataset (there are five of them) using a maximum of 1000x$N$ solution evaluations for each run. Each solution evaluation is a call to Algorithm 1 (evaluate) in the accompanying paper (
$E = 1$ ,$\lambda = 0.5$ ). Each run will be repeated with a different initial random seed 30 times and the values of R and CoVar of the best solution returned by each run will be collected. - After analysing the above results, we'll examine how the performance of the heuristic changes when we change the parameter L. Specifically, the following values of L will be examined:
- After deciding which parameter L maximizes the revenue, we'll explore the trade-off between the two objectives (R and CoVar). To do so, an efficient frontier will be produced which examines 50 different
$\lambda$ values drawn from the range [0,1] (E = 50 in the research paper) using 1000x$N$ solution evaluations for each$\lambda$ value.
To test our heuristic 5 test data-sets were used with the weekly prices of five different capital market indices drawn from around the world. Specifically, the weekly prices of the following stock markets were considered:
| Stock Markets | Number of assets (N) |
|---|---|
| Hang Seng (Hong Kong) | 31 |
| DAX 100 (Germany) | 85 |
| FTSE 100 (UK) | 89 |
| S&P 100 (USA) | 98 |
| Nikkei 225 (Japan) | 225 |
All five datasets have the following format:
31 # number of assets (N) .001309 .043208 # expected return, standard deviation of return of asset 1 .004177 .040258 # expected return, standard deviation of return of asset 2 ... .001487 .041342 # expected return, standard deviation of return of asset N 1 1 1.000000 # correlation between assets 1 and 1 1 2 .562289 # correlation between assets 1 and 2 ... 30 31 .629523 # correlation between assets 30 and 31 31 31 .379162 # correlation between assets 31 and 31
The first algorithm implemented, Random Search, included continuous generation and evaluation of sets of 10 random assets in order to achieve as many combinations of different assets as possible. Only those combinations were considered that showed dominating behaviour in terms of higher return and lower risk simultaneously as compared to others, where equal importance was given to risk and return
The results of Random Search (see appendix tables) show that the most rewarding market is Hang Seng in terms of return, however the principal of risk-return trade-off applies here, as the highest return is also accompanied with highest risk. In addition, DAX market can be regarded as the safest choice with minimum risk, reasonable return and least deviation from the mean. FTSE is also relatively a stable choice after DAX though, while Nikkei is the least attractive option as the mean return is lowermost, together with very high risk and standard deviation.
In search of the most optimal solution another algorithm was used, Tabu Search (Chang et al, 2000). What differentiates this algorithm from the previous one is that instead of randomly generating and evaluating a solution each time, it creates a number of possible solutions at once and then evaluates them to get the best solution. When this is completed it accesses the best solution's assets one by one by changing this asset with a new one and then considering if the revenue-risk association improves by such change.
The results of the Tabu Search algorithm reaffirm the outcomes of the Random Search algorithm by reinforcing the idea of Risk-return trade-off. As per the Tabu search too, Hang Seng has the greatest return with the greatest risk whereas Nikkei has the lowest return with lowest risk. The DAX portfolio is the most stable choice with the lowest risk and relatively high returns. However, the degree of risk and return have substantially increased in the Tabu Search algorithm.
The appropriate tables (see appendix A) were created in order to compare the results of both models (Random and Tabu search), the main characteristics under which they are being compared are: Mean, Standard Deviation and Range of Evaluation. Findings:
- The Tabu search achieves a higher average of revenue or return in all the scenarios.
- However, the Tabu Search displays a higher risk and standard deviation compared to Random Search.
- The Tabu search considers a wider range of return values than the Random search.
The L* (Tabu Tenure) is a value that is used to lock a sub-optimal asset for a fixed number of evaluations where it cannot be considered as a possible investment opportunity. Thus, by using the Tabu Tenure, the examination of sub-optimal or identical assets are reduced and the number of different combinations are maximized, saving both time and increasing accuracy. Box-Plots of the returns for different Tabu Tenures for each market help in the identification of the parameters that provided the most optimal results.
The analysis starts in the f value Box-Plots considering the lower values with the least variance, for example in the Market 1 (Hang Seng) we selected L = 1, 5, and 7, as they minimise the difference between risk and return. However, in order to conclude, the average value of expected return is taken into consideration in the return Box-Plots which lead to selecting L = 2 and 5 as they have the highest expected value. By combining these two analysis it is possible to conclude that L = 5 minimizes the objective function. This process was repeated for the different Datasets and different L values were chosen, however, due to the randomness non definitive value of L could be defined which lead to taking an empirical approach for selecting the parameter value.
Hang Seng
DAX
FTSE
S&P
Nikkei
Several simulations of the problems were repeated in order to establish a robust approximation for the parameter value that provides optimal results. Empirically speaking, it was concluded that the L value is highly correlated to the size of the problem studied. Our understanding of the algorithm used suggests the same, large L* in small datasets restricts the process around a solution identified as best (local maximum) and fails to access alterations that would result to a better one or possibly the best. For this reason, it was judged as crucial to use small values for markets of few assets. On the other hand, a small value to research a big market fails to consider different combinations in the context that “wastes” resources for portfolios perhaps already examined, making clear the need to use a larger value. In this project the below interval rule was established to approximate optimal L* where
For the reasons provided above and in accordance to our rule we decided to use the following:
| Stock Market | L* value |
|---|---|
| Hang Seng | 5 |
| DAX | 7 |
| FTSE | 7 |
| S&P | 7 |
| Nikkei | 10 |
To provide better investment information, the trade-off between Risk and Return (CoVar and R, respectively) was explored. An efficient frontier, for both algorithms and all five markets, was conceived by testing how the portfolios values changed when the preferences of the decision maker lied on return over risk or vice versa. The dominating portfolios were kept as approximations of the efficient frontier. The following figures depict the aforementioned trade-off where the blue points represent dominated portfolios and the yellow line consists of all those portfolios that have either better return or lower risk than each other, but never both. Naturally, the first algorithm fails to achieve as large returns as the second one. When it comes to the five different markets it is observed, as was previously, that Tabu Search outperforms Random Search in terms of revenues whilst manages to find more efficient investment portfolios, thus offering flexibility to the decision maker. Visual comparison between the available markets can also be conducted in Figure 3 where the efficient frontiers are summarized in a common graph.
Hang Seng
DAX
FTSE
S&P
Nikkei
It is easily identified that some markets are dominated by others in the context of either lower risk/greater return or both, with only two contenders standing at the end. Hang Seng market has a return fluctuating from £3,3940,000 - £10,180,000 with risks of £679,000 - £4,005,000 when at the same time DAX includes a portfolio with returns from £2,963,000 to £9,134,163 and a risk range from £216,000 to £2,292,004. Although DAX outperforms Hang Seng and should be preferred for expected returns of up to £9,000,000 in lower risk scenarios, the latter should not be neglected immediately since it supports higher returns along with higher risks, which would be fitted for risk taker investors.
The implementation is based on the following research paper: T.-J. Chang, N. Meade, J.E. Beasley, Y.M. Sharaiha, Heuristics for cardinality constrained portfolio optimisation, Computers &Operations Research, 27(13):1271-1302, 2000, https://doi.org/10.1016/S0305-0548(99)00074-X
Hang Seng
| Random Search | Tabu Search | |||
|---|---|---|---|---|
| R | CoVar | R | CoVar | |
| Mean | 6,294 | 1,306 | 8,688 | 2,338 |
| Standard deviation | 244 | 183 | 782 | 395 |
| Minimum | 6,057 | 1,034 | 5,114 | 971 |
| 25% | 6,145 | 1,191 | 8,735 | 2,248 |
| 50% | 6,210 | 1,271 | 8,864 | 2,343 |
| 75% | 6,360 | 1,363 | 9,036 | 2,573 |
| Maximum | 7,230 | 1,905 | 9,357 | 2,953 |
DAX
| Random Search | Tabu Search | |||
|---|---|---|---|---|
| Mean | 5,554 | 427 | 8,068 | 943 |
| Standard deviation | 272 | 78 | 867 | 327 |
| Minimum | 5,002 | 321 | 5,254 | 573 |
| 25% | 5,404 | 366 | 7,889 | 732 |
| 50% | 5,509 | 416 | 8,455 | 837 |
| 75% | 5,597 | 466 | 8,581 | 1,052 |
| Maximum | 6,328 | 710 | 8,900 | 1,916 |
FTSE
| Random Search | Tabu Search | |||
|---|---|---|---|---|
| Mean | 5,351 | 518 | 6,983 | 952 |
| Standard deviation | 199 | 74 | 998 | 241 |
| Minimum | 4,953 | 371 | 4,737 | 399 |
| 25% | 5,189 | 469 | 6,602 | 858 |
| 50% | 5,336 | 514 | 7,494 | 993 |
| 75% | 5,489 | 550 | 7,647 | 1,091 |
| Maximum | 5,863 | 683 | 7,897 | 1,296 |
S&P
| Random Search | Tabu Search | |||
|---|---|---|---|---|
| Mean | 6,190 | 646 | 7,846 | 1,363 |
| Standard deviation | 234 | 113 | 590 | 369 |
| Minimum | 5,870 | 463 | 6,171 | 720 |
| 25% | 6,000 | 578 | 7,513 | 1,149 |
| 50% | 6,127 | 621 | 8,035 | 1,393 |
| 75% | 6,340 | 696 | 8,322 | 1,576 |
| Maximum | 6,750 | 1,059 | 8,519 | 2,225 |
Nikkei
| Random Search | Tabu Search | |||
|---|---|---|---|---|
| Mean | 1,895 | 705 | 3,064 | 913 |
| Standard deviation | 188 | 85 | 456 | 134 |
| Minimum | 1,540 | 556 | 2,070 | 691 |
| 25% | 1,791 | 639 | 2,860 | 819 |
| 50% | 1,883 | 711 | 3,159 | 903 |
| 75% | 1,965 | 747 | 3,431 | 1,007 |
| Maximum | 2,394 | 899 | 3,687 | 1,171 |