# 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:

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.

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.

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 Traders’ Insight that is provided by third-parties and not by Interactive Brokers does NOT constitute a recommendation by Interactive Brokers that you should contract for the services of that third party. Third-party participants who contribute to IBKR Traders’ Insight 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 and Risk Management, University of Washington and is being posted with permission from Computational Finance and Risk Management, University of Washington. The views expressed in this material are solely those of the author and/or Computational Finance and Risk Management, University of Washington and IBKR 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 sell or the solicitation of an offer to buy any security. To the extent that this material discusses general market activity, industry or sector trends or other broad based economic or political conditions, it should not be construed as research or investment advice. To the extent that it includes references to specific securities, commodities, currencies, or other instruments, those references do not constitute a recommendation to buy, sell or hold such security. 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.

In accordance with EU regulation: The statements in this document shall not be considered as an objective or independent explanation of the matters. Please note that this document (a) has not been prepared in accordance with legal requirements designed to promote the independence of investment research, and (b) is not subject to any prohibition on dealing ahead of the dissemination or publication of investment research.

Any trading symbols displayed are for illustrative purposes only and are not intended to portray recommendations.