Proximal Linearized Method for Sparse Equity Portfolio Optimization with Minimum Transaction Cost

Introduced by Markowitz [20] in 1952, mean-variance optimization (MVO) has been widely used in the selection of optimal investment portfolios. The success of MVO is attributed to the simplicity of its quadratic objective function, which in turn can be solved by quadratic programming (QP) that are widely available. However, MVO has flaws on its own and its implementation in portfolio optimization has been heavily criticized by academics and professionals [22]. One of its flaws, as pointed out by Michaud [21], is its sensitivity towards input parameters, thus maximizes the errors associated with these inputs. This was proven theoretically and computationally by Best and Grauer [3], where a slight change in the assets’ expected return or correlations results in large changes in portfolio weights. Despite that, MVO remains to be one of the most successful framework due to the absence of models that are simple enough to be cast as a QP problem.

Over the past one decade or so, the success of robust optimization techniques has allowed researchers to consider non-quadratic objective function and regularization for portfolio optimization. Consequently, the work by Daubechies et al. [12] showed that the usual quadratic regularizing penalties can be replaced by weighted $\ell_{p}$-norm penalties with $p\in[1,2]$. Two specific cases in portfolio optimization, namely lasso when $p=1$ and ridge regression when $p=2$, were considered by Brodie et al. [9] and [14], respectively. While the ridge regression regularization minimizes the sample variance subject to the constraint which leads to diversification, lasso regularization encourages sparse portfolios which in turn leads to the minimization of transaction cost. Such regularizations have been studied notably by Chen et al. [10], De Mol [13] and Fastrich et al. [15].

In reality, financial institutions charge their customers transaction fees for trading over the stock market. The two most common ways to charge their customers are based on a fixed transaction fee and/or a proportion of the investment amount, whichever is higher. In general, a large number of transactions will result in higher transaction cost, likely to be caused by small investments that incur fixed transaction fees. Transaction cost, in this sense, will have an effect on the portfolio optimization and the frequency of time rebalancing the portfolio. On the other hand, diversification is the practice of spreading the investments around so that the exposure to any one type of asset is limited. This practice can help to mitigate the risk and volatility in the portfolio, but potentially upsizing the number of investment components and thus, increasing the number of transactions. Therefore, a more realistic model is needed to strike a balance between diversification and minimizing transaction cost for optimal portfolio selection.

Due to the complexity of the objective function and the regularization that are involved, many existing literature employ the alternating direction method of multipliers (ADMM), which was first introduced by Gabay and Mercier [17] in 1976. It was not until the recent decade that ADMM has received much attention in machine learning problems. The essence of ADMM is that it allows one to handle the objective terms separately when they can only be approximated using proximal operators. Its appealing features in large-scale convex optimization problems include ease of implementation and relatively good performance (see, for instance Boyd et al. [8], Fazel et al. [16] and Perrin and Roncalli [22]). Some of the examples of ADMM-like algorithms in portfolio optimization can be found in Chen et al. [10], Dai and Wen [11] and Lai et al. [18], where they are used to solve $\ell_{p}$-regularizing problems when $p\in[1,2]$. Though $\ell_{0}$-norm is ideal for sparsity problems, the regularization result in a discontinuous and nonconvex problem, of which the computation will turn out to be complicated.

In this paper, we propose a new algorithmic framework to maximize the sparsity within the entire portfolio while promoting diversification, i.e. to minimize the $\ell_{0}$-norm and $\ell_{2}$-norm of the asset weights, respectively, subject to a minimum expected return via MVO. We first transform the constrained problem into an unconstrained one, to find a non-smooth and non-convex objective term. The technique of ADMM allows us to handle these terms separately, but nevertheless converges to its optimal solution. Numerical results using real data are also provided to illustrate the reliability of the proposed model and its efficiency in generating higher expected return while minimizing transaction cost when compared to the standard MVO.

This paper is organized as follows: In Section 2, we present a model for sparse equity portfolio optimization with minimum transaction cost and establish the proximal linearized method for $\ell_{0}$-norm minimization. Subsequently, in Section 3, we present an ADMM algorithm to find the optimal portfolio of the proposed model, together with its convergence analysis. To illustrate the reliability and efficiency of our method, we present the numerical esults using real stock data in Section 4. Finally, the conclusion of the paper is presented in Section 5.

