Multiobjective portfolio optimization via Pareto front evolution

A multiobjective optimization problem¹ is stated aswhere \(\Omega \) is the decision space, \(F:\Omega \rightarrow {\mathbb {R}}^m\) consists of m real-valued objective functions and \({\mathbb {R}}^m\) is the objective space. Since the objective values are vectors rather than scalars, a partial order relation, dominance, is introduced. For two solutions a and b, the solution a is considered to dominate the solution b if and only if \(f_i(a)\le f_i(b)\) for all \(\ i \in \{1,\ldots ,m\}\) and \(f_j(a) < f_j(b)\) for at least one \(\ j \in \{1,\ldots ,m\}\). The optimal (non-dominated) solutions of this problem constitute a Pareto set (PS) and the optimal objective values compose a Pareto front (PF) [14, 32].

Variance is an important and widely studied risk measure for the portfolio problem [3, 19]. Nonetheless, this risk measure assumes that the distribution for return of assets should be normal. For example, Fig. 1 exemplifies the variance risk measure for a normal distributed asset. According to the perception of risk for investors, the proportion with lower return than the expected return is considered as the risk. This risk measure is applicable when the distribution is symmetrical about the mean line, otherwise the variance can barely depict the downside risk.

VaR measures the maximum downside risk of a portfolio with a given confidence level and CVaR is the expected loss above the VaR. Figure 2 illustrates the VaR and CVaR intuitively. The vertical axis is about the frequency and the horizontal is about the loss. It depicts a distribution of the loss when the confidence level is \(\alpha \) and the maximum downside risk is \(\beta \).

Formally, assume there are n available assets. \(\mathbf{r }\) denotes the return of the assets and its probability distribution is assumed as \(p(\mathbf{r })\) for convenience. Define \(\mathbf{w }=(w_1,\ldots ,w_n)^{\mathrm{T}}\) as the invested portfolio weight. \(f(\mathbf{w },\mathbf{r })=-\mathbf{r }^{\mathrm{T}}\mathbf{w }\) is the loss and thus the cumulative distribution function is given aswhere \(\beta \in {\mathbb {R}}\).

For a given confidence level \(\alpha \), CVaR of the loss iswhere \({\mathrm{VaR}}_{\alpha }= {\mathrm{inf}}\{\beta | \Psi (\mathbf{w },\beta ) \ge \alpha \}\). Further, Eq. (1) can be approximated by sampling the probability distribution in \(\mathbf{r }\) [10]. The approximated alteration of Eq. (1) can be stated aswhere \((\cdot )^+\) indicates only the positive numbers are considered in this expectation.

Nevertheless, directly minimizing CVaR via Eq. (2) is unachievable with existing mathematical programming methods because it is a conditional expectation instead of a direct formula. Rockafellar and Uryasev; hence, remodel it in a linear formulation [10]. Let \(\varGamma \) be the set of assets, \(|\varGamma |=n\), and \(\varPi \) be the set of time intervals, \(|\varPi |=t\). The sampling from real markets generates a collection of normalized return matrix \(\mathbf{R }\) asWith the return matrix Eq. (3), the linear formulation for CVaR is given aswhere \(\phi \) and \(\gamma _i\) that \(i\in \varPi \) are auxiliary variables. They have proved the solutions for these two CVaR models are same [10].

To build a practical mean-CVaR model, a normalized stock market indices over time are included for measuring the loss. Further, four practical constraints are also included [15, 18]. They are (i) cardinality constraint: it restricts the number of assets (K) for composing a portfolio, (ii) floor and ceiling constraint: it determines the minimum and maximum limits of the invested proportion for each asset, (iii) pre-assignment constraint: it denotes which asset must be selected regarding the preference of investors, and (iv) round lot constraint: it demands each asset should be held as multiples of trading lots.

