Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

By Tim Leung, Ph.D.

Every portfolio can be partitioned into multiple asset groups defined by asset classes, sectors, styles, or other features. A cardinality-constrained portfolio caps the number of stocks to be traded within each of these groups. These limitations arise from real-world scenarios faced by fund managers who seek to satisfy certain investment mandates or achieve their asset allocation objectives.

As an example, suppose you want to construct a portfolio by investing in stocks across m sectors you favor. And, in each sector, you select up to k stocks and each sector should not constitute more than q% of your portfolio. Moreover, you don’t know which and how many stocks should be included yet. You’ll also need to determine the portfolio weights based on your risk-return tradeoff. Now, imagine you can do all that automatically by running an algorithm.

In this paper, we develop a new approach to solve cardinality-constrained portfolio optimization problems with different constraints and objectives. In particular, our approach extends both Markowitz and conditional value at risk (CVaR) optimization models with cardinality constraints. A continuous relaxation method is proposed for the NP-hard objective, which allows for very efficient algorithms with standard convergence guarantees for nonconvex problems.

For smaller cases, where brute force search is feasible to compute the globally optimal cardinality-constrained portfolio, the new approach finds the best portfolio for the cardinality-constrained Markowitz model and a very good local minimum for the cardinality-constrained CVaR model.

As the total number of assets grows, brute-force exhaustive search quickly becomes prohibitively expensive. For instance, choosing 10 assets out of 30 requires solving more than 30 million optimization problems over the subsets, so even a seemingly simple case can be completely unmanageable. Our algorithm can solve problems of this scale on an average of 20 runs. We find feasible portfolios that are nearly as efficient as their non-cardinality constrained counterparts.

We are given a total of n candidate assets and a certain selection criterion f(w). The portfolio weights satisfy the simplex constraint:

Combinatorial constraints restrict the number of stocks to purchase, within specified subgroups and/or across the entire portfolio. The portfolio weights in each group are represented by the vector wᵢ.

This means that no more than kᵢ stocks can be included in each group i . And the sum of portfolio weights within each group i is bounded between pᵢ and qᵢ.

The constrained optimization problem is of the form:

For example, for mean-variance portfolio, we have

And the conditional value-at-risk (CVaR) model minimizes the CVaR superquantile over portfolio selections:

where the quantile β is related to the CVaR value α by

To solve the problem, we first relax the problem by introducing an auxiliary variable v which we force to be close to w using a quadratic penalty term. The optimization problem becomes

In turn, we apply a sophisticated projection method and use proximal alternating linearized minimization (PALM) with alternating updates on w and v. PALM converges to stationary points even in our nonconvex setting.

What sets our approach apart is that

(i) we formulate the problem as a continuous optimization problem over a highly nonconvex set induced by the intersection of cardinality and simplex constraints.

(ii) we develop a relaxation method using auxiliary variables and create an efficient projection map onto the nonconvex set.

These innovations allow recently developed techniques for structured nonsmooth nonconvex optimization to bear on the problem. The incorporation of cardinality constraints allows us to quantify and visualize their impact on risk and return. Among other effects, as fewer sectors and stocks are allowed to be included, the portfolio becomes less diversified, shifting the efficient frontier downward.

The mean-variance efficient frontier for unconstrained portfolio (solid line), cardinality constrained portfolios (dashed). The green (resp. red) frontier includes 6 (resp. 5) sectors and allows at most 2 stocks from each sector. Source: Paper by Tim Leung, available at See Reference section for details.


J. Zhang, T. Leung, and A. Aravkin, A Relaxed Optimization Approach for Cardinality-Constrained Portfolios, Proceedings of the 18th IEEE European Control Conference (ECC), pp.2885–2892, 2019 [pdf] [DOI]