We begin with a universe of $n$ assets under consideration, with mean return vector $\mu\in\mathbb{R}^{n}$ and the covariance matrix $V\in\mathbb{R}^{n\times n}$. Let $x\in\mathbb{R}^{n}$ be the vector of asset weights in the portfolio. Our objective is to maximize the portfolio return $\mu^{T}x$ and minimize the variance of portfolio return $x^{T}Vx$, while maintaining a certain level of diversification $||x||^{2}_{2}$ and minimizing transaction cost $||x||_{0}$. The variance of the portfolio return is the measure of risk inherent in investing in a portfolio, and we shall denote this as variance risk throughout this paper. The portfolio is said to be pure concentrated if there exists $i$ such that $x_{i}=1$ and equally-weighted if $x_{i}=\frac{1}{n}$ for all $i$. Assume that the capital is fully invested, thus $e^{T}x=1$ where $e\in\mathbb{R}^{n}$ is an all-one vector. A sparse equity portfolio optimization with minimum transaction cost (SEPO-$\ell_{0}$) goes as follows:

where $\beta_{1}>0$ is a parameter for leveraging the portfolio variance risk, $\beta_{2}>0$ is a parameter for leveraging portfolio diversification and $r\geq 0$ is the minimum guaranteed return ratio with $r\leq\max\{\mu_{i}\}$.

In a standard MVO, diversification is of general importance to reduce portfolio risk without necessarily reducing portfolio return. While diversification does not mean that we add more money into our investment, it certainly does reduce our investment value as the investment in each equity incurs transaction cost. Our proposed method takes into consideration of having diversified investments, but at the same time avoid small investments that might incur unnecessary transaction costs due to its diversification. Note that the sparsity measure of the vector $x\in\mathbb{R}^{n}$ is given by

Minimizing $\ell_{0}$-norm in (2.1) promotes sparsity within the portfolio, since the values of $x_{i}$ are forced to be zero except for the large ones, thus minimizing the transaction cost.

Our model (2.1) poses computational difficulties due to the non-convexity and discontinuity of $\ell_{0}$-norm and the inqeuality constraint $\mu^{T}x\geq r$. Instead of dealing with the problem in its entirety, we employ the alternating direction method of multipliers (ADMM) such that the smooth and non-smooth terms can be handled separately. This calls for a brief introduction of proximal operators and Moreau envelope [23]:

Suppose now we are given a problem

where $\psi,\phi\colon\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\{+\infty\}$ are closed proper functions, of which both $\psi$ and $\phi$ can be nonsmooth. Under the ADMM algorithm, each iteration $k$ takes on an alternating nature with the proximal operators of $\psi$ and $\phi$ being evaluated separately:

Viewing the above as a fixed point iteration, the ADMM scheme results in $x=z$ such that

In the next section, we will see how the proximal operators are evaluated alternately to give us the optimal solution for problem (2.1).

In this section, we present an ADMM algorithm to find the optimal portfolio of the proposed SEPO-$\ell_{0}$ model (2.1) and establish its global convergence.

SEPO-$\ell_{0}$ Algorithm

1. Step 0

   Given $\beta_{1},\beta_{2},\sigma,r,V,\mu,\rho,\alpha$, initial point $(x^{0},\lambda^{0})$ and convergence tolerance $\varepsilon$. Set $k:=0$.

2. Step 1

   Compute $\hat{x}^{k+1}\in\text{prox}_{\sigma\|\cdot\|_{0}}\!\left(x^{k}-\alpha\nabla P(x^{k},\lambda^{k})\right)$.

3. Step 2

   Compute $x^{k+1}=\text{prox}_{I_{R}}\left(\hat{x}^{k+1}\right).$

4. Step 3

   Compute $\lambda^{k+1}=\lambda^{k}+\rho(e^{T}x^{k+1}-1)$.

5. Step 4

   If $\left\|\nabla P\left(x^{k+1},\lambda^{k+1}\right)\right\|<\varepsilon$ or $k>10000$, stop. Else, set $k:=k+1$ and go to Step 1.

We have seen in Section 2 how the proposed proximal method guarantees the descent of the solution. To proceed with the convergence of SEPO-$\ell_{0}$ algorithm, we begin with Assumption A for any objective function $\mathcal{L}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\{+\infty\}$ where $\mathcal{L}=\psi+\phi$:

Before we present the result that sums up the properties of the sequence $\{x^{k}\}_{k\in\mathbb{N}}$ generated by SEPO-$\ell_{0}$ algorithm starting from the initial point $x^{0}$, we first give some basic notations. We denote by $\text{crit }\mathcal{L}$ the set of critical points of $\mathcal{L}$ and $\omega\left(x^{0}\right)$ the set of all limit points, where

Given any set $\Omega\subset\mathbb{R}^{n}$ and any point $x\in\mathbb{R}^{n}$, the distance from $x$ to $\Omega$ is denoted and defined by