Thereby, the practical mean-CVaR model, involving the normalized stock market index \(\varvec{\zeta }=(\zeta _1,\ldots ,\zeta _t)\) is stated aswhere the stock market indices, \(\varvec{\zeta }\), is considered in the risk CVaR. The return R is inverted for minimization and the vector \(\varvec{\mu }=(\mu _1,\ldots ,\mu _n)^{\mathrm{T}}\) includes the mean values for every rows in the return matrix. Equation (6) requires that all the capital should be invested. Equation (7) is the cardinality constraint (i.e., just K assets are selected) and \(\mathbf{s }=\{s_1,\ldots ,s_{n}\}^{\mathrm{T}}\) is an indicator vector; \(s_i=1\) if the asset i is selected, and \(s_i=0\) otherwise. Equation (8) is the floor and ceiling constraint. Besides, Eq. (9) represents that the asset i must be included in a portfolio if \(z_i=1\). It is a pre-assignment constraint. Then Eq. (10) defines the round lot constraint and \(\tau \) is a multiple. The multiples for every assets are set to be a same constant, with which 1 is divisible, since it will be really hard to handle flexible ones. In that case, it will be beyond the scope of the main discussion in this work. Finally, Eq. (11), which is the discrete constraint, implies that \(s_i\) must be binary. In summary, the decision variables in this practical mean-CVaR model are selection variable s (constrained to Eqs. (7), (9) and (11)), weight variable w (constrained to Eqs. (6), (8) and  (10)), and auxiliary variables \(\phi \) and \({\varvec{\gamma }}\).

Note that we evaluate a return of one portfolio by the historical data, although there are some alternatives [1, 33, 34]. Because this article mainly discusses about developing an algorithm for the mean-CVaR model, discussions of different measures for the return will be beyond the scope of this article.

The main computational burden for the exact mathematical method on the problem \(({\mathcal {P}})\) is introduced by the integer variables (cardinality constraint), casting it as a mixed-integer problem (MIP). The demanded computational resource of mathematical methods for MIPs, such as branch-and-bound and cut plane methods, grows exponentially when the amount of the integer variables increases [35, 36].

According to the problem \(({\mathcal {P}})\), there are two pivotal variables (s and w) and they are integer and real numbers. For a portfolio, the solution can be presented as \((\mathbf{s }, \mathbf{w })\). Fortunately, mathematical methods can still be efficient if the integer variables s, denoting the combinations of selected assets, are handled in advance. For instance, Fig. 3a exemplifies three sub-objective spaces for three different combinations of selected assets, \(\mathbf{s }^1\), \(\mathbf{s }^2\) and \(\mathbf{s }^3\) on a real-world portfolio problem. A solution with determinate selected assets and indeterminate weights is presented as \((\mathbf{s }, \cdot )\). The solutions, bundling a variable s with all feasible weights w, will constitute the sub-objective space of \((\mathbf{s }, \cdot )\). The optimal solutions for each sub-objective space will constitute the local PFs, as shown in Fig. 3b. Specifically, the local PFs for variables \(\mathbf{s }^1\) and \(\mathbf{s }^2\) are two curves, and the local PF for variable \(\mathbf{s }^3\) is a data point. For mathematical methods, it is much easier to find the local PFs for the sub-objective spaces than finding the global PF for the original problem \(({\mathcal {P}})\), when the integer variables are determined in advance.

In particular, when the integer part, variable \(\mathbf{s }\), can be found, the problem \(({\mathcal {P}})\) can be converted into the following problem with an additional \(\varepsilon \)-constraint.where the objective R is involved as a constraint, \(\varGamma ' \in \varGamma \), and \(|\varGamma '|=K\). In the problem \(({\mathcal {P}}_{\varepsilon })\), since the n-dimensional binary variables \(\mathbf{s }\) is eliminated, much less computational resource is required when the exact mathematical method is invoked. There are some alternative algorithms for the \(\varepsilon \)-constraint method. Most of the algorithms will approximate the PF via setting a number of different values of \(\varepsilon \) [14]. These different values of \(\varepsilon \) are called grids.

AUGMECON2 is employed in F-MOEA/D to deal with the problem \(({\mathcal {P}}_{\varepsilon })\). It is a multiobjective mathematical method based on \(\varepsilon \)-method [30]. It inherits some novel strategy from AUGMECON, escaping from weakly Pareto optimal solutions and redundant iterations [37]. Further, AUGMECON2 enhances the computational efficiency since many redundant grids can avoided. To solve the problem \(({\mathcal {P}}_{\varepsilon })\), AUGMECON2 is combined with a linear programming optimizer from Matlab.

