Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

By:

Director, Computational Finance & Risk Management (CFRM) Program

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: 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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ᵢ. 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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: 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

For example, for mean-variance portfolio, we have 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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. 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

In addition, a fast and iterative shrinkage-thresholding algorithm (FISTA) is applied to replace the proximal gradient step, which is empirically shown to help speed up the convergence. 

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. 

Cardinality-Constrained Portfolios: Optimization Approach & Algorithm

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 https://ieeexplore.ieee.org/document/8796164/. See Reference section for details. 

Reference 

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

Disclosure: Interactive Brokers

Information posted on IBKR Campus that is provided by third-parties does NOT constitute a recommendation that you should contract for the services of that third party. Third-party participants who contribute to IBKR Campus are independent of Interactive Brokers and Interactive Brokers does not make any representations or warranties concerning the services offered, their past or future performance, or the accuracy of the information provided by the third party. Past performance is no guarantee of future results.

This material is from Computational Finance & Risk Management, University of Washington and is being posted with its permission. The views expressed in this material are solely those of the author and/or Computational Finance & Risk Management, University of Washington and Interactive Brokers is not endorsing or recommending any investment or trading discussed in the material. This material is not and should not be construed as an offer to buy or sell any security. It should not be construed as research or investment advice or a recommendation to buy, sell or hold any security or commodity. This material does not and is not intended to take into account the particular financial conditions, investment objectives or requirements of individual customers. Before acting on this material, you should consider whether it is suitable for your particular circumstances and, as necessary, seek professional advice.