When $\Omega=\emptyset$, then we invoke the usual convention that $\inf\emptyset=\infty$ and hence $\text{dist}(x,\Omega)=\infty$ for all $x$.

What remains is its global convergence, of which we shall establish by means of the Kurdyka-Łojasiewicz (KL) property [7] as an extension of Łojasiewicz gradient inequality [19] for non-smooth functions. We first show that the objective function (2.7) is semi-algebraic and therefore is a KL function. This, in turn, is crucial in giving us the convergence property of the sequences generated via SEPO-$\ell_{0}$ algorithm. We begin by recalling notations and definitions concerning subdifferential (see, for instance [7, 23]) and KL property.

Let $\eta\in(0,\infty]$ and denote by $\Phi_{\eta}$ be the class of all concave and continuous functions $\varphi\colon[0,\eta)\rightarrow\mathbb{R}_{+}$ that are continuously differentiable on $(0,\eta)$ and continuous at 0 with $\varphi(0)=0$ and $\varphi^{\prime}(s)>0$ for all $s\in(0,\eta)$.

The definition above uses the sublevel sets: Given $a,b\in\mathbb{R}$, the sublevel sets of a function $\phi$ are denoted and defined by

Similar definition holds for $[a<\phi<b]$. The level sets of $\phi$ are denoted and defined by

Closely related to the KL function is the semi-algebraic function, which is crucial in the proof of the convergence property of our proposed method.

It follows that semi-algebraic functions are indeed KL functions, of which the result below is a non-smooth version of the Łojasiewicz gradient inequality.

Theorem 3.4 allows us to avoid the technicality in proving the KL property. This is due to the broad range of functions and sets that are indeed semi-algebraic (see, for instance [4, 7]). Some of the examples of semi-algebraic functions include real polynomial functions, and indicator functions of semi-algebraic sets. Apart from that, finite sums and products of semi-algebraic functions, as well as scalar products are all semi-algebraic.

We are now ready to give the global convergence result of the proposed model (2.1).

By virtue of Theorem 3.5, we now show that each term in (2.7) is semi-algebraic since the finite sum of semi-algebraic functions is also semi-algebraic. It is obvious that function (2.7) is a sum of a smooth function $P(x)$, $\ell_{0}$-norm and indicator function. The function $P(x)$ given by (2.9) is a linear combination of linear and quadratic functions, and hence $P(x)$ is a real polynomial function, which in turn is semi-algebraic.

As a specific example given by Bolte et al. [7], $\ell_{0}$-norm is nothing but the sparsity measure of the vector $x\in\mathbb{R}^{n}$, which is indeed semi-algebraic. In particular, the graph of $\|\cdot\|_{0}$ is given by a finite union of product sets:

where for any given $I\subset\{1,\dots,n\}$, $|I|$ denotes the cardinality of $I$ and

It is obvious that (3.9) is a piecewise linear set, hence the claim. Lastly, the indicator function $I_{R}(x)$ defined by (2.5) is also semi-algebraic, since the feasible set (2.4) is convex.

In this section, we study the efficiency of the proposed portfolio optimization model, SEPO-$\ell_{0}$, in maximizing portfolio return and minimizing transaction cost. We test our algorithm on real data of stock prices and returns of 100 companies across 10 different sectors in China, collected from January 2019 to June 2019. These data are in turn used to generate the covariance matrix, which gives us the portfolio variance as in our problem (2.1). We start with equally-weighted portfolio, i.e. $x_{i}^{0}=\frac{1}{n}$ for all $i$. We set $\varepsilon=10^{-7}$ and stop the algorithm when $\left\|\nabla P\left(x^{k+1},\lambda^{k+1}\right)\right\|<\varepsilon$ or $k>10000$. All computational results are obtained by running Matlab R2021a on Windows 10 (Intel Core i7 1065G7 16GB CPU @ 1.30 GHz $\sim$ 1.50GHz).

For testing purposes, we set our penalty parameter $\rho=5$ and tuning parameter $\beta_{2}=1$. The latter means that we set our weight on the portfolio diversification as constant. Meanwhile, the value of $\beta_{1}$ is chosen to be relatively smaller than $\beta_{2}$. For illustration, we present our results for minimum guaranteed return ratio $r=0.1$ and $r=0.2$.