According to the discussion above, we can construct an estimation of the local PF with a number of grids when the integer variable \(\mathbf{s }\) is determined. In the next subsection, the method about ranking the local PFs will be presented.

The optimum of the problem \(({\mathcal {P}}_{\varepsilon })\) contains a set of local Pareto optimal solutions rather than a data point. Therefore, we need to rank the corresponding local PFs for the integer variable \(\mathbf{s }\) appropriately for the environmental selection in MOEAs. Although there should be many different shapes of the local PFs, without loss of generality, we discuss how to perform the elitist selection among local PFs as illustrated in Fig. 4. These curves denote three local PFs for different \(\mathbf{s }\) and all of them includes infinite points. Performing the elitist selection among these local PFs is tricky for existing algorithms. We exploit the decomposition strategy to decompose the multiobjective problem into several scalar optimization subproblems [31, 38].

Suppose a local PF \({\mathcal {F}}\) is constructed when the integer variable \(\mathbf{s }\) is determined. In a minimization problem, we have to evaluate all the points of the local PF \({\mathcal {F}}\) for a scalar subproblem. Then the point with the minimal value can stand for the local PF on the subproblem. In this manner, the comparison between the local PFs is converted into the comparison of some representatives and any decomposition method is applicable. In this work, the Tchebycheff approach is used and it is stated aswhere \({\mathcal {F}}\) is the local PF, \(F=(f_1,\ldots ,f_m)\) is an objective vector. \(\lambda \) is a weight vector, \(\lambda =(\lambda _1,\ldots ,\lambda _m)^{\mathrm{T}}\), and \(z^*_i\) is the optimal value of the ith objective. The right side of Eq. (18) involves two parts. First, all the points F in the local PF \({\mathcal {F}}\) are evaluated by the Tchebycheff approach. Second, the minimal value for the Tchebycheff approach can be determined via traversing the all the points of the local PF. If \(g({\mathcal {F}}^1|\lambda ,z^*)\) is smaller than \(g({\mathcal {F}}^2|\lambda ,z^*)\), the local PF \({\mathcal {F}}^1\) is considered to be better than local PF \({\mathcal {F}}^2\).

Figure 4 depicts this elitist selection for two direction vectors (\(\mathbf{v }^1\) and \(\mathbf{v }^2\)), corresponding to two weight vectors. In Fig. 4a, as for local PF\(^1\), point A has the smallest Tchebycheff value with the direction vector \(\mathbf{v }^1\). For local PF\(^2\) and PF\(^3\), points B and C have the smallest Tchebycheff values. Since the smaller \(g({\mathcal {F}}|\lambda ,z^*)\) the better, we can hence conclude the local PF\(^1\) is the best while the point A has the smallest value for the Tchebycheff approach. For the same reason, the local PF\(^2\) is the best in the Fig. 4b.

MOEA/D is a decomposition-based multiobjective evolutionary algorithm, in which variables are optimized iteratively [31, 39, 40]. The main idea is using the neighborhood information to assist the search of every individual in the population. At each generation, MOEA/D maintains N solutions \(x^1,\ldots ,x^N\), where \(x^i\) is the solution to subproblem i. Assume each subproblem is a minimization problem and the objective function of subproblem is \(g^i(x)\). According to the distances among weight vectors, a T-neighborhood of each solution can be determined since each one corresponds to a weight vector. Thereby, a solution in the T-neighborhood of solution \(x^i\) is defined as a T-neighbor of \(x^i\). The main loop of a basic MOEA/D framework works as follows.

For each subproblem i:

