A Scalable Algorithm for Sparse and Robust Portfolios

November 2018
INFORMS 2018 Annual Meeting
Dimitris Bertsimas
INFORMS, Phoenix, Arizona, USA
We present a cutting-plane method which solves the sparse Markowitz portfolio problem to provable optimality at scale, by exploiting a dual representation of the continuous problem to obtain a closed form representation of the problem's subgradients. We refine the cutting-plane method by deriving an efficient local-search heuristic which exploits these subgradients, embedding the heuristic within the cutting-plane method, and exploiting a correspondence between the convexified dual problem and a rotated QCQP to obtain a strong apriori lower bound. We illustrate the method’s effectiveness by obtaining optimal sparse frontiers for major indices including the S&P 500 and the Wilshire 5000.