A Local Relaxation Method for Cardinality Constrained Portfolio Optimization Problem

The NP-hard nature of cardinality constrained mean-variance portfolio optimization problems has led to a variety of different algorithms with varying degrees of success in reaching optimality given limited computational resources and under the presence of strict time constraints in practice. The proposed local relaxation algorithm exploits the inherent structure of the objective function. It solves a sequence of small, local, quadratic-programs by first projecting asset returns onto a reduced metric space, followed by clustering in this space to identify sub-groups of assets that best accentuate a suitable measure of similarity amongst different assets. The algorithm can either be cold started using the centroids of initial clusters or be warm started based on the output of a previous result. Empirical result, using baskets of up to 3,000 stocks and with different cardinality constraints, indicates that the proposed algorithm is able to achieve significant performance gain over a sophisticated branch-and-cut method. One key application of this algorithm is in dealing with large scale cardinality constrained portfolio optimization under tight time constraint, such as for the purpose of index tracking or index arbitrage at high frequency