We take MOEA/D-DE in [41] as the basic of F-MOEA/D and Algorithm 1 summarizes F-MOEA/D. Weight vectors and neighborhood structure are initialized first (line 1). Then, the population is initialized as \(x^1,\ldots ,x^N\) and the corresponding local PFs \({\mathcal {F}}\) are obtained with the function Getfront() (line 2). The function Getfront() is based on AUGMECON2 and a linear optimizer. As for the inputs, \({\mathcal {P}}\) is the problem data, \(x^i\) is the integer variable \(\mathbf{s }\), and \(\lceil \root 2 \of {N} \rceil \) is the number of grids for the estimated local PF. For more details, audiences can refer to [30]. Afterwards, the reference point z and the fitness value \(FV^i\) for every subproblem i are initialized (line 3). Lines 4–27 describe the main loop of F-MOEA/D. From lines 6–10, the indices of the mating and replacement pool P are determined. Next, new candidates are generated and their local PFs are estimated (lines 11 and 12). The generate operators are detailed in “Representation and generate operators”. From lines 13–17, the reference point z is updated. Then, no more than \(n_r\) subproblems will be updated if the new candidate is better (lines 18–25). A more complete re-estimation of the local PFs will be performed by setting the grid number as N instead of \(\lceil \root 2 \of {N} \rceil \) (line 28). Finally, \(N^2\) points from all the local PFs are collected and N best solutions based on non-dominated sorting and the crowding distance are output (line 29).

As illustrated in Fig. 5, one example of performing F-MOEA/D on the constrained portfolio problem is presented. The iterative optimization process of F-MOEA/D is distinctively different from the general point-based MOEA. In each generation, each line is a local PF and each local PF corresponds to an individual. These individuals (local PFs) are maintained and evolved instead of points. From Fig. 5a–d (from generation 1 to 26), these sets of individuals (local PFs) gradually converge to the global PF.

Various alternative representations can be employed for the binary vector \(\mathbf{s }\). We follow and slightly alter the representation and generate operators in [15]. They are tailored for the constrained portfolio optimization and the simulator experiments have demonstrated their effectiveness. Specifically, a n-dimensional continuous vector x is employed for the binary vector \(\mathbf{s }\). If L pre-assigned assets are selected, among the assets which are not pre-assigned, the \(K-L\) assets with highest values are selected. Then two generate operators are implemented with same chances.

First, generate operators for continuous variables can be directly employed here. They are differential evolution (DE) [42] and polynomial mutation [43], which never use prior knowledge. They are defined as follows: where \(x^1\), \(x^2\) and \(x^3\) are three solutions randomly selected from the population, F is a scaling factor in DE, \(\mathrm{polymt}(u_i,\eta _m,p_m)\) is a polynomial mutation function on \(x_i\) with an index parameter \(\eta _m\) and a mutation probability \(p_m\), and \(x_{{\mathrm{new}}}\) is the new solution.

Second, a tailored operator that utilizes the known information of the portfolio optimization problem is slightly altered as follows.

The benchmarks like OR-library³ are widely used and play a significant role in promoting the study of portfolio optimization. However, a distinct feature of the financial markets nowadays is that the scale of problems raises dramatically year after year. This requires us to tackle large-scale problems, involving thousands candidate assets. Hence, we test the compared algorithms in practical stock markets (Chinese stock markets) nowadays. The data is composed of daily close prices of assets and the CSI 300 Index from 11 December 2009 to 8 December 2020.⁴ The available assets arrange from 475 to 9090 while both stocks and funds are considered. The details of the data are listed in the Table 2. The start and end dates are presented in the form of day-month-year.

Regarding the performance measures, two metrics are applied, Hypervolume (HV) [46] and Generational Distance (GD) [47], they are easy to use in PlatEMO [48]. HV prefers heuristics because it takes the diversity of solutions into account. Heuristics, like EAs, always pay much attention to the diversity of solutions while exact methods hardly do it [14, 49]. It is given aswhere Q is the set of obtained solutions of algorithms, and \(hc_i\) is the hypercube bounded by solution i and the reference point r. Better solutions lead to higher HV. On the other hand, GD evaluates the convergence ability of algorithms. In this problem, it tends to prefer exact mathematical programming approaches since exact methods are going to find the optimum if possible yet heuristics search for approximations. It is defined aswhere Q is the set of obtained solutions of algorithms and \(d_i\) is the shortest Euclidean distance among solution i and the representatives of PF. Better solutions lead to lower GD.

Note that the implementations of HV and GD require the true PFs or reference points. The PFs are obtained by implementing AUGMECON2&LP with 100 grids. However, they are unavailable while running the exact method after 7 days for some large-scale problems in this work. For these cases, all the solutions from two MOEAs with 31 independent runs are collected to construct the temporary PFs. Concerning the reference point, it is recommended to set the reference point r slightly dominated by the nadir point of the PF. Specifically, r is set as (1.1, 1.1).