In Table 4.1, we present the computational results of the expected return, variance risk and sparsity under the proposed SEPO-$\ell_{0}$ model and standard MVO model for different values of $\beta_{1}$ when we set the minimum guaranteed ratio to be 0.1 and 0.2, respectively. Note that though we leveraged on the variance risk when $\beta=1$, the portfolio selection under SEPO-$\ell_{0}$ manages to generate expected return of 0.3455 and 0.4014 when $r=0.1$ and $r=0.2$, respectively. Meanwhile, the standard MVO is only able to generate expected return of 0.1560 when we set $r=0.1$. The variance risks, however, are higher under the proposed model due to the sparsity, as compared to maximum diversification of the standard MVO. From the table, we can see that our model offers good level of sparsity between 30% and 61% when $r=0.1$ and between 52% and 72% when $r=0.2$. This simply means that out of 100 stocks considered under minimum expected return ratio $r=0.1$, one will only need to invest in the selected 39 - 70 stocks where the algorithm returns nonzero $x_{i}$’s. Despite the sparse portfolio selection and increased risk, we can see that the proposed model is more promising in terms of higher expected return.

We also compare the expected return and variance risk for the SEPO-$\ell_{0}$ and standard MVO for $r=0.1$ by using scatterplot, as seen in Figure 4.1. The downward trend of the portfolio expected return and risk mimic the standard MVO as $\beta\rightarrow 1$. Note that a higher value of $\beta_{1}$ reflects our leverage on the variance risk over expected return. At the same time, higher expected return results means higher risk as shown in Table 4.1. In general, the standard MVO model gives lower measure for risk due to maximum diversification, as we can see from Table 4.1 and Figure 4.1. The proposed SEPO-$\ell_{0}$, on the other hand, can lead to higher expected return and lower total transaction cost due to a sparse portfolio. This shows that SEPO-$\ell_{0}$ model is able to provide good combination of portfolio selection under sparsity.

To illustrate the reliability of our model, we present the output of the proposed model for $r=1$ using a scatterplot of the variables, as shown in Figure 4.2, with $\beta_{1}$ as independent variable at $x$-axis, expected return and sparsity (in decimal) at the left $y$-axis, while risk’s scale is at the right of $y$-axis. We can observe a similar trend for the three lines, which clearly reflects the consistency of our model in obtaining optimal portfolio selection.

The relationship between the independent variable $\beta_{1}$ and the response variables is further examined using multivariate linear regression model, as presented in Table 4.2. As we can see from the table, the estimates for response variables $y$ are all negative, which means their values decrease with the increase of $\beta_{1}$. Since the $p$-values of all response variables are approximately zero, it is clear that these three variables are significant. In particular, $\beta_{1}$ has significant negative relationship with expected return, risk and sparsity.

The significance of $\beta_{1}$ on these three dependent variables are supported by the values of R-squared of univariate regression, standing at 90.76%, 87.48% and 58.59% for expected return, risk and sparsity, respectively. Since R-squared is the percentage of total variation contributed by predictor variable, the high R-squared values of greater than 80% for expected return and risk mean that $\beta_{1}$ explains high percentage of the variance in these two response variables. It is slightly lower for sparsity, however any R-squared value greater than 50% can be considered as moderately high.

The classical Markowitz portfolio scheme or mean-variance optimization (MVO) is one of the most successful framework due to the simplicity in implementation, in particular it can be solved by quadratic programming which is widely available. However, it is very sensitive to input parameter and obtaining acceptable solutions requires the right weight constraints. Over the past decade, there has been renewed attention in considering non-quadratic portfolio selection models, due to the advancement in optimization algorithms for solving more general class of functions. Here we proposed a new algorithmic framework that allows portfolio managers to strike a balance between diversifying investments and minimizing transaction cost, of which the latter is achieved by means of minimizing the $\ell_{0}$-norm. This simply means that the model maximizes sparsity within the portfolio, since the weights $x_{i}$ are forced to be zero except for large ones. In practice, the regularization of $\ell_{0}$ results in a discontinuous and nonconvex problem, and hence is often approximated via $\ell_{1}$-norm. In this study, we employed the proximal methods such that function can be ’smoothed’, by means of linearizing part of the objective function at some given point and regularizing by a quadratic proximal term that acts as a measure for the ”local error” in the approximation. Writing our problem in the form of augmented Lagrangian, the unconstrained problem can be divided into two parts, namely the smooth and non-smooth terms. These terms are then handled separately through their proximal methods via the ADMM method. The global convergence of the proposed SEPO-$\ell_{0}$ algorithm for sparse equity portfolio has been established. The efficiency of our model in maximizing portfolio expectedreturn while striking a balance between minimizing transaction cost and diversification has been analyzed using actual data of 100 companies. Emperically, the implementation of our model leads to higher expected return and lower transaction cost. This shows that, despite its higher risk as compared to the standard MVO, the SEPO-$\ell_{0}$ model is promising in generating a good combination for optimal investment portfolio.