A Linearly Convergent Proximal Subgradient Algorithm for Sparse Portfolio Optimization with Transaction Cost

Transaction cost optimization (TCO) of online portfolio selection is crucial in computing science, due to the significant impact of transaction costs in practical short-term trading. Moreover, sparsity of portfolio vector is often desired to enhance stability and decrease risk. However, there is a lack of models considering transaction costs and sparsity simultaneously in the literature. In this paper, we first propose a $K$-sparse TCO model that minimizes the negative return and transaction costs while keeping the portfolio vector being $K$-sparse. Noting that the model is NP-hard due to the $K$-sparse constraint, we bypass this difficulty by reformulating the sparse model to a nonsmooth difference of convex (DC) optimization problem. We show that both problems are equivalent by proving that the penalty parameter is large enough. Then, to overcome the difficulty caused by the nonsmoothness and the simplex constraint of the model, we develop a proximal subgradient algorithm (PSGA) to solve the DC problem and apply the alternating direction of multipliers (ADMM) to compute the proximity operator of the corresponding function. Furthermore, we establish the global convergence of the entire sequence generated by PSGA through showing the surrogate function satisfies the Kurdyka-Łojasiewicz (KL) property. In addition, by showing the KL exponent of the surrogate function is $1/2$, we establish the R-linear convergence rate of PSGA for any arbitrary initiaal point. Finally, we compare our proposed algorithm with other state-of-the-art strategies on four benchmark real-market data sets, with the numerical results showing that the proposed algorithm achieves lower risk while keeping higher return than classical TCO models.