In the experimental studies, we discuss about the running time of the exact mathematical method on the constrained portfolio problems. Then the performance of the implemented algorithms are compared numerically and graphically.

Figure 6 shows the running time of AUGMECON2&LP on D1 to D8. The exact mathematical method is very effective for small problems. It just takes several hundred seconds for addressing D1, D2 and D3. Nevertheless, the required times rise non-linearly. It takes more than 1 h to solve D5 and D6, while the demanded running times raise to 32 h for D7 and D8. Furthermore, the exact mathematical method even can not finish in 7 days for the largest two problems. These computational costs for large-scale problems are unaffordable when the investors are going do some high frequency trading operations. This confirms the necessity of devising efficient heuristic algorithms.

Tables 3 and 4 summarize the results of seven algorithms regarding HV and GD. The results of AUGMECON2&LP are not reported in these tables but are plotted in the figures as the true PFs for comparison. Because if the exact mathematical method completes, the HV and GD of it must be the best since it can find the proved optimal solutions for these MIPs.

Concerning HV, F-MOEA/D outperforms other six algorithms on almost all the problems while its performance is similar with CCS-MOEA/D and worse than TDMEA on \(D_{7}\). The three MOEAs, CCS-MOEA/D, MODE-GL and TDMEA, tailored for the constrained portfolio optimization outperform the generic MOEAs. This result is expected since the tailored MOEAs either utilize specialized representation nor make use of some priori information, such as the return and risk of assets. Among these tailored MOEAs, CCS-MOEA/D and TDMEA have similar performance while MODE-GL is defeated by them on all problems. The solutions obtained by SMS-EMOA are worst while NSGA-II and MOEA/D perform similarly. It is rational because the CPU time is set as the stop criterion and SMS-EMOA will calculate the performance metrics frequently, occupying lots of computational resources. Moreover, the Wilcoxon rank-sum test at 5% significant level is also adopted. Symbols ‘+, −, \(\sim \)’ means the performance of the corresponding algorithm is better than, worse than or similar to F-MOEA/D. For instance, ‘0/9/1’ denotes the CCS-MOEA/D is worse than F-MOEA/D on 9 problems, and competitive with F-MOEA/D on 1 problem. F-MOEA/D is still the best algorithm regarding the Wilcoxon rank-sum test.

Regarding GD, similar conclusion can be made from the Table 4. The results reconfirm the superiority of F-MOEA/D since it has better performance on almost problems and hardly loses to others in terms of the employed Wilcoxon rank-sum test. The three tailored MOEAs still performs well and their performance is better than three generic MOEAs. Meanwhile, SMS-EMOA still can not compete with other algorithms on all the problems.

In Tables 3 and 4, F-MOEA/D is the best algorithm on most test problems, but it is worse than some MOEAs on a few datasets. There are probably two reasons why F-MOEA/D sometimes fails. (1) Because F-MOEA/D can only ensure the solutions for the linear programming problem are optimal but the optimality for the selection of assets from EAs is not guaranteed. (2) In a same time budget, the number of sampling times for the selection of assets is very limited in F-MOEA/D compared to MOEAs since constructing the local PFs is time consuming.

Figure 7 illustrates the obtained efficient fronts of every algorithm, hence, an intuitive comparison can be made. Approximated fronts with median HVs for every algorithm, except MOEA/D and SMS-EMOA, are plotted. MOEA/D and SMS-EMOA are omitted because the performance of three generic MOEAs is similar. Due to the space limit, fronts on 6 problems are plotted. In Fig. 7a–d, the PFs are the solutions obtained by AUGMECON2&LP. On small-scale problems, \(D_1\) and \(D_3\), the solutions of F-MOEA/D almost lie on the true PFs. It indicates the optimal solutions are almost found by F-MOEA/D. Except MODE-GL, all the other algorithms perform similarly and their solutions are close to the PFs. The solutions from MODE-GL are frustrating when they are far away from the PFs and the diversity is not good. On \(D_5\) and \(D_7\), the solutions obtained by F-MOEA/D are not bad. Despite of the limitation times for sampling the variables in EAs, the approximated PFs obtained by F-MOEA/D are not far from the PFs and they are good distributed. CCS-MOEA/D and TDMEA perform much worse than F-MOEA/D on \(D_5\) and a bit better than F-MOEA/D on \(D_7\). Both NSGA-II and MODE-GL have poor performance on these two problems, but NSGA-II is now defeated by MODE-GL. Concerning \(D_9\) and \(D_{10}\), these two problems involve large number of candidate assets, the PFs are composed of the non-dominated solutions from all MOEAs with all independent implementations. The solutions of F-MOEA/D are very close to the PFs, while there are certain gaps between the solutions from the other algorithms and the PFs. The solutions of CCS-MOEA/D, TDMEA, MODE-GL are acceptable, but those of NSGA-II are very far from the PFs. These reconfirm the superiority of F-MOEA/D.

Besides the comparison among peer algorithms, this subsection intends to analyze the swap operator (O2) for the F-MOEA/D. There are three swap strategies based on the priori information of the data, they are devised for searching the asset with the highest return, the lowest CVaR and the lowest VaR, respectively. We hence perform an ablation study on these strategies. Due to the space limitation, the simulation experiments are implemented on 4 problems, \(D_1\), \(D_3\), \(D_5\), and \(D_7\).

Table 5 shows the results, the first, second, third and all the swap strategies are eliminated. We denote these methods as F-MOEA/D\(_{\{S2,S3\}}\), F-MOEA/D\(_{\{S1,S3\}}\), F-MOEA/D\(_{\{S1,S2\}}\), F-MOEA/D\(_\emptyset \) respectively. The results indicate that the first swap strategy play the most important role, because once it is eliminated the solutions become significant worse compared to the original F-MOEA/D on these 4 problems. The algorithm will get exact benefit from the first strategy because the objective, return R, in the portfolio optimization is a linear function. It means we can directly get the best solution for the return R with a greedy method. On the other hand, since the risk CVaR is not a linear function, a portfolio can not be guaranteed to have the lowest CVaR when each asset in the portfolio has a lowest CVaR. Therefore, the second and third strategy will not make such contributions as the first one. Nevertheless, the results in the table denote the algorithm will perform better if these two strategy are included.

Figure 8 illustrates the front obtained by each algorithm. Compared to the original F-MOEA/D, the fronts obtained by the algorithm without the swap operator will distinctly shift to the upper right. Since the upper side implies lower return and the right side denotes higher risk, these results indicate that the swap operator assists the algorithm search for better solutions. Furthermore, on \(D_7\), the solutions obtained by the algorithm without the first swap strategy are very far away from the high return area, this indicates in the large-scale problem the first swap strategy will help the algorithm search for the high return solutions efficiently.

So far, we have compared F-MOEA/D with three generic and two tailored MOEAs. In this subsection, comparisons among F-MOEA/D and three variants of MOEA/D, namely MOEA/D-DE [41], MOEA/D-PSO [50] and MOEA/D-GA [31], are also made. These variants have shown excellent performance on some traditional black box problems and the parameters of these reproduction operators are kept the same as in the literature.

These three variants of MOEA/D and F-MOEA/D are implemented for 4 problems, \(D_1\), \(D_5\), \(D_7\) and \(D_{10}\). Statistical results are provided in Table 6 and graphical results are presented in Fig. 9. In the Table 6, it is easy to tell that all these variants of MOEA/D with different reproduction operators are worse than F-MOEA/D not only on the mean values of HVs but also on the Wilcoxon rank-sum-test. In Fig. 9, the solutions of these three variants of MOEA/D roughly approximate the PF on \(D_1\), but they can hardly reach the PFs, on \(D_5\), \(D_7\) and \(D_{10}\). These results are almost anticipated, because these invoked reproduction operators are generic for black box problems and they are not tailored for portfolio optimization. For the small-scale problem, D1 (\(N=475\)), these reproduction operators are barely workable, but for the large-scale problems, \(D_5\), \(D_7\) and \(D_{10}\) (\(N\ge 3406\)), these operators almost fail.